summaryrefslogtreecommitdiff
path: root/test-hashmap.c
Commit message (Collapse)AuthorAgeFilesLines
* test helpers: move test-* to t/helper/ subdirectoryNguyễn Thái Ngọc Duy2016-04-151-264/+0
| | | | | | | | This keeps top dir a bit less crowded. And because these programs are for testing purposes, it makes sense that they stay somewhere in t/ Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* Merge branch 'js/test-hashmap-squelch-gcc'Junio C Hamano2014-12-221-1/+1
|\ | | | | | | | | * js/test-hashmap-squelch-gcc: test-hashmap: squelch gcc compiler warning
| * test-hashmap: squelch gcc compiler warningjs/test-hashmap-squelch-gccJohannes Schindelin2014-12-091-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | At least on this developer's MacOSX (Snow Leopard, gcc-4.2.1), GCC prints a warning that 'hash' may be used uninitialized when compiling test-hashmap that 'hash' may be used uninitialized (but GCC 4.6.3 on this developer's Ubuntu server does not report this problem). The old compiler is wrong, of course, as the switch (method & 3) statement already handles all the possible cases, but that does not help in a scenario where it is hard or impossible to upgrade to a newer compiler (e.g. being stuck on an older MacOSX and having to rely on Xcode). So let's just initialize the variable and be done with it, it is hardly a crucial part of the code because it is only used by the test suite and invisible to the end users. Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* | hashmap: add string interning APIkb/hashmap-updatesKarsten Blees2014-07-071-0/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Interning short strings with high probability of duplicates can reduce the memory footprint and speed up comparisons. Add strintern() and memintern() APIs that use a hashmap to manage the pool of unique, interned strings. Note: strintern(getenv()) could be used to sanitize git's use of getenv(), in case we ever encounter a platform where a call to getenv() invalidates previous getenv() results (which is allowed by POSIX). Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* | hashmap: add simplified hashmap_get_from_hash() APIKarsten Blees2014-07-071-8/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Hashmap entries are typically looked up by just a key. The hashmap_get() API expects an initialized entry structure instead, to support compound keys. This flexibility is currently only needed by find_dir_entry() in name-hash.c (and compat/win32/fscache.c in the msysgit fork). All other (currently five) call sites of hashmap_get() have to set up a near emtpy entry structure, resulting in duplicate code like this: struct hashmap_entry keyentry; hashmap_entry_init(&keyentry, hash(key)); return hashmap_get(map, &keyentry, key); Add a hashmap_get_from_hash() API that allows hashmap lookups by just specifying the key and its hash code, i.e.: return hashmap_get_from_hash(map, hash(key), key); Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* | test-hashmap.c: drop unnecessary #includesJonathan Nieder2014-02-241-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | Per Documentation/CodingGuidelines most C files in git start with a #include of git-compat-util.h or another header file that includes it, such as cache.h or builtin.h. This file doesn't need anything beyond "git-compat-util.h", so use that. Remove a #include of the system header <stdio.h> since it is already included by "git-compat-util.h". Signed-off-by: Jonathan Nieder <jrnieder@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* | remove old hash.[ch] implementationKarsten Blees2013-11-181-84/+0
|/ | | | | Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
* add a hashtable implementation that supports O(1) removalKarsten Blees2013-11-181-0/+340
The existing hashtable implementation (in hash.[ch]) uses open addressing (i.e. resolve hash collisions by distributing entries across the table). Thus, removal is difficult to implement with less than O(n) complexity. Resolving collisions of entries with identical hashes (e.g. via chaining) is left to the client code. Add a hashtable implementation that supports O(1) removal and is slightly easier to use due to builtin entry chaining. Supports all basic operations init, free, get, add, remove and iteration. Also includes ready-to-use hash functions based on the public domain FNV-1 algorithm (http://www.isthe.com/chongo/tech/comp/fnv). The per-entry data structure (hashmap_entry) is piggybacked in front of the client's data structure to save memory. See test-hashmap.c for usage examples. The hashtable is resized by a factor of four when 80% full. With these settings, average memory consumption is about 2/3 of hash.[ch], and insertion is about twice as fast due to less frequent resizing. Lookups are also slightly faster, because entries are strictly confined to their bucket (i.e. no data of other buckets needs to be traversed). Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>