[RFC PATCH] generalizing sorted-array handling

[RFC PATCH] generalizing sorted-array handling

[Yann Dirson]

While writing the bulk-move series, I introduced 2 new functions,
locate_bulkmove_candidate() and locate_rename_dst_dir(), closely
derived from locate_rename_dst().  That was because it seemed not so
trivial to overcome the differences in those 3 funcs while retaining
readability.

Now when working on bulk-rm (as a new basis for next-gen bulk-move), I
find myself in the need of adding more of them: again functions for
searching/inserting in a sorted list of various contents.  My first
approach (this series) was to generalize locate_rename_dst() to
operate on other "lists of a filespec and something", since that was
matching my needs for "bulkrm_candidates".

Tell me your opinion on this: I find the result hard to read, and
difficult to adapt to all of locate_rename_dst_dir() with its
non-filespec input, let alone locate_bulkmove_candidate() with 2 of
them.  And even the memset() call is probably less efficient than the
original "= NULL".

So I'm planning of redoing the thing with a different principle:
change the core function to accept func-pointer for comparison and
initialization - that would make the core func much more readable.
Since those trivial funcs would be trivial static ones, compilers
ought to be able to instantiate specific versions of the core func,
inlining those trivial ones; if it does not, however, that would
surely give a performance penalty if it does not...

The alternative, having several mostly-identical funcs, which have to
be made generic anyway to prevent proliferation, seems to me much more
of a hell.  What's the general opinion ?

[PATCH 1/4] Start to replace locate_rename_dst() with a generic function.

[Yann Dirson]

First we introduce the trivial changes: replace hardcoded references to
rename_dst_nr, rename_dst_alloc to parameters.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 diffcore-rename.c |   25 ++++++++++++++++---------
 1 files changed, 16 insertions(+), 9 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index df41be5..fc554e4 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -6,6 +6,10 @@
 #include "diffcore.h"
 #include "hash.h"
 
+#define locate_element(list,elem,insert_ok)			\
+	_locate_element(elem, &list##_nr, &list##_alloc,	\
+			insert_ok)
+
 /* Table of rename/copy destinations */
 
 static struct diff_rename_dst {
@@ -13,14 +17,17 @@ static struct diff_rename_dst {
 	struct diff_filepair *pair;
 } *rename_dst;
 static int rename_dst_nr, rename_dst_alloc;
+#define locate_rename_dst(elem,insert_ok)		\
+	locate_element(rename_dst, elem, insert_ok)
 
-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
-						 int insert_ok)
+static struct diff_rename_dst *_locate_element(struct diff_filespec *two,
+					       int *elem_nr_p, int *elem_alloc_p,
+					       int insert_ok)
 {
 	int first, last;
 
 	first = 0;
-	last = rename_dst_nr;
+	last = (*elem_nr_p);
 	while (last > first) {
 		int next = (last + first) >> 1;
 		struct diff_rename_dst *dst = &(rename_dst[next]);
@@ -37,15 +44,15 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
 	if (!insert_ok)
 		return NULL;
 	/* insert to make it at "first" */
-	if (rename_dst_alloc <= rename_dst_nr) {
-		rename_dst_alloc = alloc_nr(rename_dst_alloc);
+	if ((*elem_alloc_p) <= (*elem_nr_p)) {
+		(*elem_alloc_p) = alloc_nr(*elem_alloc_p);
 		rename_dst = xrealloc(rename_dst,
-				      rename_dst_alloc * sizeof(*rename_dst));
+				      (*elem_alloc_p) * sizeof(*rename_dst));
 	}
-	rename_dst_nr++;
-	if (first < rename_dst_nr)
+	(*elem_nr_p)++;
+	if (first < (*elem_nr_p))
 		memmove(rename_dst + first + 1, rename_dst + first,
-			(rename_dst_nr - first - 1) * sizeof(*rename_dst));
+			((*elem_nr_p) - first - 1) * sizeof(*rename_dst));
 	rename_dst[first].two = alloc_filespec(two->path);
 	fill_filespec(rename_dst[first].two, two->sha1, two->mode);
 	rename_dst[first].pair = NULL;
-- 
1.7.2.3

[PATCH 2/4] Abstract _locate_element() some more with elem_size parameter.

[Yann Dirson]

Now offset calculations don't rely on pointer arithmetic any more, paving
the way for complete decoupling from diff_rename_dst.
---
 diffcore-rename.c |   23 +++++++++++++----------
 1 files changed, 13 insertions(+), 10 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index fc554e4..6e7ab4a 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -8,7 +8,7 @@
 
 #define locate_element(list,elem,insert_ok)			\
 	_locate_element(elem, &list##_nr, &list##_alloc,	\
-			insert_ok)
+			sizeof(*list), insert_ok)
 
 /* Table of rename/copy destinations */
 
