[PATCH v6] generalizing sorted-array handling

[PATCH v6] generalizing sorted-array handling

[Yann Dirson]

I hope the improvements to the usage syntax in this version would help
to get more feedback.  I don't plan to do much more structural work on
this, unless reviewers complain.  I want to get my focus back to
bulk-rename/builk-rm patches, which will make heavy use of this API.

Changes from v5:

* moved doc to Documentation/api-sorted-array.txt as suggested by
  Jonathan Nieder, made it a bit more comprehensive as well.

* changed API with:
  * renamed low-level wrapper-decl macros with a leading underscore
  * provide high-level wrapper-decl macros for everyday use, which
    declare the required generic funcs for use (as static funcs)

Those high-level macros make the entry points more numerousas
previously noted, but we gain much in usage clarity, as well as
consistent API (no more argument differences between macros of a
single level)

By using those macros we lose the control we had on all the
intermediate funcs, but that should not be much of a problem.


Notes on current API:

* The macro names are a bit heavy-weight.  Better ideas welcome.

* could gain a dealloc API, to minimize the explicit use of the _nr
  and _alloc vars


The following binary-search occurences were not converted:

* read-cache.c::index_name_pos has widely-used API with 2 low-coupled
  cmp/init params: sorted-array could be generalized at the cost of
  using stdarg, but is it worth it ?

* pack-revindex.c::find_pack_revindex is a bit special and needs more
  thought

* cache-tree.c::subtree_pos and sha1_file::find_pack_entry_one too

* sha1_lookup.c stuff probably too special

[PATCH 1/6] 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.
Thanks to Jonathan Nieder for this design idea.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 Documentation/technical/api-sorted-array.txt |  132 ++++++++++++++++++++++++++
 Makefile                                     |    1 +
 sorted-array.h                               |  128 +++++++++++++++++++++++++
 3 files changed, 261 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/technical/api-sorted-array.txt
 create mode 100644 sorted-array.h

