{"thread":{"id":"25681","subject":"[PATCH v3] generalizing sorted-array handling","startedAt":"2010-11-08T22:38:59Z","lastAt":"2010-11-16T22:04:18Z","messageCount":6,"participants":["Yann Dirson","Junio C Hamano"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"155443","messageId":"1289255942-19705-1-git-send-email-ydirson@altern.org","threadId":"25681","inReplyTo":null,"subject":"[PATCH v3] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-08T22:38:59Z","receivedAt":"2010-11-08T22:38:59Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Changes from v2:\n\n* separated sorted-array type declaration from array declaration\n* proper typechecking (no reason for using void* for \"callback data\")\n* fixed coding style issues\n"},{"id":"155444","messageId":"1289255942-19705-2-git-send-email-ydirson@altern.org","threadId":"25681","inReplyTo":"1289255942-19705-1-git-send-email-ydirson@altern.org","subject":"[PATCH v3 1/3] Introduce sorted-array binary-search function.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-08T22:39:00Z","receivedAt":"2010-11-08T22:39:00Z","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, derived from locate_rename_dst()\nfrom diffcore-rename.c.  Thanks to Jonathan Nieder for this design idea.\n\nNaming is kept compatible with the original use of that function.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n Makefile          |    1 +\n diffcore-rename.c |   51 +++++++++++++--------------------------------------\n sorted-array.h    |   36 ++++++++++++++++++++++++++++++++++++\n 3 files changed, 50 insertions(+), 38 deletions(-)\n create mode 100644 sorted-array.h\n\ndiff --git a/Makefile b/Makefile\nindex 1f1ce04..fa5b2e6 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -536,6 +536,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/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..1626bdc 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,52 +5,27 @@\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+\t\t     rename_dst_cmp, rename_dst_init)\n \n /* Table of rename/copy src files */\n static struct diff_rename_src {\ndiff --git a/sorted-array.h b/sorted-array.h\nnew file mode 100644\nindex 0000000..03d5d1e\n--- /dev/null\n+++ b/sorted-array.h\n@@ -0,0 +1,36 @@\n+#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,LIST,CMP,INIT)\t\\\n+MAYBESTATIC ELEMTYPE *LIST;\t\t\t\t\t\t\\\n+MAYBESTATIC int LIST##_nr, LIST##_alloc;\t\t\t\t\\\n+MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\tint first, last;\t\t\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\t\\\n+\tfirst = 0;\t\t\t\t\t\t\t\\\n+\tlast = LIST##_nr;\t\t\t\t\t\t\\\n+\twhile (last > first) {\t\t\t\t\t\t\\\n+\t\tint next = (last + first) >> 1;\t\t\t\t\\\n+\t\tELEMTYPE *nextelem = &(LIST[next]);\t\t\t\\\n+\t\tint cmp = CMP(data, nextelem);\t\t\t\t\\\n+\t\tif (!cmp)\t\t\t\t\t\t\\\n+\t\t\treturn nextelem;\t\t\t\t\\\n+\t\tif (cmp < 0) {\t\t\t\t\t\t\\\n+\t\t\tlast = next;\t\t\t\t\t\\\n+\t\t\tcontinue;\t\t\t\t\t\\\n+\t\t}\t\t\t\t\t\t\t\\\n+\t\tfirst = next+1;\t\t\t\t\t\t\\\n+\t}\t\t\t\t\t\t\t\t\\\n+\t/* not found */\t\t\t\t\t\t\t\\\n+\tif (!insert_ok)\t\t\t\t\t\t\t\\\n+\t\treturn NULL;\t\t\t\t\t\t\\\n+\t/* insert to make it at \"first\" */\t\t\t\t\\\n+\tif (LIST##_alloc <= LIST##_nr) {\t\t\t\t\\\n+\t\tLIST##_alloc = alloc_nr(LIST##_alloc);\t\t\t\\\n+\t\tLIST = xrealloc(LIST, LIST##_alloc * sizeof(*LIST));\t\\\n+\t}\t\t\t\t\t\t\t\t\\\n+\tLIST##_nr++;\t\t\t\t\t\t\t\\\n+\tif (first < LIST##_nr)\t\t\t\t\t\t\\\n+\t\tmemmove(LIST + first + 1, LIST + first,\t\t\t\\\n+\t\t\t(LIST##_nr - first - 1) * sizeof(*LIST));\t\\\n+\tINIT(&LIST[first], data);\t\t\t\t\t\\\n+\treturn &(LIST[first]);\t\t\t\t\t\t\\\n+}\n-- \n1.7.2.3\n"},{"id":"155445","messageId":"1289255942-19705-3-git-send-email-ydirson@altern.org","threadId":"25681","inReplyTo":"1289255942-19705-1-git-send-email-ydirson@altern.org","subject":"[PATCH v3 2/3] Separate sorted-array type declaration from array declaration.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-08T22:39:01Z","receivedAt":"2010-11-08T22:39:01Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Instead of a single locate() function hardcoding references to a fixed\narray, we declare a generic function taking references to the array and\nits metadata.  Declaring an array produces a lightweight wrapper for\nthis specific array, not modifying calling API any further and keeping\nit readable.\n\nThis will allow to declare several arrays of the same type without\ncausing duplication of the locate function.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n diffcore-rename.c |    5 +++--\n sorted-array.h    |   39 ++++++++++++++++++++++++---------------\n 2 files changed, 27 insertions(+), 17 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 1626bdc..a146adf 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -24,8 +24,9 @@ static void rename_dst_init(struct diff_rename_dst *elem, struct diff_filespec *\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-\t\t     rename_dst_cmp, rename_dst_init)\n+declare_sorted_array_type(static, struct diff_rename_dst, rename_dst,\n+\t\t\t  rename_dst_cmp, rename_dst_init);\n+declare_sorted_array(static, struct diff_rename_dst, rename_dst, rename_dst);\n \n /* Table of rename/copy src files */\n static struct diff_rename_src {\ndiff --git a/sorted-array.h b/sorted-array.h\nindex 03d5d1e..54fad20 100644\n--- a/sorted-array.h\n+++ b/sorted-array.h\n@@ -1,15 +1,15 @@\n-#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,LIST,CMP,INIT)\t\\\n-MAYBESTATIC ELEMTYPE *LIST;\t\t\t\t\t\t\\\n-MAYBESTATIC int LIST##_nr, LIST##_alloc;\t\t\t\t\\\n-MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\t\t\\\n+#define declare_sorted_array_type(MAYBESTATIC,ELEMTYPE,TYPENICK,CMP,INIT) \\\n+MAYBESTATIC ELEMTYPE *locate_type_##TYPENICK(\t\t\t\t\\\n+\tELEMTYPE **list_p, int *list_nr_p, int *list_nr_alloc,\t\t\\\n+\tvoid *data, int insert_ok)\t\t\t\t\t\\\n {\t\t\t\t\t\t\t\t\t\\\n \tint first, last;\t\t\t\t\t\t\\\n \t\t\t\t\t\t\t\t\t\\\n \tfirst = 0;\t\t\t\t\t\t\t\\\n-\tlast = LIST##_nr;\t\t\t\t\t\t\\\n+\tlast = *list_nr_p;\t\t\t\t\t\t\\\n \twhile (last > first) {\t\t\t\t\t\t\\\n \t\tint next = (last + first) >> 1;\t\t\t\t\\\n-\t\tELEMTYPE *nextelem = &(LIST[next]);\t\t\t\\\n+\t\tELEMTYPE *nextelem = &((*list_p)[next]);\t\t\\\n \t\tint cmp = CMP(data, nextelem);\t\t\t\t\\\n \t\tif (!cmp)\t\t\t\t\t\t\\\n \t\t\treturn nextelem;\t\t\t\t\\\n@@ -23,14 +23,23 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\t\t\\\n \tif (!insert_ok)\t\t\t\t\t\t\t\\\n \t\treturn NULL;\t\t\t\t\t\t\\\n \t/* insert to make it at \"first\" */\t\t\t\t\\\n-\tif (LIST##_alloc <= LIST##_nr) {\t\t\t\t\\\n-\t\tLIST##_alloc = alloc_nr(LIST##_alloc);\t\t\t\\\n-\t\tLIST = xrealloc(LIST, LIST##_alloc * sizeof(*LIST));\t\\\n+\tif (*list_nr_alloc <= *list_nr_p) {\t\t\t\t\\\n+\t\t(*list_nr_alloc) = alloc_nr((*list_nr_alloc));\t\t\\\n+\t\t*list_p = xrealloc(*list_p, (*list_nr_alloc) * sizeof(**list_p)); \\\n \t}\t\t\t\t\t\t\t\t\\\n-\tLIST##_nr++;\t\t\t\t\t\t\t\\\n-\tif (first < LIST##_nr)\t\t\t\t\t\t\\\n-\t\tmemmove(LIST + first + 1, LIST + first,\t\t\t\\\n-\t\t\t(LIST##_nr - first - 1) * sizeof(*LIST));\t\\\n-\tINIT(&LIST[first], data);\t\t\t\t\t\\\n-\treturn &(LIST[first]);\t\t\t\t\t\t\\\n+\t(*list_nr_p)++;\t\t\t\t\t\t\t\\\n+\tif (first < *list_nr_p)\t\t\t\t\t\t\\\n+\t\tmemmove(*list_p + first + 1, *list_p + first,\t\t\\\n+\t\t\t(*list_nr_p - first - 1) * sizeof(**list_p));\t\\\n+\tINIT(&(*list_p)[first], data);\t\t\t\t\t\\\n+\treturn &((*list_p)[first]);\t\t\t\t\t\\\n+}\n+\n+#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,TYPENICK,LIST)\t\\\n+MAYBESTATIC ELEMTYPE *LIST;\t\t\t\t\t\t\\\n+MAYBESTATIC int LIST##_nr, LIST##_alloc;\t\t\t\t\\\n+MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\t\t\\\n+{\t\t\t\t\t\t\t\t\t\\\n+\treturn locate_type_##TYPENICK(&LIST, &LIST##_nr, &LIST##_alloc,\t\\\n+\t\t\t\t data, insert_ok);\t\t\t\\\n }\n-- \n1.7.2.3\n"},{"id":"155446","messageId":"1289255942-19705-4-git-send-email-ydirson@altern.org","threadId":"25681","inReplyTo":"1289255942-19705-1-git-send-email-ydirson@altern.org","subject":"[PATCH v3 3/3] Convert diffcore-rename's rename_src to the new sorted-array API.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-08T22:39:02Z","receivedAt":"2010-11-08T22:39:02Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Alas, this time we could not keep the same prototype :)\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n diffcore-rename.c |   52 +++++++++++++++-------------------------------------\n 1 files changed, 15 insertions(+), 37 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex a146adf..6fa347e 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -29,46 +29,24 @@ declare_sorted_array_type(static, struct diff_rename_dst, rename_dst,\n declare_sorted_array(static, struct diff_rename_dst, rename_dst, rename_dst);\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_type(static, struct diff_rename_src, rename_src,\n+\t\t\t  rename_src_cmp, rename_src_init);\n+declare_sorted_array(static, struct diff_rename_src, rename_src, rename_src);\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n {\n@@ -425,7 +403,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\tlocate_rename_src(p, 1);\n \t\t}\n \t\telse if (detect_rename == DIFF_DETECT_COPY) {\n \t\t\t/*\n@@ -433,7 +411,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\tlocate_rename_src(p, 1);\n \t\t}\n \t}\n \tif (rename_dst_nr == 0 || rename_src_nr == 0)\n-- \n1.7.2.3\n"},{"id":"156001","messageId":"7vy68ti3gr.fsf@alter.siamese.dyndns.org","threadId":"25681","inReplyTo":"1289255942-19705-2-git-send-email-ydirson@altern.org","subject":"Re: [PATCH v3 1/3] Introduce sorted-array binary-search function.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-11-16T17:27:16Z","receivedAt":"2010-11-16T17:27:16Z","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> We use a cpp-based template mechanism to declare the array and its\n> management data, as well as a search function, derived from locate_rename_dst()\n> from diffcore-rename.c.  Thanks to Jonathan Nieder for this design idea.\n\nHmmm.... Yet another binary search...\n\nCan we generalize the existing ones first before adding any of this in\n(hint: look for \"git grep -w -e hi --and -e lo\")?\n"},{"id":"156024","messageId":"20101116220418.GA3187@home.lan","threadId":"25681","inReplyTo":"7vy68ti3gr.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v3 1/3] Introduce sorted-array binary-search function.","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-11-16T22:04:18Z","receivedAt":"2010-11-16T22:04:18Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Tue, Nov 16, 2010 at 09:27:16AM -0800, Junio C Hamano wrote:\n> Yann Dirson <ydirson@altern.org> writes:\n> \n> > We use a cpp-based template mechanism to declare the array and its\n> > management data, as well as a search function, derived from locate_rename_dst()\n> > from diffcore-rename.c.  Thanks to Jonathan Nieder for this design idea.\n> \n> Hmmm.... Yet another binary search...\n\nWell, not exactly another, it still generalizes code that was already here.\n\n> Can we generalize the existing ones first before adding any of this in\n> (hint: look for \"git grep -w -e hi --and -e lo\")?\n\nWith great pleasure.  I have simply missed those, only looking for the\npattern used in diffcore-rename.\n\nLooking at a few ones, that seems just a matter of:\n* refreshing my \"[RFC] Add a sorted-list API for use-cases that\n  require to get the element index.\" from v2 series\n* adding support for more than one func, which I already required for\n  bulk-rename\n"}]}