{"thread":{"id":"4722","subject":"git object hash cleanups","startedAt":"2006-06-30T18:20:33Z","lastAt":"2006-06-30T18:20:33Z","messageCount":1,"participants":["Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22941","messageId":"Pine.LNX.4.64.0606301108440.12404@g5.osdl.org","threadId":"4722","inReplyTo":null,"subject":"git object hash cleanups","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-30T18:20:33Z","receivedAt":"2006-06-30T18:20:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis IMNSHO cleans up the object hashing.\n\nThe hash expansion is separated out into a function of its own, the hash \narray (and size) names are made more obvious, and the code is generally \nmade to look a bit more like the object-ref hashing.\n\nIt also gets rid of \"find_object()\" returning an index (or negative \nposition if no object is found), since that is made redundant by the \nsimplified object rehashing. The basic operation is now \"lookup_object()\" \nwhich just returns the object itself.\n\nThere's an almost unmeasurable speed increase, but more importantly, I \nthink the end result is more readable.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\nI tried to be really careful, and this should all be good, but I'm still \nembarrassed about my hash insertion bug in object-refs.c, so people should \ndouble- and triple-check this.\n\ndiff --git a/object.c b/object.c\nindex 31c77ea..37277f9 100644\n--- a/object.c\n+++ b/object.c\n@@ -5,88 +5,97 @@ #include \"tree.h\"\n #include \"commit.h\"\n #include \"tag.h\"\n \n-static struct object **objs;\n-static int nr_objs, obj_allocs;\n+static struct object **obj_hash;\n+static int nr_objs, obj_hash_size;\n \n unsigned int get_max_object_index(void)\n {\n-\treturn obj_allocs;\n+\treturn obj_hash_size;\n }\n \n struct object *get_indexed_object(unsigned int idx)\n {\n-\treturn objs[idx];\n+\treturn obj_hash[idx];\n }\n \n const char *type_names[] = {\n \t\"none\", \"blob\", \"tree\", \"commit\", \"bad\"\n };\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_obj_hash(struct object *obj, struct object **hash, unsigned int size)\n+{\n+\tint j = hash_obj(obj, size);\n+\n+\twhile (hash[j]) {\n+\t\tj++;\n+\t\tif (j >= size)\n+\t\t\tj = 0;\n+\t}\n+\thash[j] = obj;\n+}\n+\n static int hashtable_index(const unsigned char *sha1)\n {\n \tunsigned int i;\n \tmemcpy(&i, sha1, sizeof(unsigned int));\n-\treturn (int)(i % obj_allocs);\n+\treturn (int)(i % obj_hash_size);\n }\n \n-static int find_object(const unsigned char *sha1)\n+struct object *lookup_object(const unsigned char *sha1)\n {\n \tint i;\n+\tstruct object *obj;\n \n-\tif (!objs)\n-\t\treturn -1;\n+\tif (!obj_hash)\n+\t\treturn NULL;\n \n \ti = hashtable_index(sha1);\n-\twhile (objs[i]) {\n-\t\tif (memcmp(sha1, objs[i]->sha1, 20) == 0)\n-\t\t\treturn i;\n+\twhile ((obj = obj_hash[i]) != NULL) {\n+\t\tif (!memcmp(sha1, obj->sha1, 20))\n+\t\t\tbreak;\n \t\ti++;\n-\t\tif (i == obj_allocs)\n+\t\tif (i == obj_hash_size)\n \t\t\ti = 0;\n \t}\n-\treturn -1 - i;\n+\treturn obj;\n }\n \n-struct object *lookup_object(const unsigned char *sha1)\n+static void grow_object_hash(void)\n {\n-\tint pos = find_object(sha1);\n-\tif (pos >= 0)\n-\t\treturn objs[pos];\n-\treturn NULL;\n+\tint i;\n+\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n+\tstruct object **new_hash;\n+\n+\tnew_hash = calloc(new_hash_size, sizeof(struct object *));\n+\tfor (i = 0; i < obj_hash_size; i++) {\n+\t\tstruct object *obj = obj_hash[i];\n+\t\tif (!obj)\n+\t\t\tcontinue;\n+\t\tinsert_obj_hash(obj, new_hash, new_hash_size);\n+\t}\n+\tfree(obj_hash);\n+\tobj_hash = new_hash;\n+\tobj_hash_size = new_hash_size;\n }\n \n void created_object(const unsigned char *sha1, struct object *obj)\n {\n-\tint pos;\n-\n \tobj->parsed = 0;\n-\tmemcpy(obj->sha1, sha1, 20);\n-\tobj->type = TYPE_NONE;\n \tobj->used = 0;\n+\tobj->type = TYPE_NONE;\n+\tobj->flags = 0;\n+\tmemcpy(obj->sha1, sha1, 20);\n \n-\tif (obj_allocs - 1 <= nr_objs * 2) {\n-\t\tint i, count = obj_allocs;\n-\t\tobj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs);\n-\t\tobjs = xrealloc(objs, obj_allocs * sizeof(struct object *));\n-\t\tmemset(objs + count, 0, (obj_allocs - count)\n-\t\t\t\t* sizeof(struct object *));\n-\t\tfor (i = 0; i < obj_allocs; i++)\n-\t\t\tif (objs[i]) {\n-\t\t\t\tint j = find_object(objs[i]->sha1);\n-\t\t\t\tif (j != i) {\n-\t\t\t\t\tj = -1 - j;\n-\t\t\t\t\tobjs[j] = objs[i];\n-\t\t\t\t\tobjs[i] = NULL;\n-\t\t\t\t}\n-\t\t\t}\n-\t}\n-\n-\tpos = find_object(sha1);\n-\tif (pos >= 0)\n-\t\tdie(\"Inserting %s twice\\n\", sha1_to_hex(sha1));\n-\tpos = -pos-1;\n+\tif (obj_hash_size - 1 <= nr_objs * 2)\n+\t\tgrow_object_hash();\n \n-\tobjs[pos] = obj;\n+\tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n \tnr_objs++;\n }\n \n"}]}