diff --git a/Documentation/technical/api-sorted-array.txt b/Documentation/technical/api-sorted-array.txt
new file mode 100644
index 0000000..b1238ad
--- /dev/null
+++ b/Documentation/technical/api-sorted-array.txt
@@ -0,0 +1,132 @@
+sorted-array API
+================
+
+The sorted-array API is meant to provide efficient binary-search
+functions into a C array of elements of arbitrary type, and insert
+functions that maintain ordering.
+
+It is meant for data structures where lookup time is much more
+important than insertion type: while lookup has o(log(n)) time
+complexity, insertion has o(n) and involves many copies.
+
+API overview
+------------
+
+The API allow to declare all variables and function as static or not,
+through the first argument to all macros, which can be `static` or
+empty.
+
+It is based on the idea of providing custom functions, which will then
+be used by generic algorithms:
+* one for comparing a search term with an array item
+* one for initializing a new array item from a search term after insertion
+
+A set of convenience wrapper macros are provided, to define a readable
+API for inserting and sorting.
+
+Note that the type of the search term can be different from the type
+of array elements (which can be more expensive to create).
+
+API reference
+-------------
+
+The macros can be categorized as follows:
+
+* the one used to define a sorted array, and its management variable
+  holding currently-allocated number of elements and number of
+  elements effectively used.  The name of those (int) management
+  variables are crafted by using the `LISTNAME` and appending
+  respectively `_alloc` and `_nr`.
++
+----
+declare_sorted_array(MAYBESTATIC,ELEMTYPE,LISTNAME)
+----
++
+eg:
++
+----
+declare_sorted_array(static, struct diff_rename_dst, rename_dst);
+----
+
+* those defining ready-for-use search and insert functions.  They
+  exist in several flavours, distinguished by their suffix, which
+  refer to different return-type semantics.
++
+----
+declare_sorted_array_search_*(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LISTNAME,CMP)
+declare_sorted_array_insert_*(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LISTNAME,CMP,INIT)
+----
++
+They all work by defining behind the scene a (static) generic search or insert
+function named with `_gen_` prepended to `FUNCNAME`.  Such generic functions
+may be useful to know about if you need to define an insert function with
+the exact same parameters.
++
+All functions of a given type (search or insert) take the same kind of
+arguments:
+
+`MAYBESTATIC`::
+	the ubiquitous `static`or empty placeholder
+`ELEMTYPE`::
+	type of element to be stored in the array
+`FUNCNAME`::
+	name of the function to be defined
+`INITTYPE`::
+	type of search term / initializer passed as argument to the
+	generated function
+`LISTNAME`::
+	name of the array in which the search takes place, usually declared
+	through `declare_sorted_array()`
+`CMP`::
+	comparison function taking an INITTYPE argument and a
+	pointer to an ELEMTYPE argument, and returning an int with
+	the same meaning as `strcmp()`.
+`GENSEARCH`::
+	(insert only) generic search function generated by
+	`declare_gen_binsearch()`
+`INIT`::
+	(insert only) element-initializer function taking as arguments
+	pointer to the ELEMTYPE to be initialized, and an INITTYPE argument
+	to take information from
+
+
+Suffix meanings are as follows:
+
+`check`::
+
+	Returns the position of the element if found pre-existing in
+	the list, or if not found, (-pos - 1) where pos is where the
+	element would have been (for search funcs) or has been (for
+	insert funcs) inserted.
+
+`checkbool`::
+
+	Returns an int, just telling whether the searched element was
+	pre-existing in the list (1) or not (0).
+
+`elem`::
+
+	Returns NULL if the search term was not found (for search
+	funcs), or a pointer to the element found or newly inserted.
+
+* those defining even-more-ready-for-use insert functions, which do
+  not need to define the generic search function at all.  Those macro
+  names are the same as the forms with an `GENSEARCH` argument, but
+  with a name ending in `_insertonly_*`, and without that `GENSEARCH`
+  argument.  The generic (static) search functions are named as
+  `_gensearch` prepended to the `FUNCNAME` argument.
+
+* those defining the generic algorithms
++
+They rarely need to be used directly, they are usually expanded
+transparently from the `declare_sorted_array_*` macros.
++
+----
+declare_gen_binsearch(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE)
+declare_gen_sorted_insert(MAYBESTATIC,ELEMTYPE,FUNCNAME,SEARCHFUNC,INITTYPE)
+----
+
+* those defining the individual wrappers
++
+They rarely need to be used directly, they are usually expanded
+transparently from the `declare_sorted_array_*` macros.
diff --git a/Makefile b/Makefile
index 7eb948d..522261e 100644
--- a/Makefile
+++ b/Makefile
@@ -544,6 +544,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/sorted-array.h b/sorted-array.h
new file mode 100644
index 0000000..added0e
--- /dev/null
+++ b/sorted-array.h
@@ -0,0 +1,128 @@
+#ifndef SORTED_ARRAY_H_
+#define SORTED_ARRAY_H_
+
+/*
+ * Sorted-array management.
+ * See Documentation/technical/api-sorted-array.txt
+ */
+
+#define declare_sorted_array(MAYBESTATIC,ELEMTYPE,LIST)			\
+MAYBESTATIC ELEMTYPE *LIST;						\
+MAYBESTATIC int LIST##_nr, LIST##_alloc;
+
+#define declare_gen_binsearch(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE)	\
+MAYBESTATIC int FUNCNAME(						\
+	ELEMTYPE *list, int list_nr,					\
+	int(*cmp_func)(INITTYPE ref, ELEMTYPE *elem),			\
+	INITTYPE data)							\
+{									\
+	int lo, hi;							\
+									\
+	lo = 0;								\
+	hi = list_nr;							\
+	while (hi > lo) {						\
+		int mid = (hi + lo) >> 1;				\
+		int cmp = cmp_func(data, list + mid);			\
+		if (!cmp)						\
+			return mid;					\
+		if (cmp < 0)						\
+			hi = mid;					\
+		else							\
+			lo = mid + 1;					\
+	}								\
+	return -lo - 1;							\
+}
+
+#define declare_gen_sorted_insert(MAYBESTATIC,ELEMTYPE,FUNCNAME,SEARCHFUNC,INITTYPE) \
+MAYBESTATIC int FUNCNAME(						\
+	ELEMTYPE **list_p, int *list_nr_p, int *list_alloc_p,		\
+	int(*cmp_func)(INITTYPE ref, ELEMTYPE *elem),			\
+	void(*init_func)(ELEMTYPE *elem, INITTYPE init),		\
+	INITTYPE data)							\
+{									\
+	int pos = SEARCHFUNC(*list_p, *list_nr_p, cmp_func, data);	\
+	if (pos >= 0) 							\
+		return pos;						\
+	/* not found */							\
+	pos = -pos - 1;							\
+	/* insert to make it at "pos" */				\
+	if (*list_alloc_p <= *list_nr_p) {				\
+		(*list_alloc_p) = alloc_nr((*list_alloc_p));		\
+		*list_p = xrealloc(*list_p,				\
+				   (*list_alloc_p) * sizeof(**list_p)); \
+	}								\
+	(*list_nr_p)++;							\
+	if (pos < *list_nr_p)						\
+		memmove(*list_p + pos + 1, *list_p + pos,		\
+			(*list_nr_p - pos - 1) * sizeof(**list_p));	\
+	init_func(&(*list_p)[pos], data);				\
+	return -pos - 1;						\
+}
+
+#define _declare_sorted_array_search_check(MAYBESTATIC,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP) \
+MAYBESTATIC int FUNCNAME(INITTYPE data)					\
+{									\
+	return GENSEARCH(LIST, LIST##_nr, CMP, data);			\
+}
+#define declare_sorted_array_search_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP) \
+  declare_gen_binsearch(MAYBESTATIC,ELEMTYPE,_gen_##FUNCNAME,INITTYPE); \
+  _declare_sorted_array_search_check(MAYBESTATIC,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP);
+
+#define _declare_sorted_array_insert_check(MAYBESTATIC,FUNCNAME,INITTYPE,GENINSERT,LIST,CMP,INIT) \
+MAYBESTATIC int FUNCNAME(INITTYPE data)					\
+{									\
+	return GENINSERT(&LIST, &LIST##_nr, &LIST##_alloc,		\
+			 CMP, INIT, data);				\
+}
+#define declare_sorted_array_insert_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP,INIT) \
+  declare_gen_sorted_insert(static,ELEMTYPE,_gen_##FUNCNAME,GENSEARCH,INITTYPE); \
+  _declare_sorted_array_insert_check(MAYBESTATIC,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP,INIT);
+#define declare_sorted_array_insertonly_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP,INIT) \
+  declare_gen_binsearch(static,ELEMTYPE,_gensearch_##FUNCNAME,INITTYPE); \
+  declare_sorted_array_insert_check(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gensearch_##FUNCNAME,LIST,CMP,INIT);
+
+#define _declare_sorted_array_insert_checkbool(MAYBESTATIC,FUNCNAME,INITTYPE,GENINSERT,LIST,CMP,INIT) \
+MAYBESTATIC int FUNCNAME(INITTYPE data)					\
+{									\
+	int idx = GENINSERT(&LIST, &LIST##_nr, &LIST##_alloc,		\
+			    CMP, INIT, data);				\
+	if (idx < 0)							\
+		return 0;						\
+	return 1;							\
+}
+#define declare_sorted_array_insert_checkbool(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP,INIT) \
+  declare_gen_sorted_insert(static,ELEMTYPE,_gen_##FUNCNAME,GENSEARCH,INITTYPE); \
+  _declare_sorted_array_insert_checkbool(MAYBESTATIC,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP,INIT);
+#define declare_sorted_array_insertonly_checkbool(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP,INIT) \
+  declare_gen_binsearch(static,ELEMTYPE,_gensearch_##FUNCNAME,INITTYPE); \
+  declare_sorted_array_insert_checkbool(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gensearch_##FUNCNAME,LIST,CMP,INIT);
+
+#define _declare_sorted_array_search_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP) \
+MAYBESTATIC ELEMTYPE *FUNCNAME(INITTYPE data)				\
+{									\
+	int idx = GENSEARCH(LIST, LIST##_nr, CMP, data);		\
+	if (idx < 0)							\
+		return NULL;						\
+	return &(LIST[idx]);						\
+}
+#define declare_sorted_array_search_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP) \
+  declare_gen_binsearch(static,ELEMTYPE,_gen_##FUNCNAME,INITTYPE); \
+  _declare_sorted_array_search_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP);
+
+#define _declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENINSERT,LIST,CMP,INIT) \
+MAYBESTATIC ELEMTYPE *FUNCNAME(INITTYPE data)				\
+{									\
+	int idx = GENINSERT(&LIST, &LIST##_nr, &LIST##_alloc,		\
+			    CMP, INIT, data);				\
+	if (idx < 0)							\
+		idx = -idx - 1;						\
+	return &(LIST[idx]);						\
+}
+#define declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,GENSEARCH,LIST,CMP,INIT) \
+  declare_gen_sorted_insert(static,ELEMTYPE,_gen_##FUNCNAME,GENSEARCH,INITTYPE); \
+  _declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gen_##FUNCNAME,LIST,CMP,INIT);
+#define declare_sorted_array_insertonly_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,LIST,CMP,INIT) \
+  declare_gen_binsearch(static,ELEMTYPE,_gensearch_##FUNCNAME,INITTYPE); \
+  declare_sorted_array_insert_elem(MAYBESTATIC,ELEMTYPE,FUNCNAME,INITTYPE,_gensearch_##FUNCNAME,LIST,CMP,INIT);
+
+#endif
-- 
1.7.2.3

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

[Junio C Hamano]

Yann Dirson <ydirson@altern.org> writes:

> +Suffix meanings are as follows:
> +
> +`check`::
> +...
> +* those defining the generic algorithms

Yuck.

All of these feel way overengineered and at the same time too rigid and
brittle.

I have a suspicion that the "convenience" macros that generate many
functions and definitions are the main culprit.  For example, why do all
the functions generated by a "convenience" macro must share the same
MAYBESTATIC?  "binsearch" takes a comparison function pointer, and always
picks the midpoint, but what is the performance implication if we wanted
to use sorted-array.h to rewrite say sha1-lookup.c?  How can an API user
who wants to use declare_sorted_array_insert_checkbook() easily figure out
what other macros fromt this family can be used without getting the same
thing generated twice?  If somebody wanted to have a sorted array in a
struct, it may be tempting to use declare_sorted_array() with an empty
MAYBESTATIC inside struct's field declaration (even when the struct itself
is static---which leaves a queasy feeling, but that is a separate issue),
and the _current_ macro definition of declare_sorted_array() may allow
such a usage work perfectly fine, but how can such an API user be rest
assured it won't break in later revisions of these macros?

In addition, these macros in this patch are almost unreadable, but that
probably is mostly a fault of C's macro, not yours.

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

[Yann Dirson]

On Fri, Dec 10, 2010 at 02:29:09PM -0800, Junio C Hamano wrote:
> Yann Dirson <ydirson@altern.org> writes:
> 
> > +Suffix meanings are as follows:
> > +
> > +`check`::
> > +...
> > +* those defining the generic algorithms
> 
> Yuck.
> 
> All of these feel way overengineered and at the same time too rigid and
> brittle.

I confess a natural tendency towards overengineering stuff, but more
iterations usually help :).  Indeed, most of the
overengineered-looking features added in the latest iterations are
things I already needed for the dir-rename series.

About rigidity, well, it is already less rigid than a couple of the
hardcoded implementations we have throughout the source, and as such
could be seen as an iterative step towards someting better - as I
mentionned, my primary intent was to just get things useful for that
dir-rename series, and at least on this point, I think the approach in
this series is not so bad.

It also looks generic enough to get the string-list lookup/insert
funcs use it, and this again does not look so bad to me, compared to
the stretching of the string-list API itself that would be required to
make it useful to the dir-rename stuff.

As for the "brittle" aspect, I'm not sure there is anything unfixable.
At the very least, more parentheses around the expnasion of macro args
would help making things more robust.

> I have a suspicion that the "convenience" macros that generate many
> functions and definitions are the main culprit.

Hm.  I was reluctant at first to use so many macros for an API,
fearing it would confuse people (that resulted in the v5 API:
genericity made it too verbose to be useful).  Then I saw how many
entry-points the linked-list API of the kernel has: that made me
reconsider, and I found the result much more usable, although I had to
write more doc.

> For example, why do all the functions generated by a "convenience"
> macro must share the same MAYBESTATIC?

The intention was that MAYBESTATIC only gets applied to the
explicitely-requested function, and that the transparently-generated
ones get "static".  Only declare_sorted_array_search_check() does not
conform to that, that's a bug.  That also ought to be documented in
the API.

> "binsearch" takes a comparison function pointer, and always
> picks the midpoint, but what is the performance implication if we wanted
> to use sorted-array.h to rewrite say sha1-lookup.c?

As I noted in the cover letter, I consider sha1-lookup.c too special.
What it is not doing is not a conventional binary search, and this
looks out of scope.

> How can an API user who wants to use
> declare_sorted_array_insert_checkbook() easily figure out what other
> macros fromt this family can be used without getting the same thing
> generated twice?

I have tried to make this explicit in the API reference, but things
can surely be made more clear by including examples.

> If somebody wanted to have a sorted array in a
> struct, it may be tempting to use declare_sorted_array() with an empty
> MAYBESTATIC inside struct's field declaration (even when the struct itself
> is static---which leaves a queasy feeling, but that is a separate issue),
> and the _current_ macro definition of declare_sorted_array() may allow
> such a usage work perfectly fine, but how can such an API user be rest
> assured it won't break in later revisions of these macros?

That would only work by side-effect.  We can either decide to document
it and make it part of the API if we feel it's worth it, or
explicitely state it is not supported (or enforce it: defining _nr and
_alloc with =0 initializers would be a fairly good way of catching
such attempts).


> In addition, these macros in this patch are almost unreadable, but that
> probably is mostly a fault of C's macro, not yours.

Yes.  When writing those I sorely missed the readability of C++
templates - yuck :)

-- 
Yann

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

[Erik Faye-Lund]

On Thu, Dec 30, 2010 at 1:40 AM, Yann Dirson <ydirson@free.fr> wrote:
> On Fri, Dec 10, 2010 at 02:29:09PM -0800, Junio C Hamano wrote:
>> In addition, these macros in this patch are almost unreadable, but that
>> probably is mostly a fault of C's macro, not yours.
>
> Yes.  When writing those I sorely missed the readability of C++
> templates - yuck :)

Unfortunately, it's something that ends up subtracting from the value
of the change; a couple of duplicate functions is often easier to
maintain than nasty macros.

Perhaps the pre-processor is not the right tool for the job? Some
times a generator (a perl script?) can be more readable.
Unfortunately, some times it's not :P

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

[Yann Dirson]

On Thu, Dec 30, 2010 at 02:06:28AM +0100, Erik Faye-Lund wrote:
> On Thu, Dec 30, 2010 at 1:40 AM, Yann Dirson <ydirson@free.fr> wrote:
> > On Fri, Dec 10, 2010 at 02:29:09PM -0800, Junio C Hamano wrote:
> >> In addition, these macros in this patch are almost unreadable, but that
> >> probably is mostly a fault of C's macro, not yours.
> >
> > Yes.  When writing those I sorely missed the readability of C++
> > templates - yuck :)
> 
> Unfortunately, it's something that ends up subtracting from the value
> of the change; a couple of duplicate functions is often easier to
> maintain than nasty macros.

Well, I don't find this one much less readable than, say, vcs-svn/trp.h

At least the declare_gen_* ones are quite readable.  Maybe making the
macro names shorter would help clarify the convenience wrappers ?

[PATCH 2/6] Convert diffcore-rename's rename_dst to the new sorted-array API.

[Yann Dirson]

The sorted-array API splits search and insert into two separated
functions, which makes the caller code more clear.

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

diff --git a/diffcore-rename.c b/diffcore-rename.c
index df41be5..ca3f54c 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -5,52 +5,32 @@
 #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);
+declare_sorted_array_search_elem(static, struct diff_rename_dst, locate_rename_dst,
+				 struct diff_filespec *,
+				 rename_dst, rename_dst_cmp);
+declare_sorted_array_insert_checkbool(static, struct diff_rename_dst, register_rename_dst,
+				      struct diff_filespec *, _gen_locate_rename_dst,
+				      rename_dst, rename_dst_cmp, rename_dst_init);
 
 /* Table of rename/copy src files */
 static struct diff_rename_src {
@@ -437,7 +417,7 @@ void diffcore_rename(struct diff_options *options)
 				 strcmp(options->single_follow, p->two->path))
 				continue; /* not interested */
 			else
-				locate_rename_dst(p->two, 1);
+				register_rename_dst(p->two);
 		}
 		else if (!DIFF_FILE_VALID(p->two)) {
 			/*
@@ -582,7 +562,7 @@ void diffcore_rename(struct diff_options *options)
 			 * not been turned into a rename/copy already.
 			 */
 			struct diff_rename_dst *dst =
-				locate_rename_dst(p->two, 0);
+				locate_rename_dst(p->two);
 			if (dst && dst->pair) {
 				diff_q(&outq, dst->pair);
 				pair_to_free = p;
@@ -613,7 +593,7 @@ void diffcore_rename(struct diff_options *options)
 			if (DIFF_PAIR_BROKEN(p)) {
 				/* broken delete */
 				struct diff_rename_dst *dst =
-					locate_rename_dst(p->one, 0);
+					locate_rename_dst(p->one);
 				if (dst && dst->pair)
 					/* counterpart is now rename/copy */
 					pair_to_free = p;
-- 
1.7.2.3

Re: [PATCH 2/6] Convert diffcore-rename's rename_dst to the new sorted-array API.

[Junio C Hamano]

Separating "locate with 'please optionally create'" into "locate" and
"register" looks like the right thing to do to make the callers easier to
read.

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

[Yann Dirson]

There was no compelling reason to pass separately two members of a
single struct to the insert function.  That's a happy coincidence.

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 ca3f54c..f7afdeb 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -33,46 +33,25 @@ declare_sorted_array_insert_checkbool(static, struct diff_rename_dst, register_r
 				      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(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(static, struct diff_rename_src, rename_src);
+declare_sorted_array_insertonly_checkbool(static, struct diff_rename_src, register_rename_src,
+					  struct diff_filepair *,
+					  rename_src, rename_src_cmp, rename_src_init);
 
 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
 {
@@ -429,7 +408,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);
+			register_rename_src(p);
 		}
 		else if (detect_rename == DIFF_DETECT_COPY) {
 			/*
@@ -437,7 +416,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);
+			register_rename_src(p);
 		}
 	}
 	if (rename_dst_nr == 0 || rename_src_nr == 0)
-- 
1.7.2.3

[PATCH 4/6] Convert pack-objects.c to the new sorted-array API.

[Yann Dirson]

In this file the "list size" variable was named in a non-standard way.
The new API forces to use a more common convention.

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 builtin/pack-objects.c |   50 +++++++++++++----------------------------------
 1 files changed, 14 insertions(+), 36 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index f027b3a..c26175c 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -16,6 +16,7 @@
 #include "list-objects.h"
 #include "progress.h"
 #include "refs.h"
+#include "sorted-array.h"
 
 #ifndef NO_PTHREADS
 #include <pthread.h>
@@ -871,45 +872,22 @@ static void add_pbase_object(struct tree_desc *tree,
 	}
 }
 
-static unsigned *done_pbase_paths;
-static int done_pbase_paths_num;
-static int done_pbase_paths_alloc;
-static int done_pbase_path_pos(unsigned hash)
+static int unsigned_cmp(unsigned ref, unsigned *elem)
 {
-	int lo = 0;
-	int hi = done_pbase_paths_num;
-	while (lo < hi) {
-		int mi = (hi + lo) / 2;
-		if (done_pbase_paths[mi] == hash)
-			return mi;
-		if (done_pbase_paths[mi] < hash)
-			hi = mi;
-		else
-			lo = mi + 1;
-	}
-	return -lo-1;
+	if (ref == *elem)
+		return 0;
+	if (ref < *elem)
+		return -1;
+	return 1;
 }
-
-static int check_pbase_path(unsigned hash)
+static void unsigned_init(unsigned *elem, unsigned ref)
 {
-	int pos = (!done_pbase_paths) ? -1 : done_pbase_path_pos(hash);
-	if (0 <= pos)
-		return 1;
-	pos = -pos - 1;
-	if (done_pbase_paths_alloc <= done_pbase_paths_num) {
-		done_pbase_paths_alloc = alloc_nr(done_pbase_paths_alloc);
-		done_pbase_paths = xrealloc(done_pbase_paths,
-					    done_pbase_paths_alloc *
-					    sizeof(unsigned));
-	}
-	done_pbase_paths_num++;
-	if (pos < done_pbase_paths_num)
-		memmove(done_pbase_paths + pos + 1,
-			done_pbase_paths + pos,
-			(done_pbase_paths_num - pos - 1) * sizeof(unsigned));
-	done_pbase_paths[pos] = hash;
-	return 0;
+	*elem = ref;
 }
+declare_sorted_array(static, unsigned, done_pbase_paths);
+declare_sorted_array_insertonly_checkbool(static, unsigned, check_pbase_path,
+					  unsigned,
+					  done_pbase_paths, unsigned_cmp, unsigned_init);
 
 static void add_preferred_base_object(const char *name)
 {
@@ -987,7 +965,7 @@ static void cleanup_preferred_base(void)
 
 	free(done_pbase_paths);
 	done_pbase_paths = NULL;
-	done_pbase_paths_num = done_pbase_paths_alloc = 0;
+	done_pbase_paths_nr = done_pbase_paths_alloc = 0;
 }
 
 static void check_object(struct object_entry *entry)
-- 
1.7.2.3

[PATCH 5/6] Use sorted-array API for commit.c's commit_graft.

[Yann Dirson]

Factorizing code fixes off-by-one error in the duplicated code (caused
mostly harmless anticipated growing of the array).

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 commit.c |   55 +++++++++++++++++++++----------------------------------
 1 files changed, 21 insertions(+), 34 deletions(-)

diff --git a/commit.c b/commit.c
index b21335e..786bb7a 100644
--- a/commit.c
+++ b/commit.c
@@ -6,6 +6,7 @@
 #include "diff.h"
 #include "revision.h"
 #include "notes.h"
+#include "sorted-array.h"
 
 int save_commit_buffer = 1;
 
@@ -89,33 +90,32 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)
 	return strtoul(dateptr, NULL, 10);
 }
 
-static struct commit_graft **commit_graft;
-static int commit_graft_alloc, commit_graft_nr;
-
-static int commit_graft_pos(const unsigned char *sha1)
+static int commit_graft_cmp(const unsigned char *ref_sha1, struct commit_graft **elem)
 {
-	int lo, hi;
-	lo = 0;
-	hi = commit_graft_nr;
-	while (lo < hi) {
-		int mi = (lo + hi) / 2;
-		struct commit_graft *graft = commit_graft[mi];
-		int cmp = hashcmp(sha1, graft->sha1);
-		if (!cmp)
-			return mi;
-		if (cmp < 0)
-			hi = mi;
-		else
-			lo = mi + 1;
-	}
-	return -lo - 1;
+	return hashcmp(ref_sha1, (*elem)->sha1);
 }
+declare_sorted_array(static, struct commit_graft *, commit_graft);
+declare_sorted_array_search_check(static, struct commit_graft *, commit_graft_pos,
+				  const unsigned char *,
+				  commit_graft, commit_graft_cmp);
 
+// FIXME: do we want to/can we remove INITTYPE from gen_binsearch ?
+static int commit_graft_cmp2(struct commit_graft *ref_graft, struct commit_graft **elem)
+{
+	return commit_graft_cmp(ref_graft->sha1, elem);
+}
+static void commit_graft_init(struct commit_graft **elem, struct commit_graft *ref_graft)
+{
+	*elem = ref_graft;
+}
+declare_sorted_array_insertonly_check(static, struct commit_graft *, register_commit_graft0,
+				      struct commit_graft *,
+				      commit_graft, commit_graft_cmp2, commit_graft_init);
 int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 {
-	int pos = commit_graft_pos(graft->sha1);
+	int pos = register_commit_graft0(graft);
 
-	if (0 <= pos) {
+	if (pos >= 0) {
 		if (ignore_dups)
 			free(graft);
 		else {
@@ -124,19 +124,6 @@ int register_commit_graft(struct commit_graft *graft, int ignore_dups)
 		}
 		return 1;
 	}
-	pos = -pos - 1;
-	if (commit_graft_alloc <= ++commit_graft_nr) {
-		commit_graft_alloc = alloc_nr(commit_graft_alloc);
-		commit_graft = xrealloc(commit_graft,
-					sizeof(*commit_graft) *
-					commit_graft_alloc);
-	}
-	if (pos < commit_graft_nr)
-		memmove(commit_graft + pos + 1,
-			commit_graft + pos,
-			(commit_graft_nr - pos - 1) *
-			sizeof(*commit_graft));
-	commit_graft[pos] = graft;
 	return 0;
 }
 
-- 
1.7.2.3

[PATCH 6/6] [RFC] subvert sorted-array to replace binary-search in unpack-objects.

[Yann Dirson]

Signed-off-by: Yann Dirson <ydirson@altern.org>
---
 builtin/unpack-objects.c |   40 +++++++++++++++++++++++++---------------
 1 files changed, 25 insertions(+), 15 deletions(-)

diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c
index f63973c..6d7d113 100644
--- a/builtin/unpack-objects.c
+++ b/builtin/unpack-objects.c
@@ -11,6 +11,7 @@
 #include "progress.h"
 #include "decorate.h"
 #include "fsck.h"
+#include "sorted-array.h"
 
 static int dry_run, quiet, recover, has_errors, strict;
 static const char unpack_usage[] = "git unpack-objects [-n] [-q] [-r] [--strict] < pack-file";
@@ -157,7 +158,24 @@ struct obj_info {
 #define FLAG_OPEN (1u<<20)
 #define FLAG_WRITTEN (1u<<21)
 
-static struct obj_info *obj_list;
+/*
+ * FIXME: obj_info is a sorted array, but we read it as a whole, we
+ * don't need insertion features.  This allows us to abuse unused
+ * obj_info_nr later as a means of specifying an upper bound for
+ * binary search.  obj_info_alloc shall be eliminated by the compiler
+ * as unused.
+ */
+static int obj_info_cmp(off_t ref, struct obj_info *elem)
+{
+	if (ref == elem->offset)
+		return 0;
+	if (ref < elem->offset)
+		return -1;
+	return 1;
+}
+declare_sorted_array(static, struct obj_info, obj_list);
+declare_sorted_array_search_check(static, struct obj_info, obj_list_check,
+				  off_t, obj_list, obj_info_cmp);
 static unsigned nr_objects;
 
 /*
@@ -356,7 +374,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,
 		unsigned base_found = 0;
 		unsigned char *pack, c;
 		off_t base_offset;
-		unsigned lo, mid, hi;
+		int pos;
 
 		pack = fill(1);
 		c = *pack;
@@ -380,19 +398,11 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,
 			free(delta_data);
 			return;
 		}
-		lo = 0;
-		hi = nr;
-		while (lo < hi) {
-			mid = (lo + hi)/2;
-			if (base_offset < obj_list[mid].offset) {
-				hi = mid;
-			} else if (base_offset > obj_list[mid].offset) {
-				lo = mid + 1;
-			} else {
-				hashcpy(base_sha1, obj_list[mid].sha1);
-				base_found = !is_null_sha1(base_sha1);
-				break;
-			}
+		obj_list_nr = nr; /* kludge to bound the search */
+		pos = obj_list_check(base_offset);
+		if (pos >= 0) {
+			hashcpy(base_sha1, obj_list[pos].sha1);
+			base_found = !is_null_sha1(base_sha1);
 		}
 		if (!base_found) {
 			/*
-- 
1.7.2.3

Re: [PATCH 6/6] [RFC] subvert sorted-array to replace binary-search in unpack-objects.

[Junio C Hamano]

Yann Dirson <ydirson@altern.org> writes:

> Signed-off-by: Yann Dirson <ydirson@altern.org>
> ---
>  builtin/unpack-objects.c |   40 +++++++++++++++++++++++++---------------
>  1 files changed, 25 insertions(+), 15 deletions(-)
>
> diff --git a/builtin/unpack-objects.c b/builtin/unpack-objects.c
> index f63973c..6d7d113 100644
> --- a/builtin/unpack-objects.c
> +++ b/builtin/unpack-objects.c
> @@ -157,7 +158,24 @@ struct obj_info {
>  #define FLAG_OPEN (1u<<20)
>  #define FLAG_WRITTEN (1u<<21)
>  
> -static struct obj_info *obj_list;
> +/*
> + * FIXME: obj_info is a sorted array, but we read it as a whole, we
> + * don't need insertion features.  This allows us to abuse unused
> + * obj_info_nr later as a means of specifying an upper bound for
> + * binary search.  obj_info_alloc shall be eliminated by the compiler
> + * as unused.
> + */

I was scratching my head when I read "subvert" on your Subject line and
FIXME above for the first time, but after thinking about it, I think I got
it, and more importantly, I think you realized and shared with me the "too
rigid and brittle" I mentioned in my response to [1/6] earlier, if not
"overengineered" part.

As pack stream is read in, obj_list is built into an array that is sorted
by its "offset" field up to "nr"-th element.  And assigning the current
number of elements in the array to obj_list_nr is not a "kludge to bound
the search" as you said in the comment, but is the right thing to do given
the structure of your API.  "nr" is "up to this index the array is filled
and used", "alloc" is "this many is allocated", and at the point of that
assignment, "nr" is indeed what it is.

The only reason it might seem kludgy is because the API is not designed to
anticipate that there is a way to add new elements at the end by feeding
elements in the already sorted order, and that facility does so without
calling the functions your API autogenerates.

I think the most bothersome repetition with the current codebase around
binary searchable tables is the binary search loops.  Perhaps introducing
a macro that lets us write them in a more structured way, without trying
to build an elaborate top-level declarations that do everything (and
failing to do so), may give you a better payback?

Re: [PATCH v6] generalizing sorted-array handling

[Junio C Hamano]

Yann Dirson <ydirson@altern.org> writes:

> ... I want to get my focus back to
> bulk-rename/builk-rm patches, which will make heavy use of this API.

Final comment.  As the primary thing you want to use this is to change the
way how the rename_dst/rename_src tables are managed, and these are both
tables sorted by a string, I suspect a more reasonable might be to first
updated them to use string-list API and add to that API whatever necessary
features you might need, if any.

Re: [PATCH v6] generalizing sorted-array handling

[Yann Dirson]

On Fri, Dec 10, 2010 at 03:22:18PM -0800, Junio C Hamano wrote:
> Yann Dirson <ydirson@altern.org> writes:
> 
> > ... I want to get my focus back to
> > bulk-rename/builk-rm patches, which will make heavy use of this API.
> 
> Final comment.  As the primary thing you want to use this is to change the
> way how the rename_dst/rename_src tables are managed, and these are both
> tables sorted by a string, I suspect a more reasonable might be to first
> updated them to use string-list API and add to that API whatever necessary
> features you might need, if any.

It sounds reasonable to build on existing stuff (furthermore, the
string-list binary search is one I had missed).

Using string-lists here however will imply some tradeofs:

* the additional char* pointer in every list element is possibly not
  so high a price to pay

* using the "util" pointer for the payload will make memory management
  even more hairy (eg. "util" as a pointer to a struct which contains
  a pointer to a diff_filespec).  Convenience wrappers will be highly
  needed, and will also be required to keep calls to lookup/insert
  readable, when the elements we deal with are not strings but indeed
  the "util" stuff.

All in all, looks that the data-structure needed should have a higher
focus on the "util" field than string-list has.

Features that seem to miss from string-list today (for the
"dir-rename" series) include:

* custom string-comparison function (ie. prefix comparison): that
  would not be so difficult to generalize by adding a cmp_func
  parameter to get_entry_index().  That would imply changing
  widely-used API funcs like string_list_lookup() to shallow wrappers
  around variants that also take a cmp_func argument.

* lists indexed by 2 strings (bulkmove_candidates): could be replaced
  by using string-lists of string-lists instead, but I'm not sure the
  result would be that great


I still have mixed feelings about all of this.

-- 
Yann