@@ -22,15 +22,16 @@ static int rename_dst_nr, rename_dst_alloc;
 
 static struct diff_rename_dst *_locate_element(struct diff_filespec *two,
 					       int *elem_nr_p, int *elem_alloc_p,
-					       int insert_ok)
+					       size_t elem_size, int insert_ok)
 {
 	int first, last;
+	struct diff_rename_dst *first_elem_p;
 
 	first = 0;
 	last = (*elem_nr_p);
 	while (last > first) {
 		int next = (last + first) >> 1;
-		struct diff_rename_dst *dst = &(rename_dst[next]);
+		struct diff_rename_dst *dst = (void*)rename_dst + (next * elem_size);
 		int cmp = strcmp(two->path, dst->two->path);
 		if (!cmp)
 			return dst;
@@ -47,16 +48,18 @@ static struct diff_rename_dst *_locate_element(struct diff_filespec *two,
 	if ((*elem_alloc_p) <= (*elem_nr_p)) {
 		(*elem_alloc_p) = alloc_nr(*elem_alloc_p);
 		rename_dst = xrealloc(rename_dst,
-				      (*elem_alloc_p) * sizeof(*rename_dst));
+				      (*elem_alloc_p) * elem_size);
 	}
 	(*elem_nr_p)++;
+	first_elem_p = (void*)rename_dst + first * elem_size;
 	if (first < (*elem_nr_p))
-		memmove(rename_dst + first + 1, rename_dst + first,
-			((*elem_nr_p) - first - 1) * sizeof(*rename_dst));
-	rename_dst[first].two = alloc_filespec(two->path);
-	fill_filespec(rename_dst[first].two, two->sha1, two->mode);
-	rename_dst[first].pair = NULL;
-	return &(rename_dst[first]);
+		memmove((void*)rename_dst + (first + 1) * elem_size,
+			first_elem_p,
+			((*elem_nr_p) - first - 1) * elem_size);
+	first_elem_p->two = alloc_filespec(two->path);
+	fill_filespec(first_elem_p->two, two->sha1, two->mode);
+	first_elem_p->pair = NULL;
+	return first_elem_p;
 }
 
 /* Table of rename/copy src files */
-- 
1.7.2.3

[PATCH 3/4] Introduce "abstract class" to make _locate_element() more independant of diff_rename_dst.

[Yann Dirson]

The dst_obj struct acts as an absract base class for the elements which
_locate_element() manipulates arrays of.
---
 diffcore-rename.c |   21 +++++++++++++--------
 1 files changed, 13 insertions(+), 8 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 6e7ab4a..a674fbb 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -6,12 +6,16 @@
 #include "diffcore.h"
 #include "hash.h"
 
+
+/* "Abstract class" for lists of filespecs */
+struct dst_obj {
+	struct diff_filespec *two;
+};
 #define locate_element(list,elem,insert_ok)			\
 	_locate_element(elem, &list##_nr, &list##_alloc,	\
 			sizeof(*list), insert_ok)
 
-/* Table of rename/copy destinations */
-
+/* Table of rename/copy destinations, "subclass" of dst_obj */
 static struct diff_rename_dst {
 	struct diff_filespec *two;
 	struct diff_filepair *pair;
@@ -20,18 +24,18 @@ static int rename_dst_nr, rename_dst_alloc;
 #define locate_rename_dst(elem,insert_ok)		\
 	locate_element(rename_dst, elem, insert_ok)
 
-static struct diff_rename_dst *_locate_element(struct diff_filespec *two,
-					       int *elem_nr_p, int *elem_alloc_p,
-					       size_t elem_size, int insert_ok)
+static void *_locate_element(struct diff_filespec *two,
+			     int *elem_nr_p, int *elem_alloc_p,
+			     size_t elem_size, int insert_ok)
 {
 	int first, last;
-	struct diff_rename_dst *first_elem_p;
+	struct dst_obj *first_elem_p;
 
 	first = 0;
 	last = (*elem_nr_p);
 	while (last > first) {
 		int next = (last + first) >> 1;
-		struct diff_rename_dst *dst = (void*)rename_dst + (next * elem_size);
+		struct dst_obj *dst = (void*)rename_dst + (next * elem_size);
 		int cmp = strcmp(two->path, dst->two->path);
 		if (!cmp)
 			return dst;
@@ -58,7 +62,8 @@ static struct diff_rename_dst *_locate_element(struct diff_filespec *two,
 			((*elem_nr_p) - first - 1) * elem_size);
 	first_elem_p->two = alloc_filespec(two->path);
 	fill_filespec(first_elem_p->two, two->sha1, two->mode);
-	first_elem_p->pair = NULL;
+	memset(((struct dst_obj *)first_elem_p) + 1, 0,
+	       elem_size - sizeof(struct dst_obj));
 	return first_elem_p;
 }
 
-- 
1.7.2.3

[PATCH 4/4] Remove remaining rename_dst references in _locate_element() and pass a pointer to it.

[Yann Dirson]

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 diffcore-rename.c |   15 +++++++--------
 1 files changed, 7 insertions(+), 8 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index a674fbb..a4e0a96 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -11,8 +11,8 @@
 struct dst_obj {
 	struct diff_filespec *two;
 };
-#define locate_element(list,elem,insert_ok)			\
-	_locate_element(elem, &list##_nr, &list##_alloc,	\
+#define locate_element(list,elem,insert_ok)				\
+	_locate_element((void**)&list, elem, &list##_nr, &list##_alloc,	\
 			sizeof(*list), insert_ok)
 
 /* Table of rename/copy destinations, "subclass" of dst_obj */
@@ -24,7 +24,7 @@ static int rename_dst_nr, rename_dst_alloc;
 #define locate_rename_dst(elem,insert_ok)		\
 	locate_element(rename_dst, elem, insert_ok)
 
-static void *_locate_element(struct diff_filespec *two,
+static void *_locate_element(void **listp, struct diff_filespec *two,
 			     int *elem_nr_p, int *elem_alloc_p,
 			     size_t elem_size, int insert_ok)
 {
@@ -35,7 +35,7 @@ static void *_locate_element(struct diff_filespec *two,
 	last = (*elem_nr_p);
 	while (last > first) {
 		int next = (last + first) >> 1;
-		struct dst_obj *dst = (void*)rename_dst + (next * elem_size);
+		struct dst_obj *dst = *listp + (next * elem_size);
 		int cmp = strcmp(two->path, dst->two->path);
 		if (!cmp)
 			return dst;
@@ -51,13 +51,12 @@ static void *_locate_element(struct diff_filespec *two,
 	/* insert to make it at "first" */
 	if ((*elem_alloc_p) <= (*elem_nr_p)) {
 		(*elem_alloc_p) = alloc_nr(*elem_alloc_p);
-		rename_dst = xrealloc(rename_dst,
-				      (*elem_alloc_p) * elem_size);
+		*listp = xrealloc(*listp, (*elem_alloc_p) * elem_size);
 	}
 	(*elem_nr_p)++;
-	first_elem_p = (void*)rename_dst + first * elem_size;
+	first_elem_p = *listp + first * elem_size;
 	if (first < (*elem_nr_p))
-		memmove((void*)rename_dst + (first + 1) * elem_size,
+		memmove(*listp + (first + 1) * elem_size,
 			first_elem_p,
 			((*elem_nr_p) - first - 1) * elem_size);
 	first_elem_p->two = alloc_filespec(two->path);
-- 
1.7.2.3

Re: [PATCH 1/4] Start to replace locate_rename_dst() with a generic function.

[Jonathan Nieder]

Yann Dirson wrote:

> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -6,6 +6,10 @@
>  #include "diffcore.h"
>  #include "hash.h"
>  
> +#define locate_element(list,elem,insert_ok)			\
> +	_locate_element(elem, &list##_nr, &list##_alloc,	\
> +			insert_ok)
> +

Is this syntactic sugar needed?

 static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
						  insert_ok)
 {
	return locate_element(&rename_dst_nr, &rename_dst_alloc, elem, insert_ok);
 }

takes more advantage of the compiler's typechecking and looks easy
enough to read.

Since this is local to diffcore-rename, I don't mind the locate_element()
name, but if this is to be used more widely I think it would need to be
named more precisely.  (find_or_insert_in_array()?)

> @@ -13,14 +17,17 @@ static struct diff_rename_dst {
[...]
> -static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
> -						 int insert_ok)
> +static struct diff_rename_dst *_locate_element(struct diff_filespec *two,
> +					       int *elem_nr_p, int *elem_alloc_p,
> +					       int insert_ok)
>  {
>  	int first, last;
>  
>  	first = 0;
> -	last = rename_dst_nr;
> +	last = (*elem_nr_p);

I guess these parentheses came from search+replace?  It's more
readable without them.

[...]
> +	(*elem_nr_p)++;

Except for this one.

Generally, the approach seems sane so far.

Re: [PATCH 3/4] Introduce "abstract class" to make _locate_element() more independant of diff_rename_dst.

[Jonathan Nieder]

Yann Dirson wrote:

> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -6,12 +6,16 @@
>  #include "diffcore.h"
>  #include "hash.h"
>  
> +
> +/* "Abstract class" for lists of filespecs */
> +struct dst_obj {
> +	struct diff_filespec *two;
> +};
>  #define locate_element(list,elem,insert_ok)			\
>  	_locate_element(elem, &list##_nr, &list##_alloc,	\
>  			sizeof(*list), insert_ok)
>  
> -/* Table of rename/copy destinations */
> -
> +/* Table of rename/copy destinations, "subclass" of dst_obj */
>  static struct diff_rename_dst {
>  	struct diff_filespec *two;

Nit: language lawyers might be happier with:

  struct dst_obj {
	struct diff_filespec *spec
  };
  struct diff_rename_dst {
	struct dst_obj two;
	...
  };

or

  typedef struct diff_filespec *dst_obj;
  struct diff_rename_dst {
	dst_obj two;
	...
  };

or

  struct diff_rename_dst {
	struct diff_filespec *two;
	...
  };
  ...
  struct diff_filespec **dst = (const char *) rename_dst + next * elem_size;

to avoid violating strict aliasing rules.

Meanwhile, something like

 #define container_of(ptr, type, member) \
	((type *)((char *) ptr - offsetof(type, member)))

can be useful for making the meaning more obvious when downcasting.

Re: [PATCH 1/4] Start to replace locate_rename_dst() with a generic function.

[Yann Dirson]

On Thu, Nov 04, 2010 at 03:45:55PM -0500, Jonathan Nieder wrote:
>  static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
> 						  insert_ok)
>  {
> 	return locate_element(&rename_dst_nr, &rename_dst_alloc, elem, insert_ok);
>  }

The idea was to deprecate locate_rename_dst() itself and only use
locate_element()...

> takes more advantage of the compiler's typechecking and looks easy
> enough to read.

... but typechecking was something that was worrying me here.  Looks
like a good idea, after all.


> Since this is local to diffcore-rename, I don't mind the locate_element()
> name, but if this is to be used more widely I think it would need to be
> named more precisely.  (find_or_insert_in_array()?)

Yes - that's just a prototype.

> I guess these parentheses came from search+replace?  It's more
> readable without them.

Right, many of them are superfluous.