New hash table implementation
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v5 Latest14 patches 3 repliesIn review
- v414 patches 11 repliesSuperseded
- v311 patches 1 replySuperseded
Earlier versions · 2
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v2 | 5 patches | 8 replies | Superseded | |
| v1 | 5 patches | 4 replies | Superseded |
Changes since v3 from the cover letter
- changed table resizing and grow / shrink thresholds (#02)
- hashmap_free: changed free_function to boolean (#02, #06, #07, #09)
- swapped xcalloc args (num elements, element size) (#02)
- fixed pointer cast formatting "(type*)" -> "(type *)" (#02)
- removed function pointer casts "(*fn)(...)" -> "fn(...)" (#02)
- api-hashmap.txt: clarified removal / replacement of entries (#02)
- update-index.c: fixed const-casts (#13, #14)
Patches in v5 No applies recorded yet
Reviews trailers per patch
1 of 14 patches has a Reviewed-by or Acked-by.
| Patch | Karsten Blees |
|---|---|
| 1/14 | |
| 2/14 | A-b |
| 3/14 | |
| 4/14 | |
| 5/14 | |
| 6/14 | |
| 7/14 | |
| 8/14 | |
| 9/14 | |
| 10/14 | |
| 11/14 | |
| 12/14 | |
| 13/14 | |
| 14/14 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH v5 00/14] New hash table implementation
Also here:
https://github.com/kblees/git/commits/kb/hashmap-v5
Changes since v3:
- changed table resizing and grow / shrink thresholds (#02)
- hashmap_free: changed free_function to boolean (#02, #06, #07, #09)
- swapped xcalloc args (num elements, element size) (#02)
- fixed pointer cast formatting "(type*)" -> "(type *)" (#02)
- removed function pointer casts "(*fn)(...)" -> "fn(...)" (#02)
- api-hashmap.txt: clarified removal / replacement of entries (#02)
- update-index.c: fixed const-casts (#13, #14)
Karsten
Jens Lehmann (1):
submodule: don't access the .gitmodules cache entry after removing it
Karsten Blees (13):
add a hashtable implementation that supports O(1) removal buitin/describe.c: use new hash map implementation diffcore-rename.c: move code around to prepare for the next patch diffcore-rename.c: simplify finding exact renames diffcore-rename.c: use new hash map implementation name-hash.c: use new hash map implementation for directories name-hash.c: remove unreferenced directory entries name-hash.c: use new hash map implementation for cache entries name-hash.c: remove cache entries instead of marking them CE_UNHASHED remove old hash.[ch] implementation
fix 'git update-index --verbose --again' output builtin/update-index.c: cleanup update_one
read-cache.c: fix memory leaks caused by removed cache entries
Documentation/technical/api-hash.txt | 52 ------- Documentation/technical/api-hashmap.txt | 235 +++++++++++++++++++++++++++++ Makefile | 5 +- builtin/describe.c | 53 +++---- builtin/rm.c | 2 +- builtin/update-index.c | 39 +++-- cache.h | 18 +-- diffcore-rename.c | 185 ++++++++--------------- hash.c | 110 -------------- hash.h | 50 ------- hashmap.c | 228 ++++++++++++++++++++++++++++ hashmap.h | 71 +++++++++ name-hash.c | 156 +++++++------------ read-cache.c | 10 +- resolve-undo.c | 7 +- submodule.c | 25 +--- t/t0011-hashmap.sh | 240 ++++++++++++++++++++++++++++++ test-hashmap.c | 256 ++++++++++++++++++++++++++++++++ unpack-trees.c | 3 +- 19 files changed, 1216 insertions(+), 529 deletions(-) delete mode 100644 Documentation/technical/api-hash.txt create mode 100644 Documentation/technical/api-hashmap.txt delete mode 100644 hash.c delete mode 100644 hash.h create mode 100644 hashmap.c create mode 100644 hashmap.h create mode 100755 t/t0011-hashmap.sh create mode 100644 test-hashmap.c
--
git diff kb/hashmap-v4:
Documentation/technical/api-hashmap.txt +13 -15
@@ -42,11 +42,6 @@ parameters that have the same hash code. When looking up an entry, the `key` and `keydata` parameters to hashmap_get and hashmap_remove are always passed as second and third argument, respectively. Otherwise, `keydata` is NULL. -`void (*hashmap_free_fn)(void *entry)`:: - - User-supplied function to free a hashmap_entry. If entries are simply - malloc'ed memory, use stdlib's free() function. - Functions ---------
@@ -76,14 +71,14 @@ If the total number of entries is known in advance, the `initial_size` parameter may be used to preallocate a sufficiently large table and thus prevent expensive resizing. If 0, the table is dynamically resized. -`void hashmap_free(struct hashmap *map, hashmap_free_fn free_function)`:: +`void hashmap_free(struct hashmap *map, int free_entries)`:: Frees a hashmap structure and allocated memory. + `map` is the hashmap to free. + -If `free_function` is specified (not NULL), it is called to free each -hashmap_entry in the map. If entries are simply malloc'ed, use stdlib's free(). +If `free_entries` is true, each hashmap_entry in the map is freed as well +(using stdlib's free()). `void hashmap_entry_init(void *entry, int hash)`::
@@ -127,17 +122,20 @@ call to `hashmap_get` or `hashmap_get_next`. `void *hashmap_put(struct hashmap *map, void *entry)`:: - Adds or replaces a hashmap entry. + Adds or replaces a hashmap entry. If the hashmap contains duplicate + entries equal to the specified entry, only one of them will be replaced. + `map` is the hashmap structure. + -`entry` is the entry to add or update. +`entry` is the entry to add or replace. + -Returns the previous entry, or NULL if not found (i.e. the entry was added). +Returns the replaced entry, or NULL if not found (i.e. the entry was added). `void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata)`:: - Removes a hashmap entry matching the specified key. + Removes a hashmap entry matching the specified key. If the hashmap + contains duplicate entries equal to the specified key, only one of + them will be removed. + `map` is the hashmap structure. +
@@ -183,14 +181,14 @@ static int long2double_cmp(const struct long2double *e1, const struct long2doubl return !(e1->key == e2->key); } -void long2double_init() +void long2double_init(void) { hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); } -void long2double_free() +void long2double_free(void) { - hashmap_free(&map, free); + hashmap_free(&map, 1); } static struct long2double *find_entry(long key)
builtin/update-index.c +3 -3
@@ -559,7 +559,7 @@ static int do_reupdate(int ac, const char **av,const struct cache_entry *ce = active_cache[pos];struct cache_entry *old =NULL ;int save_nr; -const char *path; +char *path;if (ce_stage (ce) || !ce_path_match (ce, &pathspec))continue ;
@@ -838,7 +838,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)update_one (p);if (set_executable_bit)chmod_path (set_executable_bit, p); -free (p); +free ((char *)p); ctx.argc--; ctx.argv++;break ;
@@ -880,7 +880,7 @@ int cmd_update_index(int argc, const char **argv, const char *prefix)update_one (p);if (set_executable_bit)chmod_path (set_executable_bit, p); -free (p); +free ((char *)p); }strbuf_release (&nbuf);strbuf_release (&buf);
diffcore-rename.c +1 -1
@@ -343,7 +343,7 @@ static int find_exact_renames(struct diff_options *options) renames +=find_identical_files (&file_table, i, options);/* Free the hash data structure and entries */ -hashmap_free (&file_table, free); +hashmap_free (&file_table,1 );return renames; }
hashmap.c +41 -25
135 lines not on this page · raw message
hashmap.h +2 -3
@@ -22,12 +22,11 @@ struct hashmap_entry {typedef int (*hashmap_cmp_fn )(const void *entry,const void *entry_or_key,const void *keydata); -typedef void (*hashmap_free_fn )(void *entry);struct hashmap {struct hashmap_entry **table;hashmap_cmp_fn cmpfn; -unsigned int size, tablesize; +unsigned int size, tablesize, grow_at, shrink_at; };struct hashmap_iter {
@@ -40,7 +39,7 @@ struct hashmap_iter {extern void hashmap_init (struct hashmap *map,hashmap_cmp_fn equals_function,size_t initial_size); -extern void hashmap_free (struct hashmap *map,hashmap_free_fn free_function); +extern void hashmap_free (struct hashmap *map,int free_entries);/* hashmap_entry functions */
name-hash.c +2 -2
@@ -240,6 +240,6 @@ void free_name_hash(struct index_state *istate)return ; istate->name_hash_initialized =0 ; -hashmap_free (&istate->name_hash,NULL ); -hashmap_free (&istate->dir_hash, free); +hashmap_free (&istate->name_hash,0 ); +hashmap_free (&istate->dir_hash,1 ); }
t/t0011-hashmap.sh +6 -2
@@ -221,13 +221,17 @@ test_expect_success 'grow / shrink' ' echo NULL >> expect echo size >> in && echo 256 52 >> expect && - for n in $(test_seq 10) + for n in $(test_seq 12) do echo remove key$n >> in && echo value$n >> expect done && echo size >> in && - echo 64 42 >> expect && + echo 256 40 >> expect && + echo remove key40 >> in && + echo value40 >> expect && + echo size >> in && + echo 64 39 >> expect && cat in | test-hashmap > out && test_cmp expect out
test-hashmap.c +5 -5
@@ -71,7 +71,7 @@ static unsigned int hash(unsigned int method, unsigned int i, const char *key) }/* -* Test insert performance of hashmap.[ch] +* Test performance of hashmap.[ch] * Usage: time echo "perfhashmap method rounds" | test-hashmap */ static void perf_hashmap (unsigned int method,unsigned int rounds)
@@ -82,7 +82,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)unsigned int *hashes;unsigned int i, j; - entries =malloc (TEST_SIZE *sizeof (struct test_entry *)); + entries =malloc (TEST_SIZE *sizeof (struct test_entry *)); hashes =malloc (TEST_SIZE *sizeof (int ));for (i =0 ; i <TEST_SIZE ; i++) {snprintf (buf,sizeof (buf),"%i" , i);
@@ -101,7 +101,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)hashmap_add (&map, entries[i]); } -hashmap_free (&map,NULL ); +hashmap_free (&map,0 ); } }else {/* test map lookups */
@@ -122,7 +122,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds) } } -hashmap_free (&map,NULL ); +hashmap_free (&map,0 ); } }
@@ -251,6 +251,6 @@ int main(int argc, char *argv[]) } } -hashmap_free (&map, free); +hashmap_free (&map,1 );return 0 ; }