[PATCH v3] generalizing sorted-array handling

[PATCH v3] generalizing sorted-array handling

[Yann Dirson]

Changes from v2:

* separated sorted-array type declaration from array declaration
* proper typechecking (no reason for using void* for "callback data")
* fixed coding style issues

[PATCH v3 1/3] Introduce sorted-array binary-search function.

[Yann Dirson]

We use a cpp-based template mechanism to declare the array and its
management data, as well as a search function, derived from locate_rename_dst()
from diffcore-rename.c.  Thanks to Jonathan Nieder for this design idea.

Naming is kept compatible with the original use of that function.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 Makefile          |    1 +
 diffcore-rename.c |   51 +++++++++++++--------------------------------------
 sorted-array.h    |   36 ++++++++++++++++++++++++++++++++++++
 3 files changed, 50 insertions(+), 38 deletions(-)
 create mode 100644 sorted-array.h

diff --git a/Makefile b/Makefile
index 1f1ce04..fa5b2e6 100644
--- a/Makefile
+++ b/Makefile
@@ -536,6 +536,7 @@ LIB_H += run-command.h
 LIB_H += sha1-lookup.h
 LIB_H += sideband.h
 LIB_H += sigchain.h
+LIB_H += sorted-array.h
 LIB_H += strbuf.h
 LIB_H += string-list.h
 LIB_H += submodule.h
diff --git a/diffcore-rename.c b/diffcore-rename.c
index df41be5..1626bdc 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -5,52 +5,27 @@
 #include "diff.h"
 #include "diffcore.h"
 #include "hash.h"
+#include "sorted-array.h"
 
 /* Table of rename/copy destinations */
 
-static struct diff_rename_dst {
+struct diff_rename_dst {
 	struct diff_filespec *two;
 	struct diff_filepair *pair;
-} *rename_dst;
-static int rename_dst_nr, rename_dst_alloc;
+};
 
-static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
-						 int insert_ok)
+static int rename_dst_cmp(struct diff_filespec *ref_spec, struct diff_rename_dst *elem)
 {
-	int first, last;
-
-	first = 0;
-	last = rename_dst_nr;
-	while (last > first) {
-		int next = (last + first) >> 1;
-		struct diff_rename_dst *dst = &(rename_dst[next]);
-		int cmp = strcmp(two->path, dst->two->path);
-		if (!cmp)
-			return dst;
-		if (cmp < 0) {
-			last = next;
-			continue;
-		}
-		first = next+1;
-	}
-	/* not found */
-	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);
-		rename_dst = xrealloc(rename_dst,
-				      rename_dst_alloc * sizeof(*rename_dst));
-	}
-	rename_dst_nr++;
-	if (first < rename_dst_nr)
-		memmove(rename_dst + first + 1, rename_dst + first,
-			(rename_dst_nr - 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]);
+	return strcmp(ref_spec->path, elem->two->path);
+}
+static void rename_dst_init(struct diff_rename_dst *elem, struct diff_filespec *ref_spec)
+{
+	elem->two = alloc_filespec(ref_spec->path);
+	fill_filespec(elem->two, ref_spec->sha1, ref_spec->mode);
+	elem->pair = NULL;
 }
