[PATCH v2] generalizing sorted-array handling

[PATCH v2] generalizing sorted-array handling

[Yann Dirson]

This is a complete rewrite of the previous series, following a
suggestion by Jonathan Nieder.  It is much more generic than the
previous one, and removes existing duplicated code in diffcore-rename.

I also had a quick look at other binary-search occurences in the code
that would share the same search code.  That revealed
index_name_pos(): not sure it is a good idea to make it use this API -
it would require changes all over the code.  I still include a
possibly-useful additional API for similar cases.

[PATCH v2 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.  Naming is kept compatible with the original use
of that function.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 Makefile          |    1 +
 diffcore-rename.c |   53 +++++++++++++++--------------------------------------
 sorted-array.h    |   36 ++++++++++++++++++++++++++++++++++++
 3 files changed, 52 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..72a9b94 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -5,52 +5,29 @@
 #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(void* data, 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]);
+	struct diff_filespec *two = data;
+	return strcmp(two->path, elem->two->path);
+}
+static void rename_dst_init(struct diff_rename_dst *elem, void* data)
+{
+	struct diff_filespec *two = data;
+	elem->two = alloc_filespec(two->path);
+	fill_filespec(elem->two, two->sha1, two->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 v2 2/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 |   53 ++++++++++++++++-------------------------------------
 1 files changed, 16 insertions(+), 37 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 72a9b94..ec40cf7 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -30,46 +30,25 @@ 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 {
+
+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(void* data, 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]);
+	struct diff_filepair *p = data;
+	return strcmp(p->one->path, elem->one->path);
+}
+static void rename_src_init(struct diff_rename_src *elem, void* data)
+{
+	struct diff_filepair *p = data;
+	elem->one = p->one;
+	elem->score = p->score;
 }
+declare_sorted_array(static, struct diff_rename_src, rename_src,
+		     rename_src_cmp, rename_src_init)
 
 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
 {
@@ -426,7 +405,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) {
 			/*
@@ -434,7 +413,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

[PATCH v2 3/3] [RFC] Add a sorted-list API for use-cases that require to get the element index.

[Yann Dirson]

The idea was to replace index_name_pos(), but that would require a much
larger API change in callers.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 sorted-array.h |   15 +++++++++++----
 1 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/sorted-array.h b/sorted-array.h
index 03d5d1e..df07687 100644
--- a/sorted-array.h
+++ b/sorted-array.h
@@ -1,7 +1,7 @@
 #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)		\
+MAYBESTATIC int locate_##LIST##_idx(void *data, int insert_ok)		\
 {									\
 	int first, last;						\
 									\
@@ -12,7 +12,7 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
 		ELEMTYPE *nextelem = &(LIST[next]);			\
 		int cmp = CMP(data, nextelem);				\
 		if (!cmp)						\
-			return nextelem;				\
+			return next;					\
 		if (cmp < 0) {						\
 			last = next;					\
 			continue;					\
@@ -21,7 +21,7 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
 	}								\
 	/* not found */							\
 	if (!insert_ok)							\
-		return NULL;						\
+		return -first-1;					\
 	/* insert to make it at "first" */				\
 	if (LIST##_alloc <= LIST##_nr) {				\
 		LIST##_alloc = alloc_nr(LIST##_alloc);			\
@@ -32,5 +32,12 @@ MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
 		memmove(LIST + first + 1, LIST + first,			\
 			(LIST##_nr - first - 1) * sizeof(*LIST));	\
 	INIT(&LIST[first], data);					\
-	return &(LIST[first]);						\
+	return first;							\
+}									\
+MAYBESTATIC ELEMTYPE *locate_##LIST(void *data, int insert_ok)		\
+{									\
+	int idx = locate_##LIST##_idx(data, insert_ok);			\
+	if (idx < 0)							\
+		return NULL;						\
+	return &(LIST[idx]);						\
 }
-- 
1.7.2.3