Also here: https://github.com/kblees/git/tree/kb/hashmap-v3 Previous discussion: http://thread.gmane.org/gmane.comp.version-control.git/234508 Changes since v2: - move documentation from hashmap.h to Documentation/technical/api-hashmap.txt - simpler way to deal with FLEX_ARRAY keys: instead of requiring a special key structure (and function hashmap_entry_is_key), hashmap_get and hashmap_remove now take an additional parameter that is passed through to the comparison function Added since v2 (patches 06 - 11): - convert name-hash.c to new hash map implementation - fix memory leaks caused by not free()ing removed cache_entries - remove now unused hash.[ch] implementation Performance: While the main motivation for the patch series wasn't performance, _actual_ git performance will most likely benefit from the name-hash.c changes. So here's the numbers for 10 git-status runs on the WebKit repo (~200k files, with core.preloadindex=true). Not exactly a quantum leap, but its measurable. git status -s | hash | hashmap | gain --------------+-------+---------+------------- real avg | 0.969 | 0.959 | 0.010 / 1.0% real min | 0.910 | 0.895 | 0.015 / 1.6% real max | 1.079 | 0.993 | 0.086 / 8.0% Cheers, Karsten Karsten Blees (11): 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 read-cache.c: fix memory leaks caused by removed cache entries remove old hash.[ch] implementation Documentation/technical/api-hash.txt | 52 ------- Documentation/technical/api-hashmap.txt | 237 +++++++++++++++++++++++++++++ Makefile | 5 +- builtin/describe.c | 53 +++---- builtin/rm.c | 2 +- cache.h | 18 +-- diffcore-rename.c | 185 ++++++++--------------- hash.c | 110 -------------- hash.h | 50 ------- hashmap.c | 212 ++++++++++++++++++++++++++ hashmap.h | 72 +++++++++ name-hash.c | 156 +++++++------------ read-cache.c | 8 +- resolve-undo.c | 7 +- t/t0011-hashmap.sh | 236 +++++++++++++++++++++++++++++ test-hashmap.c | 256 ++++++++++++++++++++++++++++++++ unpack-trees.c | 3 +- 17 files changed, 1179 insertions(+), 483 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 --- Note: interdiff for patches 01 - 05 only (which have been part of v2): git diff -p --stat kb/hashmap-v2..kb/hashmap-v3~6 Documentation/technical/api-hashmap.txt | 237 ++++++++++++++++++++++++++++++++ builtin/describe.c | 12 +- diffcore-rename.c | 6 +- hashmap.c | 23 ++-- hashmap.h | 170 +++-------------------- test-hashmap.c | 48 +++---- 6 files changed, 296 insertions(+), 200 deletions(-) diff --git a/Documentation/technical/api-hashmap.txt b/Documentation/technical/api-hashmap.txt new file mode 100644 index 0000000..fc46e56 --- /dev/null +++ b/Documentation/technical/api-hashmap.txt @@ -0,0 +1,237 @@ +hashmap API +=========== + +The hashmap API is a generic implementation of hash-based key-value mappings. + +Data Structures +--------------- + +`struct hashmap`:: + + The hash table structure. ++ +The `size` member keeps track of the total number of entries. The `cmpfn` +member is a function used to compare two entries for equality. The `table` and +`tablesize` members store the hash table and its size, respectively. + +`struct hashmap_entry`:: + + An opaque structure representing an entry in the hash table, which must + be used as first member of user data structures. Ideally it should be + followed by an int-sized member to prevent unused memory on 64-bit + systems due to alignment. ++ +The `hash` member is the entry's hash code and the `next` member points to the +next entry in case of collisions (i.e. if multiple entries map to the same +bucket). + +`struct hashmap_iter`:: + + An iterator structure, to be used with hashmap_iter_* functions. + +Types +----- + +`int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key, const void *keydata)`:: + + User-supplied function to test two hashmap entries for equality. Shall + return 0 if the entries are equal. ++ +This function is always called with non-NULL `entry` / `entry_or_key` +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 +--------- + +`unsigned int strhash(const char *buf)`:: +`unsigned int strihash(const char *buf)`:: +`unsigned int memhash(const void *buf, size_t len)`:: +`unsigned int memihash(const void *buf, size_t len)`:: + + Ready-to-use hash functions for strings, using the FNV-1 algorithm (see + http://www.isthe.com/chongo/tech/comp/fnv). ++ +`strhash` and `strihash` take 0-terminated strings, while `memhash` and +`memihash` operate on arbitrary-length memory. ++ +`strihash` and `memihash` are case insensitive versions. + +`void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size)`:: + + Initializes a hashmap structure. ++ +`map` is the hashmap to initialize. ++ +The `equals_function` can be specified to compare two entries for equality. +If NULL, entries are considered equal if their hash codes are equal. ++ +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)`:: + + 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(). + +`void hashmap_entry_init(void *entry, int hash)`:: + + Initializes a hashmap_entry structure. ++ +`entry` points to the entry to initialize. ++ +`hash` is the hash code of the entry. + +`void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata)`:: + + Returns the hashmap entry for the specified key, or NULL if not found. ++ +`map` is the hashmap structure. ++ +`key` is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via `hashmap_entry_init`). ++ +If an entry with matching hash code is found, `key` and `keydata` are passed +to `hashmap_cmp_fn` to decide whether the entry matches the key. + +`void *hashmap_get_next(const struct hashmap *map, const void *entry)`:: + + Returns the next equal hashmap entry, or NULL if not found. This can be + used to iterate over duplicate entries (see `hashmap_add`). ++ +`map` is the hashmap structure. ++ +`entry` is the hashmap_entry to start the search from, obtained via a previous +call to `hashmap_get` or `hashmap_get_next`. + +`void hashmap_add(struct hashmap *map, void *entry)`:: + + Adds a hashmap entry. This allows to add duplicate entries (i.e. + separate values with the same key according to hashmap_cmp_fn). ++ +`map` is the hashmap structure. ++ +`entry` is the entry to add. + +`void *hashmap_put(struct hashmap *map, void *entry)`:: + + Adds or replaces a hashmap entry. ++ +`map` is the hashmap structure. ++ +`entry` is the entry to add or update. ++ +Returns the previous 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. ++ +`map` is the hashmap structure. ++ +`key` is a hashmap_entry structure (or user data structure that starts with +hashmap_entry) that has at least been initialized with the proper hash code +(via `hashmap_entry_init`). ++ +If an entry with matching hash code is found, `key` and `keydata` are +passed to `hashmap_cmp_fn` to decide whether the entry matches the key. ++ +Returns the removed entry, or NULL if not found. + +`void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter)`:: +`void *hashmap_iter_next(struct hashmap_iter *iter)`:: +`void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter)`:: + + Used to iterate over all entries of a hashmap. ++ +`hashmap_iter_init` initializes a `hashmap_iter` structure. ++ +`hashmap_iter_next` returns the next hashmap_entry, or NULL if there are no +more entries. ++ +`hashmap_iter_first` is a combination of both (i.e. initializes the iterator +and returns the first entry, if any). + +Usage example +------------- + +Here's a simple usage example that maps long keys to double values. +[source,c] +------------ +struct hashmap map; + +struct long2double { + struct hashmap_entry ent; /* must be the first member! */ + long key; + double value; +}; + +static int long2double_cmp(const struct long2double *e1, const struct long2double *e2, const void *unused) +{ + return !(e1->key == e2->key); +} + +void long2double_init() +{ + hashmap_init(&map, (hashmap_cmp_fn) long2double_cmp, 0); +} + +void long2double_free() +{ + hashmap_free(&map, free); +} + +static struct long2double *find_entry(long key) +{ + struct long2double k; + hashmap_entry_init(&k, memhash(&key, sizeof(long))); + k.key = key; + return hashmap_get(&map, &k, NULL); +} + +double get_value(long key) +{ + struct long2double *e = find_entry(key); + return e ? e->value : 0; +} + +void set_value(long key, double value) +{ + struct long2double *e = find_entry(key); + if (!e) { + e = malloc(sizeof(struct long2double)); + hashmap_entry_init(e, memhash(&key, sizeof(long))); + e->key = key; + hashmap_add(&map, e); + } + e->value = value; +} +------------ + +Using variable-sized keys +------------------------- + +The `hashmap_entry_get` and `hashmap_entry_remove` functions expect an ordinary +`hashmap_entry` structure as key to find the correct entry. If the key data is +variable-sized (e.g. a FLEX_ARRAY string) or quite large, it is undesirable +to create a full-fledged entry structure on the heap and copy all the key data +into the structure. + +In this case, the `keydata` parameter can be used to pass +variable-sized key data directly to the comparison function, and the `key` +parameter can be a stripped-down, fixed size entry structure allocated on the +stack. + +See test-hashmap.c for an example using arbitrary-length strings as keys. diff --git a/builtin/describe.c b/builtin/describe.c index 5db5d89..ae8d32c 100644 --- a/builtin/describe.c +++ b/builtin/describe.c @@ -50,9 +50,10 @@ static const char *prio_names[] = { "head", "lightweight", "annotated", }; -static int commit_name_cmp(struct commit_name *cn1, struct commit_name *cn2) +static int commit_name_cmp(const struct commit_name *cn1, + const struct commit_name *cn2, const void *peeled) { - return hashcmp(cn1->peeled, cn2->peeled); + return hashcmp(cn1->peeled, peeled ? peeled : cn2->peeled); } static inline unsigned int hash_sha1(const unsigned char *sha1) @@ -65,9 +66,8 @@ static inline unsigned int hash_sha1(const unsigned char *sha1) static inline struct commit_name *find_commit_name(const unsigned char *peeled) { struct commit_name key; - hashmap_entry_init(&key, hash_sha1(peeled), 0); - hashcpy(key.peeled, peeled); - return hashmap_get(&names, &key); + hashmap_entry_init(&key, hash_sha1(peeled)); + return hashmap_get(&names, &key, peeled); } static int replace_name(struct commit_name *e, @@ -114,7 +114,7 @@ static void add_to_known_names(const char *path, if (!e) { e = xmalloc(sizeof(struct commit_name)); hashcpy(e->peeled, peeled); - hashmap_entry_init(e, hash_sha1(peeled), 0); + hashmap_entry_init(e, hash_sha1(peeled)); hashmap_add(&names, e); e->path = NULL; } diff --git a/diffcore-rename.c b/diffcore-rename.c index 2e70d31..c6bd776 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -274,8 +274,8 @@ static int find_identical_files(struct hashmap *srcs, * Find the best source match for specified destination. */ best = NULL; - hashmap_entry_init(&dst, hash_filespec(target), 0); - for (p = hashmap_get(srcs, &dst); p; p = hashmap_get_next(srcs, p)) { + hashmap_entry_init(&dst, hash_filespec(target)); + for (p = hashmap_get(srcs, &dst, NULL); p; p = hashmap_get_next(srcs, p)) { int score; struct diff_filespec *source = p->filespec; @@ -317,7 +317,7 @@ static void insert_file_table(struct hashmap *table, int index, struct diff_file entry->index = index; entry->filespec = filespec; - hashmap_entry_init(entry, hash_filespec(filespec), 0); + hashmap_entry_init(entry, hash_filespec(filespec)); hashmap_add(table, entry); } diff --git a/hashmap.c b/hashmap.c index 75a8578..3a9f8c1 100644 --- a/hashmap.c +++ b/hashmap.c @@ -59,9 +59,10 @@ unsigned int memihash(const void *buf, size_t len) #define HASHMAP_SHRINK_AT 6 static inline int entry_equals(const struct hashmap *map, - const struct hashmap_entry *e1, const struct hashmap_entry *e2) + const struct hashmap_entry *e1, const struct hashmap_entry *e2, + const void *keydata) { - return (e1 == e2) || (e1->hash == e2->hash && !(*map->cmpfn)(e1, e2)); + return (e1 == e2) || (e1->hash == e2->hash && !(*map->cmpfn)(e1, e2, keydata)); } static inline unsigned int bucket(const struct hashmap *map, @@ -91,15 +92,15 @@ static void rehash(struct hashmap *map, unsigned int newsize) } static inline struct hashmap_entry **find_entry_ptr(const struct hashmap *map, - const struct hashmap_entry *key) + const struct hashmap_entry *key, const void *keydata) { struct hashmap_entry **e = &map->table[bucket(map, key)]; - while (*e && !entry_equals(map, *e, key)) + while (*e && !entry_equals(map, *e, key, keydata)) e = &(*e)->next; return e; } -static int always_equal(const void *unused1, const void *unused2) +static int always_equal(const void *unused1, const void *unused2, const void *unused3) { return 0; } @@ -132,16 +133,16 @@ void hashmap_free(struct hashmap *map, hashmap_free_fn free_function) memset(map, 0, sizeof(*map)); } -void *hashmap_get(const struct hashmap *map, const void *key) +void *hashmap_get(const struct hashmap *map, const void *key, const void *keydata) { - return *find_entry_ptr(map, key); + return *find_entry_ptr(map, key, keydata); } void *hashmap_get_next(const struct hashmap *map, const void *entry) { struct hashmap_entry *e = ((struct hashmap_entry*) entry)->next; for (; e; e = e->next) - if (entry_equals(map, entry, e)) + if (entry_equals(map, entry, e, NULL)) return e; return NULL; } @@ -160,10 +161,10 @@ void hashmap_add(struct hashmap *map, void *entry) rehash(map, map->tablesize << HASHMAP_GROW); } -void *hashmap_remove(struct hashmap *map, const void *key) +void *hashmap_remove(struct hashmap *map, const void *key, const void *keydata) { struct hashmap_entry *old; - struct hashmap_entry **e = find_entry_ptr(map, key); + struct hashmap_entry **e = find_entry_ptr(map, key, keydata); if (!*e) return NULL; @@ -182,7 +183,7 @@ void *hashmap_remove(struct hashmap *map, const void *key) void *hashmap_put(struct hashmap *map, void *entry) { - struct hashmap_entry *old = hashmap_remove(map, entry); + struct hashmap_entry *old = hashmap_remove(map, entry, NULL); hashmap_add(map, entry); return old; } diff --git a/hashmap.h b/hashmap.h index 98c4ebc..eea003a 100644 --- a/hashmap.h +++ b/hashmap.h @@ -2,194 +2,66 @@ #define HASHMAP_H /* - * Generic implementation of hash-based key value mappings. - * Supports basic operations get, add/put, remove and iteration. - * - * Also contains a set of ready-to-use hash functions for strings, using the - * FNV-1 algorithm (see http://www.isthe.com/chongo/tech/comp/fnv). + * Generic implementation of hash-based key-value mappings. + * See Documentation/technical/api-hashmap.txt. */ -/* - * Case-sensitive FNV-1 hash of 0-terminated string. - * str: the string - * returns hash code - */ -extern unsigned int strhash(const char *buf); +/* FNV-1 functions */ -/* - * Case-insensitive FNV-1 hash of 0-terminated string. - * str: the string - * returns hash code - */ +extern unsigned int strhash(const char *buf); extern unsigned int strihash(const char *buf); - -/* - * Case-sensitive FNV-1 hash of a memory block. - * buf: start of the memory block - * len: length of the memory block - * returns hash code - */ extern unsigned int memhash(const void *buf, size_t len); - -/* - * Case-insensitive FNV-1 hash of a memory block. - * buf: start of the memory block - * len: length of the memory block - * returns hash code - */ extern unsigned int memihash(const void *buf, size_t len); -/* - * Hashmap entry data structure, must be used as first member of user data - * structures. Consists of a pointer and an int. Ideally it should be followed - * by an int-sized member to prevent unused memory on 64-bit systems due to - * alignment. - */ +/* data structures */ + struct hashmap_entry { struct hashmap_entry *next; unsigned int hash; }; -/* - * User-supplied function to test two hashmap entries for equality, shall - * return 0 if the entries are equal. This function is always called with - * non-NULL parameters that have the same hash code. When looking up an entry, - * the key parameter to hashmap_get and hashmap_remove is always passed as - * second argument. - */ -typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key); - -/* - * User-supplied function to free a 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); -/* - * Hashmap data structure, use with hashmap_* functions. - */ struct hashmap { struct hashmap_entry **table; hashmap_cmp_fn cmpfn; unsigned int size, tablesize; }; -/* - * Hashmap iterator data structure, use with hasmap_iter_* functions. - */ struct hashmap_iter { struct hashmap *map; struct hashmap_entry *next; unsigned int tablepos; }; -/* - * Initializes a hashmap_entry structure. - * entry: pointer to the entry to initialize - * hash: hash code of the entry - * key_only: true if entry is a key-only structure, see hashmap_entry_is_key - */ -static inline void hashmap_entry_init(void *entry, int hash, int key_only) -{ - struct hashmap_entry *e = entry; - e->hash = hash; - e->next = key_only ? (struct hashmap_entry*) -1 : NULL; -} - -/* - * Checks if hashmap_entry was initialized with the key_only flag. This is - * useful if the entry structure is variable-sized (e.g. ending in a FLEX_ARRAY) - * and the key is part of the variable portion. To prevent dynamic allocation of - * a full-fledged entry structure for each lookup, a smaller, statically sized - * structure can be used as key (i.e. replacing the FLEX_ARRAY member with a - * char pointer). The hashmap_cmp_fn comparison function can then check whether - * entry_or_key is a full-fledged entry or a key-only structure. - * entry: pointer to the entry to check - * returns 0 for key-value entries and non-0 for key-only entries - */ -static inline int hashmap_entry_is_key(const void *entry) -{ - const struct hashmap_entry *e = entry; - return e->next == (struct hashmap_entry*) -1; -} +/* hashmap functions */ -/* - * Initializes a hashmap structure. - * map: hashmap to initialize - * equals_function: optional function to test equality of hashmap entries. If - * NULL, entries are considered equal if their hash codes are equal. - * initial_size: optional number of initial entries, 0 if unknown - */ extern void hashmap_init(struct hashmap *map, hashmap_cmp_fn equals_function, size_t initial_size); - -/* - * Frees a hashmap structure and allocated memory. - * map: hashmap to free - * free_function: optional function to free the hashmap entries - */ extern void hashmap_free(struct hashmap *map, hashmap_free_fn free_function); -/* - * Returns the hashmap entry for the specified key, or NULL if not found. - * map: the hashmap - * key: key of the entry to look up - * returns matching hashmap entry, or NULL if not found - */ -extern void *hashmap_get(const struct hashmap *map, const void *key); +/* hashmap_entry functions */ -/* - * Returns the next equal hashmap entry if the map contains duplicates (see - * hashmap_add). - * map: the hashmap - * entry: current entry, obtained via hashmap_get or hashmap_get_next - * returns next equal hashmap entry, or NULL if not found - */ +static inline void hashmap_entry_init(void *entry, int hash) +{ + struct hashmap_entry *e = entry; + e->hash = hash; + e->next = NULL; +} +extern void *hashmap_get(const struct hashmap *map, const void *key, + const void *keydata); extern void *hashmap_get_next(const struct hashmap *map, const void *entry); - -/* - * Adds a hashmap entry. This allows to add duplicate entries (i.e. separate - * values with the same key according to hashmap_cmp_fn). - * map: the hashmap - * entry: the entry to add - */ extern void hashmap_add(struct hashmap *map, void *entry); - -/* - * Adds or replaces a hashmap entry. - * map: the hashmap - * entry: the entry to add or replace - * returns previous entry, or NULL if the entry is new - */ extern void *hashmap_put(struct hashmap *map, void *entry); +extern void *hashmap_remove(struct hashmap *map, const void *key, + const void *keydata); -/* - * Removes a hashmap entry matching the specified key. - * map: the hashmap - * key: key of the entry to remove - * returns removed entry, or NULL if not found - */ -extern void *hashmap_remove(struct hashmap *map, const void *key); +/* hashmap_iter functions */ -/* - * Initializes a hashmap iterator structure. - * map: the hashmap - * iter: hashmap iterator structure - */ extern void hashmap_iter_init(struct hashmap *map, struct hashmap_iter *iter); - -/** - * Returns the next hashmap entry. - * iter: hashmap iterator - * returns next entry, or NULL if there are no more entries - */ extern void *hashmap_iter_next(struct hashmap_iter *iter); - -/** - * Initializes a hashmap iterator and returns the first hashmap entry. - * map: the hashmap - * iter: hashmap iterator - * returns first entry, or NULL if there are no entries - */ static inline void *hashmap_iter_first(struct hashmap *map, struct hashmap_iter *iter) { diff --git a/test-hashmap.c b/test-hashmap.c index de94c6d..2d2b834 100644 --- a/test-hashmap.c +++ b/test-hashmap.c @@ -9,32 +9,21 @@ struct test_entry char key[FLEX_ARRAY]; }; -struct test_key -{ - struct hashmap_entry ent; - char *key; -}; - -static const char *get_key(const struct test_entry *e) -{ - return hashmap_entry_is_key(e) ? ((struct test_key*) e)->key : e->key; -} - static const char *get_value(const struct test_entry *e) { return e->key + strlen(e->key) + 1; } static int test_entry_cmp(const struct test_entry *e1, - const struct test_entry *e2) + const struct test_entry *e2, const char* key) { - return strcmp(e1->key, get_key(e2)); + return strcmp(e1->key, key ? key : e2->key); } static int test_entry_cmp_icase(const struct test_entry *e1, - const struct test_entry *e2) + const struct test_entry *e2, const char* key) { - return strcasecmp(e1->key, get_key(e2)); + return strcasecmp(e1->key, key ? key : e2->key); } static struct test_entry *alloc_test_entry(int hash, char *key, int klen, @@ -42,7 +31,7 @@ static struct test_entry *alloc_test_entry(int hash, char *key, int klen, { struct test_entry *entry = malloc(sizeof(struct test_entry) + klen + vlen + 2); - hashmap_entry_init(entry, hash, 0); + hashmap_entry_init(entry, hash); memcpy(entry->key, key, klen + 1); memcpy(entry->key + klen + 1, value, vlen + 1); return entry; @@ -108,7 +97,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds) /* add entries */ for (i = 0; i < TEST_SIZE; i++) { - hashmap_entry_init(entries[i], hashes[i], 0); + hashmap_entry_init(entries[i], hashes[i]); hashmap_add(&map, entries[i]); } @@ -121,16 +110,15 @@ static void perf_hashmap(unsigned int method, unsigned int rounds) /* fill the map (sparsely if specified) */ j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE; for (i = 0; i < j; i++) { - hashmap_entry_init(entries[i], hashes[i], 0); + hashmap_entry_init(entries[i], hashes[i]); hashmap_add(&map, entries[i]); } for (j = 0; j < rounds; j++) { for (i = 0; i < TEST_SIZE; i++) { - struct test_key k; - hashmap_entry_init(&k, hashes[i], 1); - k.key = entries[i]->key; - hashmap_get(&map, &k); + struct hashmap_entry key; + hashmap_entry_init(&key, hashes[i]); + hashmap_get(&map, &key, entries[i]->key); } } @@ -293,12 +281,11 @@ int main(int argc, char *argv[]) } else if (!strcmp("get", cmd) && l1) { /* setup static key */ - struct test_key key; - hashmap_entry_init(&key, hash, 1); - key.key = p1; + struct hashmap_entry key; + hashmap_entry_init(&key, hash); /* lookup entry in hashmap */ - entry = hashmap_get(&map, &key); + entry = hashmap_get(&map, &key, p1); /* print result */ if (!entry) @@ -311,12 +298,11 @@ int main(int argc, char *argv[]) } else if (!strcmp("remove", cmd) && l1) { /* setup static key */ - struct test_key key; - hashmap_entry_init(&key, hash, 1); - key.key = p1; + struct hashmap_entry key; + hashmap_entry_init(&key, hash); /* remove entry from hashmap */ - entry = hashmap_remove(&map, &key); + entry = hashmap_remove(&map, &key, p1); /* print result and free entry*/ puts(entry ? get_value(entry) : "NULL"); @@ -327,7 +313,7 @@ int main(int argc, char *argv[]) struct hashmap_iter iter; hashmap_iter_init(&map, &iter); while ((entry = hashmap_iter_next(&iter))) - printf("%s %s\n", get_key(entry), get_value(entry)); + printf("%s %s\n", entry->key, get_value(entry)); } else if (!strcmp("size", cmd)) { -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html