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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include "cache.h"
#include "path-list.h"
/* if there is no exact match, point to the index where the entry could be
* inserted */
static int get_entry_index(const struct path_list *list, const char *path,
int *exact_match)
{
int left = -1, right = list->nr;
while (left + 1 < right) {
int middle = (left + right) / 2;
int compare = strcmp(path, list->items[middle].path);
if (compare < 0)
right = middle;
else if (compare > 0)
left = middle;
else {
*exact_match = 1;
return middle;
}
}
*exact_match = 0;
return right;
}
/* returns -1-index if already exists */
static int add_entry(struct path_list *list, const char *path)
{
int exact_match;
int index = get_entry_index(list, path, &exact_match);
if (exact_match)
return -1 - index;
if (list->nr + 1 >= list->alloc) {
list->alloc += 32;
list->items = xrealloc(list->items, list->alloc
* sizeof(struct path_list_item));
}
if (index < list->nr)
memmove(list->items + index + 1, list->items + index,
(list->nr - index)
* sizeof(struct path_list_item));
list->items[index].path = list->strdup_paths ?
xstrdup(path) : (char *)path;
list->items[index].util = NULL;
list->nr++;
return index;
}
struct path_list_item *path_list_insert(const char *path, struct path_list *list)
{
int index = add_entry(list, path);
if (index < 0)
index = -1 - index;
return list->items + index;
}
int path_list_has_path(const struct path_list *list, const char *path)
{
int exact_match;
get_entry_index(list, path, &exact_match);
return exact_match;
}
struct path_list_item *path_list_lookup(const char *path, struct path_list *list)
{
int exact_match, i = get_entry_index(list, path, &exact_match);
if (!exact_match)
return NULL;
return list->items + i;
}
void path_list_clear(struct path_list *list, int free_util)
{
if (list->items) {
int i;
if (list->strdup_paths) {
for (i = 0; i < list->nr; i++)
free(list->items[i].path);
}
if (free_util) {
for (i = 0; i < list->nr; i++)
free(list->items[i].util);
}
free(list->items);
}
list->items = NULL;
list->nr = list->alloc = 0;
}
void print_path_list(const char *text, const struct path_list *p)
{
int i;
if ( text )
printf("%s\n", text);
for (i = 0; i < p->nr; i++)
printf("%s:%p\n", p->items[i].path, p->items[i].util);
}
struct path_list_item *path_list_append(const char *path, struct path_list *list)
{
ALLOC_GROW(list->items, list->nr + 1, list->alloc);
list->items[list->nr].path =
list->strdup_paths ? xstrdup(path) : (char *)path;
return list->items + list->nr++;
}
static int cmp_items(const void *a, const void *b)
{
const struct path_list_item *one = a;
const struct path_list_item *two = b;
return strcmp(one->path, two->path);
}
void sort_path_list(struct path_list *list)
{
qsort(list->items, list->nr, sizeof(*list->items), cmp_items);
}
int unsorted_path_list_has_path(struct path_list *list, const char *path)
{
int i;
for (i = 0; i < list->nr; i++)
if (!strcmp(path, list->items[i].path))
return 1;
return 0;
}
|
