summaryrefslogtreecommitdiff
path: root/src/tsort.c
diff options
context:
space:
mode:
authorRussell Belfer <rb@github.com>2013-01-09 16:00:16 -0800
committerRussell Belfer <rb@github.com>2013-01-15 09:51:35 -0800
commit851ad65081793bb5fd65052907bf1c3c4e7e5729 (patch)
treef548ff1dbc20894aebfabfe2cf6e19ba372bbfb0 /src/tsort.c
parenta49340c3e5de90ca551b46ea79573c428e3836b0 (diff)
downloadlibgit2-851ad65081793bb5fd65052907bf1c3c4e7e5729.tar.gz
Add payload "_r" versions of bsearch and tsort
git__bsearch and git__tsort did not pass a payload through to the comparison function. This makes it impossible to implement sorted lists where the sort order depends on external data (e.g. building a secondary sort order for the entries in a tree). This commit adds git__bsearch_r and git__tsort_r versions that pass a third parameter to the cmp function of a user payload.
Diffstat (limited to 'src/tsort.c')
-rw-r--r--src/tsort.c60
1 files changed, 38 insertions, 22 deletions
diff --git a/src/tsort.c b/src/tsort.c
index 634fe2672..97473be91 100644
--- a/src/tsort.c
+++ b/src/tsort.c
@@ -23,9 +23,8 @@
# define MIN(x,y) (((x) < (y) ? (x) : (y)))
#endif
-typedef int (*cmp_ptr_t)(const void *, const void *);
-
-static int binsearch(void **dst, const void *x, size_t size, cmp_ptr_t cmp)
+static int binsearch(
+ void **dst, const void *x, size_t size, git__tsort_r_cmp cmp, void *payload)
{
int l, c, r;
void *lx, *cx;
@@ -38,12 +37,12 @@ static int binsearch(void **dst, const void *x, size_t size, cmp_ptr_t cmp)
lx = dst[l];
/* check for beginning conditions */
- if (cmp(x, lx) < 0)
+ if (cmp(x, lx, payload) < 0)
return 0;
- else if (cmp(x, lx) == 0) {
+ else if (cmp(x, lx, payload) == 0) {
int i = 1;
- while (cmp(x, dst[i]) == 0)
+ while (cmp(x, dst[i], payload) == 0)
i++;
return i;
}
@@ -51,7 +50,7 @@ static int binsearch(void **dst, const void *x, size_t size, cmp_ptr_t cmp)
/* guaranteed not to be >= rx */
cx = dst[c];
while (1) {
- const int val = cmp(x, cx);
+ const int val = cmp(x, cx, payload);
if (val < 0) {
if (c - l <= 1) return c;
r = c;
@@ -62,7 +61,7 @@ static int binsearch(void **dst, const void *x, size_t size, cmp_ptr_t cmp)
} else {
do {
cx = dst[++c];
- } while (cmp(x, cx) == 0);
+ } while (cmp(x, cx, payload) == 0);
return c;
}
c = l + ((r - l) >> 1);
@@ -71,7 +70,8 @@ static int binsearch(void **dst, const void *x, size_t size, cmp_ptr_t cmp)
}
/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
-static void bisort(void **dst, size_t start, size_t size, cmp_ptr_t cmp)
+static void bisort(
+ void **dst, size_t start, size_t size, git__tsort_r_cmp cmp, void *payload)
{
size_t i;
void *x;
@@ -80,12 +80,12 @@ static void bisort(void **dst, size_t start, size_t size, cmp_ptr_t cmp)
for (i = start; i < size; i++) {
int j;
/* If this entry is already correct, just move along */
- if (cmp(dst[i - 1], dst[i]) <= 0)
+ if (cmp(dst[i - 1], dst[i], payload) <= 0)
continue;
/* Else we need to find the right place, shift everything over, and squeeze in */
x = dst[i];
- location = binsearch(dst, x, i, cmp);
+ location = binsearch(dst, x, i, cmp, payload);
for (j = (int)i - 1; j >= location; j--) {
dst[j + 1] = dst[j];
}
@@ -102,7 +102,8 @@ struct tsort_run {
struct tsort_store {
size_t alloc;
- cmp_ptr_t cmp;
+ git__tsort_r_cmp cmp;
+ void *payload;
void **storage;
};
@@ -118,7 +119,8 @@ static void reverse_elements(void **dst, ssize_t start, ssize_t end)
}
}
-static ssize_t count_run(void **dst, ssize_t start, ssize_t size, struct tsort_store *store)
+static ssize_t count_run(
+ void **dst, ssize_t start, ssize_t size, struct tsort_store *store)
{
ssize_t curr = start + 2;
@@ -126,7 +128,7 @@ static ssize_t count_run(void **dst, ssize_t start, ssize_t size, struct tsort_s
return 1;
if (start >= size - 2) {
- if (store->cmp(dst[size - 2], dst[size - 1]) > 0) {
+ if (store->cmp(dst[size - 2], dst[size - 1], store->payload) > 0) {
void *tmp = dst[size - 1];
dst[size - 1] = dst[size - 2];
dst[size - 2] = tmp;
@@ -135,13 +137,15 @@ static ssize_t count_run(void **dst, ssize_t start, ssize_t size, struct tsort_s
return 2;
}
- if (store->cmp(dst[start], dst[start + 1]) <= 0) {
- while (curr < size - 1 && store->cmp(dst[curr - 1], dst[curr]) <= 0)
+ if (store->cmp(dst[start], dst[start + 1], store->payload) <= 0) {
+ while (curr < size - 1 &&
+ store->cmp(dst[curr - 1], dst[curr], store->payload) <= 0)
curr++;
return curr - start;
} else {
- while (curr < size - 1 && store->cmp(dst[curr - 1], dst[curr]) > 0)
+ while (curr < size - 1 &&
+ store->cmp(dst[curr - 1], dst[curr], store->payload) > 0)
curr++;
/* reverse in-place */
@@ -219,7 +223,7 @@ static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr,
for (k = curr; k < curr + A + B; k++) {
if ((i < A) && (j < curr + A + B)) {
- if (store->cmp(storage[i], dst[j]) <= 0)
+ if (store->cmp(storage[i], dst[j], store->payload) <= 0)
dst[k] = storage[i++];
else
dst[k] = dst[j++];
@@ -235,7 +239,7 @@ static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr,
for (k = curr + A + B - 1; k >= curr; k--) {
if ((i >= 0) && (j >= curr)) {
- if (store->cmp(dst[j], storage[i]) > 0)
+ if (store->cmp(dst[j], storage[i], store->payload) > 0)
dst[k] = dst[j--];
else
dst[k] = storage[i--];
@@ -307,7 +311,7 @@ static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr,
if (run < minrun) run = minrun;\
if (run > (ssize_t)size - curr) run = size - curr;\
if (run > len) {\
- bisort(&dst[curr], len, run, cmp);\
+ bisort(&dst[curr], len, run, cmp, payload);\
len = run;\
}\
run_stack[stack_curr].start = curr;\
@@ -329,7 +333,8 @@ static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr,
}\
while (0)
-void git__tsort(void **dst, size_t size, cmp_ptr_t cmp)
+void git__tsort_r(
+ void **dst, size_t size, git__tsort_r_cmp cmp, void *payload)
{
struct tsort_store _store, *store = &_store;
struct tsort_run run_stack[128];
@@ -340,7 +345,7 @@ void git__tsort(void **dst, size_t size, cmp_ptr_t cmp)
ssize_t minrun;
if (size < 64) {
- bisort(dst, 1, size, cmp);
+ bisort(dst, 1, size, cmp, payload);
return;
}
@@ -351,6 +356,7 @@ void git__tsort(void **dst, size_t size, cmp_ptr_t cmp)
store->alloc = 0;
store->storage = NULL;
store->cmp = cmp;
+ store->payload = payload;
PUSH_NEXT();
PUSH_NEXT();
@@ -365,3 +371,13 @@ void git__tsort(void **dst, size_t size, cmp_ptr_t cmp)
PUSH_NEXT();
}
}
+
+static int tsort_r_cmp(const void *a, const void *b, void *payload)
+{
+ return ((git__tsort_cmp)payload)(a, b);
+}
+
+void git__tsort(void **dst, size_t size, git__tsort_cmp cmp)
+{
+ git__tsort_r(dst, size, tsort_r_cmp, cmp);
+}