{"thread":{"id":"14365","subject":"[PATCH 2/3] cached-sha1-map: refactoring hash traversal code","startedAt":"2008-07-09T03:56:06Z","lastAt":"2008-07-09T05:27:46Z","messageCount":2,"participants":["Geoffrey Irving","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"82674","messageId":"7f9d599f0807082056o666fced9nf87cc81447e16e05@mail.gmail.com","threadId":"14365","inReplyTo":null,"subject":"[PATCH 2/3] cached-sha1-map: refactoring hash traversal code","fromName":"Geoffrey Irving","fromEmail":"irving@naml.us","sentAt":"2008-07-09T03:56:06Z","receivedAt":"2008-07-09T03:56:06Z","isPatch":true,"sender":{"key":"irving@naml.us","avatar":"https://gravatar.com/avatar/52d7452fcd134aac0fa12f57a3bb7ef5f3f7e73ca0ab36736d06c6a6132de718?d=mp&s=160"},"body":">From c4e60c28fe66985ac8224da832589c982010744e Mon Sep 17 00:00:00 2001\nFrom: Geoffrey Irving <irving@naml.us>\nDate: Tue, 8 Jul 2008 19:47:22 -0700\nSubject: [PATCH 2/3] cached-sha1-map: refactoring hash traversal code\n\nPulling common code from get_cached_sha1_entry and set_cached_sha1_entry\ninto static find_helper function.\n---\n cached-sha1-map.c |   68 +++++++++++++++++++++++++++++-----------------------\n 1 files changed, 38 insertions(+), 30 deletions(-)\n\ndiff --git a/cached-sha1-map.c b/cached-sha1-map.c\nindex e363745..147c7a2 100644\n--- a/cached-sha1-map.c\n+++ b/cached-sha1-map.c\n@@ -129,10 +129,14 @@ static size_t get_hash_index(const unsigned char *sha1)\n \treturn ntohl(*(size_t*)sha1);\n }\n\n-int get_cached_sha1_entry(struct cached_sha1_map *cache,\n-\tconst unsigned char *key, unsigned char *value)\n+/*\n+ * Returns the index if the entry exists, and the complemented index of\n+ * the next free entry otherwise.\n+ */\n+static long find_helper(struct cached_sha1_map *cache,\n+\tconst unsigned char *key)\n {\n-\tsize_t i, mask;\n+\tlong i, mask;\n\n \tif (!cache->initialized)\n \t\tinit_cached_sha1_map(cache);\n@@ -140,43 +144,47 @@ int get_cached_sha1_entry(struct cached_sha1_map *cache,\n \tmask = cache->size - 1;\n\n \tfor (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {\n-\t\tif (!hashcmp(key, cache->entries[i].key)) {\n-\t\t\thashcpy(value, cache->entries[i].value);\n-\t\t\treturn 0;\n-\t\t} else if (is_null_sha1(cache->entries[i].key))\n-\t\t\treturn -1;\n+\t\tif (!hashcmp(key, cache->entries[i].key))\n+\t\t\treturn i;\n+\t\telse if (is_null_sha1(cache->entries[i].key))\n+\t\t\treturn ~i;\n \t}\n }\n\n+int get_cached_sha1_entry(struct cached_sha1_map *cache,\n+\tconst unsigned char *key, unsigned char *value)\n+{\n+\tlong i = find_helper(cache, key);\n+\tif(i < 0)\n+\t\treturn -1;\n+\n+\t/* entry found, return value */\n+\thashcpy(value, cache->entries[i].value);\n+\treturn 0;\n+}\n+\n void set_cached_sha1_entry(struct cached_sha1_map *cache,\n \tconst unsigned char *key, const unsigned char *value)\n {\n-\tsize_t i, mask;\n+\tlong i;\n \tstruct cached_sha1_entry *entry;\n\n-\tif (!cache->initialized)\n-\t\tinit_cached_sha1_map(cache);\n-\n-\tif (4*cache->count >= 3*cache->size)\n-\t\tgrow_map(cache);\n-\n-\tmask = cache->size - 1;\n-\n-\tfor (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {\n-\t\tentry = cache->entries+i;\n-\n-\t\tif (is_null_sha1(entry->key)) {\n-\t\t\thashcpy(entry->key, key);\n+\ti = find_helper(cache, key);\n+\n+\tif (i < 0) { /* write new entry */\n+\t\tentry = cache->entries + ~i;\n+\t\thashcpy(entry->key, key);\n+\t\thashcpy(entry->value, value);\n+\t\tcache->count++;\n+\t\tcache->dirty = 1;\n+\t} else { /* overwrite existing entry */\n+\t\tentry = cache->entries + i;\n+\t\tif (hashcmp(value, entry->value)) {\n \t\t\thashcpy(entry->value, value);\n-\t\t\tcache->count++;\n \t\t\tcache->dirty = 1;\n-\t\t\treturn;\n-\t\t} else if(!hashcmp(key, entry->key)) {\n-\t\t\tif (hashcmp(value, entry->value)) {\n-\t\t\t\thashcpy(entry->value, value);\n-\t\t\t\tcache->dirty = 1;\n-\t\t\t}\n-\t\t\treturn;\n \t\t}\n \t}\n+\n+\tif (4*cache->count >= 3*cache->size)\n+\t\tgrow_map(cache);\n }\n-- \n1.5.6.2.258.g7a51a\n"},{"id":"82686","messageId":"7vabgrmxt9.fsf@gitster.siamese.dyndns.org","threadId":"14365","inReplyTo":"7f9d599f0807082056o666fced9nf87cc81447e16e05@mail.gmail.com","subject":"Re: [PATCH 2/3] cached-sha1-map: refactoring hash traversal code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-09T05:27:46Z","receivedAt":"2008-07-09T05:27:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Geoffrey Irving\" <irving@naml.us> writes:\n\n> From c4e60c28fe66985ac8224da832589c982010744e Mon Sep 17 00:00:00 2001\n> From: Geoffrey Irving <irving@naml.us>\n> Date: Tue, 8 Jul 2008 19:47:22 -0700\n> Subject: [PATCH 2/3] cached-sha1-map: refactoring hash traversal code\n>\n> Pulling common code from get_cached_sha1_entry and set_cached_sha1_entry\n> into static find_helper function.\n> ---\n\nSign-off?\n\n>  cached-sha1-map.c |   68 +++++++++++++++++++++++++++++-----------------------\n>  1 files changed, 38 insertions(+), 30 deletions(-)\n\nThe refactoring is good, and it should have been that way from the\nbeginning.  Please don't send in \"introduce foo.c [1/N]\", \"oops, initial\nversion of foo.c was crap, here is a fixup [2/N]\".\n\n> diff --git a/cached-sha1-map.c b/cached-sha1-map.c\n> index e363745..147c7a2 100644\n> --- a/cached-sha1-map.c\n> +++ b/cached-sha1-map.c\n> @@ -140,43 +144,47 @@ int get_cached_sha1_entry(struct cached_sha1_map *cache,\n>  \tmask = cache->size - 1;\n>\n>  \tfor (i = get_hash_index(key) & mask; ; i = (i+1) & mask) {\n> -\t\tif (!hashcmp(key, cache->entries[i].key)) {\n> -\t\t\thashcpy(value, cache->entries[i].value);\n> -\t\t\treturn 0;\n> -\t\t} else if (is_null_sha1(cache->entries[i].key))\n> -\t\t\treturn -1;\n> +\t\tif (!hashcmp(key, cache->entries[i].key))\n> +\t\t\treturn i;\n> +\t\telse if (is_null_sha1(cache->entries[i].key))\n> +\t\t\treturn ~i;\n>  \t}\n>  }\n>\n> +int get_cached_sha1_entry(struct cached_sha1_map *cache,\n> +\tconst unsigned char *key, unsigned char *value)\n> +{\n> +\tlong i = find_helper(cache, key);\n> +\tif(i < 0)\n> +\t\treturn -1;\n\nDoes this have to be extern?\n\nIf you are designing an API from scratch, and if you want a long, use it\nconsistently.  Do not demote an int to shorter int in a callchain\nunnecessarily.\n"}]}