{"thread":{"id":"25873","subject":"[PATCH 1/6] Introduce sorted-array binary-search function.","startedAt":"2010-11-29T22:57:15Z","lastAt":"2010-11-29T22:57:21Z","messageCount":7,"participants":["Yann Dirson"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"156853","messageId":"1291071441-11808-1-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":null,"subject":"[PATCH v4] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:15Z","receivedAt":"2010-11-29T22:57:15Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Changes from v3:\n\n* this is a major rewrite, which allows the API to be used in some\n  more places than the previous version.  It does not cover all\n  binary-search uses, however, but it's not clear to me that trying to\n  get any further would be a good use of my time (see last section\n  below for details).\n\n* based the API and implementation on the most widely used\n  binary-search implementation found in the current tree, and on the\n  must flexible API (the \"return -lo - 1\" one)\n\n* given full control of generated function names to caller\n\n* completely separated sorted-array typedecl from generic search/insert\n  implementations, allowing several search/insert functions with\n  different cmp/init callbacks\n\n* provided several convenience wrappers around the generic\n  search/insert implementations, depending on the needs of surrounding\n  code\n\nNotes on current API:\n\n* The macro names are a bit heavy-weight.  Better ideas welcome.\n\n* This API is very verbose, and I'm not happy with that aspect.\n\nIt could be made less so, eg. causing insert wrappers to auto-declare\nthe required generic insert func, and causing the latter auto-declare\nthe required generic search func.  That would cause duplication of the\ngeneric search func in many cases.\n\nThe duplication problem would not be an issue if we add an automatic\ncall to declare_gen_sorted_insert() in declare_sorted_array_insert_*,\nbut we would loose the symetry with the search API.\n\nAdding \"simple\" API variants that would call all the necessary stuff\nwould help code readability, but adding yet more entry points seems a\ndubious approach.\n\nOr is that just the \"use cpp for templating\" just inadequate here ?\n\n\nTODO? list:\n\n* take binsearch desc from sha1_lookup.c\n\n* dealloc API\n\n* read-cache.c::index_name_pos has widely-used API with 2 low-coupled\n  cmp/init params: sorted-array could be generalized at the cost of\n  using stdarg, but is it worth it ?\n\n* pack-revindex.c::find_pack_revindex is a bit special and needs more\n  thought\n\n* cache-tree.c::subtree_pos and sha1_file::find_pack_entry_one too\n\n* sha1_lookup.c stuff probably too special\n"},{"id":"156851","messageId":"1291071441-11808-2-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":"1291071441-11808-1-git-send-email-ydirson@altern.org","subject":"[PATCH 1/6] Introduce sorted-array binary-search function.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:16Z","receivedAt":"2010-11-29T22:57:16Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"We use a cpp-based template mechanism to declare the array and its\nmanagement data, as well as a search function.\nThanks to Jonathan Nieder for this design idea.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n Makefile       |    1 +\n sorted-array.h |  104 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 105 insertions(+), 0 deletions(-)\n create mode 100644 sorted-array.h\n\ndiff --git a/Makefile b/Makefile\nindex 919ed2b..4b26976 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -539,6 +539,7 @@ LIB_H += run-command.h\n LIB_H += sha1-lookup.h\n LIB_H += sideband.h\n LIB_H += sigchain.h\n+LIB_H += sorted-array.h\n LIB_H += strbuf.h\n LIB_H += string-list.h\n LIB_H += submodule.h\ndiff --git a/sorted-array.h b/sorted-array.h\nnew file mode 100644\nindex 0000000..20219e7\n--- /dev/null\n+++ b/sorted-array.h\n@@ -0,0 +1,104 @@\n+#ifndef SORTED_ARRAY_H_\n+#define SORTED_ARRAY_H_\n+\n+#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,LIST)\t\t\t\\\n+MAYBESTATIC ELEMTYPE *LIST;\t\t\t\t\t\t\\\n+MAYBESTATIC int LIST##_nr, LIST##_alloc;\n+\n+/* internal func: the implementation */\n+#define declare_gen_binsearch(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE)\t\\\n+MAYBESTATIC int FUNCNAME(\t\t\t\t\t\t\\\n+\tELEMTYPE *list, int list_nr,\t\t\t\t\t\\\n+\tint(*cmp_func)(INITTYPE ref, ELEMTYPE *elem),\t\t\t\\\n+\tINITTYPE data)\t\t\t\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\tint lo, hi;\t\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\t\\\n+\tlo = 0;\t\t\t\t\t\t\t\t\\\n+\thi = list_nr;\t\t\t\t\t\t\t\\\n+\twhile (hi > lo) {\t\t\t\t\t\t\\\n+\t\tint mid = (hi + lo) >> 1;\t\t\t\t\\\n+\t\tint cmp = cmp_func(data, list + mid);\t\t\t\\\n+\t\tif (!cmp)\t\t\t\t\t\t\\\n+\t\t\treturn mid;\t\t\t\t\t\\\n+\t\tif (cmp < 0)\t\t\t\t\t\t\\\n+\t\t\thi = mid;\t\t\t\t\t\\\n+\t\telse\t\t\t\t\t\t\t\\\n+\t\t\tlo = mid + 1;\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\\\n+\treturn -lo - 1;\t\t\t\t\t\t\t\\\n+}\n+\n+#define declare_gen_sorted_insert(MAYBESTATIC,ELEMTYPE,FUNCNAME,SEARCHFUNC,INITTYPE) \\\n+MAYBESTATIC int FUNCNAME(\t\t\t\t\t\t\\\n+\tELEMTYPE **list_p, int *list_nr_p, int *list_alloc_p,\t\t\\\n+\tint(*cmp_func)(INITTYPE ref, ELEMTYPE *elem),\t\t\t\\\n+\tvoid(*init_func)(ELEMTYPE *elem, INITTYPE init),\t\t\\\n+\tINITTYPE data)\t\t\t\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\tint pos = SEARCHFUNC(*list_p, *list_nr_p, cmp_func, data);\t\\\n+\tif (pos >= 0) \t\t\t\t\t\t\t\\\n+\t\treturn pos;\t\t\t\t\t\t\\\n+\t/* not found */\t\t\t\t\t\t\t\\\n+\tpos = -pos - 1;\t\t\t\t\t\t\t\\\n+\t/* insert to make it at \"pos\" */\t\t\t\t\\\n+\tif (*list_alloc_p <= *list_nr_p) {\t\t\t\t\\\n+\t\t(*list_alloc_p) = alloc_nr((*list_alloc_p));\t\t\\\n+\t\t*list_p = xrealloc(*list_p,\t\t\t\t\\\n+\t\t\t\t   (*list_alloc_p) * sizeof(**list_p)); \\\n+\t}\t\t\t\t\t\t\t\t\\\n+\t(*list_nr_p)++;\t\t\t\t\t\t\t\\\n+\tif (pos < *list_nr_p)\t\t\t\t\t\t\\\n+\t\tmemmove(*list_p + pos + 1, *list_p + pos,\t\t\\\n+\t\t\t(*list_nr_p - pos - 1) * sizeof(**list_p));\t\\\n+\tinit_func(&(*list_p)[pos], data);\t\t\t\t\\\n+\treturn -pos - 1;\t\t\t\t\t\t\\\n+}\n+\n+/*\n+ * Returns the position of the element if found pre-existing in the\n+ * list, or if not found, -pos-1 where pos is where the element was\n+ * inserted if insert_ok, or would have been inserted if !insert_ok.\n+ */\n+#define declare_sorted_array_search_check(MAYBESTATIC,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP) \\\n+MAYBESTATIC int FUNCNAME(INITTYPE data)\t\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\treturn GENSEARCH(LIST, LIST##_nr, CMP, data);\t\t\t\\\n+}\n+\n+#define declare_sorted_array_insert_check(MAYBESTATIC,FUNCNAME,INITTYPE,GENINSERT,LIST,CMP,INIT) \\\n+MAYBESTATIC int FUNCNAME(INITTYPE data)\t\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\treturn GENINSERT(&LIST, &LIST##_nr, &LIST##_alloc,\t\t\\\n+\t\t\t CMP, INIT, data);\t\t\t\t\\\n+}\n+\n+/*\n+ * Insert, and just tell whether the searched element was pre-existing\n+ * in the list or not.\n+ */\n+#define declare_sorted_array_insert_checkbool(MAYBESTATIC,FUNCNAME,INITTYPE,GENINSERT,LIST,CMP,INIT) \\\n+MAYBESTATIC int FUNCNAME(INITTYPE data)\t\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\tint idx = GENINSERT(&LIST, &LIST##_nr, &LIST##_alloc,\t\t\\\n+\t\t\t    CMP, INIT, data);\t\t\t\t\\\n+\tif (idx < 0)\t\t\t\t\t\t\t\\\n+\t\treturn 0;\t\t\t\t\t\t\\\n+\treturn 1;\t\t\t\t\t\t\t\\\n+}\n+\n+/*\n+ * Search for element, inserting it if requested.  Returns address of\n+ * the element found or newly-inserted, or NULL if not found and\n+ * insertion was not requested.\n+ */\n+#define declare_sorted_array_search_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP) \\\n+MAYBESTATIC ELEMTYPE *FUNCNAME(INITTYPE data)\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\tint idx = GENSEARCH(LIST, LIST##_nr, CMP, data);\t\t\\\n+\tif (idx < 0)\t\t\t\t\t\t\t\\\n+\t\treturn NULL;\t\t\t\t\t\t\\\n+\treturn &(LIST[idx]);\t\t\t\t\t\t\\\n+}\n+\n+#endif\n-- \n1.7.2.3\n"},{"id":"156858","messageId":"1291071441-11808-3-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":"1291071441-11808-1-git-send-email-ydirson@altern.org","subject":"[PATCH 2/6] Convert diffcore-rename's rename_dst to the new sorted-array API.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:17Z","receivedAt":"2010-11-29T22:57:17Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"The sorted-array API splits search and insert into two separated\nfunctions, which makes the caller code more clear.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n diffcore-rename.c |   66 ++++++++++++++++++++---------------------------------\n 1 files changed, 25 insertions(+), 41 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..a655017 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,52 +5,36 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"hash.h\"\n+#include \"sorted-array.h\"\n \n /* Table of rename/copy destinations */\n \n-static struct diff_rename_dst {\n+struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n-} *rename_dst;\n-static int rename_dst_nr, rename_dst_alloc;\n+};\n \n-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n-\t\t\t\t\t\t int insert_ok)\n+static int rename_dst_cmp(struct diff_filespec *ref_spec, struct diff_rename_dst *elem)\n {\n-\tint first, last;\n-\n-\tfirst = 0;\n-\tlast = rename_dst_nr;\n-\twhile (last > first) {\n-\t\tint next = (last + first) >> 1;\n-\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n-\t\tint cmp = strcmp(two->path, dst->two->path);\n-\t\tif (!cmp)\n-\t\t\treturn dst;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\t/* not found */\n-\tif (!insert_ok)\n-\t\treturn NULL;\n-\t/* insert to make it at \"first\" */\n-\tif (rename_dst_alloc <= rename_dst_nr) {\n-\t\trename_dst_alloc = alloc_nr(rename_dst_alloc);\n-\t\trename_dst = xrealloc(rename_dst,\n-\t\t\t\t      rename_dst_alloc * sizeof(*rename_dst));\n-\t}\n-\trename_dst_nr++;\n-\tif (first < rename_dst_nr)\n-\t\tmemmove(rename_dst + first + 1, rename_dst + first,\n-\t\t\t(rename_dst_nr - first - 1) * sizeof(*rename_dst));\n-\trename_dst[first].two = alloc_filespec(two->path);\n-\tfill_filespec(rename_dst[first].two, two->sha1, two->mode);\n-\trename_dst[first].pair = NULL;\n-\treturn &(rename_dst[first]);\n+\treturn strcmp(ref_spec->path, elem->two->path);\n+}\n+static void rename_dst_init(struct diff_rename_dst *elem, struct diff_filespec *ref_spec)\n+{\n+\telem->two = alloc_filespec(ref_spec->path);\n+\tfill_filespec(elem->two, ref_spec->sha1, ref_spec->mode);\n+\telem->pair = NULL;\n }\n+declare_sorted_array(static, struct diff_rename_dst, rename_dst);\n+declare_gen_binsearch(static, struct diff_rename_dst, _locate_rename_dst,\n+\t\t      struct diff_filespec *);\n+declare_sorted_array_search_elem(static, struct diff_rename_dst, locate_rename_dst,\n+\t\t\t\t struct diff_filespec *, _locate_rename_dst,\n+\t\t\t\t rename_dst, rename_dst_cmp);\n+declare_gen_sorted_insert(static, struct diff_rename_dst, _register_rename_dst,\n+\t\t\t  _locate_rename_dst, struct diff_filespec *);\n+declare_sorted_array_insert_checkbool(static, register_rename_dst, struct diff_filespec *,\n+\t\t\t\t      _register_rename_dst,\n+\t\t\t\t      rename_dst, rename_dst_cmp, rename_dst_init);\n \n /* Table of rename/copy src files */\n static struct diff_rename_src {\n@@ -437,7 +421,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t\t strcmp(options->single_follow, p->two->path))\n \t\t\t\tcontinue; /* not interested */\n \t\t\telse\n-\t\t\t\tlocate_rename_dst(p->two, 1);\n+\t\t\t\tregister_rename_dst(p->two);\n \t\t}\n \t\telse if (!DIFF_FILE_VALID(p->two)) {\n \t\t\t/*\n@@ -582,7 +566,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t * not been turned into a rename/copy already.\n \t\t\t */\n \t\t\tstruct diff_rename_dst *dst =\n-\t\t\t\tlocate_rename_dst(p->two, 0);\n+\t\t\t\tlocate_rename_dst(p->two);\n \t\t\tif (dst && dst->pair) {\n \t\t\t\tdiff_q(&outq, dst->pair);\n \t\t\t\tpair_to_free = p;\n@@ -613,7 +597,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tif (DIFF_PAIR_BROKEN(p)) {\n \t\t\t\t/* broken delete */\n \t\t\t\tstruct diff_rename_dst *dst =\n-\t\t\t\t\tlocate_rename_dst(p->one, 0);\n+\t\t\t\t\tlocate_rename_dst(p->one);\n \t\t\t\tif (dst && dst->pair)\n \t\t\t\t\t/* counterpart is now rename/copy */\n \t\t\t\t\tpair_to_free = p;\n-- \n1.7.2.3\n"},{"id":"156856","messageId":"1291071441-11808-4-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":"1291071441-11808-1-git-send-email-ydirson@altern.org","subject":"[PATCH 3/6] Convert diffcore-rename's rename_src to the new sorted-array API.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:18Z","receivedAt":"2010-11-29T22:57:18Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"There was no compelling reason to pass separately two members of a\nsingle struct to the insert function.  That's a happy coincidence.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n diffcore-rename.c |   57 ++++++++++++++++++----------------------------------\n 1 files changed, 20 insertions(+), 37 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex a655017..7e35a82 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -37,46 +37,29 @@ declare_sorted_array_insert_checkbool(static, register_rename_dst, struct diff_f\n \t\t\t\t      rename_dst, rename_dst_cmp, rename_dst_init);\n \n /* Table of rename/copy src files */\n-static struct diff_rename_src {\n+\n+struct diff_rename_src {\n \tstruct diff_filespec *one;\n \tunsigned short score; /* to remember the break score */\n-} *rename_src;\n-static int rename_src_nr, rename_src_alloc;\n+};\n \n-static struct diff_rename_src *register_rename_src(struct diff_filespec *one,\n-\t\t\t\t\t\t   unsigned short score)\n+static int rename_src_cmp(struct diff_filepair *ref_pair, struct diff_rename_src *elem)\n {\n-\tint first, last;\n-\n-\tfirst = 0;\n-\tlast = rename_src_nr;\n-\twhile (last > first) {\n-\t\tint next = (last + first) >> 1;\n-\t\tstruct diff_rename_src *src = &(rename_src[next]);\n-\t\tint cmp = strcmp(one->path, src->one->path);\n-\t\tif (!cmp)\n-\t\t\treturn src;\n-\t\tif (cmp < 0) {\n-\t\t\tlast = next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tfirst = next+1;\n-\t}\n-\n-\t/* insert to make it at \"first\" */\n-\tif (rename_src_alloc <= rename_src_nr) {\n-\t\trename_src_alloc = alloc_nr(rename_src_alloc);\n-\t\trename_src = xrealloc(rename_src,\n-\t\t\t\t      rename_src_alloc * sizeof(*rename_src));\n-\t}\n-\trename_src_nr++;\n-\tif (first < rename_src_nr)\n-\t\tmemmove(rename_src + first + 1, rename_src + first,\n-\t\t\t(rename_src_nr - first - 1) * sizeof(*rename_src));\n-\trename_src[first].one = one;\n-\trename_src[first].score = score;\n-\treturn &(rename_src[first]);\n+\treturn strcmp(ref_pair->one->path, elem->one->path);\n+}\n+static void rename_src_init(struct diff_rename_src *elem, struct diff_filepair *ref_pair)\n+{\n+\telem->one = ref_pair->one;\n+\telem->score = ref_pair->score;\n }\n+declare_sorted_array(static, struct diff_rename_src, rename_src);\n+declare_gen_binsearch(static, struct diff_rename_src, _locate_rename_src,\n+\t\t      struct diff_filepair *);\n+declare_gen_sorted_insert(static, struct diff_rename_src, _register_rename_src,\n+\t\t\t  _locate_rename_src, struct diff_filepair *);\n+declare_sorted_array_insert_checkbool(static, register_rename_src, struct diff_filepair *,\n+\t\t\t\t      _register_rename_src,\n+\t\t\t\t      rename_src, rename_src_cmp, rename_src_init);\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n {\n@@ -433,7 +416,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t */\n \t\t\tif (p->broken_pair && !p->score)\n \t\t\t\tp->one->rename_used++;\n-\t\t\tregister_rename_src(p->one, p->score);\n+\t\t\tregister_rename_src(p);\n \t\t}\n \t\telse if (detect_rename == DIFF_DETECT_COPY) {\n \t\t\t/*\n@@ -441,7 +424,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\t * one, to indicate ourselves as a user.\n \t\t\t */\n \t\t\tp->one->rename_used++;\n-\t\t\tregister_rename_src(p->one, p->score);\n+\t\t\tregister_rename_src(p);\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n-- \n1.7.2.3\n"},{"id":"156855","messageId":"1291071441-11808-5-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":"1291071441-11808-1-git-send-email-ydirson@altern.org","subject":"[PATCH 4/6] Convert pack-objects.c to the new sorted-array API.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:19Z","receivedAt":"2010-11-29T22:57:19Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"In this file the \"list size\" variable was named in a non-standard way.\nThe new API forces to use a more common convention.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n builtin/pack-objects.c |   51 ++++++++++++++---------------------------------\n 1 files changed, 15 insertions(+), 36 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f8eba53..c4af9f7 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -16,6 +16,7 @@\n #include \"list-objects.h\"\n #include \"progress.h\"\n #include \"refs.h\"\n+#include \"sorted-array.h\"\n \n #ifndef NO_PTHREADS\n #include <pthread.h>\n@@ -871,45 +872,23 @@ static void add_pbase_object(struct tree_desc *tree,\n \t}\n }\n \n-static unsigned *done_pbase_paths;\n-static int done_pbase_paths_num;\n-static int done_pbase_paths_alloc;\n-static int done_pbase_path_pos(unsigned hash)\n+static int unsigned_cmp(unsigned ref, unsigned *elem)\n {\n-\tint lo = 0;\n-\tint hi = done_pbase_paths_num;\n-\twhile (lo < hi) {\n-\t\tint mi = (hi + lo) / 2;\n-\t\tif (done_pbase_paths[mi] == hash)\n-\t\t\treturn mi;\n-\t\tif (done_pbase_paths[mi] < hash)\n-\t\t\thi = mi;\n-\t\telse\n-\t\t\tlo = mi + 1;\n-\t}\n-\treturn -lo-1;\n+\tif (ref == *elem)\n+\t\treturn 0;\n+\tif (ref < *elem)\n+\t\treturn -1;\n+\treturn 1;\n }\n-\n-static int check_pbase_path(unsigned hash)\n+static void unsigned_init(unsigned *elem, unsigned ref)\n {\n-\tint pos = (!done_pbase_paths) ? -1 : done_pbase_path_pos(hash);\n-\tif (0 <= pos)\n-\t\treturn 1;\n-\tpos = -pos - 1;\n-\tif (done_pbase_paths_alloc <= done_pbase_paths_num) {\n-\t\tdone_pbase_paths_alloc = alloc_nr(done_pbase_paths_alloc);\n-\t\tdone_pbase_paths = xrealloc(done_pbase_paths,\n-\t\t\t\t\t    done_pbase_paths_alloc *\n-\t\t\t\t\t    sizeof(unsigned));\n-\t}\n-\tdone_pbase_paths_num++;\n-\tif (pos < done_pbase_paths_num)\n-\t\tmemmove(done_pbase_paths + pos + 1,\n-\t\t\tdone_pbase_paths + pos,\n-\t\t\t(done_pbase_paths_num - pos - 1) * sizeof(unsigned));\n-\tdone_pbase_paths[pos] = hash;\n-\treturn 0;\n+\t*elem = ref;\n }\n+declare_sorted_array(static, unsigned, done_pbase_paths);\n+declare_gen_binsearch(static, unsigned, done_pbase_path_pos, unsigned);\n+declare_gen_sorted_insert(static, unsigned, _check_pbase_path, done_pbase_path_pos, unsigned);\n+declare_sorted_array_insert_checkbool(static, check_pbase_path, unsigned, _check_pbase_path,\n+\t\t\t\t      done_pbase_paths, unsigned_cmp, unsigned_init);\n \n static void add_preferred_base_object(const char *name)\n {\n@@ -987,7 +966,7 @@ static void cleanup_preferred_base(void)\n \n \tfree(done_pbase_paths);\n \tdone_pbase_paths = NULL;\n-\tdone_pbase_paths_num = done_pbase_paths_alloc = 0;\n+\tdone_pbase_paths_nr = done_pbase_paths_alloc = 0;\n }\n \n static void check_object(struct object_entry *entry)\n-- \n1.7.2.3\n"},{"id":"156852","messageId":"1291071441-11808-6-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":"1291071441-11808-1-git-send-email-ydirson@altern.org","subject":"[PATCH 5/6] Use sorted-array API for commit.c's commit_graft.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:20Z","receivedAt":"2010-11-29T22:57:20Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Factorizing code fixes off-by-one error in the duplicated code (caused\nmostly harmless anticipated growing of the array).\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n commit.c |   62 +++++++++++++++++++++++++++-----------------------------------\n 1 files changed, 27 insertions(+), 35 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 0094ec1..5b9a554 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -6,6 +6,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"notes.h\"\n+#include \"sorted-array.h\"\n \n int save_commit_buffer = 1;\n \n@@ -76,33 +77,37 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)\n \treturn strtoul(dateptr, NULL, 10);\n }\n \n-static struct commit_graft **commit_graft;\n-static int commit_graft_alloc, commit_graft_nr;\n-\n-static int commit_graft_pos(const unsigned char *sha1)\n+static int commit_graft_cmp(const unsigned char *ref_sha1, struct commit_graft **elem)\n {\n-\tint lo, hi;\n-\tlo = 0;\n-\thi = commit_graft_nr;\n-\twhile (lo < hi) {\n-\t\tint mi = (lo + hi) / 2;\n-\t\tstruct commit_graft *graft = commit_graft[mi];\n-\t\tint cmp = hashcmp(sha1, graft->sha1);\n-\t\tif (!cmp)\n-\t\t\treturn mi;\n-\t\tif (cmp < 0)\n-\t\t\thi = mi;\n-\t\telse\n-\t\t\tlo = mi + 1;\n-\t}\n-\treturn -lo - 1;\n+\treturn hashcmp(ref_sha1, (*elem)->sha1);\n }\n+declare_sorted_array(static, struct commit_graft *, commit_graft);\n+declare_gen_binsearch(static, struct commit_graft *, _commit_graft_pos,\n+\t\t      const unsigned char *);\n+declare_sorted_array_search_check(static, commit_graft_pos, const unsigned char *,\n+\t\t\t\t  _commit_graft_pos, commit_graft, commit_graft_cmp);\n \n+// FIXME: do we want to/can we remove INITTYPE from gen_binsearch ?\n+static int commit_graft_cmp2(struct commit_graft *ref_graft, struct commit_graft **elem)\n+{\n+\treturn commit_graft_cmp(ref_graft->sha1, elem);\n+}\n+declare_gen_binsearch(static, struct commit_graft *, _commit_graft_pos2,\n+\t\t      struct commit_graft *);\n+static void commit_graft_init(struct commit_graft **elem, struct commit_graft *ref_graft)\n+{\n+\t*elem = ref_graft;\n+}\n+declare_gen_sorted_insert(static, struct commit_graft *, _register_commit_graft0,\n+\t\t\t  _commit_graft_pos2, struct commit_graft *)\n+declare_sorted_array_insert_check(static, register_commit_graft0, struct commit_graft *,\n+\t\t\t\t  _register_commit_graft0, commit_graft,\n+\t\t\t\t  commit_graft_cmp2, commit_graft_init);\n int register_commit_graft(struct commit_graft *graft, int ignore_dups)\n {\n-\tint pos = commit_graft_pos(graft->sha1);\n+\tint pos = register_commit_graft0(graft);\n \n-\tif (0 <= pos) {\n+\tif (pos >= 0) {\n \t\tif (ignore_dups)\n \t\t\tfree(graft);\n \t\telse {\n@@ -111,19 +116,6 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)\n \t\t}\n \t\treturn 1;\n \t}\n-\tpos = -pos - 1;\n-\tif (commit_graft_alloc <= ++commit_graft_nr) {\n-\t\tcommit_graft_alloc = alloc_nr(commit_graft_alloc);\n-\t\tcommit_graft = xrealloc(commit_graft,\n-\t\t\t\t\tsizeof(*commit_graft) *\n-\t\t\t\t\tcommit_graft_alloc);\n-\t}\n-\tif (pos < commit_graft_nr)\n-\t\tmemmove(commit_graft + pos + 1,\n-\t\t\tcommit_graft + pos,\n-\t\t\t(commit_graft_nr - pos - 1) *\n-\t\t\tsizeof(*commit_graft));\n-\tcommit_graft[pos] = graft;\n \treturn 0;\n }\n \n-- \n1.7.2.3\n"},{"id":"156854","messageId":"1291071441-11808-7-git-send-email-ydirson@altern.org","threadId":"25873","inReplyTo":"1291071441-11808-1-git-send-email-ydirson@altern.org","subject":"[PATCH 6/6] [WIP] subvert sorted-array to replace binary-search in unpack-objects.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-29T22:57:21Z","receivedAt":"2010-11-29T22:57:21Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Signed-off-by: Yann Dirson <ydirson@altern.org>\n---\n builtin/unpack-objects.c |   41 ++++++++++++++++++++++++++---------------\n 1 files changed, 26 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\nindex f63973c..b0c15e6 100644\n--- a/builtin/unpack-objects.c\n+++ b/builtin/unpack-objects.c\n@@ -11,6 +11,7 @@\n #include \"progress.h\"\n #include \"decorate.h\"\n #include \"fsck.h\"\n+#include \"sorted-array.h\"\n \n static int dry_run, quiet, recover, has_errors, strict;\n static const char unpack_usage[] = \"git unpack-objects [-n] [-q] [-r] [--strict] < pack-file\";\n@@ -157,7 +158,25 @@ struct obj_info {\n #define FLAG_OPEN (1u<<20)\n #define FLAG_WRITTEN (1u<<21)\n \n-static struct obj_info *obj_list;\n+/*\n+ * FIXME: obj_info is a sorted array, but we read it as a whole, we\n+ * don't need insertion features.  This allows us to abuse unused\n+ * obj_info_nr later as a means of specifying an upper bound for\n+ * binary search.  obj_info_alloc shall be eliminated by the compiler\n+ * as unused.\n+ */\n+static int obj_info_cmp(off_t ref, struct obj_info *elem)\n+{\n+\tif (ref == elem->offset)\n+\t\treturn 0;\n+\tif (ref < elem->offset)\n+\t\treturn -1;\n+\treturn 1;\n+}\n+declare_sorted_array(static, struct obj_info, obj_list);\n+declare_gen_binsearch(static, struct obj_info, _obj_list_check, off_t);\n+declare_sorted_array_search_check(static, obj_list_check, off_t, _obj_list_check,\n+\t\t\t\t  obj_list, obj_info_cmp);\n static unsigned nr_objects;\n \n /*\n@@ -356,7 +375,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t\tunsigned base_found = 0;\n \t\tunsigned char *pack, c;\n \t\toff_t base_offset;\n-\t\tunsigned lo, mid, hi;\n+\t\tint pos;\n \n \t\tpack = fill(1);\n \t\tc = *pack;\n@@ -380,19 +399,11 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t\t\tfree(delta_data);\n \t\t\treturn;\n \t\t}\n-\t\tlo = 0;\n-\t\thi = nr;\n-\t\twhile (lo < hi) {\n-\t\t\tmid = (lo + hi)/2;\n-\t\t\tif (base_offset < obj_list[mid].offset) {\n-\t\t\t\thi = mid;\n-\t\t\t} else if (base_offset > obj_list[mid].offset) {\n-\t\t\t\tlo = mid + 1;\n-\t\t\t} else {\n-\t\t\t\thashcpy(base_sha1, obj_list[mid].sha1);\n-\t\t\t\tbase_found = !is_null_sha1(base_sha1);\n-\t\t\t\tbreak;\n-\t\t\t}\n+\t\tobj_list_nr = nr; /* kludge to bound the search */\n+\t\tpos = obj_list_check(base_offset);\n+\t\tif (pos >= 0) {\n+\t\t\thashcpy(base_sha1, obj_list[pos].sha1);\n+\t\t\tbase_found = !is_null_sha1(base_sha1);\n \t\t}\n \t\tif (!base_found) {\n \t\t\t/*\n-- \n1.7.2.3\n"}]}