{"thread":{"id":"6858","subject":"[PATCH 1/2] Add `struct object_hash`","startedAt":"2007-02-17T17:38:50Z","lastAt":"2007-02-18T16:48:50Z","messageCount":4,"participants":["Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"34874","messageId":"Pine.LNX.4.63.0702171838150.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6858","inReplyTo":null,"subject":"[PATCH 1/2] Add `struct object_hash`","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-02-17T17:38:50Z","receivedAt":"2007-02-17T17:38:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nUsing object_hash, you can store interesting information about\nobjects in a private hash map. This makes up for the lack of a\n`util` member of `struct object`.\n\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n\n\tWe should have done that earlier. Now, git.git already\n\tcontains two specialised versions of an object hash map:\n\tobj_hash and refs_hash.\n\n\tobj_hash is not really a hash map, but rather a hash set,\n\tbut there is no excuse for refs_hash having its own little\n\tprivate implementation nobody else can reuse.\n\n Makefile      |    2 +-\n object-hash.c |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n object-hash.h |   19 ++++++++++++++++\n 3 files changed, 87 insertions(+), 1 deletions(-)\n create mode 100644 object-hash.c\n create mode 100644 object-hash.h\n\ndiff --git a/Makefile b/Makefile\nindex dfe226f..e53a5ad 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -267,7 +267,7 @@ LIB_OBJS = \\\n \twrite_or_die.o trace.o list-objects.o grep.o \\\n \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \\\n \tcolor.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o \\\n-\tconvert.o\n+\tconvert.o object-hash.o\n \n BUILTIN_OBJS = \\\n \tbuiltin-add.o \\\ndiff --git a/object-hash.c b/object-hash.c\nnew file mode 100644\nindex 0000000..2295e33\n--- /dev/null\n+++ b/object-hash.c\n@@ -0,0 +1,67 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"object-hash.h\"\n+\n+static unsigned int hash_obj(struct object *obj, unsigned int n)\n+{\n+\tunsigned int hash = *(unsigned int *)obj->sha1;\n+\treturn hash % n;\n+}\n+\n+static void insert_object_into_hash(struct object *object, void *util,\n+\t\tstruct object_hash *hash)\n+{\n+\tint j = hash_obj(object, hash->size);\n+\n+\twhile (hash->hash[j].object) {\n+\t\tj++;\n+\t\tif (j >= hash->size)\n+\t\t\tj = 0;\n+\t}\n+\thash->hash[j].object = object;\n+\thash->hash[j].util = util;\n+}\n+\n+static void grow_object_hash(struct object_hash *hash)\n+{\n+\tstruct object_hash_entry *old_hash = hash->hash;\n+\tint new_size = (hash->size + 1000) * 3 / 2, i;\n+\n+\thash->hash = xcalloc(sizeof(struct object_hash_entry), new_size);\n+\tfor (i = 0; i < hash->size; i++) {\n+\t\tstruct object_hash_entry *entry = old_hash + i;\n+\t\tif (!entry->object)\n+\t\t\tcontinue;\n+\t\tinsert_object_into_hash(entry->object, entry->util, hash);\n+\t}\n+\thash->size = new_size;\n+\tfree(old_hash);\n+}\n+\n+void add_object_to_hash(struct object *obj, void *util,\n+\t\tstruct object_hash *hash)\n+{\n+\tif (++hash->nr > hash->size * 2 / 3)\n+\t\tgrow_object_hash(hash);\n+\tinsert_object_into_hash(obj, util, hash);\n+}\n+\n+void *lookup_object_in_hash(struct object *obj, struct object_hash *hash)\n+{\n+\tint j;\n+\n+\t/* nothing to lookup */\n+\tif (!hash->size)\n+\t\treturn NULL;\n+\tj = hash_obj(obj, hash->size);\n+\twhile (hash->hash[j].object) {\n+\t\tif (hash->hash[j].object == obj)\n+\t\t\treturn hash->hash[j].util;\n+\t\tj++;\n+\t\tif (j >= hash->size)\n+\t\t\tj = 0;\n+\t}\n+\treturn NULL;\n+}\n+\n+\ndiff --git a/object-hash.h b/object-hash.h\nnew file mode 100644\nindex 0000000..0da7824\n--- /dev/null\n+++ b/object-hash.h\n@@ -0,0 +1,19 @@\n+#ifndef OBJECT_HASH_H\n+#define OBJECT_HASH_H\n+\n+struct object_hash_entry {\n+\tstruct object *object;\n+\tvoid *util;\n+};\n+\n+struct object_hash {\n+\tunsigned int size, nr;\n+\tstruct object_hash_entry *hash;\n+};\n+\n+extern void add_object_to_hash(struct object *obj, void *util,\n+\t\tstruct object_hash *hash);\n+extern void *lookup_object_in_hash(struct object *obj,\n+\t\tstruct object_hash *hash);\n+\n+#endif\n-- \n1.5.0.2139.gdafc9-dirty\n"},{"id":"34942","messageId":"7vtzxjj24j.fsf@assigned-by-dhcp.cox.net","threadId":"6858","inReplyTo":"Pine.LNX.4.63.0702171838150.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH 1/2] Add `struct object_hash`","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-18T08:34:04Z","receivedAt":"2007-02-18T08:34:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> Using object_hash, you can store interesting information about\n> objects in a private hash map. This makes up for the lack of a\n> `util` member of `struct object`.\n>\n> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> ---\n>\n> \tWe should have done that earlier. Now, git.git already\n> \tcontains two specialised versions of an object hash map:\n> \tobj_hash and refs_hash.\n>\n> \tobj_hash is not really a hash map, but rather a hash set,\n> \tbut there is no excuse for refs_hash having its own little\n> \tprivate implementation nobody else can reuse.\n\nOk, having now looked at it more, I can say:\n\n - I hate it.\n\nI dislike it intensely, because it's so _close_ to being usable.\nFor one thing, I do not like that the patch was not accompanied\nwith rewrite of object-refs.c using this new facility.\n\nAnd I kind of know why.  You would end up making obj_refs quite\nmore expensive by doing so if you use two-pointer hash_entry\nthat points at a separate structure (and you would want the hash\ntable not too full, which means you would waste at least twice\nas much memory for growing room for the hashtable, plus malloc\noverhead for the separate flexible array of refs), and obj_refs\nis something we would really want to keep its memory footprint\nto the bare minimum, because nowhere else in git we keep\ninformation on potentially thousands of objects.  I suspect that\nit would have been bit more palatable if object_hash_entry were\na flex structure type like object_refs.\n\n> +static void grow_object_hash(struct object_hash *hash)\n> +{\n> +\tstruct object_hash_entry *old_hash = hash->hash;\n> +\tint new_size = (hash->size + 1000) * 3 / 2, i;\n> +\n> +\thash->hash = xcalloc(sizeof(struct object_hash_entry), new_size);\n> +\tfor (i = 0; i < hash->size; i++) {\n> +\t\tstruct object_hash_entry *entry = old_hash + i;\n> +\t\tif (!entry->object)\n> +\t\t\tcontinue;\n> +\t\tinsert_object_into_hash(entry->object, entry->util, hash);\n> +\t}\n> +\thash->size = new_size;\n> +\tfree(old_hash);\n> +}\n\nIsn't this broken?  You still have old hash size in hash->size\ninside loop, which is given to insert_object_info_hash(), so the\nrehashing will use the old (smaller) hash size to compute the\nnew location for the entry.  You want to keep old_size in a\nvariable to control the loop termination, update hash->size with\nnew_size at the same time you update hash->hash with the new\nempty array, and walk the old array by hand, rehashing the\nexisting entries into new hashtable.\n\nHere is a suggested replacement; patch is applicable on top of\nv1.5.0 (or master).\n\n-- >8 --\nFrom: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n\nAdd `struct object_hash`\n\nUsing object_hash, you can store interesting information about\nobjects in a private hash map.  The earlier object-refs API is\nnow built on top of this generalized facility\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n Makefile      |    3 +-\n object-hash.c |   64 +++++++++++++++++++++++++++++++++++++++++++++++++++\n object-refs.c |   71 ++++-----------------------------------------------------\n object.h      |   19 ++++++++++++++-\n 4 files changed, 89 insertions(+), 68 deletions(-)\n create mode 100644 object-hash.c\n\ndiff --git a/Makefile b/Makefile\nindex 40bdcff..0b0a926 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -262,7 +262,8 @@ LIB_OBJS = \\\n \trevision.o pager.o tree-walk.o xdiff-interface.o \\\n \twrite_or_die.o trace.o list-objects.o grep.o \\\n \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \\\n-\tcolor.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o\n+\tcolor.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o \\\n+\tobject-hash.o\n \n BUILTIN_OBJS = \\\n \tbuiltin-add.o \\\ndiff --git a/object-hash.c b/object-hash.c\nnew file mode 100644\nindex 0000000..8e16e0e\n--- /dev/null\n+++ b/object-hash.c\n@@ -0,0 +1,64 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+\n+static unsigned int hash_obj(struct object *obj, unsigned int n)\n+{\n+\tunsigned int hash = *(unsigned int *)obj->sha1;\n+\treturn hash % n;\n+}\n+\n+static void insert_object_into_hash(struct object_hash_entry *ent, struct object_hash *hash)\n+{\n+\tint j = hash_obj(ent->object, hash->size);\n+\n+\twhile (hash->hash[j]) {\n+\t\tj++;\n+\t\tif (j >= hash->size)\n+\t\t\tj = 0;\n+\t}\n+\thash->hash[j] = ent;\n+}\n+\n+static void grow_object_hash(struct object_hash *hash)\n+{\n+\tstruct object_hash_entry **old_hash = hash->hash;\n+\tint i;\n+\tint old_size = hash->size;\n+\tint new_size = (old_size + 1000) * 3 / 2;\n+\n+\thash->hash = xcalloc(new_size, sizeof(struct object_hash_entry *));\n+\thash->size = new_size;\n+\tfor (i = 0; i < old_size; i++) {\n+\t\tstruct object_hash_entry *entry = old_hash[i];\n+\t\tif (!entry)\n+\t\t\tcontinue;\n+\t\tinsert_object_into_hash(entry, hash);\n+\t}\n+\tfree(old_hash);\n+}\n+\n+void add_object_to_hash(struct object_hash_entry *ent, struct object_hash *hash)\n+{\n+\tif (++hash->nr > hash->size * 2 / 3)\n+\t\tgrow_object_hash(hash);\n+\tinsert_object_into_hash(ent, hash);\n+}\n+\n+struct object_hash_entry *lookup_object_in_hash(struct object *obj, struct object_hash *hash)\n+{\n+\tstruct object_hash_entry *ent;\n+\tint j;\n+\n+\t/* nothing to lookup */\n+\tif (!hash->size)\n+\t\treturn NULL;\n+\tj = hash_obj(obj, hash->size);\n+\twhile ((ent = hash->hash[j]) != NULL) {\n+\t\tif (ent->object == obj)\n+\t\t\tbreak;\n+\t\tj++;\n+\t\tif (j >= hash->size)\n+\t\t\tj = 0;\n+\t}\n+\treturn ent;\n+}\ndiff --git a/object-refs.c b/object-refs.c\nindex 98ea100..022b5ca 100644\n--- a/object-refs.c\n+++ b/object-refs.c\n@@ -3,73 +3,11 @@\n \n int track_object_refs = 0;\n \n-static unsigned int refs_hash_size, nr_object_refs;\n-static struct object_refs **refs_hash;\n-\n-static unsigned int hash_obj(struct object *obj, unsigned int n)\n-{\n-\tunsigned int hash = *(unsigned int *)obj->sha1;\n-\treturn hash % n;\n-}\n-\n-static void insert_ref_hash(struct object_refs *ref, struct object_refs **hash, unsigned int size)\n-{\n-\tint j = hash_obj(ref->base, size);\n-\n-\twhile (hash[j]) {\n-\t\tj++;\n-\t\tif (j >= size)\n-\t\t\tj = 0;\n-\t}\n-\thash[j] = ref;\n-}\n-\n-static void grow_refs_hash(void)\n-{\n-\tint i;\n-\tint new_hash_size = (refs_hash_size + 1000) * 3 / 2;\n-\tstruct object_refs **new_hash;\n-\n-\tnew_hash = xcalloc(new_hash_size, sizeof(struct object_refs *));\n-\tfor (i = 0; i < refs_hash_size; i++) {\n-\t\tstruct object_refs *ref = refs_hash[i];\n-\t\tif (!ref)\n-\t\t\tcontinue;\n-\t\tinsert_ref_hash(ref, new_hash, new_hash_size);\n-\t}\n-\tfree(refs_hash);\n-\trefs_hash = new_hash;\n-\trefs_hash_size = new_hash_size;\n-}\n-\n-static void add_object_refs(struct object *obj, struct object_refs *ref)\n-{\n-\tint nr = nr_object_refs + 1;\n-\n-\tif (nr > refs_hash_size * 2 / 3)\n-\t\tgrow_refs_hash();\n-\tref->base = obj;\n-\tinsert_ref_hash(ref, refs_hash, refs_hash_size);\n-\tnr_object_refs = nr;\n-}\n+static struct object_hash refs_hash;\n \n struct object_refs *lookup_object_refs(struct object *obj)\n {\n-\tstruct object_refs *ref;\n-\tint j;\n-\n-\t/* nothing to lookup */\n-\tif (!refs_hash_size)\n-\t\treturn NULL;\n-\tj = hash_obj(obj, refs_hash_size);\n-\twhile ((ref = refs_hash[j]) != NULL) {\n-\t\tif (ref->base == obj)\n-\t\t\tbreak;\n-\t\tj++;\n-\t\tif (j >= refs_hash_size)\n-\t\t\tj = 0;\n-\t}\n-\treturn ref;\n+\treturn (struct object_refs *)lookup_object_in_hash(obj, &refs_hash);\n }\n \n struct object_refs *alloc_object_refs(unsigned count)\n@@ -120,7 +58,8 @@ void set_object_refs(struct object *obj, struct object_refs *refs)\n \n \tfor (i = 0; i < refs->count; i++)\n \t\trefs->ref[i]->used = 1;\n-\tadd_object_refs(obj, refs);\n+\trefs->base = obj;\n+\tadd_object_to_hash((struct object_hash_entry *)refs, &refs_hash);\n }\n \n void mark_reachable(struct object *obj, unsigned int mask)\n@@ -133,7 +72,7 @@ void mark_reachable(struct object *obj, unsigned int mask)\n \tif (obj->flags & mask)\n \t\treturn;\n \tobj->flags |= mask;\n-\trefs = lookup_object_refs(obj);\n+\trefs = (struct object_refs *)lookup_object_in_hash(obj, &refs_hash);\n \tif (refs) {\n \t\tunsigned i;\n \t\tfor (i = 0; i < refs->count; i++)\ndiff --git a/object.h b/object.h\nindex caee733..c417cf2 100644\n--- a/object.h\n+++ b/object.h\n@@ -7,11 +7,28 @@ struct object_list {\n };\n \n struct object_refs {\n-\tunsigned count;\n \tstruct object *base;\n+\tunsigned count;\n \tstruct object *ref[FLEX_ARRAY]; /* more */\n };\n \n+/*\n+ * This is a \"shell\" type that represents the actual structure you\n+ * would place in object_hash.  The user would cast up the pointer to\n+ * object_hash_entry to a more concrete type, such as object_refs.\n+ */\n+struct object_hash_entry {\n+\tstruct object *object;\n+};\n+\n+struct object_hash {\n+\tunsigned int size, nr;\n+\tstruct object_hash_entry **hash;\n+};\n+\n+void add_object_to_hash(struct object_hash_entry *, struct object_hash *);\n+struct object_hash_entry *lookup_object_in_hash(struct object *, struct object_hash *);\n+\n struct object_array {\n \tunsigned int nr;\n \tunsigned int alloc;\n"},{"id":"34953","messageId":"Pine.LNX.4.63.0702181241090.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6858","inReplyTo":"7vtzxjj24j.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 1/2] Add `struct object_hash`","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-02-18T11:43:06Z","receivedAt":"2007-02-18T11:43:06Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 18 Feb 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > Using object_hash, you can store interesting information about\n> > objects in a private hash map. This makes up for the lack of a\n> > `util` member of `struct object`.\n> >\n> > Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> > ---\n> >\n> > \tWe should have done that earlier. Now, git.git already\n> > \tcontains two specialised versions of an object hash map:\n> > \tobj_hash and refs_hash.\n> >\n> > \tobj_hash is not really a hash map, but rather a hash set,\n> > \tbut there is no excuse for refs_hash having its own little\n> > \tprivate implementation nobody else can reuse.\n> \n> Ok, having now looked at it more, I can say:\n> \n>  - I hate it.\n> \n> I dislike it intensely, because it's so _close_ to being usable.\n\nSeeing your patch I know why. I could not think of a sane method to \ncondense the two pointers into one. Thank you for pointing out one.\n\nI have not had a close look at it, that will have to wait for tomorrow.\n\nCiao,\nDscho\n"},{"id":"34958","messageId":"Pine.LNX.4.63.0702181740100.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6858","inReplyTo":"7vtzxjj24j.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 1/2] Add `struct object_hash`","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-02-18T16:48:50Z","receivedAt":"2007-02-18T16:48:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nThese are only minor nits, as I think your code is bug free.\n\nOn Sun, 18 Feb 2007, Junio C Hamano wrote:\n\n> +static void insert_object_into_hash(struct object_hash_entry *ent, struct object_hash *hash)\n\nI'd rather _not_ name it \"ent\", as that has a different meaning already.\n\nAlso, what is your preferred width? Your line is way longer than 80 \ncolumns.\n\n> +static void grow_object_hash(struct object_hash *hash)\n> +{\n> +\tstruct object_hash_entry **old_hash = hash->hash;\n> +\tint i;\n> +\tint old_size = hash->size;\n> +\tint new_size = (old_size + 1000) * 3 / 2;\n> +\n> +\thash->hash = xcalloc(new_size, sizeof(struct object_hash_entry *));\n> +\thash->size = new_size;\n\nEither have a \"new_hash\" variable, or get rid of \"new_size\".\n\nBTW I just tried to convert obj_hash to this interface, and it seems that \nthere really is no elegant way (without wasting memory; You could do it, \nbut then you'd have _two_ pointers for each object: one to the \nobject_hash_entry, and from _that_ to the object). Maybe you have a clever \nway to solve this?\n\nCiao,\nDscho\n"}]}