threads / rfc / 25646

RFC patchgeneralizing sorted-array handling

Subject: [RFC PATCH] generalizing sorted-array handling

## tl;dr

8 messages between Nov 4, 2010 and Nov 4, 2010. Diffs are folded; open one to read it.

replies: 7people: 3as markdown or json

Yann Dirson· Nov 4, 2010, 20:33 UTC · lore

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 ?

Yann Dirson· Nov 4, 2010, 20:33 UTC · re: Yann Dirson · lore

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

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(-)
Show changes to diffcore-rename.c +16 −9
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
Jonathan Nieder· Nov 4, 2010, 20:45 UTC · re: Yann Dirson · lore

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

Yann Dirson wrote:
Show 10 quoted lines
> --- 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 {
[...]
Show 11 quoted lines
> -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.
Yann Dirson· Nov 4, 2010, 21:22 UTC · re: Jonathan Nieder · lore

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

On Thu, Nov 04, 2010 at 03:45:55PM -0500, Jonathan Nieder wrote:
Show 5 quoted lines
>  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.
Yann Dirson· Nov 4, 2010, 20:33 UTC · re: Yann Dirson · lore

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

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(-)
Show changes to diffcore-rename.c +13 −10
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
Yann Dirson· Nov 4, 2010, 20:33 UTC · re: Yann Dirson · lore

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

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(-)
Show changes to diffcore-rename.c +13 −8
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
Jonathan Nieder· Nov 4, 2010, 20:56 UTC · re: Yann Dirson · lore

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

Yann Dirson wrote:
Show 20 quoted lines
> --- 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.
Yann Dirson· Nov 4, 2010, 20:33 UTC · re: Yann Dirson · lore

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

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

← back to recent threads