{"thread":{"id":"26000","subject":"[PATCH v6] generalizing sorted-array handling","startedAt":"2010-12-08T22:51:29Z","lastAt":"2010-12-30T10:49:08Z","messageCount":15,"participants":["Yann Dirson","Junio C Hamano","Erik Faye-Lund"],"isPatch":true,"patchVersion":6,"patchTotal":null},"messages":[{"id":"157637","messageId":"1291848695-24601-1-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":null,"subject":"[PATCH v6] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-12-08T22:51:29Z","receivedAt":"2010-12-08T22:51:29Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"I hope the improvements to the usage syntax in this version would help\nto get more feedback.  I don't plan to do much more structural work on\nthis, unless reviewers complain.  I want to get my focus back to\nbulk-rename/builk-rm patches, which will make heavy use of this API.\n\nChanges from v5:\n\n* moved doc to Documentation/api-sorted-array.txt as suggested by\n  Jonathan Nieder, made it a bit more comprehensive as well.\n\n* changed API with:\n  * renamed low-level wrapper-decl macros with a leading underscore\n  * provide high-level wrapper-decl macros for everyday use, which\n    declare the required generic funcs for use (as static funcs)\n\nThose high-level macros make the entry points more numerousas\npreviously noted, but we gain much in usage clarity, as well as\nconsistent API (no more argument differences between macros of a\nsingle level)\n\nBy using those macros we lose the control we had on all the\nintermediate funcs, but that should not be much of a problem.\n\n\nNotes on current API:\n\n* The macro names are a bit heavy-weight.  Better ideas welcome.\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":"157644","messageId":"1291848695-24601-2-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":"1291848695-24601-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-08T22:51:30Z","receivedAt":"2010-12-08T22:51:30Z","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 Documentation/technical/api-sorted-array.txt |  132 ++++++++++++++++++++++++++\n Makefile                                     |    1 +\n sorted-array.h                               |  128 +++++++++++++++++++++++++\n 3 files changed, 261 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/api-sorted-array.txt\n create mode 100644 sorted-array.h\n\ndiff --git a/Documentation/technical/api-sorted-array.txt b/Documentation/technical/api-sorted-array.txt\nnew file mode 100644\nindex 0000000..b1238ad\n--- /dev/null\n+++ b/Documentation/technical/api-sorted-array.txt\n@@ -0,0 +1,132 @@\n+sorted-array API\n+================\n+\n+The sorted-array API is meant to provide efficient binary-search\n+functions into a C array of elements of arbitrary type, and insert\n+functions that maintain ordering.\n+\n+It is meant for data structures where lookup time is much more\n+important than insertion type: while lookup has o(log(n)) time\n+complexity, insertion has o(n) and involves many copies.\n+\n+API overview\n+------------\n+\n+The API allow to declare all variables and function as static or not,\n+through the first argument to all macros, which can be `static` or\n+empty.\n+\n+It is based on the idea of providing custom functions, which will then\n+be used by generic algorithms:\n+* one for comparing a search term with an array item\n+* one for initializing a new array item from a search term after insertion\n+\n+A set of convenience wrapper macros are provided, to define a readable\n+API for inserting and sorting.\n+\n+Note that the type of the search term can be different from the type\n+of array elements (which can be more expensive to create).\n+\n+API reference\n+-------------\n+\n+The macros can be categorized as follows:\n+\n+* the one used to define a sorted array, and its management variable\n+  holding currently-allocated number of elements and number of\n+  elements effectively used.  The name of those (int) management\n+  variables are crafted by using the `LISTNAME` and appending\n+  respectively `_alloc` and `_nr`.\n++\n+----\n+declare_sorted_array(MAYBESTATIC,ELEMTYPE,LISTNAME)\n+----\n++\n+eg:\n++\n+----\n+declare_sorted_array(static, struct diff_rename_dst, rename_dst);\n+----\n+\n+* those defining ready-for-use search and insert functions.  They\n+  exist in several flavours, distinguished by their suffix, which\n+  refer to different return-type semantics.\n++\n+----\n+declare_sorted_array_search_*(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LISTNAME,CMP)\n+declare_sorted_array_insert_*(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LISTNAME,CMP,INIT)\n+----\n++\n+They all work by defining behind the scene a (static) generic search or insert\n+function named with `_gen_` prepended to `FUNCNAME`.  Such generic functions\n+may be useful to know about if you need to define an insert function with\n+the exact same parameters.\n++\n+All functions of a given type (search or insert) take the same kind of\n+arguments:\n+\n+`MAYBESTATIC`::\n+\tthe ubiquitous `static`or empty placeholder\n+`ELEMTYPE`::\n+\ttype of element to be stored in the array\n+`FUNCNAME`::\n+\tname of the function to be defined\n+`INITTYPE`::\n+\ttype of search term / initializer passed as argument to the\n+\tgenerated function\n+`LISTNAME`::\n+\tname of the array in which the search takes place, usually declared\n+\tthrough `declare_sorted_array()`\n+`CMP`::\n+\tcomparison function taking an INITTYPE argument and a\n+\tpointer to an ELEMTYPE argument, and returning an int with\n+\tthe same meaning as `strcmp()`.\n+`GENSEARCH`::\n+\t(insert only) generic search function generated by\n+\t`declare_gen_binsearch()`\n+`INIT`::\n+\t(insert only) element-initializer function taking as arguments\n+\tpointer to the ELEMTYPE to be initialized, and an INITTYPE argument\n+\tto take information from\n+\n+\n+Suffix meanings are as follows:\n+\n+`check`::\n+\n+\tReturns the position of the element if found pre-existing in\n+\tthe list, or if not found, (-pos - 1) where pos is where the\n+\telement would have been (for search funcs) or has been (for\n+\tinsert funcs) inserted.\n+\n+`checkbool`::\n+\n+\tReturns an int, just telling whether the searched element was\n+\tpre-existing in the list (1) or not (0).\n+\n+`elem`::\n+\n+\tReturns NULL if the search term was not found (for search\n+\tfuncs), or a pointer to the element found or newly inserted.\n+\n+* those defining even-more-ready-for-use insert functions, which do\n+  not need to define the generic search function at all.  Those macro\n+  names are the same as the forms with an `GENSEARCH` argument, but\n+  with a name ending in `_insertonly_*`, and without that `GENSEARCH`\n+  argument.  The generic (static) search functions are named as\n+  `_gensearch` prepended to the `FUNCNAME` argument.\n+\n+* those defining the generic algorithms\n++\n+They rarely need to be used directly, they are usually expanded\n+transparently from the `declare_sorted_array_*` macros.\n++\n+----\n+declare_gen_binsearch(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE)\n+declare_gen_sorted_insert(MAYBESTATIC,ELEMTYPE,FUNCNAME,SEARCHFUNC,INITTYPE)\n+----\n+\n+* those defining the individual wrappers\n++\n+They rarely need to be used directly, they are usually expanded\n+transparently from the `declare_sorted_array_*` macros.\ndiff --git a/Makefile b/Makefile\nindex 7eb948d..522261e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -544,6 +544,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..added0e\n--- /dev/null\n+++ b/sorted-array.h\n@@ -0,0 +1,128 @@\n+#ifndef SORTED_ARRAY_H_\n+#define SORTED_ARRAY_H_\n+\n+/*\n+ * Sorted-array management.\n+ * See Documentation/technical/api-sorted-array.txt\n+ */\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+#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+#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+#define declare_sorted_array_search_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP) \\\n+  declare_gen_binsearch(MAYBESTATIC,ELEMTYPE,_gen_##FUNCNAME,INITTYPE); \\\n+  _declare_sorted_array_search_check(MAYBESTATIC,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP);\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+#define declare_sorted_array_insert_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP,INIT) \\\n+  declare_gen_sorted_insert(static,ELEMTYPE,_gen_##FUNCNAME,GENSEARCH,INITTYPE); \\\n+  _declare_sorted_array_insert_check(MAYBESTATIC,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP,INIT);\n+#define declare_sorted_array_insertonly_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP,INIT) \\\n+  declare_gen_binsearch(static,ELEMTYPE,_gensearch_##FUNCNAME,INITTYPE); \\\n+  declare_sorted_array_insert_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gensearch_##FUNCNAME,LIST,CMP,INIT);\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+#define declare_sorted_array_insert_checkbool(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP,INIT) \\\n+  declare_gen_sorted_insert(static,ELEMTYPE,_gen_##FUNCNAME,GENSEARCH,INITTYPE); \\\n+  _declare_sorted_array_insert_checkbool(MAYBESTATIC,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP,INIT);\n+#define declare_sorted_array_insertonly_checkbool(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP,INIT) \\\n+  declare_gen_binsearch(static,ELEMTYPE,_gensearch_##FUNCNAME,INITTYPE); \\\n+  declare_sorted_array_insert_checkbool(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gensearch_##FUNCNAME,LIST,CMP,INIT);\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+#define declare_sorted_array_search_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP) \\\n+  declare_gen_binsearch(static,ELEMTYPE,_gen_##FUNCNAME,INITTYPE); \\\n+  _declare_sorted_array_search_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP);\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+#define declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP,INIT) \\\n+  declare_gen_sorted_insert(static,ELEMTYPE,_gen_##FUNCNAME,GENSEARCH,INITTYPE); \\\n+  _declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP,INIT);\n+#define declare_sorted_array_insertonly_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP,INIT) \\\n+  declare_gen_binsearch(static,ELEMTYPE,_gensearch_##FUNCNAME,INITTYPE); \\\n+  declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gensearch_##FUNCNAME,LIST,CMP,INIT);\n+\n+#endif\n-- \n1.7.2.3\n"},{"id":"157643","messageId":"1291848695-24601-3-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":"1291848695-24601-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-08T22:51:31Z","receivedAt":"2010-12-08T22:51:31Z","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 |   62 ++++++++++++++++++-----------------------------------\n 1 files changed, 21 insertions(+), 41 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..ca3f54c 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,52 +5,32 @@\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_sorted_array_search_elem(static, struct diff_rename_dst, locate_rename_dst,\n+\t\t\t\t struct diff_filespec *,\n+\t\t\t\t rename_dst, rename_dst_cmp);\n+declare_sorted_array_insert_checkbool(static, struct diff_rename_dst, register_rename_dst,\n+\t\t\t\t      struct diff_filespec *, _gen_locate_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 +417,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 +562,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 +593,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":"157639","messageId":"1291848695-24601-4-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":"1291848695-24601-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-08T22:51:32Z","receivedAt":"2010-12-08T22:51:32Z","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 |   53 ++++++++++++++++-------------------------------------\n 1 files changed, 16 insertions(+), 37 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex ca3f54c..f7afdeb 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -33,46 +33,25 @@ declare_sorted_array_insert_checkbool(static, struct diff_rename_dst, register_r\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_sorted_array_insertonly_checkbool(static, struct diff_rename_src, register_rename_src,\n+\t\t\t\t\t  struct diff_filepair *,\n+\t\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@@ -429,7 +408,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@@ -437,7 +416,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":"157640","messageId":"1291848695-24601-5-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":"1291848695-24601-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-08T22:51:33Z","receivedAt":"2010-12-08T22:51:33Z","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 |   50 +++++++++++++----------------------------------\n 1 files changed, 14 insertions(+), 36 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f027b3a..c26175c 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,22 @@ 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_sorted_array_insertonly_checkbool(static, unsigned, check_pbase_path,\n+\t\t\t\t\t  unsigned,\n+\t\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 +965,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":"157641","messageId":"1291848695-24601-6-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":"1291848695-24601-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-08T22:51:34Z","receivedAt":"2010-12-08T22:51:34Z","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 |   55 +++++++++++++++++++++----------------------------------\n 1 files changed, 21 insertions(+), 34 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex b21335e..786bb7a 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@@ -89,33 +90,32 @@ 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_sorted_array_search_check(static, struct commit_graft *, commit_graft_pos,\n+\t\t\t\t  const unsigned char *,\n+\t\t\t\t  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+static void commit_graft_init(struct commit_graft **elem, struct commit_graft *ref_graft)\n+{\n+\t*elem = ref_graft;\n+}\n+declare_sorted_array_insertonly_check(static, struct commit_graft *, register_commit_graft0,\n+\t\t\t\t      struct commit_graft *,\n+\t\t\t\t      commit_graft, 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@@ -124,19 +124,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":"157642","messageId":"1291848695-24601-7-git-send-email-ydirson@altern.org","threadId":"26000","inReplyTo":"1291848695-24601-1-git-send-email-ydirson@altern.org","subject":"[PATCH 6/6] [RFC] subvert sorted-array to replace binary-search in unpack-objects.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-12-08T22:51:35Z","receivedAt":"2010-12-08T22:51:35Z","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 |   40 +++++++++++++++++++++++++---------------\n 1 files changed, 25 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\nindex f63973c..6d7d113 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,24 @@ 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_sorted_array_search_check(static, struct obj_info, obj_list_check,\n+\t\t\t\t  off_t, obj_list, obj_info_cmp);\n static unsigned nr_objects;\n \n /*\n@@ -356,7 +374,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 +398,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":"157849","messageId":"7vwrnhb6tm.fsf@alter.siamese.dyndns.org","threadId":"26000","inReplyTo":"1291848695-24601-2-git-send-email-ydirson@altern.org","subject":"Re: [PATCH 1/6] Introduce sorted-array binary-search function.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-10T22:29:09Z","receivedAt":"2010-12-10T22:29:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yann Dirson <ydirson@altern.org> writes:\n\n> +Suffix meanings are as follows:\n> +\n> +`check`::\n> +...\n> +* those defining the generic algorithms\n\nYuck.\n\nAll of these feel way overengineered and at the same time too rigid and\nbrittle.\n\nI have a suspicion that the \"convenience\" macros that generate many\nfunctions and definitions are the main culprit.  For example, why do all\nthe functions generated by a \"convenience\" macro must share the same\nMAYBESTATIC?  \"binsearch\" takes a comparison function pointer, and always\npicks the midpoint, but what is the performance implication if we wanted\nto use sorted-array.h to rewrite say sha1-lookup.c?  How can an API user\nwho wants to use declare_sorted_array_insert_checkbook() easily figure out\nwhat other macros fromt this family can be used without getting the same\nthing generated twice?  If somebody wanted to have a sorted array in a\nstruct, it may be tempting to use declare_sorted_array() with an empty\nMAYBESTATIC inside struct's field declaration (even when the struct itself\nis static---which leaves a queasy feeling, but that is a separate issue),\nand the _current_ macro definition of declare_sorted_array() may allow\nsuch a usage work perfectly fine, but how can such an API user be rest\nassured it won't break in later revisions of these macros?\n\nIn addition, these macros in this patch are almost unreadable, but that\nprobably is mostly a fault of C's macro, not yours.\n"},{"id":"157850","messageId":"7vsjy5b6ob.fsf@alter.siamese.dyndns.org","threadId":"26000","inReplyTo":"1291848695-24601-3-git-send-email-ydirson@altern.org","subject":"Re: [PATCH 2/6] Convert diffcore-rename's rename_dst to the new sorted-array API.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-10T22:32:20Z","receivedAt":"2010-12-10T22:32:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Separating \"locate with 'please optionally create'\" into \"locate\" and\n\"register\" looks like the right thing to do to make the callers easier to\nread.\n"},{"id":"157851","messageId":"7vmxodb5d3.fsf@alter.siamese.dyndns.org","threadId":"26000","inReplyTo":"1291848695-24601-7-git-send-email-ydirson@altern.org","subject":"Re: [PATCH 6/6] [RFC] subvert sorted-array to replace binary-search in unpack-objects.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-10T23:00:40Z","receivedAt":"2010-12-10T23:00:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yann Dirson <ydirson@altern.org> writes:\n\n> Signed-off-by: Yann Dirson <ydirson@altern.org>\n> ---\n>  builtin/unpack-objects.c |   40 +++++++++++++++++++++++++---------------\n>  1 files changed, 25 insertions(+), 15 deletions(-)\n>\n> diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c\n> index f63973c..6d7d113 100644\n> --- a/builtin/unpack-objects.c\n> +++ b/builtin/unpack-objects.c\n> @@ -157,7 +158,24 @@ 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\nI was scratching my head when I read \"subvert\" on your Subject line and\nFIXME above for the first time, but after thinking about it, I think I got\nit, and more importantly, I think you realized and shared with me the \"too\nrigid and brittle\" I mentioned in my response to [1/6] earlier, if not\n\"overengineered\" part.\n\nAs pack stream is read in, obj_list is built into an array that is sorted\nby its \"offset\" field up to \"nr\"-th element.  And assigning the current\nnumber of elements in the array to obj_list_nr is not a \"kludge to bound\nthe search\" as you said in the comment, but is the right thing to do given\nthe structure of your API.  \"nr\" is \"up to this index the array is filled\nand used\", \"alloc\" is \"this many is allocated\", and at the point of that\nassignment, \"nr\" is indeed what it is.\n\nThe only reason it might seem kludgy is because the API is not designed to\nanticipate that there is a way to add new elements at the end by feeding\nelements in the already sorted order, and that facility does so without\ncalling the functions your API autogenerates.\n\nI think the most bothersome repetition with the current codebase around\nbinary searchable tables is the binary search loops.  Perhaps introducing\na macro that lets us write them in a more structured way, without trying\nto build an elaborate top-level declarations that do everything (and\nfailing to do so), may give you a better payback?\n"},{"id":"157855","messageId":"7vd3p9b4d1.fsf@alter.siamese.dyndns.org","threadId":"26000","inReplyTo":"1291848695-24601-1-git-send-email-ydirson@altern.org","subject":"Re: [PATCH v6] generalizing sorted-array handling","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-10T23:22:18Z","receivedAt":"2010-12-10T23:22:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yann Dirson <ydirson@altern.org> writes:\n\n> ... I want to get my focus back to\n> bulk-rename/builk-rm patches, which will make heavy use of this API.\n\nFinal comment.  As the primary thing you want to use this is to change the\nway how the rename_dst/rename_src tables are managed, and these are both\ntables sorted by a string, I suspect a more reasonable might be to first\nupdated them to use string-list API and add to that API whatever necessary\nfeatures you might need, if any.\n"},{"id":"158739","messageId":"20101230000119.GA6639@home.lan","threadId":"26000","inReplyTo":"7vd3p9b4d1.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v6] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-12-30T00:01:19Z","receivedAt":"2010-12-30T00:01:19Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Fri, Dec 10, 2010 at 03:22:18PM -0800, Junio C Hamano wrote:\n> Yann Dirson <ydirson@altern.org> writes:\n> \n> > ... I want to get my focus back to\n> > bulk-rename/builk-rm patches, which will make heavy use of this API.\n> \n> Final comment.  As the primary thing you want to use this is to change the\n> way how the rename_dst/rename_src tables are managed, and these are both\n> tables sorted by a string, I suspect a more reasonable might be to first\n> updated them to use string-list API and add to that API whatever necessary\n> features you might need, if any.\n\nIt sounds reasonable to build on existing stuff (furthermore, the\nstring-list binary search is one I had missed).\n\nUsing string-lists here however will imply some tradeofs:\n\n* the additional char* pointer in every list element is possibly not\n  so high a price to pay\n\n* using the \"util\" pointer for the payload will make memory management\n  even more hairy (eg. \"util\" as a pointer to a struct which contains\n  a pointer to a diff_filespec).  Convenience wrappers will be highly\n  needed, and will also be required to keep calls to lookup/insert\n  readable, when the elements we deal with are not strings but indeed\n  the \"util\" stuff.\n\nAll in all, looks that the data-structure needed should have a higher\nfocus on the \"util\" field than string-list has.\n\nFeatures that seem to miss from string-list today (for the\n\"dir-rename\" series) include:\n\n* custom string-comparison function (ie. prefix comparison): that\n  would not be so difficult to generalize by adding a cmp_func\n  parameter to get_entry_index().  That would imply changing\n  widely-used API funcs like string_list_lookup() to shallow wrappers\n  around variants that also take a cmp_func argument.\n\n* lists indexed by 2 strings (bulkmove_candidates): could be replaced\n  by using string-lists of string-lists instead, but I'm not sure the\n  result would be that great\n\n\nI still have mixed feelings about all of this.\n\n-- \nYann\n"},{"id":"158741","messageId":"20101230004027.GB6639@home.lan","threadId":"26000","inReplyTo":"7vwrnhb6tm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/6] Introduce sorted-array binary-search function.","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-12-30T00:40:27Z","receivedAt":"2010-12-30T00:40:27Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Fri, Dec 10, 2010 at 02:29:09PM -0800, Junio C Hamano wrote:\n> Yann Dirson <ydirson@altern.org> writes:\n> \n> > +Suffix meanings are as follows:\n> > +\n> > +`check`::\n> > +...\n> > +* those defining the generic algorithms\n> \n> Yuck.\n> \n> All of these feel way overengineered and at the same time too rigid and\n> brittle.\n\nI confess a natural tendency towards overengineering stuff, but more\niterations usually help :).  Indeed, most of the\noverengineered-looking features added in the latest iterations are\nthings I already needed for the dir-rename series.\n\nAbout rigidity, well, it is already less rigid than a couple of the\nhardcoded implementations we have throughout the source, and as such\ncould be seen as an iterative step towards someting better - as I\nmentionned, my primary intent was to just get things useful for that\ndir-rename series, and at least on this point, I think the approach in\nthis series is not so bad.\n\nIt also looks generic enough to get the string-list lookup/insert\nfuncs use it, and this again does not look so bad to me, compared to\nthe stretching of the string-list API itself that would be required to\nmake it useful to the dir-rename stuff.\n\nAs for the \"brittle\" aspect, I'm not sure there is anything unfixable.\nAt the very least, more parentheses around the expnasion of macro args\nwould help making things more robust.\n\n> I have a suspicion that the \"convenience\" macros that generate many\n> functions and definitions are the main culprit.\n\nHm.  I was reluctant at first to use so many macros for an API,\nfearing it would confuse people (that resulted in the v5 API:\ngenericity made it too verbose to be useful).  Then I saw how many\nentry-points the linked-list API of the kernel has: that made me\nreconsider, and I found the result much more usable, although I had to\nwrite more doc.\n\n> For example, why do all the functions generated by a \"convenience\"\n> macro must share the same MAYBESTATIC?\n\nThe intention was that MAYBESTATIC only gets applied to the\nexplicitely-requested function, and that the transparently-generated\nones get \"static\".  Only declare_sorted_array_search_check() does not\nconform to that, that's a bug.  That also ought to be documented in\nthe API.\n\n> \"binsearch\" takes a comparison function pointer, and always\n> picks the midpoint, but what is the performance implication if we wanted\n> to use sorted-array.h to rewrite say sha1-lookup.c?\n\nAs I noted in the cover letter, I consider sha1-lookup.c too special.\nWhat it is not doing is not a conventional binary search, and this\nlooks out of scope.\n\n> How can an API user who wants to use\n> declare_sorted_array_insert_checkbook() easily figure out what other\n> macros fromt this family can be used without getting the same thing\n> generated twice?\n\nI have tried to make this explicit in the API reference, but things\ncan surely be made more clear by including examples.\n\n> If somebody wanted to have a sorted array in a\n> struct, it may be tempting to use declare_sorted_array() with an empty\n> MAYBESTATIC inside struct's field declaration (even when the struct itself\n> is static---which leaves a queasy feeling, but that is a separate issue),\n> and the _current_ macro definition of declare_sorted_array() may allow\n> such a usage work perfectly fine, but how can such an API user be rest\n> assured it won't break in later revisions of these macros?\n\nThat would only work by side-effect.  We can either decide to document\nit and make it part of the API if we feel it's worth it, or\nexplicitely state it is not supported (or enforce it: defining _nr and\n_alloc with =0 initializers would be a fairly good way of catching\nsuch attempts).\n\n\n> In addition, these macros in this patch are almost unreadable, but that\n> probably is mostly a fault of C's macro, not yours.\n\nYes.  When writing those I sorely missed the readability of C++\ntemplates - yuck :)\n\n-- \nYann\n"},{"id":"158743","messageId":"AANLkTimkemRW1H7XvwbECWUHHWVpGnvKukn06DiQO9Ce@mail.gmail.com","threadId":"26000","inReplyTo":"20101230004027.GB6639@home.lan","subject":"Re: [PATCH 1/6] Introduce sorted-array binary-search function.","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2010-12-30T01:06:28Z","receivedAt":"2010-12-30T01:06:28Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Thu, Dec 30, 2010 at 1:40 AM, Yann Dirson <ydirson@free.fr> wrote:\n> On Fri, Dec 10, 2010 at 02:29:09PM -0800, Junio C Hamano wrote:\n>> In addition, these macros in this patch are almost unreadable, but that\n>> probably is mostly a fault of C's macro, not yours.\n>\n> Yes.  When writing those I sorely missed the readability of C++\n> templates - yuck :)\n\nUnfortunately, it's something that ends up subtracting from the value\nof the change; a couple of duplicate functions is often easier to\nmaintain than nasty macros.\n\nPerhaps the pre-processor is not the right tool for the job? Some\ntimes a generator (a perl script?) can be more readable.\nUnfortunately, some times it's not :P\n"},{"id":"158751","messageId":"20101230104908.GB3296@home.lan","threadId":"26000","inReplyTo":"AANLkTimkemRW1H7XvwbECWUHHWVpGnvKukn06DiQO9Ce@mail.gmail.com","subject":"Re: [PATCH 1/6] Introduce sorted-array binary-search function.","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-12-30T10:49:08Z","receivedAt":"2010-12-30T10:49:08Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Thu, Dec 30, 2010 at 02:06:28AM +0100, Erik Faye-Lund wrote:\n> On Thu, Dec 30, 2010 at 1:40 AM, Yann Dirson <ydirson@free.fr> wrote:\n> > On Fri, Dec 10, 2010 at 02:29:09PM -0800, Junio C Hamano wrote:\n> >> In addition, these macros in this patch are almost unreadable, but that\n> >> probably is mostly a fault of C's macro, not yours.\n> >\n> > Yes.  When writing those I sorely missed the readability of C++\n> > templates - yuck :)\n> \n> Unfortunately, it's something that ends up subtracting from the value\n> of the change; a couple of duplicate functions is often easier to\n> maintain than nasty macros.\n\nWell, I don't find this one much less readable than, say, vcs-svn/trp.h\n\nAt least the declare_gen_* ones are quite readable.  Maybe making the\nmacro names shorter would help clarify the convenience wrappers ?\n"}]}