{"thread":{"id":"25970","subject":"[PATCH v5] generalizing sorted-array handling","startedAt":"2010-12-05T10:34:01Z","lastAt":"2010-12-05T12:02:38Z","messageCount":9,"participants":["Yann Dirson","Jonathan Nieder"],"isPatch":true,"patchVersion":5,"patchTotal":null},"messages":[{"id":"157343","messageId":"1291545247-4151-1-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":null,"subject":"[PATCH v5] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-12-05T10:34:01Z","receivedAt":"2010-12-05T10:34:01Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Changes from v4:\n\n* better API documentation (was previously lacking or plain obsolete)\n* added one more wrapper (used by yet-to-be-resent bulk-* series\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* could gain a dealloc API, to minimize the explicit use of the _nr\n  and _alloc vars\n\n\nThe following binary-search occurences were not converted:\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":"157346","messageId":"1291545247-4151-2-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":"1291545247-4151-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-12-05T10:34:02Z","receivedAt":"2010-12-05T10:34:02Z","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 |  153 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 154 insertions(+), 0 deletions(-)\n create mode 100644 sorted-array.h\n\ndiff --git a/Makefile b/Makefile\nindex 1d42413..ced07df 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..dc4be87\n--- /dev/null\n+++ b/sorted-array.h\n@@ -0,0 +1,153 @@\n+#ifndef SORTED_ARRAY_H_\n+#define SORTED_ARRAY_H_\n+\n+/*\n+ * Declare an array of given type, together with its management\n+ * variable holding currently-allocated number of elements and number\n+ * of elements effectively used.\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+/*\n+ * Declare FUNCNAME as a binary-search function on sorted-arrays of\n+ * ELEMTYPE elements, search term being be of type INITTYPE.\n+ *\n+ * The resulting function can act on any ELEMTYPE* list, using any\n+ * suitable comparison function taking an INITTYPE argument and a\n+ * pointer to an ELEMTYPE argument, and returning an int with the same\n+ * meaning as strcmp.  If the element is found, it returns the index\n+ * in the list where it was found; if it is not found, it returns\n+ * (-pos - 1), where \"pos\" is the index in the list where the element\n+ * would be inserted.\n+ *\n+ * See below for macros to define more specific functions tailored to\n+ * a given list, and with output suitable to various usages.\n+ */\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+/*\n+ * Declare FUNCNAME as a function to search for an element in\n+ * sorted-arrays of ELEMTYPE elements, inserting it if it was not\n+ * found, search term being be of type INITTYPE.  The position where\n+ * to insert will be given found by SEARCHFUNC, which must be\n+ * compatible with the search functions defined by\n+ * declare_gen_binsearch().\n+ *\n+ * The resulting function takes the same arguments as similar search\n+ * functions, with the addition of a function to initialize the\n+ * newly-allocated element from the search term.\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 would\n+ * have been inserted.\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+/*\n+ * Returns the position of the element if found pre-existing in the\n+ * list, or if not found inserts it, and returns -pos-1 where pos is\n+ * where the element was inserted.\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.  Returns address of the element found, or NULL\n+ * if not found.\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+/*\n+ * Insert element if not there already.  Returns address of the\n+ * element found or newly-inserted.\n+ */\n+#define declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENINSERT,LIST,CMP,INIT) \\\n+MAYBESTATIC ELEMTYPE *FUNCNAME(INITTYPE data)\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\tidx = -idx - 1;\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":"157348","messageId":"1291545247-4151-3-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":"1291545247-4151-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-12-05T10:34:03Z","receivedAt":"2010-12-05T10:34:03Z","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":"157347","messageId":"1291545247-4151-4-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":"1291545247-4151-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-12-05T10:34:04Z","receivedAt":"2010-12-05T10:34:04Z","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":"157345","messageId":"1291545247-4151-5-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":"1291545247-4151-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-12-05T10:34:05Z","receivedAt":"2010-12-05T10:34:05Z","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 3cbeb29..887a55c 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":"157349","messageId":"1291545247-4151-6-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":"1291545247-4151-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-12-05T10:34:06Z","receivedAt":"2010-12-05T10:34:06Z","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 2d9265d..b7aeee4 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":"157344","messageId":"1291545247-4151-7-git-send-email-ydirson@altern.org","threadId":"25970","inReplyTo":"1291545247-4151-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-12-05T10:34:07Z","receivedAt":"2010-12-05T10:34:07Z","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"},{"id":"157350","messageId":"20101205104426.GG4332@burratino","threadId":"25970","inReplyTo":"1291545247-4151-1-git-send-email-ydirson@altern.org","subject":"Re: [PATCH v5] generalizing sorted-array handling","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-05T10:44:26Z","receivedAt":"2010-12-05T10:44:26Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Yann Dirson wrote:\n\n> * better API documentation (was previously lacking or plain obsolete)\n\nThanks!  In general I find it is easiest to read and write\ndocumentation out of line for this sort of thing.  That way, even\nafter the documentation grows obsolete it doesn't seem so out of\nplace.\n\nSee Documentation/technical/api-strbuf.txt, api-sigchain, and\napi-allocation-growing for some nice (up-to-date) examples.\n\nIn particular:\n\n> * This API is very verbose, and I'm not happy with that aspect.\n\nCould you give a quick stripped-down usage example?\n\n[...]\n> Adding \"simple\" API variants that would call all the necessary stuff\n> would help code readability, but adding yet more entry points seems a\n> dubious approach.\n\nOn the contrary, simple API variants don't sound so bad to me,\nonce the fundamentals are in good shape.\n"},{"id":"157352","messageId":"20101205120238.GB7466@home.lan","threadId":"25970","inReplyTo":"20101205104426.GG4332@burratino","subject":"Re: [PATCH v5] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-12-05T12:02:38Z","receivedAt":"2010-12-05T12:02:38Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Sun, Dec 05, 2010 at 04:44:26AM -0600, Jonathan Nieder wrote:\n> Yann Dirson wrote:\n> \n> > * better API documentation (was previously lacking or plain obsolete)\n> \n> Thanks!  In general I find it is easiest to read and write\n> documentation out of line for this sort of thing.  That way, even\n> after the documentation grows obsolete it doesn't seem so out of\n> place.\n> \n> See Documentation/technical/api-strbuf.txt, api-sigchain, and\n> api-allocation-growing for some nice (up-to-date) examples.\n\nOK, can do that.\n\n> In particular:\n> \n> > * This API is very verbose, and I'm not happy with that aspect.\n> \n> Could you give a quick stripped-down usage example?\n\nWell, patches 2-5 in the series provide good examples - probably\nbetter seen with the \"New version\" checkbos in gitk, did not find a\ncommandline flag equivalent (is there one ?).\n\nPatch 4 is probably the simplest example: we use the new macros to\ndefine the same insert API (except for the \"number of element\" var,\nwhich used a non-standard naming scheme here).  Since the lookup API\nwas only used inside the insert func, there was no need for a lookup\nwrapper here, so we just declare the generic search+ insert funcs, and\nan insert wrapper.\n\n---------------------------- builtin/pack-objects.c ----------------------------\nindex 3cbeb29..887a55c 100644\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 int unsigned_cmp(unsigned ref, unsigned *elem)\n {\n+\tif (ref == *elem)\n+\t\treturn 0;\n+\tif (ref < *elem)\n+\t\treturn -1;\n+\treturn 1;\n }\n+static void unsigned_init(unsigned *elem, unsigned ref)\n {\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_nr = done_pbase_paths_alloc = 0;\n }\n \n static void check_object(struct object_entry *entry)\n----------------------------\n\n\nPatch 2 is a more complete example, where the oiginal API used a\nsingle function with an additional boolean arg to select the\nbehaviour.  So here we also define a search wrapper, and this make the\ncallsites more explicit.\n\n------------------------------ diffcore-rename.c ------------------------------\nindex df41be5..a655017 100644\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+struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n+};\n \n+static int rename_dst_cmp(struct diff_filespec *ref_spec, struct diff_rename_dst *elem)\n {\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\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);\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);\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------------------------------\n\n> [...]\n> > Adding \"simple\" API variants that would call all the necessary stuff\n> > would help code readability, but adding yet more entry points seems a\n> > dubious approach.\n> \n> On the contrary, simple API variants don't sound so bad to me,\n> once the fundamentals are in good shape.\n\nThe problem is with the number of combinations.  We already have\npotentially 6 wrappers (not all of which are defined yet), with:\n\n* operation: search | insert\n* return-value semantic: check | checkbool | elem\n\nIf we add to these basic building-blocks:\n\n* wrapper variants that declare the generic func: we double the count\n* insert-wrapper variants that declare the generic search: *1.5\n\n... which gives something like 18 wrappers.  And this number will\nstill raise by 6 each time we feel the need for a new return-value\nsemantic.\n"}]}