{"thread":{"id":"25656","subject":"[PATCH v2] generalizing sorted-array handling","startedAt":"2010-11-06T21:00:32Z","lastAt":"2010-11-06T21:00:35Z","messageCount":4,"participants":["Yann Dirson"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"155302","messageId":"1289077235-3208-1-git-send-email-ydirson@altern.org","threadId":"25656","inReplyTo":null,"subject":"[PATCH v2] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-06T21:00:32Z","receivedAt":"2010-11-06T21:00:32Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"This is a complete rewrite of the previous series, following a\nsuggestion by Jonathan Nieder.  It is much more generic than the\nprevious one, and removes existing duplicated code in diffcore-rename.\n\nI also had a quick look at other binary-search occurences in the code\nthat would share the same search code.  That revealed\nindex_name_pos(): not sure it is a good idea to make it use this API -\nit would require changes all over the code.  I still include a\npossibly-useful additional API for similar cases.\n"},{"id":"155303","messageId":"1289077235-3208-2-git-send-email-ydirson@altern.org","threadId":"25656","inReplyTo":"1289077235-3208-1-git-send-email-ydirson@altern.org","subject":"[PATCH v2 1/3] Introduce sorted-array binary-search function.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-06T21:00:33Z","receivedAt":"2010-11-06T21:00:33Z","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.  Naming is kept compatible with the original use\nof that function.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n Makefile          |    1 +\n diffcore-rename.c |   53 +++++++++++++++--------------------------------------\n sorted-array.h    |   36 ++++++++++++++++++++++++++++++++++++\n 3 files changed, 52 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..72a9b94 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -5,52 +5,29 @@\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(void* data, 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+\tstruct diff_filespec *two = data;\n+\treturn strcmp(two->path, elem->two->path);\n+}\n+static void rename_dst_init(struct diff_rename_dst *elem, void* data)\n+{\n+\tstruct diff_filespec *two = data;\n+\telem->two = alloc_filespec(two->path);\n+\tfill_filespec(elem->two, two->sha1, two->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":"155305","messageId":"1289077235-3208-3-git-send-email-ydirson@altern.org","threadId":"25656","inReplyTo":"1289077235-3208-1-git-send-email-ydirson@altern.org","subject":"[PATCH v2 2/3] Convert diffcore-rename's rename_src to the new sorted-array API.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-06T21:00:34Z","receivedAt":"2010-11-06T21:00:34Z","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 |   53 ++++++++++++++++-------------------------------------\n 1 files changed, 16 insertions(+), 37 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 72a9b94..ec40cf7 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -30,46 +30,25 @@ 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 {\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(void* data, 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+\tstruct diff_filepair *p = data;\n+\treturn strcmp(p->one->path, elem->one->path);\n+}\n+static void rename_src_init(struct diff_rename_src *elem, void* data)\n+{\n+\tstruct diff_filepair *p = data;\n+\telem->one = p->one;\n+\telem->score = p->score;\n }\n+declare_sorted_array(static, struct diff_rename_src, rename_src,\n+\t\t     rename_src_cmp, rename_src_init)\n \n static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)\n {\n@@ -426,7 +405,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@@ -434,7 +413,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":"155304","messageId":"1289077235-3208-4-git-send-email-ydirson@altern.org","threadId":"25656","inReplyTo":"1289077235-3208-1-git-send-email-ydirson@altern.org","subject":"[PATCH v2 3/3] [RFC] Add a sorted-list API for use-cases that require to get the element index.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-06T21:00:35Z","receivedAt":"2010-11-06T21:00:35Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"The idea was to replace index_name_pos(), but that would require a much\nlarger API change in callers.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n sorted-array.h |   15 +++++++++++----\n 1 files changed, 11 insertions(+), 4 deletions(-)\n\ndiff --git a/sorted-array.h b/sorted-array.h\nindex 03d5d1e..df07687 100644\n--- a/sorted-array.h\n+++ b/sorted-array.h\n@@ -1,7 +1,7 @@\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+MAYBESTATIC int locate_##LIST##_idx(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@@ -12,7 +12,7 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\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\t\treturn next;\t\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@@ -21,7 +21,7 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\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\treturn -first-1;\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@@ -32,5 +32,12 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)\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+\treturn first;\t\t\t\t\t\t\t\\\n+}\t\t\t\t\t\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 idx = locate_##LIST##_idx(data, insert_ok);\t\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-- \n1.7.2.3\n"}]}