Skip to content

Commit e2e4bae

Browse files
author
Edward Thomson
committed
tree: drop the now-unnecessary entries vector
Remove the now-unnecessary entries vector. Add `git_array_search` to binary search through an array to accomplish this.
1 parent 7adca53 commit e2e4bae

File tree

4 files changed

+125
-46
lines changed

4 files changed

+125
-46
lines changed

‎src/array.h‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -82,4 +82,44 @@ GIT_INLINE(void *) git_array_grow(void *_a, size_t item_size)
8282

8383
#define git_array_valid_index(a, i) ((i) < (a).size)
8484

85+
#define git_array_foreach(a, i, element) \
86+
for ((i) = 0; (i) < (a).size && ((element) = &(a).ptr[(i)]); (i)++)
87+
88+
89+
GIT_INLINE(int) git_array__search(
90+
size_t *out,
91+
void *array_ptr,
92+
size_t item_size,
93+
size_t array_len,
94+
int (*compare)(const void *, const void *),
95+
const void *key)
96+
{
97+
size_t lim;
98+
unsigned char *part, *array = array_ptr, *base = array_ptr;
99+
int cmp;
100+
101+
for (lim = array_len; lim != 0; lim >>= 1) {
102+
part = base + (lim >> 1) * item_size;
103+
cmp = (*compare)(key, part);
104+
105+
if (cmp == 0) {
106+
base = part;
107+
break;
108+
}
109+
if (cmp > 0) { /* key > p; take right partition */
110+
base = part + 1 * item_size;
111+
lim--;
112+
} /* else take left partition */
113+
}
114+
115+
if (out)
116+
*out = (base - array) / item_size;
117+
118+
return (cmp == 0) ? 0 : GIT_ENOTFOUND;
119+
}
120+
121+
#define git_array_search(out, a, cmp, key) \
122+
git_array__search(out, (a).ptr, sizeof(*(a).ptr), (a).size, \
123+
(cmp), (key))
124+
85125
#endif

‎src/tree.c‎

