{"thread":{"id":"25646","subject":"[RFC PATCH] generalizing sorted-array handling","startedAt":"2010-11-04T20:33:11Z","lastAt":"2010-11-04T21:22:04Z","messageCount":8,"participants":["Yann Dirson","Jonathan Nieder"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"155201","messageId":"1288902795-8597-1-git-send-email-ydirson@altern.org","threadId":"25646","inReplyTo":null,"subject":"[RFC PATCH] generalizing sorted-array handling","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-04T20:33:11Z","receivedAt":"2010-11-04T20:33:11Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"While writing the bulk-move series, I introduced 2 new functions,\nlocate_bulkmove_candidate() and locate_rename_dst_dir(), closely\nderived from locate_rename_dst().  That was because it seemed not so\ntrivial to overcome the differences in those 3 funcs while retaining\nreadability.\n\nNow when working on bulk-rm (as a new basis for next-gen bulk-move), I\nfind myself in the need of adding more of them: again functions for\nsearching/inserting in a sorted list of various contents.  My first\napproach (this series) was to generalize locate_rename_dst() to\noperate on other \"lists of a filespec and something\", since that was\nmatching my needs for \"bulkrm_candidates\".\n\nTell me your opinion on this: I find the result hard to read, and\ndifficult to adapt to all of locate_rename_dst_dir() with its\nnon-filespec input, let alone locate_bulkmove_candidate() with 2 of\nthem.  And even the memset() call is probably less efficient than the\noriginal \"= NULL\".\n\nSo I'm planning of redoing the thing with a different principle:\nchange the core function to accept func-pointer for comparison and\ninitialization - that would make the core func much more readable.\nSince those trivial funcs would be trivial static ones, compilers\nought to be able to instantiate specific versions of the core func,\ninlining those trivial ones; if it does not, however, that would\nsurely give a performance penalty if it does not...\n\nThe alternative, having several mostly-identical funcs, which have to\nbe made generic anyway to prevent proliferation, seems to me much more\nof a hell.  What's the general opinion ?\n"},{"id":"155202","messageId":"1288902795-8597-2-git-send-email-ydirson@altern.org","threadId":"25646","inReplyTo":"1288902795-8597-1-git-send-email-ydirson@altern.org","subject":"[PATCH 1/4] Start to replace locate_rename_dst() with a generic function.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-04T20:33:12Z","receivedAt":"2010-11-04T20:33:12Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"First we introduce the trivial changes: replace hardcoded references to\nrename_dst_nr, rename_dst_alloc to parameters.\n\nSigned-off-by: Yann Dirson <ydirson@altern.org>\n---\n diffcore-rename.c |   25 ++++++++++++++++---------\n 1 files changed, 16 insertions(+), 9 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex df41be5..fc554e4 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,6 +6,10 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n \n+#define locate_element(list,elem,insert_ok)\t\t\t\\\n+\t_locate_element(elem, &list##_nr, &list##_alloc,\t\\\n+\t\t\tinsert_ok)\n+\n /* Table of rename/copy destinations */\n \n static struct diff_rename_dst {\n@@ -13,14 +17,17 @@ static struct diff_rename_dst {\n \tstruct diff_filepair *pair;\n } *rename_dst;\n static int rename_dst_nr, rename_dst_alloc;\n+#define locate_rename_dst(elem,insert_ok)\t\t\\\n+\tlocate_element(rename_dst, elem, insert_ok)\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 struct diff_rename_dst *_locate_element(struct diff_filespec *two,\n+\t\t\t\t\t       int *elem_nr_p, int *elem_alloc_p,\n+\t\t\t\t\t       int insert_ok)\n {\n \tint first, last;\n \n \tfirst = 0;\n-\tlast = rename_dst_nr;\n+\tlast = (*elem_nr_p);\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n \t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n@@ -37,15 +44,15 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\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+\tif ((*elem_alloc_p) <= (*elem_nr_p)) {\n+\t\t(*elem_alloc_p) = alloc_nr(*elem_alloc_p);\n \t\trename_dst = xrealloc(rename_dst,\n-\t\t\t\t      rename_dst_alloc * sizeof(*rename_dst));\n+\t\t\t\t      (*elem_alloc_p) * sizeof(*rename_dst));\n \t}\n-\trename_dst_nr++;\n-\tif (first < rename_dst_nr)\n+\t(*elem_nr_p)++;\n+\tif (first < (*elem_nr_p))\n \t\tmemmove(rename_dst + first + 1, rename_dst + first,\n-\t\t\t(rename_dst_nr - first - 1) * sizeof(*rename_dst));\n+\t\t\t((*elem_nr_p) - 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-- \n1.7.2.3\n"},{"id":"155203","messageId":"1288902795-8597-3-git-send-email-ydirson@altern.org","threadId":"25646","inReplyTo":"1288902795-8597-1-git-send-email-ydirson@altern.org","subject":"[PATCH 2/4] Abstract _locate_element() some more with elem_size parameter.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-04T20:33:13Z","receivedAt":"2010-11-04T20:33:13Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"Now offset calculations don't rely on pointer arithmetic any more, paving\nthe way for complete decoupling from diff_rename_dst.\n---\n diffcore-rename.c |   23 +++++++++++++----------\n 1 files changed, 13 insertions(+), 10 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex fc554e4..6e7ab4a 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -8,7 +8,7 @@\n \n #define locate_element(list,elem,insert_ok)\t\t\t\\\n \t_locate_element(elem, &list##_nr, &list##_alloc,\t\\\n-\t\t\tinsert_ok)\n+\t\t\tsizeof(*list), insert_ok)\n \n /* Table of rename/copy destinations */\n \n@@ -22,15 +22,16 @@ static int rename_dst_nr, rename_dst_alloc;\n \n static struct diff_rename_dst *_locate_element(struct diff_filespec *two,\n \t\t\t\t\t       int *elem_nr_p, int *elem_alloc_p,\n-\t\t\t\t\t       int insert_ok)\n+\t\t\t\t\t       size_t elem_size, int insert_ok)\n {\n \tint first, last;\n+\tstruct diff_rename_dst *first_elem_p;\n \n \tfirst = 0;\n \tlast = (*elem_nr_p);\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n-\t\tstruct diff_rename_dst *dst = &(rename_dst[next]);\n+\t\tstruct diff_rename_dst *dst = (void*)rename_dst + (next * elem_size);\n \t\tint cmp = strcmp(two->path, dst->two->path);\n \t\tif (!cmp)\n \t\t\treturn dst;\n@@ -47,16 +48,18 @@ static struct diff_rename_dst *_locate_element(struct diff_filespec *two,\n \tif ((*elem_alloc_p) <= (*elem_nr_p)) {\n \t\t(*elem_alloc_p) = alloc_nr(*elem_alloc_p);\n \t\trename_dst = xrealloc(rename_dst,\n-\t\t\t\t      (*elem_alloc_p) * sizeof(*rename_dst));\n+\t\t\t\t      (*elem_alloc_p) * elem_size);\n \t}\n \t(*elem_nr_p)++;\n+\tfirst_elem_p = (void*)rename_dst + first * elem_size;\n \tif (first < (*elem_nr_p))\n-\t\tmemmove(rename_dst + first + 1, rename_dst + first,\n-\t\t\t((*elem_nr_p) - 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+\t\tmemmove((void*)rename_dst + (first + 1) * elem_size,\n+\t\t\tfirst_elem_p,\n+\t\t\t((*elem_nr_p) - first - 1) * elem_size);\n+\tfirst_elem_p->two = alloc_filespec(two->path);\n+\tfill_filespec(first_elem_p->two, two->sha1, two->mode);\n+\tfirst_elem_p->pair = NULL;\n+\treturn first_elem_p;\n }\n \n /* Table of rename/copy src files */\n-- \n1.7.2.3\n"},{"id":"155204","messageId":"1288902795-8597-4-git-send-email-ydirson@altern.org","threadId":"25646","inReplyTo":"1288902795-8597-1-git-send-email-ydirson@altern.org","subject":"[PATCH 3/4] Introduce \"abstract class\" to make _locate_element() more independant of diff_rename_dst.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-04T20:33:14Z","receivedAt":"2010-11-04T20:33:14Z","isPatch":true,"sender":{"key":"ydirson@altern.org","avatar":"https://avatars.githubusercontent.com/u/1190950?v=4"},"body":"The dst_obj struct acts as an absract base class for the elements which\n_locate_element() manipulates arrays of.\n---\n diffcore-rename.c |   21 +++++++++++++--------\n 1 files changed, 13 insertions(+), 8 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 6e7ab4a..a674fbb 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -6,12 +6,16 @@\n #include \"diffcore.h\"\n #include \"hash.h\"\n \n+\n+/* \"Abstract class\" for lists of filespecs */\n+struct dst_obj {\n+\tstruct diff_filespec *two;\n+};\n #define locate_element(list,elem,insert_ok)\t\t\t\\\n \t_locate_element(elem, &list##_nr, &list##_alloc,\t\\\n \t\t\tsizeof(*list), insert_ok)\n \n-/* Table of rename/copy destinations */\n-\n+/* Table of rename/copy destinations, \"subclass\" of dst_obj */\n static struct diff_rename_dst {\n \tstruct diff_filespec *two;\n \tstruct diff_filepair *pair;\n@@ -20,18 +24,18 @@ static int rename_dst_nr, rename_dst_alloc;\n #define locate_rename_dst(elem,insert_ok)\t\t\\\n \tlocate_element(rename_dst, elem, insert_ok)\n \n-static struct diff_rename_dst *_locate_element(struct diff_filespec *two,\n-\t\t\t\t\t       int *elem_nr_p, int *elem_alloc_p,\n-\t\t\t\t\t       size_t elem_size, int insert_ok)\n+static void *_locate_element(struct diff_filespec *two,\n+\t\t\t     int *elem_nr_p, int *elem_alloc_p,\n+\t\t\t     size_t elem_size, int insert_ok)\n {\n \tint first, last;\n-\tstruct diff_rename_dst *first_elem_p;\n+\tstruct dst_obj *first_elem_p;\n \n \tfirst = 0;\n \tlast = (*elem_nr_p);\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n-\t\tstruct diff_rename_dst *dst = (void*)rename_dst + (next * elem_size);\n+\t\tstruct dst_obj *dst = (void*)rename_dst + (next * elem_size);\n \t\tint cmp = strcmp(two->path, dst->two->path);\n \t\tif (!cmp)\n \t\t\treturn dst;\n@@ -58,7 +62,8 @@ static struct diff_rename_dst *_locate_element(struct diff_filespec *two,\n \t\t\t((*elem_nr_p) - first - 1) * elem_size);\n \tfirst_elem_p->two = alloc_filespec(two->path);\n \tfill_filespec(first_elem_p->two, two->sha1, two->mode);\n-\tfirst_elem_p->pair = NULL;\n+\tmemset(((struct dst_obj *)first_elem_p) + 1, 0,\n+\t       elem_size - sizeof(struct dst_obj));\n \treturn first_elem_p;\n }\n \n-- \n1.7.2.3\n"},{"id":"155205","messageId":"1288902795-8597-5-git-send-email-ydirson@altern.org","threadId":"25646","inReplyTo":"1288902795-8597-1-git-send-email-ydirson@altern.org","subject":"[PATCH 4/4] Remove remaining rename_dst references in _locate_element() and pass a pointer to it.","fromName":"Yann Dirson","fromEmail":"ydirson@altern.org","sentAt":"2010-11-04T20:33:15Z","receivedAt":"2010-11-04T20:33:15Z","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 diffcore-rename.c |   15 +++++++--------\n 1 files changed, 7 insertions(+), 8 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex a674fbb..a4e0a96 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -11,8 +11,8 @@\n struct dst_obj {\n \tstruct diff_filespec *two;\n };\n-#define locate_element(list,elem,insert_ok)\t\t\t\\\n-\t_locate_element(elem, &list##_nr, &list##_alloc,\t\\\n+#define locate_element(list,elem,insert_ok)\t\t\t\t\\\n+\t_locate_element((void**)&list, elem, &list##_nr, &list##_alloc,\t\\\n \t\t\tsizeof(*list), insert_ok)\n \n /* Table of rename/copy destinations, \"subclass\" of dst_obj */\n@@ -24,7 +24,7 @@ static int rename_dst_nr, rename_dst_alloc;\n #define locate_rename_dst(elem,insert_ok)\t\t\\\n \tlocate_element(rename_dst, elem, insert_ok)\n \n-static void *_locate_element(struct diff_filespec *two,\n+static void *_locate_element(void **listp, struct diff_filespec *two,\n \t\t\t     int *elem_nr_p, int *elem_alloc_p,\n \t\t\t     size_t elem_size, int insert_ok)\n {\n@@ -35,7 +35,7 @@ static void *_locate_element(struct diff_filespec *two,\n \tlast = (*elem_nr_p);\n \twhile (last > first) {\n \t\tint next = (last + first) >> 1;\n-\t\tstruct dst_obj *dst = (void*)rename_dst + (next * elem_size);\n+\t\tstruct dst_obj *dst = *listp + (next * elem_size);\n \t\tint cmp = strcmp(two->path, dst->two->path);\n \t\tif (!cmp)\n \t\t\treturn dst;\n@@ -51,13 +51,12 @@ static void *_locate_element(struct diff_filespec *two,\n \t/* insert to make it at \"first\" */\n \tif ((*elem_alloc_p) <= (*elem_nr_p)) {\n \t\t(*elem_alloc_p) = alloc_nr(*elem_alloc_p);\n-\t\trename_dst = xrealloc(rename_dst,\n-\t\t\t\t      (*elem_alloc_p) * elem_size);\n+\t\t*listp = xrealloc(*listp, (*elem_alloc_p) * elem_size);\n \t}\n \t(*elem_nr_p)++;\n-\tfirst_elem_p = (void*)rename_dst + first * elem_size;\n+\tfirst_elem_p = *listp + first * elem_size;\n \tif (first < (*elem_nr_p))\n-\t\tmemmove((void*)rename_dst + (first + 1) * elem_size,\n+\t\tmemmove(*listp + (first + 1) * elem_size,\n \t\t\tfirst_elem_p,\n \t\t\t((*elem_nr_p) - first - 1) * elem_size);\n \tfirst_elem_p->two = alloc_filespec(two->path);\n-- \n1.7.2.3\n"},{"id":"155208","messageId":"20101104204555.GA18187@burratino","threadId":"25646","inReplyTo":"1288902795-8597-2-git-send-email-ydirson@altern.org","subject":"Re: [PATCH 1/4] Start to replace locate_rename_dst() with a generic function.","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-11-04T20:45:55Z","receivedAt":"2010-11-04T20:45:55Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Yann Dirson wrote:\n\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -6,6 +6,10 @@\n>  #include \"diffcore.h\"\n>  #include \"hash.h\"\n>  \n> +#define locate_element(list,elem,insert_ok)\t\t\t\\\n> +\t_locate_element(elem, &list##_nr, &list##_alloc,\t\\\n> +\t\t\tinsert_ok)\n> +\n\nIs this syntactic sugar needed?\n\n static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n\t\t\t\t\t\t  insert_ok)\n {\n\treturn locate_element(&rename_dst_nr, &rename_dst_alloc, elem, insert_ok);\n }\n\ntakes more advantage of the compiler's typechecking and looks easy\nenough to read.\n\nSince this is local to diffcore-rename, I don't mind the locate_element()\nname, but if this is to be used more widely I think it would need to be\nnamed more precisely.  (find_or_insert_in_array()?)\n\n> @@ -13,14 +17,17 @@ static struct diff_rename_dst {\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 struct diff_rename_dst *_locate_element(struct diff_filespec *two,\n> +\t\t\t\t\t       int *elem_nr_p, int *elem_alloc_p,\n> +\t\t\t\t\t       int insert_ok)\n>  {\n>  \tint first, last;\n>  \n>  \tfirst = 0;\n> -\tlast = rename_dst_nr;\n> +\tlast = (*elem_nr_p);\n\nI guess these parentheses came from search+replace?  It's more\nreadable without them.\n\n[...]\n> +\t(*elem_nr_p)++;\n\nExcept for this one.\n\nGenerally, the approach seems sane so far.\n"},{"id":"155211","messageId":"20101104205655.GB18187@burratino","threadId":"25646","inReplyTo":"1288902795-8597-4-git-send-email-ydirson@altern.org","subject":"Re: [PATCH 3/4] Introduce \"abstract class\" to make _locate_element() more independant of diff_rename_dst.","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-11-04T20:56:55Z","receivedAt":"2010-11-04T20:56:55Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Yann Dirson wrote:\n\n> --- a/diffcore-rename.c\n> +++ b/diffcore-rename.c\n> @@ -6,12 +6,16 @@\n>  #include \"diffcore.h\"\n>  #include \"hash.h\"\n>  \n> +\n> +/* \"Abstract class\" for lists of filespecs */\n> +struct dst_obj {\n> +\tstruct diff_filespec *two;\n> +};\n>  #define locate_element(list,elem,insert_ok)\t\t\t\\\n>  \t_locate_element(elem, &list##_nr, &list##_alloc,\t\\\n>  \t\t\tsizeof(*list), insert_ok)\n>  \n> -/* Table of rename/copy destinations */\n> -\n> +/* Table of rename/copy destinations, \"subclass\" of dst_obj */\n>  static struct diff_rename_dst {\n>  \tstruct diff_filespec *two;\n\nNit: language lawyers might be happier with:\n\n  struct dst_obj {\n\tstruct diff_filespec *spec\n  };\n  struct diff_rename_dst {\n\tstruct dst_obj two;\n\t...\n  };\n\nor\n\n  typedef struct diff_filespec *dst_obj;\n  struct diff_rename_dst {\n\tdst_obj two;\n\t...\n  };\n\nor\n\n  struct diff_rename_dst {\n\tstruct diff_filespec *two;\n\t...\n  };\n  ...\n  struct diff_filespec **dst = (const char *) rename_dst + next * elem_size;\n\nto avoid violating strict aliasing rules.\n\nMeanwhile, something like\n\n #define container_of(ptr, type, member) \\\n\t((type *)((char *) ptr - offsetof(type, member)))\n\ncan be useful for making the meaning more obvious when downcasting.\n"},{"id":"155216","messageId":"20101104212204.GC8911@home.lan","threadId":"25646","inReplyTo":"20101104204555.GA18187@burratino","subject":"Re: [PATCH 1/4] Start to replace locate_rename_dst() with a generic function.","fromName":"Yann Dirson","fromEmail":"ydirson@free.fr","sentAt":"2010-11-04T21:22:04Z","receivedAt":"2010-11-04T21:22:04Z","isPatch":true,"sender":{"key":"ydirson@free.fr","avatar":null},"body":"On Thu, Nov 04, 2010 at 03:45:55PM -0500, Jonathan Nieder wrote:\n>  static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,\n> \t\t\t\t\t\t  insert_ok)\n>  {\n> \treturn locate_element(&rename_dst_nr, &rename_dst_alloc, elem, insert_ok);\n>  }\n\nThe idea was to deprecate locate_rename_dst() itself and only use\nlocate_element()...\n\n> takes more advantage of the compiler's typechecking and looks easy\n> enough to read.\n\n... but typechecking was something that was worrying me here.  Looks\nlike a good idea, after all.\n\n\n> Since this is local to diffcore-rename, I don't mind the locate_element()\n> name, but if this is to be used more widely I think it would need to be\n> named more precisely.  (find_or_insert_in_array()?)\n\nYes - that's just a prototype.\n\n> I guess these parentheses came from search+replace?  It's more\n> readable without them.\n\nRight, many of them are superfluous.\n"}]}