+declare_sorted_array(static, struct diff_rename_dst, rename_dst,
+		     rename_dst_cmp, rename_dst_init)
 
 /* Table of rename/copy src files */
 static struct diff_rename_src {
diff --git a/sorted-array.h b/sorted-array.h
new file mode 100644
index 0000000..03d5d1e
--- /dev/null
+++ b/sorted-array.h
@@ -0,0 +1,36 @@
+#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,LIST,CMP,INIT)	\
+MAYBESTATIC ELEMTYPE *LIST;						\
+MAYBESTATIC int LIST##_nr, LIST##_alloc;				\
+MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
+{									\
+	int first, last;						\
+									\
+	first = 0;							\
+	last = LIST##_nr;						\
+	while (last > first) {						\
+		int next = (last + first) >> 1;				\
+		ELEMTYPE *nextelem = &(LIST[next]);			\
+		int cmp = CMP(data, nextelem);				\
+		if (!cmp)						\
+			return nextelem;				\
+		if (cmp < 0) {						\
+			last = next;					\
+			continue;					\
+		}							\
+		first = next+1;						\
+	}								\
+	/* not found */							\
+	if (!insert_ok)							\
+		return NULL;						\
+	/* insert to make it at "first" */				\
+	if (LIST##_alloc <= LIST##_nr) {				\
+		LIST##_alloc = alloc_nr(LIST##_alloc);			\
+		LIST = xrealloc(LIST, LIST##_alloc * sizeof(*LIST));	\
+	}								\
+	LIST##_nr++;							\
+	if (first < LIST##_nr)						\
+		memmove(LIST + first + 1, LIST + first,			\
+			(LIST##_nr - first - 1) * sizeof(*LIST));	\
+	INIT(&LIST[first], data);					\
+	return &(LIST[first]);						\
+}
-- 
1.7.2.3

[PATCH v3 2/3] Separate sorted-array type declaration from array declaration.

[Yann Dirson]

Instead of a single locate() function hardcoding references to a fixed
array, we declare a generic function taking references to the array and
its metadata.  Declaring an array produces a lightweight wrapper for
this specific array, not modifying calling API any further and keeping
it readable.

This will allow to declare several arrays of the same type without
causing duplication of the locate function.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 diffcore-rename.c |    5 +++--
 sorted-array.h    |   39 ++++++++++++++++++++++++---------------
 2 files changed, 27 insertions(+), 17 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 1626bdc..a146adf 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -24,8 +24,9 @@ static void rename_dst_init(struct diff_rename_dst *elem, struct diff_filespec *
 	fill_filespec(elem->two, ref_spec->sha1, ref_spec->mode);
 	elem->pair = NULL;
 }
-declare_sorted_array(static, struct diff_rename_dst, rename_dst,
-		     rename_dst_cmp, rename_dst_init)
+declare_sorted_array_type(static, struct diff_rename_dst, rename_dst,
+			  rename_dst_cmp, rename_dst_init);
+declare_sorted_array(static, struct diff_rename_dst, rename_dst, rename_dst);
 
 /* Table of rename/copy src files */
 static struct diff_rename_src {
diff --git a/sorted-array.h b/sorted-array.h
index 03d5d1e..54fad20 100644
--- a/sorted-array.h
+++ b/sorted-array.h
@@ -1,15 +1,15 @@
-#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,LIST,CMP,INIT)	\
-MAYBESTATIC ELEMTYPE *LIST;						\
-MAYBESTATIC int LIST##_nr, LIST##_alloc;				\
-MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
+#define declare_sorted_array_type(MAYBESTATIC,ELEMTYPE,TYPENICK,CMP,INIT) \
+MAYBESTATIC ELEMTYPE *locate_type_##TYPENICK(				\
+	ELEMTYPE **list_p, int *list_nr_p, int *list_nr_alloc,		\
+	void *data, int insert_ok)					\
 {									\
 	int first, last;						\
 									\
 	first = 0;							\
-	last = LIST##_nr;						\
+	last = *list_nr_p;						\
 	while (last > first) {						\
 		int next = (last + first) >> 1;				\
-		ELEMTYPE *nextelem = &(LIST[next]);			\
+		ELEMTYPE *nextelem = &((*list_p)[next]);		\
 		int cmp = CMP(data, nextelem);				\
 		if (!cmp)						\
 			return nextelem;				\
@@ -23,14 +23,23 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
 	if (!insert_ok)							\
 		return NULL;						\
 	/* insert to make it at "first" */				\
-	if (LIST##_alloc <= LIST##_nr) {				\
-		LIST##_alloc = alloc_nr(LIST##_alloc);			\
-		LIST = xrealloc(LIST, LIST##_alloc * sizeof(*LIST));	\
+	if (*list_nr_alloc <= *list_nr_p) {				\
+		(*list_nr_alloc) = alloc_nr((*list_nr_alloc));		\
+		*list_p = xrealloc(*list_p, (*list_nr_alloc) * sizeof(**list_p)); \
 	}								\
-	LIST##_nr++;							\
-	if (first < LIST##_nr)						\
-		memmove(LIST + first + 1, LIST + first,			\
-			(LIST##_nr - first - 1) * sizeof(*LIST));	\
-	INIT(&LIST[first], data);					\
-	return &(LIST[first]);						\
+	(*list_nr_p)++;							\
+	if (first < *list_nr_p)						\
+		memmove(*list_p + first + 1, *list_p + first,		\
+			(*list_nr_p - first - 1) * sizeof(**list_p));	\
+	INIT(&(*list_p)[first], data);					\
+	return &((*list_p)[first]);					\
+}
+
+#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,TYPENICK,LIST)	\
+MAYBESTATIC ELEMTYPE *LIST;						\
+MAYBESTATIC int LIST##_nr, LIST##_alloc;				\
+MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
+{									\
+	return locate_type_##TYPENICK(&LIST, &LIST##_nr, &LIST##_alloc,	\
+				 data, insert_ok);			\
 }
-- 
1.7.2.3

[PATCH v3 3/3] Convert diffcore-rename's rename_src to the new sorted-array API.

[Yann Dirson]

Alas, this time we could not keep the same prototype :)

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

diff --git a/diffcore-rename.c b/diffcore-rename.c
index a146adf..6fa347e 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -29,46 +29,24 @@ declare_sorted_array_type(static, struct diff_rename_dst, rename_dst,
 declare_sorted_array(static, struct diff_rename_dst, rename_dst, rename_dst);
 
 /* Table of rename/copy src files */
-static struct diff_rename_src {
+
+struct diff_rename_src {
 	struct diff_filespec *one;
 	unsigned short score; /* to remember the break score */
-} *rename_src;
-static int rename_src_nr, rename_src_alloc;
+};
 
-static struct diff_rename_src *register_rename_src(struct diff_filespec *one,
-						   unsigned short score)
+static int rename_src_cmp(struct diff_filepair *ref_pair, struct diff_rename_src *elem)
 {
-	int first, last;
-
-	first = 0;
-	last = rename_src_nr;
-	while (last > first) {
-		int next = (last + first) >> 1;
-		struct diff_rename_src *src = &(rename_src[next]);
-		int cmp = strcmp(one->path, src->one->path);
-		if (!cmp)
-			return src;
-		if (cmp < 0) {
-			last = next;
-			continue;
-		}
-		first = next+1;
-	}
-
-	/* insert to make it at "first" */
-	if (rename_src_alloc <= rename_src_nr) {
-		rename_src_alloc = alloc_nr(rename_src_alloc);
-		rename_src = xrealloc(rename_src,
-				      rename_src_alloc * sizeof(*rename_src));
-	}
-	rename_src_nr++;
-	if (first < rename_src_nr)
-		memmove(rename_src + first + 1, rename_src + first,
-			(rename_src_nr - first - 1) * sizeof(*rename_src));
-	rename_src[first].one = one;
-	rename_src[first].score = score;
-	return &(rename_src[first]);
+	return strcmp(ref_pair->one->path, elem->one->path);
+}
+static void rename_src_init(struct diff_rename_src *elem, struct diff_filepair *ref_pair)
+{
+	elem->one = ref_pair->one;
+	elem->score = ref_pair->score;
 }
+declare_sorted_array_type(static, struct diff_rename_src, rename_src,
+			  rename_src_cmp, rename_src_init);
+declare_sorted_array(static, struct diff_rename_src, rename_src, rename_src);
 
 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
 {
@@ -425,7 +403,7 @@ void diffcore_rename(struct diff_options *options)
 			 */
 			if (p->broken_pair && !p->score)
 				p->one->rename_used++;
-			register_rename_src(p->one, p->score);
+			locate_rename_src(p, 1);
 		}
 		else if (detect_rename == DIFF_DETECT_COPY) {
 			/*
@@ -433,7 +411,7 @@ void diffcore_rename(struct diff_options *options)
 			 * one, to indicate ourselves as a user.
 			 */
 			p->one->rename_used++;
-			register_rename_src(p->one, p->score);
+			locate_rename_src(p, 1);
 		}
 	}
 	if (rename_dst_nr == 0 || rename_src_nr == 0)
-- 
1.7.2.3

Re: [PATCH v3 1/3] Introduce sorted-array binary-search function.

[Junio C Hamano]

Yann Dirson <ydirson@altern.org> writes:

> We use a cpp-based template mechanism to declare the array and its
> management data, as well as a search function, derived from locate_rename_dst()
> from diffcore-rename.c.  Thanks to Jonathan Nieder for this design idea.

Hmmm.... Yet another binary search...

Can we generalize the existing ones first before adding any of this in
(hint: look for "git grep -w -e hi --and -e lo")?

Re: [PATCH v3 1/3] Introduce sorted-array binary-search function.

[Yann Dirson]

On Tue, Nov 16, 2010 at 09:27:16AM -0800, Junio C Hamano wrote:
> Yann Dirson <ydirson@altern.org> writes:
> 
> > We use a cpp-based template mechanism to declare the array and its
> > management data, as well as a search function, derived from locate_rename_dst()
> > from diffcore-rename.c.  Thanks to Jonathan Nieder for this design idea.
> 
> Hmmm.... Yet another binary search...

Well, not exactly another, it still generalizes code that was already here.

> Can we generalize the existing ones first before adding any of this in
> (hint: look for "git grep -w -e hi --and -e lo")?

With great pleasure.  I have simply missed those, only looking for the
pattern used in diffcore-rename.

Looking at a few ones, that seems just a matter of:
* refreshing my "[RFC] Add a sorted-list API for use-cases that
  require to get the element index." from v2 series
* adding support for more than one func, which I already required for
  bulk-rename