Lines changed: 29 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -163,7 +163,10 @@ static int homing_search_cmp(const void *key, const void *array_member)
163163
* around the area for our target file.
164164
*/
165165
static int tree_key_search(
166-
size_t *at_pos, git_vector *entries, const char *filename, size_t filename_len)
166+
size_t *at_pos,
167+
const git_tree *tree,
168+
const char *filename,
169+
size_t filename_len)
167170
{
168171
struct tree_key_search ksearch;
169172
const git_tree_entry *entry;
@@ -176,13 +179,15 @@ static int tree_key_search(
176179

177180
/* Initial homing search; find an entry on the tree with
178181
* the same prefix as the filename we're looking for */
179-
if (git_vector_bsearch2(&homing, entries, &homing_search_cmp, &ksearch) < 0)
182+
183+
if (git_array_search(&homing,
184+
tree->entries, &homing_search_cmp, &ksearch) < 0)
180185
return GIT_ENOTFOUND; /* just a signal error; not passed back to user */
181186

182187
/* We found a common prefix. Look forward as long as
183188
* there are entries that share the common prefix */
184-
for (i = homing; i < entries->length; ++i) {
185-
entry = entries->contents[i];
189+
for (i = homing; i < tree->entries.size; ++i) {
190+
entry = git_array_get(tree->entries, i);
186191

187192
if (homing_search_cmp(&ksearch, entry) < 0)
188193
break;
@@ -202,7 +207,7 @@ static int tree_key_search(
202207
i = homing - 1;
203208

204209
do {
205-
entry = entries->contents[i];
210+
entry = git_array_get(tree->entries, i);
206211

207212
if (homing_search_cmp(&ksearch, entry) > 0)
208213
break;
@@ -250,8 +255,7 @@ void git_tree__free(void *_tree)
250255
git_tree *tree = _tree;
251256

252257
git_odb_object_free(tree->odb_obj);
253-
git_vector_free(&tree->entries);
254-
git_array_clear(tree->entries_arr);
258+
git_array_clear(tree->entries);
255259
git__free(tree);
256260
}
257261

@@ -303,13 +307,10 @@ static const git_tree_entry *entry_fromname(
303307
{
304308
size_t idx;
305309

306-
/* be safe when we cast away constness - i.e. don't trigger a sort */
307-
assert(git_vector_is_sorted(&tree->entries));
308-
309-
if (tree_key_search(&idx, (git_vector *)&tree->entries, name, name_len) < 0)
310+
if (tree_key_search(&idx, tree, name, name_len) < 0)
310311
return NULL;
311312

312-
return git_vector_get(&tree->entries, idx);
313+
return git_array_get(tree->entries, idx);
313314
}
314315

315316
const git_tree_entry *git_tree_entry_byname(
@@ -324,7 +325,7 @@ const git_tree_entry *git_tree_entry_byindex(
324325
const git_tree *tree, size_t idx)
325326
{
326327
assert(tree);
327-
return git_vector_get(&tree->entries, idx);
328+
return git_array_get(tree->entries, idx);
328329
}
329330

330331
const git_tree_entry *git_tree_entry_byid(
@@ -335,7 +336,7 @@ const git_tree_entry *git_tree_entry_byid(
335336

336337
assert(tree);
337338

338-
git_vector_foreach(&tree->entries, i, e) {
339+
git_array_foreach(tree->entries, i, e) {
339340
if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0)
340341
return e;
341342
}
@@ -345,7 +346,6 @@ const git_tree_entry *git_tree_entry_byid(
345346

346347
int git_tree__prefix_position(const git_tree *tree, const char *path)
347348
{
348-
const git_vector *entries = &tree->entries;
349349
struct tree_key_search ksearch;
350350
size_t at_pos, path_len;
351351

@@ -358,21 +358,20 @@ int git_tree__prefix_position(const git_tree *tree, const char *path)
358358
ksearch.filename = path;
359359
ksearch.filename_len = (uint16_t)path_len;
360360

361-
/* be safe when we cast away constness - i.e. don't trigger a sort */
362-
assert(git_vector_is_sorted(&tree->entries));
363-
364361
/* Find tree entry with appropriate prefix */
365-
git_vector_bsearch2(
366-
&at_pos, (git_vector *)entries, &homing_search_cmp, &ksearch);
362+
git_array_search(
363+
&at_pos, tree->entries, &homing_search_cmp, &ksearch);
367364

368-
for (; at_pos < entries->length; ++at_pos) {
369-
const git_tree_entry *entry = entries->contents[at_pos];
365+
for (; at_pos < tree->entries.size; ++at_pos) {
366+
const git_tree_entry *entry = git_array_get(tree->entries, at_pos);
370367
if (homing_search_cmp(&ksearch, entry) < 0)
371368
break;
372369
}
373370

374371
for (; at_pos > 0; --at_pos) {
375-
const git_tree_entry *entry = entries->contents[at_pos - 1];
372+
const git_tree_entry *entry =
373+
git_array_get(tree->entries, at_pos - 1);
374+
376375
if (homing_search_cmp(&ksearch, entry) > 0)
377376
break;
378377
}
@@ -383,7 +382,7 @@ int git_tree__prefix_position(const git_tree *tree, const char *path)
383382
size_t git_tree_entrycount(const git_tree *tree)
384383
{
385384
assert(tree);
386-
return tree->entries.length;
385+
return tree->entries.size;
387386
}
388387

389388
unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
@@ -423,7 +422,6 @@ static int parse_mode(unsigned int *modep, const char *buffer, const char **buff
423422

424423
int git_tree__parse(void *_tree, git_odb_object *odb_obj)
425424
{
426-
size_t i;
427425
git_tree *tree = _tree;
428426
const char *buffer;
429427
const char *buffer_end;
@@ -434,8 +432,8 @@ int git_tree__parse(void *_tree, git_odb_object *odb_obj)
434432
buffer = git_odb_object_data(tree->odb_obj);
435433
buffer_end = buffer + git_odb_object_size(tree->odb_obj);
436434

437-
git_array_init_to_size(tree->entries_arr, DEFAULT_TREE_SIZE);
438-
GITERR_CHECK_ARRAY(tree->entries_arr);
435+
git_array_init_to_size(tree->entries, DEFAULT_TREE_SIZE);
436+
GITERR_CHECK_ARRAY(tree->entries);
439437

440438
while (buffer < buffer_end) {
441439
git_tree_entry *entry;
@@ -450,9 +448,9 @@ int git_tree__parse(void *_tree, git_odb_object *odb_obj)
450448
return tree_error("Failed to parse tree. Object is corrupted", NULL);
451449

452450
filename_len = nul - buffer;
453-
/** Allocate the entry and store it in the entries vector */
451+
/* Allocate the entry */
454452
{
455-
entry = git_array_alloc(tree->entries_arr);
453+
entry = git_array_alloc(tree->entries);
456454
GITERR_CHECK_ALLOC(entry);
457455

458456
entry->attr = attr;
@@ -465,18 +463,6 @@ int git_tree__parse(void *_tree, git_odb_object *odb_obj)
465463
buffer += GIT_OID_RAWSZ;
466464
}
467465

468-
/* Add the entries to the vector here, as we may reallocate during the loop */
469-
if (git_vector_init(&tree->entries, tree->entries_arr.size, entry_sort_cmp) < 0)
470-
return -1;
471-
472-
for (i = 0; i < tree->entries_arr.size; i++) {
473-
if (git_vector_insert(&tree->entries, git_array_get(tree->entries_arr, i)) < 0)
474-
return -1;
475-
}
476-
477-
/* The tree is sorted by definition. Bad inputs give bad outputs */
478-
tree->entries.flags |= GIT_VECTOR_SORTED;
479-
480466
return 0;
481467
}
482468

@@ -700,7 +686,7 @@ int git_treebuilder_new(
700686
if (source != NULL) {
701687
git_tree_entry *entry_src;
702688

703-
git_vector_foreach(&source->entries, i, entry_src) {
689+
git_array_foreach(source->entries, i, entry_src) {
704690
if (append_entry(
705691
bld, entry_src->filename,
706692
entry_src->oid,
@@ -845,7 +831,6 @@ int git_treebuilder_write(git_oid *oid, git_treebuilder *bld)
845831
error = -1;
846832
}
847833

848-
git_vector_free(&entries);
849834

850835
if (!error &&
851836
!(error = git_repository_odb__weakptr(&odb, bld->repo)))
@@ -975,7 +960,7 @@ static int tree_walk(
975960
size_t i;
976961
const git_tree_entry *entry;
977962

978-
git_vector_foreach(&tree->entries, i, entry) {
963+
git_array_foreach(tree->entries, i, entry) {
979964
if (preorder) {
980965
error = callback(path->ptr, entry, payload);
981966
if (error < 0) { /* negative value stops iteration */

‎src/tree.h‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,8 +24,7 @@ struct git_tree_entry {
2424
struct git_tree {
2525
git_object object;
2626
git_odb_object *odb_obj;
27-
git_array_t(git_tree_entry) entries_arr;
28-
git_vector entries;
27+
git_array_t(git_tree_entry) entries;
2928
};
3029

3130
struct git_treebuilder {

‎tests/core/array.c‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
#include "clar_libgit2.h"
2+
#include "array.h"
3+
4+
static int int_lookup(const void *k, const void *a)
5+
{
6+
const int *one = (const int *)k;
7+
int *two = (int *)a;
8+
9+
return *one - *two;
10+
}
11+
12+
#define expect_pos(k, n, ret) \
13+
key = (k); \
14+
cl_assert_equal_i((ret), \
15+
git_array_search(&p, integers, int_lookup, &key)); \
16+
cl_assert_equal_i((n), p);
17+
18+
void test_core_array__bsearch2(void)
19+
{
20+
git_array_t(int) integers = GIT_ARRAY_INIT;
21+
int *i, key;
22+
size_t p;
23+
24+
i = git_array_alloc(integers); *i = 2;
25+
i = git_array_alloc(integers); *i = 3;
26+
i = git_array_alloc(integers); *i = 5;
27+
i = git_array_alloc(integers); *i = 7;
28+
i = git_array_alloc(integers); *i = 7;
29+
i = git_array_alloc(integers); *i = 8;
30+
i = git_array_alloc(integers); *i = 13;
31+
i = git_array_alloc(integers); *i = 21;
32+
i = git_array_alloc(integers); *i = 25;
33+
i = git_array_alloc(integers); *i = 42;
34+
i = git_array_alloc(integers); *i = 69;
35+
i = git_array_alloc(integers); *i = 121;
36+
i = git_array_alloc(integers); *i = 256;
37+
i = git_array_alloc(integers); *i = 512;
38+
i = git_array_alloc(integers); *i = 513;
39+
i = git_array_alloc(integers); *i = 514;
40+
i = git_array_alloc(integers); *i = 516;
41+
i = git_array_alloc(integers); *i = 516;
42+
i = git_array_alloc(integers); *i = 517;
43+
44+
/* value to search for, expected position, return code */
45+
expect_pos(3, 1, GIT_OK);
46+
expect_pos(2, 0, GIT_OK);
47+
expect_pos(1, 0, GIT_ENOTFOUND);
48+
expect_pos(25, 8, GIT_OK);
49+
expect_pos(26, 9, GIT_ENOTFOUND);
50+
expect_pos(42, 9, GIT_OK);
51+
expect_pos(50, 10, GIT_ENOTFOUND);
52+
expect_pos(68, 10, GIT_ENOTFOUND);
53+
expect_pos(256, 12, GIT_OK);
54+
}
55+

0 commit comments

Comments
 (0)