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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
#include "cache.h"
#include "string-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 string_list *list, const char *string,
int *exact_match)
{
int left = -1, right = list->nr;
while (left + 1 < right) {
int middle = (left + right) / 2;
int compare = strcmp(string, list->items[middle].string);
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(int insert_at, struct string_list *list, const char *string)
{
int exact_match = 0;
int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &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 string_list_item));
}
if (index < list->nr)
memmove(list->items + index + 1, list->items + index,
(list->nr - index)
* sizeof(struct string_list_item));
list->items[index].string = list->strdup_strings ?
xstrdup(string) : (char *)string;
list->items[index].util = NULL;
list->nr++;
return index;
}
struct string_list_item *string_list_insert(const char *string, struct string_list *list)
{
return string_list_insert_at_index(-1, string, list);
}
struct string_list_item *string_list_insert_at_index(int insert_at,
const char *string, struct string_list *list)
{
int index = add_entry(insert_at, list, string);
if (index < 0)
index = -1 - index;
return list->items + index;
}
int string_list_has_string(const struct string_list *list, const char *string)
{
int exact_match;
get_entry_index(list, string, &exact_match);
return exact_match;
}
int string_list_find_insert_index(const struct string_list *list, const char *string,
int negative_existing_index)
{
int exact_match;
int index = get_entry_index(list, string, &exact_match);
if (exact_match)
index = -1 - (negative_existing_index ? index : 0);
return index;
}
struct string_list_item *string_list_lookup(const char *string, struct string_list *list)
{
int exact_match, i = get_entry_index(list, string, &exact_match);
if (!exact_match)
return NULL;
return list->items + i;
}
void string_list_clear(struct string_list *list, int free_util)
{
if (list->items) {
int i;
if (list->strdup_strings) {
for (i = 0; i < list->nr; i++)
free(list->items[i].string);
}
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 string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc)
{
if (list->items) {
int i;
if (clearfunc) {
for (i = 0; i < list->nr; i++)
clearfunc(list->items[i].util, list->items[i].string);
}
if (list->strdup_strings) {
for (i = 0; i < list->nr; i++)
free(list->items[i].string);
}
free(list->items);
}
list->items = NULL;
list->nr = list->alloc = 0;
}
void print_string_list(const char *text, const struct string_list *p)
{
int i;
if ( text )
printf("%s\n", text);
for (i = 0; i < p->nr; i++)
printf("%s:%p\n", p->items[i].string, p->items[i].util);
}
struct string_list_item *string_list_append(const char *string, struct string_list *list)
{
ALLOC_GROW(list->items, list->nr + 1, list->alloc);
list->items[list->nr].string =
list->strdup_strings ? xstrdup(string) : (char *)string;
return list->items + list->nr++;
}
static int cmp_items(const void *a, const void *b)
{
const struct string_list_item *one = a;
const struct string_list_item *two = b;
return strcmp(one->string, two->string);
}
void sort_string_list(struct string_list *list)
{
qsort(list->items, list->nr, sizeof(*list->items), cmp_items);
}
int unsorted_string_list_has_string(struct string_list *list, const char *string)
{
int i;
for (i = 0; i < list->nr; i++)
if (!strcmp(string, list->items[i].string))
return 1;
return 0;
}
|
