1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| | #include "git-compat-util.h"
#include "unique-prefix.h"
static int prefix_item_ptr_cmp(const void *item1, const void *item2)
{
const struct prefix_item *pi1 = *((struct prefix_item**) item1);
const struct prefix_item *pi2 = *((struct prefix_item**) item2);
return strcmp(pi1->name, pi2->name);
}
static int str_is_shorter_than(const char *s, size_t len)
{
for (; *s && len; s++, len--);
return !!len;
}
static size_t str_common_prefix_len(const char *s1, const char *s2, size_t limit)
{
size_t i;
for (i = 0; i < limit; i++)
if (s1[i] != s2[i] || s1[i] == '\0')
return i;
return limit + 1;
}
void find_unique_prefixes(struct prefix_item **items, size_t nr,
int min_length, int max_length)
{
size_t i;
struct prefix_item **sorted_items;
ALLOC_ARRAY(sorted_items, nr);
COPY_ARRAY(sorted_items, items, nr);
QSORT(sorted_items, nr, prefix_item_ptr_cmp);
if (str_is_shorter_than(sorted_items[0]->name, min_length))
sorted_items[0]->prefix_length = 0;
else
sorted_items[0]->prefix_length = min_length;
for (i = 1; i < nr; i++) {
size_t common_len = str_common_prefix_len(
sorted_items[i - 1]->name, sorted_items[i]->name,
max_length);
if (!sorted_items[i - 1]->prefix_length)
/*
* The previous iteration already determined that
* it doesn't have a unique prefix.
*/
;
else if (max_length < common_len)
sorted_items[i - 1]->prefix_length = 0;
else if (sorted_items[i - 1]->name[common_len] == '\0')
/* Either prefix of or equal to the next string. */
sorted_items[i - 1]->prefix_length = 0;
else if (sorted_items[i - 1]->prefix_length <= common_len)
sorted_items[i - 1]->prefix_length = common_len + 1;
if (max_length < common_len)
sorted_items[i]->prefix_length = 0;
else if (sorted_items[i]->name[common_len] == '\0')
/* the two strings are the same */
sorted_items[i]->prefix_length = 0;
else if (min_length <= common_len)
sorted_items[i]->prefix_length = common_len + 1;
else if (str_is_shorter_than(sorted_items[i]->name, min_length))
sorted_items[i]->prefix_length = 0;
else
sorted_items[i]->prefix_length = min_length;
}
free(sorted_items);
}
|