{"thread":{"id":"46849","subject":"[PATCH] oidmap: map with OID as key","startedAt":"2017-09-27T22:19:22Z","lastAt":"2017-10-04T08:48:13Z","messageCount":16,"participants":["Jonathan Tan","Brandon Williams","Junio C Hamano","Jeff King","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"329070","messageId":"20170927221910.164552-1-jonathantanmy@google.com","threadId":"46849","inReplyTo":null,"subject":"[PATCH] oidmap: map with OID as key","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-09-27T22:19:10Z","receivedAt":"2017-09-27T22:19:22Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is similar to using the hashmap in hashmap.c, but with an\neasier-to-use API. In particular, custom entry comparisons no longer\nneed to be written, and lookups can be done without constructing a\ntemporary entry structure.\n\noidset has been updated to use oidmap.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nI have been wishing for an OID map for a while, and it seems to me that\nJeff Hostetler's recent patches [1] could use one too, so here it is.\n\n(Also, I wonder if some details such as grow_at, shrink_at, and\ndo_count_items can be removed, since the applications of this are\nnarrower than that of hashmap.)\n\n[1] https://public-inbox.org/git/20170922202632.53714-1-git@jeffhostetler.com/\n---\n Makefile |   1 +\n oidmap.c | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n oidmap.h |  98 ++++++++++++++++++++++++++++++++++++++++\n oidset.c |  38 ++++------------\n oidset.h |   4 +-\n 5 files changed, 263 insertions(+), 30 deletions(-)\n create mode 100644 oidmap.c\n create mode 100644 oidmap.h\n\ndiff --git a/Makefile b/Makefile\nindex ed4ca438b..64136dde4 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -821,6 +821,7 @@ LIB_OBJS += notes-cache.o\n LIB_OBJS += notes-merge.o\n LIB_OBJS += notes-utils.o\n LIB_OBJS += object.o\n+LIB_OBJS += oidmap.o\n LIB_OBJS += oidset.o\n LIB_OBJS += packfile.o\n LIB_OBJS += pack-bitmap.o\ndiff --git a/oidmap.c b/oidmap.c\nnew file mode 100644\nindex 000000000..40e696cee\n--- /dev/null\n+++ b/oidmap.c\n@@ -0,0 +1,152 @@\n+#include \"cache.h\"\n+#include \"oidmap.h\"\n+\n+#define OIDMAP_INITIAL_SIZE 64\n+/* grow / shrink by 2^2 */\n+#define OIDMAP_RESIZE_BITS 2\n+/* load factor in percent */\n+#define OIDMAP_LOAD_FACTOR 80\n+\n+static void alloc_table(struct oidmap *map, unsigned int size)\n+{\n+\tmap->tablesize = size;\n+\tmap->table = xcalloc(size, sizeof(struct oidmap_entry *));\n+\n+\t/* calculate resize thresholds for new size */\n+\tmap->grow_at = (unsigned int) ((uint64_t) size * OIDMAP_LOAD_FACTOR / 100);\n+\tif (size <= OIDMAP_INITIAL_SIZE)\n+\t\tmap->shrink_at = 0;\n+\telse\n+\t\t/*\n+\t\t * The shrink-threshold must be slightly smaller than\n+\t\t * (grow-threshold / resize-factor) to prevent erratic resizing,\n+\t\t * thus we divide by (resize-factor + 1).\n+\t\t */\n+\t\tmap->shrink_at = map->grow_at / ((1 << OIDMAP_RESIZE_BITS) + 1);\n+}\n+\n+static inline unsigned int bucket(const struct oidmap *map,\n+\t\t\t\t  const struct object_id *key)\n+{\n+\tunsigned int hash;\n+\tmemcpy(&hash, key->hash, sizeof(hash));\n+\treturn hash & (map->tablesize - 1);\n+}\n+\n+static void rehash(struct oidmap *map, unsigned int newsize)\n+{\n+\tunsigned int i, oldsize = map->tablesize;\n+\tstruct oidmap_entry **oldtable = map->table;\n+\n+\talloc_table(map, newsize);\n+\tfor (i = 0; i < oldsize; i++) {\n+\t\tstruct oidmap_entry *e = oldtable[i];\n+\t\twhile (e) {\n+\t\t\tstruct oidmap_entry *next = e->next;\n+\t\t\tunsigned int b = bucket(map, &e->oid);\n+\t\t\te->next = map->table[b];\n+\t\t\tmap->table[b] = e;\n+\t\t\te = next;\n+\t\t}\n+\t}\n+\tfree(oldtable);\n+}\n+\n+static inline struct oidmap_entry **find_entry_ptr(const struct oidmap *map,\n+\t\t\t\t\t\t   const struct object_id *key)\n+{\n+\tstruct oidmap_entry **e = &map->table[bucket(map, key)];\n+\twhile (*e && oidcmp(&(*e)->oid, key))\n+\t\te = &(*e)->next;\n+\treturn e;\n+}\n+\n+void oidmap_init(struct oidmap *map, size_t initial_size)\n+{\n+\tunsigned int size = OIDMAP_INITIAL_SIZE;\n+\n+\tmemset(map, 0, sizeof(*map));\n+\n+\t/* calculate initial table size and allocate the table */\n+\tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n+\t\t\t/ OIDMAP_LOAD_FACTOR);\n+\twhile (initial_size > size)\n+\t\tsize <<= OIDMAP_RESIZE_BITS;\n+\talloc_table(map, size);\n+\n+\t/*\n+\t * Keep track of the number of items in the map and\n+\t * allow the map to automatically grow as necessary.\n+\t */\n+\tmap->do_count_items = 1;\n+}\n+\n+void oidmap_free(struct oidmap *map, int free_entries)\n+{\n+\tif (!map || !map->table)\n+\t\treturn;\n+\tif (free_entries) {\n+\t\tint i;\n+\t\tfor (i = 0; i < map->tablesize; i++) {\n+\t\t\tstruct oidmap_entry *e = map->table[i];\n+\t\t\twhile (e) {\n+\t\t\t\tstruct oidmap_entry *next = e->next;\n+\t\t\t\tfree(e);\n+\t\t\t\te = next;\n+\t\t\t}\n+\t\t}\n+\t}\n+\tfree(map->table);\n+\tmemset(map, 0, sizeof(*map));\n+}\n+\n+void *oidmap_get(const struct oidmap *map, const struct object_id *key)\n+{\n+\treturn *find_entry_ptr(map, key);\n+}\n+\n+static void oidmap_add(struct oidmap *map, struct oidmap_entry *entry)\n+{\n+\tunsigned int b = bucket(map, &entry->oid);\n+\n+\t/* add entry */\n+\tentry->next = map->table[b];\n+\tmap->table[b] = entry;\n+\n+\t/* fix size and rehash if appropriate */\n+\tif (map->do_count_items) {\n+\t\tmap->private_size++;\n+\t\tif (map->private_size > map->grow_at)\n+\t\t\trehash(map, map->tablesize << OIDMAP_RESIZE_BITS);\n+\t}\n+}\n+\n+void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n+{\n+\tstruct oidmap_entry *old;\n+\tstruct oidmap_entry **e = find_entry_ptr(map, key);\n+\tif (!*e)\n+\t\treturn NULL;\n+\n+\t/* remove existing entry */\n+\told = *e;\n+\t*e = old->next;\n+\told->next = NULL;\n+\n+\t/* fix size and rehash if appropriate */\n+\tif (map->do_count_items) {\n+\t\tmap->private_size--;\n+\t\tif (map->private_size < map->shrink_at)\n+\t\t\trehash(map, map->tablesize >> OIDMAP_RESIZE_BITS);\n+\t}\n+\n+\treturn old;\n+}\n+\n+void *oidmap_put(struct oidmap *map, void *entry)\n+{\n+\tstruct oidmap_entry *to_put = entry;\n+\tstruct oidmap_entry *old = oidmap_remove(map, &to_put->oid);\n+\toidmap_add(map, to_put);\n+\treturn old;\n+}\ndiff --git a/oidmap.h b/oidmap.h\nnew file mode 100644\nindex 000000000..a543ed828\n--- /dev/null\n+++ b/oidmap.h\n@@ -0,0 +1,98 @@\n+#ifndef OIDMAP_H\n+#define OIDMAP_H\n+\n+/*\n+ * struct oidmap_entry is a structure representing an entry in the hash table,\n+ * which must be used as first member of user data structures. It must be\n+ * zero-initialized (or use OIDMAP_ENTRY_INIT).\n+ */\n+struct oidmap_entry {\n+\t/*\n+\t * next points to the next entry in case of collisions (i.e. if\n+\t * multiple entries map to the same bucket). For oidmap's internal use\n+\t * only.\n+\t */\n+\tstruct oidmap_entry *next;\n+\n+\tstruct object_id oid;\n+};\n+#define OIDMAP_ENTRY_INIT { NULL }\n+\n+/*\n+ * struct oidmap is the hash table structure. Members can be used as follows,\n+ * but should not be modified directly.\n+ */\n+struct oidmap {\n+\tstruct oidmap_entry **table;\n+\n+\t/* total number of entries (0 means the hashmap is empty) */\n+\tunsigned int private_size; /* use oidmap_get_size() */\n+\n+\t/*\n+\t * tablesize is the allocated size of the hash table. A non-0 value\n+\t * indicates that the hashmap is initialized. It may also be useful\n+\t * for statistical purposes (i.e. `size / tablesize` is the current\n+\t * load factor).\n+\t */\n+\tunsigned int tablesize;\n+\n+\tunsigned int grow_at;\n+\tunsigned int shrink_at;\n+\n+\tunsigned int do_count_items : 1;\n+};\n+\n+/* oidmap functions */\n+\n+/*\n+ * Initializes an oidmap structure.\n+ *\n+ * `map` is the oidmap to initialize.\n+ *\n+ * If the total number of entries is known in advance, the `initial_size`\n+ * parameter may be used to preallocate a sufficiently large table and thus\n+ * prevent expensive resizing. If 0, the table is dynamically resized.\n+ */\n+extern void oidmap_init(struct oidmap *map, size_t initial_size);\n+\n+/*\n+ * Frees an oidmap structure and allocated memory.\n+ *\n+ * If `free_entries` is true, each oidmap_entry in the map is freed as well\n+ * using stdlibs free().\n+ */\n+extern void oidmap_free(struct oidmap *map, int free_entries);\n+\n+/*\n+ * Return the number of items in the map.\n+ */\n+static inline unsigned int oidmap_get_size(struct oidmap *map)\n+{\n+\tif (map->do_count_items)\n+\t\treturn map->private_size;\n+\n+\tBUG(\"oidmap_get_size: size not set\");\n+\treturn 0;\n+}\n+\n+/*\n+ * Returns the oidmap entry for the specified oid, or NULL if not found.\n+ */\n+extern void *oidmap_get(const struct oidmap *map,\n+\t\t\tconst struct object_id *key);\n+\n+/*\n+ * Adds or replaces an oidmap entry.\n+ *\n+ * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n+ */\n+extern void *oidmap_put(struct oidmap *map, void *entry);\n+\n+/*\n+ * Removes an oidmap entry matching the specified oid.\n+ *\n+ * Returns the removed entry, or NULL if not found.\n+ */\n+extern void *oidmap_remove(struct oidmap *map, const struct object_id *key);\n+\n+#endif\ndiff --git a/oidset.c b/oidset.c\nindex a6a08ba52..6fe7036c4 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -1,50 +1,30 @@\n #include \"cache.h\"\n #include \"oidset.h\"\n \n-struct oidset_entry {\n-\tstruct hashmap_entry hash;\n-\tstruct object_id oid;\n-};\n-\n-static int oidset_hashcmp(const void *unused_cmp_data,\n-\t\t\t  const void *va, const void *vb,\n-\t\t\t  const void *vkey)\n-{\n-\tconst struct oidset_entry *a = va, *b = vb;\n-\tconst struct object_id *key = vkey;\n-\treturn oidcmp(&a->oid, key ? key : &b->oid);\n-}\n-\n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n-\tstruct hashmap_entry key;\n-\n-\tif (!set->map.cmpfn)\n+\tif (!set->map.tablesize)\n \t\treturn 0;\n-\n-\thashmap_entry_init(&key, sha1hash(oid->hash));\n-\treturn !!hashmap_get(&set->map, &key, oid);\n+\treturn !!oidmap_get(&set->map, oid);\n }\n \n int oidset_insert(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidset_entry *entry;\n-\n-\tif (!set->map.cmpfn)\n-\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n+\tstruct oidmap_entry *entry;\n \n-\tif (oidset_contains(set, oid))\n+\tif (!set->map.tablesize)\n+\t\toidmap_init(&set->map, 0);\n+\telse if (oidset_contains(set, oid))\n \t\treturn 1;\n \n-\tentry = xmalloc(sizeof(*entry));\n-\thashmap_entry_init(&entry->hash, sha1hash(oid->hash));\n+\tentry = xcalloc(1, sizeof(*entry));\n \toidcpy(&entry->oid, oid);\n \n-\thashmap_add(&set->map, entry);\n+\toidmap_put(&set->map, entry);\n \treturn 0;\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\thashmap_free(&set->map, 1);\n+\toidmap_free(&set->map, 1);\n }\ndiff --git a/oidset.h b/oidset.h\nindex b7eaab5b8..b1ec82bfc 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -1,6 +1,8 @@\n #ifndef OIDSET_H\n #define OIDSET_H\n \n+#include \"oidmap.h\"\n+\n /**\n  * This API is similar to sha1-array, in that it maintains a set of object ids\n  * in a memory-efficient way. The major differences are:\n@@ -17,7 +19,7 @@\n  * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n  */\n struct oidset {\n-\tstruct hashmap map;\n+\tstruct oidmap map;\n };\n \n #define OIDSET_INIT { { NULL } }\n-- \n2.14.2.822.g60be5d43e6-goog\n\n"},{"id":"329083","messageId":"20170928004137.GD68699@google.com","threadId":"46849","inReplyTo":"20170927221910.164552-1-jonathantanmy@google.com","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Brandon Williams","fromEmail":"bmwill@google.com","sentAt":"2017-09-28T00:41:37Z","receivedAt":"2017-09-28T00:41:45Z","isPatch":true,"sender":{"key":"bwilliams.eng@gmail.com","avatar":null},"body":"On 09/27, Jonathan Tan wrote:\n> This is similar to using the hashmap in hashmap.c, but with an\n> easier-to-use API. In particular, custom entry comparisons no longer\n> need to be written, and lookups can be done without constructing a\n> temporary entry structure.\n> \n> oidset has been updated to use oidmap.\n\nAfter a quick glance at the code, I think it looks good.  I do have one\nsuggestion though.  This map is structured much like our internal\nhashmap where if you want to include any data you have to implement your\nown struct with the internal 'entry' struct as the first member in your\ncustom struct.  I personal dislike this method, despite the potential\nmemory savings, because it makes the data structure much more difficult\nto use.\n\nIf all i wanted was a map from 'OID -> const char *' then I would need\nto write all the boilerplate code to make a struct which contains the\nmap 'entry' struct + the 'const char *' entry.  You are also making the\ncaller responsible for allocating the individual entries instead of\nletting the data structure take care of that internally.\n\nTo me it seems like a much simpler API for a map would be to just allow\ncallers to store a 'void *' as the value.\n\n-- \nBrandon Williams\n"},{"id":"329086","messageId":"xmqqr2ur348z.fsf@gitster.mtv.corp.google.com","threadId":"46849","inReplyTo":"20170927221910.164552-1-jonathantanmy@google.com","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-28T03:13:00Z","receivedAt":"2017-09-28T03:13:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jonathan Tan <jonathantanmy@google.com> writes:\n\n> This is similar to using the hashmap in hashmap.c, but with an\n> easier-to-use API. In particular, custom entry comparisons no longer\n> need to be written, and lookups can be done without constructing a\n> temporary entry structure.\n\nA naïve question is why this needs to duplicate so much code, just\nto build something similar in spirit to hashmap but unlike hashmap\nthat can take caller-defined keys, limited to using oid as the keys,\ninstead of just being a thin API wrapper that uses hashmap as its\ninternal implementation detail.  \n\nIs the way hashmap API is structured so hard to use it in such a\nway, or something?\n\n>  Makefile |   1 +\n>  oidmap.c | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  oidmap.h |  98 ++++++++++++++++++++++++++++++++++++++++\n>  oidset.c |  38 ++++------------\n>  oidset.h |   4 +-\n>  5 files changed, 263 insertions(+), 30 deletions(-)\n>  create mode 100644 oidmap.c\n>  create mode 100644 oidmap.h\n>\n> diff --git a/Makefile b/Makefile\n> index ed4ca438b..64136dde4 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -821,6 +821,7 @@ LIB_OBJS += notes-cache.o\n>  LIB_OBJS += notes-merge.o\n>  LIB_OBJS += notes-utils.o\n>  LIB_OBJS += object.o\n> +LIB_OBJS += oidmap.o\n>  LIB_OBJS += oidset.o\n>  LIB_OBJS += packfile.o\n>  LIB_OBJS += pack-bitmap.o\n> diff --git a/oidmap.c b/oidmap.c\n> new file mode 100644\n> index 000000000..40e696cee\n> --- /dev/null\n> +++ b/oidmap.c\n> @@ -0,0 +1,152 @@\n> +#include \"cache.h\"\n> +#include \"oidmap.h\"\n> +\n> +#define OIDMAP_INITIAL_SIZE 64\n> +/* grow / shrink by 2^2 */\n> +#define OIDMAP_RESIZE_BITS 2\n> +/* load factor in percent */\n> +#define OIDMAP_LOAD_FACTOR 80\n> +\n> +static void alloc_table(struct oidmap *map, unsigned int size)\n> +{\n> +\tmap->tablesize = size;\n> +\tmap->table = xcalloc(size, sizeof(struct oidmap_entry *));\n> +\n> +\t/* calculate resize thresholds for new size */\n> +\tmap->grow_at = (unsigned int) ((uint64_t) size * OIDMAP_LOAD_FACTOR / 100);\n> +\tif (size <= OIDMAP_INITIAL_SIZE)\n> +\t\tmap->shrink_at = 0;\n> +\telse\n> +\t\t/*\n> +\t\t * The shrink-threshold must be slightly smaller than\n> +\t\t * (grow-threshold / resize-factor) to prevent erratic resizing,\n> +\t\t * thus we divide by (resize-factor + 1).\n> +\t\t */\n> +\t\tmap->shrink_at = map->grow_at / ((1 << OIDMAP_RESIZE_BITS) + 1);\n> +}\n> +\n> +static inline unsigned int bucket(const struct oidmap *map,\n> +\t\t\t\t  const struct object_id *key)\n> +{\n> +\tunsigned int hash;\n> +\tmemcpy(&hash, key->hash, sizeof(hash));\n> +\treturn hash & (map->tablesize - 1);\n> +}\n> +\n> +static void rehash(struct oidmap *map, unsigned int newsize)\n> +{\n> +\tunsigned int i, oldsize = map->tablesize;\n> +\tstruct oidmap_entry **oldtable = map->table;\n> +\n> +\talloc_table(map, newsize);\n> +\tfor (i = 0; i < oldsize; i++) {\n> +\t\tstruct oidmap_entry *e = oldtable[i];\n> +\t\twhile (e) {\n> +\t\t\tstruct oidmap_entry *next = e->next;\n> +\t\t\tunsigned int b = bucket(map, &e->oid);\n> +\t\t\te->next = map->table[b];\n> +\t\t\tmap->table[b] = e;\n> +\t\t\te = next;\n> +\t\t}\n> +\t}\n> +\tfree(oldtable);\n> +}\n> +\n> +static inline struct oidmap_entry **find_entry_ptr(const struct oidmap *map,\n> +\t\t\t\t\t\t   const struct object_id *key)\n> +{\n> +\tstruct oidmap_entry **e = &map->table[bucket(map, key)];\n> +\twhile (*e && oidcmp(&(*e)->oid, key))\n> +\t\te = &(*e)->next;\n> +\treturn e;\n> +}\n> +\n> +void oidmap_init(struct oidmap *map, size_t initial_size)\n> +{\n> +\tunsigned int size = OIDMAP_INITIAL_SIZE;\n> +\n> +\tmemset(map, 0, sizeof(*map));\n> +\n> +\t/* calculate initial table size and allocate the table */\n> +\tinitial_size = (unsigned int) ((uint64_t) initial_size * 100\n> +\t\t\t/ OIDMAP_LOAD_FACTOR);\n> +\twhile (initial_size > size)\n> +\t\tsize <<= OIDMAP_RESIZE_BITS;\n> +\talloc_table(map, size);\n> +\n> +\t/*\n> +\t * Keep track of the number of items in the map and\n> +\t * allow the map to automatically grow as necessary.\n> +\t */\n> +\tmap->do_count_items = 1;\n> +}\n> +\n> +void oidmap_free(struct oidmap *map, int free_entries)\n> +{\n> +\tif (!map || !map->table)\n> +\t\treturn;\n> +\tif (free_entries) {\n> +\t\tint i;\n> +\t\tfor (i = 0; i < map->tablesize; i++) {\n> +\t\t\tstruct oidmap_entry *e = map->table[i];\n> +\t\t\twhile (e) {\n> +\t\t\t\tstruct oidmap_entry *next = e->next;\n> +\t\t\t\tfree(e);\n> +\t\t\t\te = next;\n> +\t\t\t}\n> +\t\t}\n> +\t}\n> +\tfree(map->table);\n> +\tmemset(map, 0, sizeof(*map));\n> +}\n> +\n> +void *oidmap_get(const struct oidmap *map, const struct object_id *key)\n> +{\n> +\treturn *find_entry_ptr(map, key);\n> +}\n> +\n> +static void oidmap_add(struct oidmap *map, struct oidmap_entry *entry)\n> +{\n> +\tunsigned int b = bucket(map, &entry->oid);\n> +\n> +\t/* add entry */\n> +\tentry->next = map->table[b];\n> +\tmap->table[b] = entry;\n> +\n> +\t/* fix size and rehash if appropriate */\n> +\tif (map->do_count_items) {\n> +\t\tmap->private_size++;\n> +\t\tif (map->private_size > map->grow_at)\n> +\t\t\trehash(map, map->tablesize << OIDMAP_RESIZE_BITS);\n> +\t}\n> +}\n> +\n> +void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n> +{\n> +\tstruct oidmap_entry *old;\n> +\tstruct oidmap_entry **e = find_entry_ptr(map, key);\n> +\tif (!*e)\n> +\t\treturn NULL;\n> +\n> +\t/* remove existing entry */\n> +\told = *e;\n> +\t*e = old->next;\n> +\told->next = NULL;\n> +\n> +\t/* fix size and rehash if appropriate */\n> +\tif (map->do_count_items) {\n> +\t\tmap->private_size--;\n> +\t\tif (map->private_size < map->shrink_at)\n> +\t\t\trehash(map, map->tablesize >> OIDMAP_RESIZE_BITS);\n> +\t}\n> +\n> +\treturn old;\n> +}\n> +\n> +void *oidmap_put(struct oidmap *map, void *entry)\n> +{\n> +\tstruct oidmap_entry *to_put = entry;\n> +\tstruct oidmap_entry *old = oidmap_remove(map, &to_put->oid);\n> +\toidmap_add(map, to_put);\n> +\treturn old;\n> +}\n> diff --git a/oidmap.h b/oidmap.h\n> new file mode 100644\n> index 000000000..a543ed828\n> --- /dev/null\n> +++ b/oidmap.h\n> @@ -0,0 +1,98 @@\n> +#ifndef OIDMAP_H\n> +#define OIDMAP_H\n> +\n> +/*\n> + * struct oidmap_entry is a structure representing an entry in the hash table,\n> + * which must be used as first member of user data structures. It must be\n> + * zero-initialized (or use OIDMAP_ENTRY_INIT).\n> + */\n> +struct oidmap_entry {\n> +\t/*\n> +\t * next points to the next entry in case of collisions (i.e. if\n> +\t * multiple entries map to the same bucket). For oidmap's internal use\n> +\t * only.\n> +\t */\n> +\tstruct oidmap_entry *next;\n> +\n> +\tstruct object_id oid;\n> +};\n> +#define OIDMAP_ENTRY_INIT { NULL }\n> +\n> +/*\n> + * struct oidmap is the hash table structure. Members can be used as follows,\n> + * but should not be modified directly.\n> + */\n> +struct oidmap {\n> +\tstruct oidmap_entry **table;\n> +\n> +\t/* total number of entries (0 means the hashmap is empty) */\n> +\tunsigned int private_size; /* use oidmap_get_size() */\n> +\n> +\t/*\n> +\t * tablesize is the allocated size of the hash table. A non-0 value\n> +\t * indicates that the hashmap is initialized. It may also be useful\n> +\t * for statistical purposes (i.e. `size / tablesize` is the current\n> +\t * load factor).\n> +\t */\n> +\tunsigned int tablesize;\n> +\n> +\tunsigned int grow_at;\n> +\tunsigned int shrink_at;\n> +\n> +\tunsigned int do_count_items : 1;\n> +};\n> +\n> +/* oidmap functions */\n> +\n> +/*\n> + * Initializes an oidmap structure.\n> + *\n> + * `map` is the oidmap to initialize.\n> + *\n> + * If the total number of entries is known in advance, the `initial_size`\n> + * parameter may be used to preallocate a sufficiently large table and thus\n> + * prevent expensive resizing. If 0, the table is dynamically resized.\n> + */\n> +extern void oidmap_init(struct oidmap *map, size_t initial_size);\n> +\n> +/*\n> + * Frees an oidmap structure and allocated memory.\n> + *\n> + * If `free_entries` is true, each oidmap_entry in the map is freed as well\n> + * using stdlibs free().\n> + */\n> +extern void oidmap_free(struct oidmap *map, int free_entries);\n> +\n> +/*\n> + * Return the number of items in the map.\n> + */\n> +static inline unsigned int oidmap_get_size(struct oidmap *map)\n> +{\n> +\tif (map->do_count_items)\n> +\t\treturn map->private_size;\n> +\n> +\tBUG(\"oidmap_get_size: size not set\");\n> +\treturn 0;\n> +}\n> +\n> +/*\n> + * Returns the oidmap entry for the specified oid, or NULL if not found.\n> + */\n> +extern void *oidmap_get(const struct oidmap *map,\n> +\t\t\tconst struct object_id *key);\n> +\n> +/*\n> + * Adds or replaces an oidmap entry.\n> + *\n> + * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n> + */\n> +extern void *oidmap_put(struct oidmap *map, void *entry);\n> +\n> +/*\n> + * Removes an oidmap entry matching the specified oid.\n> + *\n> + * Returns the removed entry, or NULL if not found.\n> + */\n> +extern void *oidmap_remove(struct oidmap *map, const struct object_id *key);\n> +\n> +#endif\n> diff --git a/oidset.c b/oidset.c\n> index a6a08ba52..6fe7036c4 100644\n> --- a/oidset.c\n> +++ b/oidset.c\n> @@ -1,50 +1,30 @@\n>  #include \"cache.h\"\n>  #include \"oidset.h\"\n>  \n> -struct oidset_entry {\n> -\tstruct hashmap_entry hash;\n> -\tstruct object_id oid;\n> -};\n> -\n> -static int oidset_hashcmp(const void *unused_cmp_data,\n> -\t\t\t  const void *va, const void *vb,\n> -\t\t\t  const void *vkey)\n> -{\n> -\tconst struct oidset_entry *a = va, *b = vb;\n> -\tconst struct object_id *key = vkey;\n> -\treturn oidcmp(&a->oid, key ? key : &b->oid);\n> -}\n> -\n>  int oidset_contains(const struct oidset *set, const struct object_id *oid)\n>  {\n> -\tstruct hashmap_entry key;\n> -\n> -\tif (!set->map.cmpfn)\n> +\tif (!set->map.tablesize)\n>  \t\treturn 0;\n> -\n> -\thashmap_entry_init(&key, sha1hash(oid->hash));\n> -\treturn !!hashmap_get(&set->map, &key, oid);\n> +\treturn !!oidmap_get(&set->map, oid);\n>  }\n>  \n>  int oidset_insert(struct oidset *set, const struct object_id *oid)\n>  {\n> -\tstruct oidset_entry *entry;\n> -\n> -\tif (!set->map.cmpfn)\n> -\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n> +\tstruct oidmap_entry *entry;\n>  \n> -\tif (oidset_contains(set, oid))\n> +\tif (!set->map.tablesize)\n> +\t\toidmap_init(&set->map, 0);\n> +\telse if (oidset_contains(set, oid))\n>  \t\treturn 1;\n>  \n> -\tentry = xmalloc(sizeof(*entry));\n> -\thashmap_entry_init(&entry->hash, sha1hash(oid->hash));\n> +\tentry = xcalloc(1, sizeof(*entry));\n>  \toidcpy(&entry->oid, oid);\n>  \n> -\thashmap_add(&set->map, entry);\n> +\toidmap_put(&set->map, entry);\n>  \treturn 0;\n>  }\n>  \n>  void oidset_clear(struct oidset *set)\n>  {\n> -\thashmap_free(&set->map, 1);\n> +\toidmap_free(&set->map, 1);\n>  }\n> diff --git a/oidset.h b/oidset.h\n> index b7eaab5b8..b1ec82bfc 100644\n> --- a/oidset.h\n> +++ b/oidset.h\n> @@ -1,6 +1,8 @@\n>  #ifndef OIDSET_H\n>  #define OIDSET_H\n>  \n> +#include \"oidmap.h\"\n> +\n>  /**\n>   * This API is similar to sha1-array, in that it maintains a set of object ids\n>   * in a memory-efficient way. The major differences are:\n> @@ -17,7 +19,7 @@\n>   * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n>   */\n>  struct oidset {\n> -\tstruct hashmap map;\n> +\tstruct oidmap map;\n>  };\n>  \n>  #define OIDSET_INIT { { NULL } }\n"},{"id":"329113","messageId":"20170928103850.449bd743d5f10f2c948b0c83@google.com","threadId":"46849","inReplyTo":"xmqqr2ur348z.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-09-28T17:38:50Z","receivedAt":"2017-09-28T17:38:58Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Thu, 28 Sep 2017 12:13:00 +0900\nJunio C Hamano <gitster@pobox.com> wrote:\n\n> Jonathan Tan <jonathantanmy@google.com> writes:\n> \n> > This is similar to using the hashmap in hashmap.c, but with an\n> > easier-to-use API. In particular, custom entry comparisons no longer\n> > need to be written, and lookups can be done without constructing a\n> > temporary entry structure.\n> \n> A naïve question is why this needs to duplicate so much code, just\n> to build something similar in spirit to hashmap but unlike hashmap\n> that can take caller-defined keys, limited to using oid as the keys,\n> instead of just being a thin API wrapper that uses hashmap as its\n> internal implementation detail.  \n> \n> Is the way hashmap API is structured so hard to use it in such a\n> way, or something?\n\nAnother reason that I probably should have mentioned is the opportunity\nto save 4 bytes. I didn't mention it in the commit message at first\nbecause I felt that the benefit was very specific and, as far as I know,\nwouldn't be seen on architectures with 8-byte-aligned pointers until we\nchange the hash function. But I should have probably written something\nlike this in the commit message:\n\n    Using oidmap also saves 4 bytes per entry, compared to hashmap,\n    because the hash does not need to be stored separately as an int.\n    (However, alignment considerations might mean that we will not\n    observe these savings until we change the hash function, since\n    currently 20-byte hashes are being used.)\n\nIf we decide that the 4 bytes are not important, right now at least, I\ncan change it so that this is a thin API wrapper over hashmap. We could\nalways change it later.\n"},{"id":"329114","messageId":"20170928104616.be61b394b50dc5193be275be@google.com","threadId":"46849","inReplyTo":"20170928004137.GD68699@google.com","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-09-28T17:46:16Z","receivedAt":"2017-09-28T17:46:22Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Wed, 27 Sep 2017 17:41:37 -0700\nBrandon Williams <bmwill@google.com> wrote:\n\n> On 09/27, Jonathan Tan wrote:\n> > This is similar to using the hashmap in hashmap.c, but with an\n> > easier-to-use API. In particular, custom entry comparisons no longer\n> > need to be written, and lookups can be done without constructing a\n> > temporary entry structure.\n> > \n> > oidset has been updated to use oidmap.\n> \n> After a quick glance at the code, I think it looks good.  I do have one\n> suggestion though.  This map is structured much like our internal\n> hashmap where if you want to include any data you have to implement your\n> own struct with the internal 'entry' struct as the first member in your\n> custom struct.  I personal dislike this method, despite the potential\n> memory savings, because it makes the data structure much more difficult\n> to use.\n> \n> If all i wanted was a map from 'OID -> const char *' then I would need\n> to write all the boilerplate code to make a struct which contains the\n> map 'entry' struct + the 'const char *' entry.\n>\n> You are also making the\n> caller responsible for allocating the individual entries instead of\n> letting the data structure take care of that internally.\n\nIn the case where your extra data (\"const char *\" in your example) fits\nin a pointer, yes it's true that the \"util\" design eliminates the need\nto define and allocate a struct. But if you need to store more than\nthat, you will still have that need.\n\n> To me it seems like a much simpler API for a map would be to just allow\n> callers to store a 'void *' as the value.\n\nI agree that the API would be simpler.\n\nMy main motivation with this design is indeed to save memory, and not\ninconvenience the user too much (in the case where you're storing things\nlarger than one pointer, you just need to remember to put the special\nstruct at the beginning of your struct), but if memory is not so\nimportant, I agree that we can switch to the \"util\" design.\n"},{"id":"329117","messageId":"20170928200556.grysihlj7cbzocfq@sigill.intra.peff.net","threadId":"46849","inReplyTo":"20170928104616.be61b394b50dc5193be275be@google.com","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-28T20:05:57Z","receivedAt":"2017-09-28T20:06:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 28, 2017 at 10:46:16AM -0700, Jonathan Tan wrote:\n\n> > To me it seems like a much simpler API for a map would be to just allow\n> > callers to store a 'void *' as the value.\n> \n> I agree that the API would be simpler.\n> \n> My main motivation with this design is indeed to save memory, and not\n> inconvenience the user too much (in the case where you're storing things\n> larger than one pointer, you just need to remember to put the special\n> struct at the beginning of your struct), but if memory is not so\n> important, I agree that we can switch to the \"util\" design.\n\nWhen I saw that you were implementing \"oidset\" in terms of \"oidmap\", I\nwas all ready to be crabby about this extra memory. But then I saw that\nthe implementation tries hard not to waste any memory. :)\n\nAll of which is to say I gave this some thought when I was in the \"ready\nto be crabby\" phase, and came to the conclusion that it probably isn't\nthat painful. An unused pointer is 8 bytes per entry. We're already\nspending 20 for the oid itself (which is likely to grow to 32\neventually), plus 8 for the chained \"next\" pointer. Plus potentially 8\nfor a padded version of the hash, if we just use a straight hashmap that\nduplicates the hash field.\n\nSo depending how you count it, we're wasting between 28% (sha1 and no\nextra hash) and 16% (sha256 plus reusing hashmap). That's not great, but\nit's probably not breaking the bank.\n\nAnother way of thinking about it. Large-ish (but not insane) repos have\non the order of 5-10 million objects. If we had an oidset that mentioned\nevery single object in the repository, that's 40-80MB wasted in the\nworst case. For current uses of oidset, that's probably fine. It's\ngenerally used only to collect ref tips (so probably two orders of\nmagnitude less).\n\nIf you're planning on using an oidset to mark every object in a\n100-million-object monorepo, we'd probably care more. But I'd venture to\nsay that any scheme which involves generating that hash table on the fly\nis doing it wrong. At at that scale we'd want to look at compact\nmmap-able on-disk representations.\n\nSo I think we may be better off going with the solution here that's\nsimpler and requires introducing less code. If it does turn out to be a\nmemory problem in the future, this is a _really_ easy thing to optimize\nafter the fact, because we have these nice abstractions.\n\n-Peff\n"},{"id":"329188","messageId":"20170929120456.3bb8021de1c7aebee7bb5026@google.com","threadId":"46849","inReplyTo":"20170928200556.grysihlj7cbzocfq@sigill.intra.peff.net","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-09-29T19:04:56Z","receivedAt":"2017-09-29T19:05:04Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Thu, 28 Sep 2017 16:05:57 -0400\nJeff King <peff@peff.net> wrote:\n\n> When I saw that you were implementing \"oidset\" in terms of \"oidmap\", I\n> was all ready to be crabby about this extra memory. But then I saw that\n> the implementation tries hard not to waste any memory. :)\n> \n> All of which is to say I gave this some thought when I was in the \"ready\n> to be crabby\" phase, and came to the conclusion that it probably isn't\n> that painful. An unused pointer is 8 bytes per entry. We're already\n> spending 20 for the oid itself (which is likely to grow to 32\n> eventually), plus 8 for the chained \"next\" pointer. Plus potentially 8\n> for a padded version of the hash, if we just use a straight hashmap that\n> duplicates the hash field.\n> \n> So depending how you count it, we're wasting between 28% (sha1 and no\n> extra hash) and 16% (sha256 plus reusing hashmap). That's not great, but\n> it's probably not breaking the bank.\n\nHmm...how did you get the 16% figure? The values, as I see it, are:\n - 32 for the sha256 hash itself\n - 8 for the \"next\" chain pointer\n - 8 for the padded hash\n - 8 for the \"util\" pointer\n\nFor an oidset, the padded hash and the \"util\" pointer are wasted, which is\n16/56=0.286. (If you assume, say, 8 bytes of malloc bookkeeping overhead, then\n16/64=0.25.)\n\nFor other uses of an oidmap, the padded hash and \"util\" pointer are still\nwasted, so the numbers are the same as above (except that the malloc\nbookkeeping overhead is doubled).\n\n> Another way of thinking about it. Large-ish (but not insane) repos have\n> on the order of 5-10 million objects. If we had an oidset that mentioned\n> every single object in the repository, that's 40-80MB wasted in the\n> worst case. For current uses of oidset, that's probably fine. It's\n> generally used only to collect ref tips (so probably two orders of\n> magnitude less).\n> \n> If you're planning on using an oidset to mark every object in a\n> 100-million-object monorepo, we'd probably care more. But I'd venture to\n> say that any scheme which involves generating that hash table on the fly\n> is doing it wrong. At at that scale we'd want to look at compact\n> mmap-able on-disk representations.\n\nIn a 100-million-object monorepo, we will probably end up only operating on the\n\"frontier\" objects (objects that we do not have but we know about because some\nobject we have reference them) at the worst. I don't have numbers but I think\nthat that is at least an order of magnitude less than 100M.\n\n> So I think we may be better off going with the solution here that's\n> simpler and requires introducing less code. If it does turn out to be a\n> memory problem in the future, this is a _really_ easy thing to optimize\n> after the fact, because we have these nice abstractions.\n\nOptimizing away the padded hash should be straightforward. Optimizing away the\n\"util\" pointer after we have code that uses it is (slightly?) less\nstraightforward, but still doable.\n\nI still lean towards saving memory by eliminating the padded hash and\nnot using the \"util\" pointer, because the complication is contained\nwithin only two files (oidmap.{c,h}), and because the constant factors\nin memory savings might end up mattering. But I don't feel strongly\nabout that - I think any of the oidmaps that we have discussed is an\nimprovement over what we have now.\n"},{"id":"329189","messageId":"20170929192624.4ukvpjujgiyzgibb@sigill.intra.peff.net","threadId":"46849","inReplyTo":"20170929120456.3bb8021de1c7aebee7bb5026@google.com","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-29T19:26:25Z","receivedAt":"2017-09-29T19:26:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 29, 2017 at 12:04:56PM -0700, Jonathan Tan wrote:\n\n> > So depending how you count it, we're wasting between 28% (sha1 and no\n> > extra hash) and 16% (sha256 plus reusing hashmap). That's not great, but\n> > it's probably not breaking the bank.\n> \n> Hmm...how did you get the 16% figure? The values, as I see it, are:\n>  - 32 for the sha256 hash itself\n>  - 8 for the \"next\" chain pointer\n>  - 8 for the padded hash\n>  - 8 for the \"util\" pointer\n> \n> For an oidset, the padded hash and the \"util\" pointer are wasted, which is\n> 16/56=0.286. (If you assume, say, 8 bytes of malloc bookkeeping overhead, then\n> 16/64=0.25.)\n\nSorry to be unclear. I was just counting the waste for the \"util\"\npointer, not the extra padded hash bit (which AFAIK is already wasted in\noidset). So I computed 48 bytes without the util pointer, which means we\nwaste an additional 16% to add it.\n\nAnyway, my point was mostly to say that this is a fractional percentage\nof the total memory. So it falls into the category of \"this might help\nin tight situations\" and less \"this will blow up in our faces\".\n\n> In a 100-million-object monorepo, we will probably end up only operating on the\n> \"frontier\" objects (objects that we do not have but we know about because some\n> object we have reference them) at the worst. I don't have numbers but I think\n> that that is at least an order of magnitude less than 100M.\n\nAgreed.\n\n> > So I think we may be better off going with the solution here that's\n> > simpler and requires introducing less code. If it does turn out to be a\n> > memory problem in the future, this is a _really_ easy thing to optimize\n> > after the fact, because we have these nice abstractions.\n> \n> Optimizing away the padded hash should be straightforward. Optimizing away the\n> \"util\" pointer after we have code that uses it is (slightly?) less\n> straightforward, but still doable.\n\nI was thinking here of just oidset. It has a limited API, so swapping\nout the implementation for one that does not depend on oidmap and waste\nthe \"util\" pointer would be the \"easy\" part.\n\n> I still lean towards saving memory by eliminating the padded hash and\n> not using the \"util\" pointer, because the complication is contained\n> within only two files (oidmap.{c,h}), and because the constant factors\n> in memory savings might end up mattering. But I don't feel strongly\n> about that - I think any of the oidmaps that we have discussed is an\n> improvement over what we have now.\n\nMy main concern is not so much about complexity bleeding out of the\noidmap code, but that now we have two parallel near-identical hashmap\nimplementations.  When one gets an optimization, bugfix, or new feature,\nwe have to port it over manually to the other.\n\n-Peff\n"},{"id":"329219","messageId":"alpine.DEB.2.21.1.1709292341280.40514@virtualbox","threadId":"46849","inReplyTo":"20170928200556.grysihlj7cbzocfq@sigill.intra.peff.net","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-09-29T21:43:57Z","receivedAt":"2017-09-29T21:44:17Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Thu, 28 Sep 2017, Jeff King wrote:\n\n> If you're planning on using an oidset to mark every object in a\n> 100-million-object monorepo, we'd probably care more. But I'd venture to\n> say that any scheme which involves generating that hash table on the fly\n> is doing it wrong. At at that scale we'd want to look at compact\n> mmap-able on-disk representations.\n\nOr maybe you would look at a *not-so-compact* mmap()able on-disk\nrepresentation, to allow for painless updates.\n\nYou really will want to avoid having to write out large files just because\na small part of them changed. We learn that lesson the hard way, from\nhaving to write 350MB worth of .git/index for every single, painful `git\nadd` operation.\n\nCiao,\nDscho\n"},{"id":"329223","messageId":"20170929225422.81467-1-jonathantanmy@google.com","threadId":"46849","inReplyTo":"20170927221910.164552-1-jonathantanmy@google.com","subject":"[PATCH v2] oidmap: map with OID as key","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-09-29T22:54:22Z","receivedAt":"2017-09-29T22:54:32Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"This is similar to using the hashmap in hashmap.c, but with an\neasier-to-use API. In particular, custom entry comparisons no longer\nneed to be written, and lookups can be done without constructing a\ntemporary entry structure.\n\nThis is implemented as a thin wrapper over the hashmap API. In\nparticular, this means that there is an additional 4-byte overhead due\nto the fact that the first 4 bytes of the hash is redundantly stored.\nFor now, I'm taking the simpler approach, but if need be, we can\nreimplement oidmap without affecting the callers significantly.\n\noidset has been updated to use oidmap.\n\nSigned-off-by: Jonathan Tan <jonathantanmy@google.com>\n---\nSome replies to v1 [1] [2] seem to indicate that simpler non-duplicated\ncode should be preferred over optimizing away the storage of the 4-byte\nhash code, and I have no objection to that, so I have updated this code\nto be a thin wrapper over hashmap with the 4-byte overhead.\n\nAfter this patch, if the 4-byte overhead is found to be too much, we can\nmigrate to something similar to v1 relatively easily.\n\nI decided not to go with the util pointer method because we will not be\nable to migrate away from it so easily if need be.\n\n[1] https://public-inbox.org/git/xmqqr2ur348z.fsf@gitster.mtv.corp.google.com/\n[2] https://public-inbox.org/git/20170929192624.4ukvpjujgiyzgibb@sigill.intra.peff.net/\n---\n Makefile     |  1 +\n fetch-pack.c |  2 +-\n oidmap.c     | 51 +++++++++++++++++++++++++++++++++++++++++++++\n oidmap.h     | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n oidset.c     | 36 +++++++-------------------------\n oidset.h     |  6 ++++--\n 6 files changed, 133 insertions(+), 31 deletions(-)\n create mode 100644 oidmap.c\n create mode 100644 oidmap.h\n\ndiff --git a/Makefile b/Makefile\nindex ed4ca438b..64136dde4 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -821,6 +821,7 @@ LIB_OBJS += notes-cache.o\n LIB_OBJS += notes-merge.o\n LIB_OBJS += notes-utils.o\n LIB_OBJS += object.o\n+LIB_OBJS += oidmap.o\n LIB_OBJS += oidset.o\n LIB_OBJS += packfile.o\n LIB_OBJS += pack-bitmap.o\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 105506e9a..008b25d3d 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -611,7 +611,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n \t * add to \"newlist\" between calls, the additions will always be for\n \t * oids that are already in the set.\n \t */\n-\tif (!tip_oids->map.tablesize) {\n+\tif (!tip_oids->map.map.tablesize) {\n \t\tadd_refs_to_oidset(tip_oids, unmatched);\n \t\tadd_refs_to_oidset(tip_oids, newlist);\n \t}\ndiff --git a/oidmap.c b/oidmap.c\nnew file mode 100644\nindex 000000000..6db4fffcd\n--- /dev/null\n+++ b/oidmap.c\n@@ -0,0 +1,51 @@\n+#include \"cache.h\"\n+#include \"oidmap.h\"\n+\n+static int cmpfn(const void *hashmap_cmp_fn_data,\n+\t\t const void *entry, const void *entry_or_key,\n+\t\t const void *keydata)\n+{\n+\tconst struct oidmap_entry *entry_ = entry;\n+\tif (keydata)\n+\t\treturn oidcmp(&entry_->oid, (const struct object_id *) keydata);\n+\treturn oidcmp(&entry_->oid,\n+\t\t      &((const struct oidmap_entry *) entry_or_key)->oid);\n+}\n+\n+static int hash(const struct object_id *oid)\n+{\n+\tint hash;\n+\tmemcpy(&hash, oid->hash, sizeof(hash));\n+\treturn hash;\n+}\n+\n+void oidmap_init(struct oidmap *map, size_t initial_size)\n+{\n+\thashmap_init(&map->map, cmpfn, NULL, initial_size);\n+}\n+\n+void oidmap_free(struct oidmap *map, int free_entries)\n+{\n+\tif (!map)\n+\t\treturn;\n+\thashmap_free(&map->map, free_entries);\n+}\n+\n+void *oidmap_get(const struct oidmap *map, const struct object_id *key)\n+{\n+\treturn hashmap_get_from_hash(&map->map, hash(key), key);\n+}\n+\n+void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n+{\n+\tstruct hashmap_entry entry;\n+\thashmap_entry_init(&entry, hash(key));\n+\treturn hashmap_remove(&map->map, &entry, key);\n+}\n+\n+void *oidmap_put(struct oidmap *map, void *entry)\n+{\n+\tstruct oidmap_entry *to_put = entry;\n+\thashmap_entry_init(&to_put->internal_entry, hash(&to_put->oid));\n+\treturn hashmap_put(&map->map, to_put);\n+}\ndiff --git a/oidmap.h b/oidmap.h\nnew file mode 100644\nindex 000000000..18f54cde1\n--- /dev/null\n+++ b/oidmap.h\n@@ -0,0 +1,68 @@\n+#ifndef OIDMAP_H\n+#define OIDMAP_H\n+\n+#include \"hashmap.h\"\n+\n+/*\n+ * struct oidmap_entry is a structure representing an entry in the hash table,\n+ * which must be used as first member of user data structures.\n+ *\n+ * Users should set the oid field. oidmap_put() will populate the\n+ * internal_entry field.\n+ */\n+struct oidmap_entry {\n+\t/* For internal use only */\n+\tstruct hashmap_entry internal_entry;\n+\n+\tstruct object_id oid;\n+};\n+\n+struct oidmap {\n+\tstruct hashmap map;\n+};\n+\n+#define OIDMAP_INIT { { NULL } }\n+\n+/*\n+ * Initializes an oidmap structure.\n+ *\n+ * `map` is the oidmap to initialize.\n+ *\n+ * If the total number of entries is known in advance, the `initial_size`\n+ * parameter may be used to preallocate a sufficiently large table and thus\n+ * prevent expensive resizing. If 0, the table is dynamically resized.\n+ */\n+extern void oidmap_init(struct oidmap *map, size_t initial_size);\n+\n+/*\n+ * Frees an oidmap structure and allocated memory.\n+ *\n+ * If `free_entries` is true, each oidmap_entry in the map is freed as well\n+ * using stdlibs free().\n+ */\n+extern void oidmap_free(struct oidmap *map, int free_entries);\n+\n+/*\n+ * Returns the oidmap entry for the specified oid, or NULL if not found.\n+ */\n+extern void *oidmap_get(const struct oidmap *map,\n+\t\t\tconst struct object_id *key);\n+\n+/*\n+ * Adds or replaces an oidmap entry.\n+ *\n+ * ((struct oidmap_entry *) entry)->internal_entry will be populated by this\n+ * function.\n+ *\n+ * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n+ */\n+extern void *oidmap_put(struct oidmap *map, void *entry);\n+\n+/*\n+ * Removes an oidmap entry matching the specified oid.\n+ *\n+ * Returns the removed entry, or NULL if not found.\n+ */\n+extern void *oidmap_remove(struct oidmap *map, const struct object_id *key);\n+\n+#endif\ndiff --git a/oidset.c b/oidset.c\nindex a6a08ba52..f1f874aaa 100644\n--- a/oidset.c\n+++ b/oidset.c\n@@ -1,50 +1,30 @@\n #include \"cache.h\"\n #include \"oidset.h\"\n \n-struct oidset_entry {\n-\tstruct hashmap_entry hash;\n-\tstruct object_id oid;\n-};\n-\n-static int oidset_hashcmp(const void *unused_cmp_data,\n-\t\t\t  const void *va, const void *vb,\n-\t\t\t  const void *vkey)\n-{\n-\tconst struct oidset_entry *a = va, *b = vb;\n-\tconst struct object_id *key = vkey;\n-\treturn oidcmp(&a->oid, key ? key : &b->oid);\n-}\n-\n int oidset_contains(const struct oidset *set, const struct object_id *oid)\n {\n-\tstruct hashmap_entry key;\n-\n-\tif (!set->map.cmpfn)\n+\tif (!set->map.map.tablesize)\n \t\treturn 0;\n-\n-\thashmap_entry_init(&key, sha1hash(oid->hash));\n-\treturn !!hashmap_get(&set->map, &key, oid);\n+\treturn !!oidmap_get(&set->map, oid);\n }\n \n int oidset_insert(struct oidset *set, const struct object_id *oid)\n {\n-\tstruct oidset_entry *entry;\n-\n-\tif (!set->map.cmpfn)\n-\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n+\tstruct oidmap_entry *entry;\n \n-\tif (oidset_contains(set, oid))\n+\tif (!set->map.map.tablesize)\n+\t\toidmap_init(&set->map, 0);\n+\telse if (oidset_contains(set, oid))\n \t\treturn 1;\n \n \tentry = xmalloc(sizeof(*entry));\n-\thashmap_entry_init(&entry->hash, sha1hash(oid->hash));\n \toidcpy(&entry->oid, oid);\n \n-\thashmap_add(&set->map, entry);\n+\toidmap_put(&set->map, entry);\n \treturn 0;\n }\n \n void oidset_clear(struct oidset *set)\n {\n-\thashmap_free(&set->map, 1);\n+\toidmap_free(&set->map, 1);\n }\ndiff --git a/oidset.h b/oidset.h\nindex b7eaab5b8..f4c9e0f9c 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -1,6 +1,8 @@\n #ifndef OIDSET_H\n #define OIDSET_H\n \n+#include \"oidmap.h\"\n+\n /**\n  * This API is similar to sha1-array, in that it maintains a set of object ids\n  * in a memory-efficient way. The major differences are:\n@@ -17,10 +19,10 @@\n  * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n  */\n struct oidset {\n-\tstruct hashmap map;\n+\tstruct oidmap map;\n };\n \n-#define OIDSET_INIT { { NULL } }\n+#define OIDSET_INIT { OIDMAP_INIT }\n \n /**\n  * Returns true iff `set` contains `oid`.\n-- \n2.14.2.822.g60be5d43e6-goog\n\n"},{"id":"329226","messageId":"20170929232412.mmimg7srkjsypg2y@sigill.intra.peff.net","threadId":"46849","inReplyTo":"alpine.DEB.2.21.1.1709292341280.40514@virtualbox","subject":"Re: [PATCH] oidmap: map with OID as key","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-29T23:24:13Z","receivedAt":"2017-09-29T23:24:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 29, 2017 at 11:43:57PM +0200, Johannes Schindelin wrote:\n\n> On Thu, 28 Sep 2017, Jeff King wrote:\n> \n> > If you're planning on using an oidset to mark every object in a\n> > 100-million-object monorepo, we'd probably care more. But I'd venture to\n> > say that any scheme which involves generating that hash table on the fly\n> > is doing it wrong. At at that scale we'd want to look at compact\n> > mmap-able on-disk representations.\n> \n> Or maybe you would look at a *not-so-compact* mmap()able on-disk\n> representation, to allow for painless updates.\n> \n> You really will want to avoid having to write out large files just because\n> a small part of them changed. We learn that lesson the hard way, from\n> having to write 350MB worth of .git/index for every single, painful `git\n> add` operation.\n\nSure. I didn't mean to start designing the format. I just mean that if\nthe first step of the process is \"read information about all 100 million\nobjects into an in-RAM hashmap\", then that is definitely not going to\nfly.\n\n-Peff\n"},{"id":"329498","messageId":"20171002234848.GG5189@google.com","threadId":"46849","inReplyTo":"20170929225422.81467-1-jonathantanmy@google.com","subject":"Re: [PATCH v2] oidmap: map with OID as key","fromName":"Brandon Williams","fromEmail":"bmwill@google.com","sentAt":"2017-10-02T23:48:48Z","receivedAt":"2017-10-02T23:48:56Z","isPatch":true,"sender":{"key":"bwilliams.eng@gmail.com","avatar":null},"body":"On 09/29, Jonathan Tan wrote:\n> This is similar to using the hashmap in hashmap.c, but with an\n> easier-to-use API. In particular, custom entry comparisons no longer\n> need to be written, and lookups can be done without constructing a\n> temporary entry structure.\n> \n> This is implemented as a thin wrapper over the hashmap API. In\n> particular, this means that there is an additional 4-byte overhead due\n> to the fact that the first 4 bytes of the hash is redundantly stored.\n> For now, I'm taking the simpler approach, but if need be, we can\n> reimplement oidmap without affecting the callers significantly.\n> \n> oidset has been updated to use oidmap.\n> \n> Signed-off-by: Jonathan Tan <jonathantanmy@google.com>\n> ---\n> Some replies to v1 [1] [2] seem to indicate that simpler non-duplicated\n> code should be preferred over optimizing away the storage of the 4-byte\n> hash code, and I have no objection to that, so I have updated this code\n> to be a thin wrapper over hashmap with the 4-byte overhead.\n> \n> After this patch, if the 4-byte overhead is found to be too much, we can\n> migrate to something similar to v1 relatively easily.\n> \n> I decided not to go with the util pointer method because we will not be\n> able to migrate away from it so easily if need be.\n\nThis makes me a bit sad because I tend to lean more towards making\nthings simpler.  I'm still a supporter of the 'util' pointer but I\nunderstand why we would choose otherwise.\n\n> \n> [1] https://public-inbox.org/git/xmqqr2ur348z.fsf@gitster.mtv.corp.google.com/\n> [2] https://public-inbox.org/git/20170929192624.4ukvpjujgiyzgibb@sigill.intra.peff.net/\n> ---\n>  Makefile     |  1 +\n>  fetch-pack.c |  2 +-\n>  oidmap.c     | 51 +++++++++++++++++++++++++++++++++++++++++++++\n>  oidmap.h     | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  oidset.c     | 36 +++++++-------------------------\n>  oidset.h     |  6 ++++--\n>  6 files changed, 133 insertions(+), 31 deletions(-)\n>  create mode 100644 oidmap.c\n>  create mode 100644 oidmap.h\n> \n> diff --git a/Makefile b/Makefile\n> index ed4ca438b..64136dde4 100644\n> --- a/Makefile\n> +++ b/Makefile\n> @@ -821,6 +821,7 @@ LIB_OBJS += notes-cache.o\n>  LIB_OBJS += notes-merge.o\n>  LIB_OBJS += notes-utils.o\n>  LIB_OBJS += object.o\n> +LIB_OBJS += oidmap.o\n>  LIB_OBJS += oidset.o\n>  LIB_OBJS += packfile.o\n>  LIB_OBJS += pack-bitmap.o\n> diff --git a/fetch-pack.c b/fetch-pack.c\n> index 105506e9a..008b25d3d 100644\n> --- a/fetch-pack.c\n> +++ b/fetch-pack.c\n> @@ -611,7 +611,7 @@ static int tip_oids_contain(struct oidset *tip_oids,\n>  \t * add to \"newlist\" between calls, the additions will always be for\n>  \t * oids that are already in the set.\n>  \t */\n> -\tif (!tip_oids->map.tablesize) {\n> +\tif (!tip_oids->map.map.tablesize) {\n>  \t\tadd_refs_to_oidset(tip_oids, unmatched);\n>  \t\tadd_refs_to_oidset(tip_oids, newlist);\n>  \t}\n> diff --git a/oidmap.c b/oidmap.c\n> new file mode 100644\n> index 000000000..6db4fffcd\n> --- /dev/null\n> +++ b/oidmap.c\n> @@ -0,0 +1,51 @@\n> +#include \"cache.h\"\n> +#include \"oidmap.h\"\n> +\n> +static int cmpfn(const void *hashmap_cmp_fn_data,\n> +\t\t const void *entry, const void *entry_or_key,\n> +\t\t const void *keydata)\n> +{\n> +\tconst struct oidmap_entry *entry_ = entry;\n> +\tif (keydata)\n> +\t\treturn oidcmp(&entry_->oid, (const struct object_id *) keydata);\n> +\treturn oidcmp(&entry_->oid,\n> +\t\t      &((const struct oidmap_entry *) entry_or_key)->oid);\n> +}\n> +\n> +static int hash(const struct object_id *oid)\n> +{\n> +\tint hash;\n> +\tmemcpy(&hash, oid->hash, sizeof(hash));\n> +\treturn hash;\n> +}\n> +\n> +void oidmap_init(struct oidmap *map, size_t initial_size)\n> +{\n> +\thashmap_init(&map->map, cmpfn, NULL, initial_size);\n> +}\n> +\n> +void oidmap_free(struct oidmap *map, int free_entries)\n> +{\n> +\tif (!map)\n> +\t\treturn;\n> +\thashmap_free(&map->map, free_entries);\n> +}\n> +\n> +void *oidmap_get(const struct oidmap *map, const struct object_id *key)\n> +{\n> +\treturn hashmap_get_from_hash(&map->map, hash(key), key);\n> +}\n> +\n> +void *oidmap_remove(struct oidmap *map, const struct object_id *key)\n> +{\n> +\tstruct hashmap_entry entry;\n> +\thashmap_entry_init(&entry, hash(key));\n> +\treturn hashmap_remove(&map->map, &entry, key);\n> +}\n> +\n> +void *oidmap_put(struct oidmap *map, void *entry)\n> +{\n> +\tstruct oidmap_entry *to_put = entry;\n> +\thashmap_entry_init(&to_put->internal_entry, hash(&to_put->oid));\n> +\treturn hashmap_put(&map->map, to_put);\n> +}\n> diff --git a/oidmap.h b/oidmap.h\n> new file mode 100644\n> index 000000000..18f54cde1\n> --- /dev/null\n> +++ b/oidmap.h\n> @@ -0,0 +1,68 @@\n> +#ifndef OIDMAP_H\n> +#define OIDMAP_H\n> +\n> +#include \"hashmap.h\"\n> +\n> +/*\n> + * struct oidmap_entry is a structure representing an entry in the hash table,\n> + * which must be used as first member of user data structures.\n> + *\n> + * Users should set the oid field. oidmap_put() will populate the\n> + * internal_entry field.\n> + */\n> +struct oidmap_entry {\n> +\t/* For internal use only */\n> +\tstruct hashmap_entry internal_entry;\n> +\n> +\tstruct object_id oid;\n> +};\n> +\n> +struct oidmap {\n> +\tstruct hashmap map;\n> +};\n> +\n> +#define OIDMAP_INIT { { NULL } }\n> +\n> +/*\n> + * Initializes an oidmap structure.\n> + *\n> + * `map` is the oidmap to initialize.\n> + *\n> + * If the total number of entries is known in advance, the `initial_size`\n> + * parameter may be used to preallocate a sufficiently large table and thus\n> + * prevent expensive resizing. If 0, the table is dynamically resized.\n> + */\n> +extern void oidmap_init(struct oidmap *map, size_t initial_size);\n> +\n> +/*\n> + * Frees an oidmap structure and allocated memory.\n> + *\n> + * If `free_entries` is true, each oidmap_entry in the map is freed as well\n> + * using stdlibs free().\n> + */\n> +extern void oidmap_free(struct oidmap *map, int free_entries);\n> +\n> +/*\n> + * Returns the oidmap entry for the specified oid, or NULL if not found.\n> + */\n> +extern void *oidmap_get(const struct oidmap *map,\n> +\t\t\tconst struct object_id *key);\n> +\n> +/*\n> + * Adds or replaces an oidmap entry.\n> + *\n> + * ((struct oidmap_entry *) entry)->internal_entry will be populated by this\n> + * function.\n> + *\n> + * Returns the replaced entry, or NULL if not found (i.e. the entry was added).\n> + */\n> +extern void *oidmap_put(struct oidmap *map, void *entry);\n> +\n> +/*\n> + * Removes an oidmap entry matching the specified oid.\n> + *\n> + * Returns the removed entry, or NULL if not found.\n> + */\n> +extern void *oidmap_remove(struct oidmap *map, const struct object_id *key);\n> +\n> +#endif\n> diff --git a/oidset.c b/oidset.c\n> index a6a08ba52..f1f874aaa 100644\n> --- a/oidset.c\n> +++ b/oidset.c\n> @@ -1,50 +1,30 @@\n>  #include \"cache.h\"\n>  #include \"oidset.h\"\n>  \n> -struct oidset_entry {\n> -\tstruct hashmap_entry hash;\n> -\tstruct object_id oid;\n> -};\n> -\n> -static int oidset_hashcmp(const void *unused_cmp_data,\n> -\t\t\t  const void *va, const void *vb,\n> -\t\t\t  const void *vkey)\n> -{\n> -\tconst struct oidset_entry *a = va, *b = vb;\n> -\tconst struct object_id *key = vkey;\n> -\treturn oidcmp(&a->oid, key ? key : &b->oid);\n> -}\n> -\n>  int oidset_contains(const struct oidset *set, const struct object_id *oid)\n>  {\n> -\tstruct hashmap_entry key;\n> -\n> -\tif (!set->map.cmpfn)\n> +\tif (!set->map.map.tablesize)\n>  \t\treturn 0;\n> -\n> -\thashmap_entry_init(&key, sha1hash(oid->hash));\n> -\treturn !!hashmap_get(&set->map, &key, oid);\n> +\treturn !!oidmap_get(&set->map, oid);\n>  }\n>  \n>  int oidset_insert(struct oidset *set, const struct object_id *oid)\n>  {\n> -\tstruct oidset_entry *entry;\n> -\n> -\tif (!set->map.cmpfn)\n> -\t\thashmap_init(&set->map, oidset_hashcmp, NULL, 0);\n> +\tstruct oidmap_entry *entry;\n>  \n> -\tif (oidset_contains(set, oid))\n> +\tif (!set->map.map.tablesize)\n> +\t\toidmap_init(&set->map, 0);\n> +\telse if (oidset_contains(set, oid))\n>  \t\treturn 1;\n>  \n>  \tentry = xmalloc(sizeof(*entry));\n> -\thashmap_entry_init(&entry->hash, sha1hash(oid->hash));\n>  \toidcpy(&entry->oid, oid);\n>  \n> -\thashmap_add(&set->map, entry);\n> +\toidmap_put(&set->map, entry);\n>  \treturn 0;\n>  }\n>  \n>  void oidset_clear(struct oidset *set)\n>  {\n> -\thashmap_free(&set->map, 1);\n> +\toidmap_free(&set->map, 1);\n>  }\n> diff --git a/oidset.h b/oidset.h\n> index b7eaab5b8..f4c9e0f9c 100644\n> --- a/oidset.h\n> +++ b/oidset.h\n> @@ -1,6 +1,8 @@\n>  #ifndef OIDSET_H\n>  #define OIDSET_H\n>  \n> +#include \"oidmap.h\"\n> +\n>  /**\n>   * This API is similar to sha1-array, in that it maintains a set of object ids\n>   * in a memory-efficient way. The major differences are:\n> @@ -17,10 +19,10 @@\n>   * A single oidset; should be zero-initialized (or use OIDSET_INIT).\n>   */\n>  struct oidset {\n> -\tstruct hashmap map;\n> +\tstruct oidmap map;\n>  };\n>  \n> -#define OIDSET_INIT { { NULL } }\n> +#define OIDSET_INIT { OIDMAP_INIT }\n>  \n>  /**\n>   * Returns true iff `set` contains `oid`.\n> -- \n> 2.14.2.822.g60be5d43e6-goog\n> \n\n-- \nBrandon Williams\n"},{"id":"329532","messageId":"20171003063119.iht5kl7zsiuxpaqz@sigill.intra.peff.net","threadId":"46849","inReplyTo":"20171002234848.GG5189@google.com","subject":"Re: [PATCH v2] oidmap: map with OID as key","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-03T06:31:19Z","receivedAt":"2017-10-03T06:31:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 02, 2017 at 04:48:48PM -0700, Brandon Williams wrote:\n\n> > Some replies to v1 [1] [2] seem to indicate that simpler non-duplicated\n> > code should be preferred over optimizing away the storage of the 4-byte\n> > hash code, and I have no objection to that, so I have updated this code\n> > to be a thin wrapper over hashmap with the 4-byte overhead.\n> > \n> > After this patch, if the 4-byte overhead is found to be too much, we can\n> > migrate to something similar to v1 relatively easily.\n> > \n> > I decided not to go with the util pointer method because we will not be\n> > able to migrate away from it so easily if need be.\n> \n> This makes me a bit sad because I tend to lean more towards making\n> things simpler.  I'm still a supporter of the 'util' pointer but I\n> understand why we would choose otherwise.\n\nRight, I kind of wonder if this has fallen into an uncanny value where\nwe have this almost-hashmap infrastructure, but the end result is not\nsignificantly easier to use than a plain-old hashmap.\n\nI.e., it looks like you still have to declare something like:\n\n  struct my_data {\n        struct oidmap_entry oid;\n\tint value; /* mapping to an int */\n  };\n\nand handle the allocation of the entry yourself. If we instead just\nadding an oidhash() and oidcmpfn(), then callers could those directly.\n\nThe invocations are a _little_ longer with a raw hashmap, but not much\n(as you can see from the actual oidmap implementation, and the changes\nto oidset).\n\nI dunno. I'm not against it per se. The API _is_ a little nicer, but I\njust wonder if there's a downside to even the thin wrapper, in that\ncallers are no longer free to use other parts of the hashmap API. If I\nsaw some converted callers I might be more convinced.\n\n-Peff\n"},{"id":"329628","messageId":"CAGf8dgKtwdT912CaARdjYnSAd2m7mmdOzM=OGCUupw80snrd_w@mail.gmail.com","threadId":"46849","inReplyTo":"20171003063119.iht5kl7zsiuxpaqz@sigill.intra.peff.net","subject":"Re: [PATCH v2] oidmap: map with OID as key","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-10-04T00:29:01Z","receivedAt":"2017-10-04T00:29:32Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, Oct 2, 2017 at 11:31 PM, Jeff King <peff@peff.net> wrote:\n> Right, I kind of wonder if this has fallen into an uncanny value where\n> we have this almost-hashmap infrastructure, but the end result is not\n> significantly easier to use than a plain-old hashmap.\n>\n> I.e., it looks like you still have to declare something like:\n>\n>   struct my_data {\n>         struct oidmap_entry oid;\n>         int value; /* mapping to an int */\n>   };\n>\n> and handle the allocation of the entry yourself. If we instead just\n> adding an oidhash() and oidcmpfn(), then callers could those directly.\n\nI thought of something like that, but it seems that you have to\nremember quite a few things:\n- your entry must have \"struct oidmap_entry\" at the start, not \"struct\nhashmap_entry\"\n- initialize your hashmap with oidcmpfn()\n- when getting, hashmap_get_from_hash(map, oidhash(&oid), &oid) (and\noid might be longer e.g. ref->old_oid)\n\n> The invocations are a _little_ longer with a raw hashmap, but not much\n> (as you can see from the actual oidmap implementation, and the changes\n> to oidset).\n\nAbout the invocation of hashmap_get_from_hash(), I felt that it would\nget annoying quickly enough that I would want an oidmap_get(const\nstruct hashmap *, const struct object_id *) but it might be strange\nthat the \"get\" method is named differently from the rest. If we\ntolerate oidmap_get(), and tolerate the fact that the user must both\ndeclare \"struct oidmap_entry\" instead of \"struct hashmap_entry\" and\ninitialize the hashmap with oidcmpfn() (so that the invocation to\nhashmap_get_from_hash() within oidmap_get() sends the correct\nkeydata), we can avoid the thin wrapper issue where callers can no\nlonger use other methods of hashmap. At this point I decided that I\nprefer the thin wrapper, but the \"light touch\" (struct oidmap_entry,\noidcmpfn(), oidmap_get() only) still better than the status quo.\n"},{"id":"329662","messageId":"20171004074547.56ks2efcr7cbldbq@sigill.intra.peff.net","threadId":"46849","inReplyTo":"CAGf8dgKtwdT912CaARdjYnSAd2m7mmdOzM=OGCUupw80snrd_w@mail.gmail.com","subject":"Re: [PATCH v2] oidmap: map with OID as key","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-04T07:45:48Z","receivedAt":"2017-10-04T07:46:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 03, 2017 at 05:29:01PM -0700, Jonathan Tan wrote:\n\n> At this point I decided that I prefer the thin wrapper, but the \"light\n> touch\" (struct oidmap_entry, oidcmpfn(), oidmap_get() only) still\n> better than the status quo.\n\nOK. I can certainly live with that. And worst case, I suppose, is that a\ncaller wants some underlying hashmap function and we just have to extend\nthe oidmap API to include it. It's not like we're adding new hashmap\nfunctions willy-nilly.\n\n-Peff\n"},{"id":"329669","messageId":"xmqqmv57b8or.fsf@gitster.mtv.corp.google.com","threadId":"46849","inReplyTo":"20171004074547.56ks2efcr7cbldbq@sigill.intra.peff.net","subject":"Re: [PATCH v2] oidmap: map with OID as key","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-04T08:48:04Z","receivedAt":"2017-10-04T08:48:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Tue, Oct 03, 2017 at 05:29:01PM -0700, Jonathan Tan wrote:\n>\n>> At this point I decided that I prefer the thin wrapper, but the \"light\n>> touch\" (struct oidmap_entry, oidcmpfn(), oidmap_get() only) still\n>> better than the status quo.\n>\n> OK. I can certainly live with that. And worst case, I suppose, is that a\n> caller wants some underlying hashmap function and we just have to extend\n> the oidmap API to include it. It's not like we're adding new hashmap\n> functions willy-nilly.\n\nOK, I think I can live with that, too.  I'll tentatively mark the\ntopic to be merged to 'next' but give it for a few days so that\nothers can stop me.\n\nThanks.\n"}]}