| 1 | #include "git-compat-util.h" |
| 2 | #include "string-list.h" |
| 3 | |
| 4 | void string_list_init_nodup(struct string_list *list) |
| 5 | { |
| 6 | struct string_list blank = STRING_LIST_INIT_NODUP; |
| 7 | memcpy(list, &blank, sizeof(*list)); |
| 8 | } |
| 9 | |
| 10 | void string_list_init_dup(struct string_list *list) |
| 11 | { |
| 12 | struct string_list blank = STRING_LIST_INIT_DUP; |
| 13 | memcpy(list, &blank, sizeof(*list)); |
| 14 | } |
| 15 | |
| 16 | /* if there is no exact match, point to the index where the entry could be |
| 17 | * inserted */ |
| 18 | static size_t get_entry_index(const struct string_list *list, const char *string, |
| 19 | bool *exact_match) |
| 20 | { |
| 21 | size_t left = 0, right = list->nr; |
| 22 | compare_strings_fn cmp = list->cmp ? list->cmp : strcmp; |
| 23 | |
| 24 | while (left < right) { |
| 25 | size_t middle = left + (right - left) / 2; |
| 26 | int compare = cmp(string, list->items[middle].string); |
| 27 | if (compare < 0) |
| 28 | right = middle; |
| 29 | else if (compare > 0) |
| 30 | left = middle + 1; |
| 31 | else { |
| 32 | if (exact_match) |
| 33 | *exact_match = true; |
| 34 | return middle; |
| 35 | } |
| 36 | } |
| 37 | |
| 38 | if (exact_match) |
| 39 | *exact_match = false; |
| 40 | return right; |
| 41 | } |
| 42 | |
| 43 | static size_t add_entry(struct string_list *list, const char *string) |
| 44 | { |
| 45 | bool exact_match; |
| 46 | size_t index = get_entry_index(list, string, &exact_match); |
| 47 | |
| 48 | if (exact_match) |
| 49 | return index; |
| 50 | |
| 51 | ALLOC_GROW(list->items, list->nr+1, list->alloc); |
| 52 | if (index < list->nr) |
| 53 | MOVE_ARRAY(list->items + index + 1, list->items + index, |
| 54 | list->nr - index); |
| 55 | list->items[index].string = list->strdup_strings ? |
| 56 | xstrdup(string) : (char *)string; |
| 57 | list->items[index].util = NULL; |
| 58 | list->nr++; |
| 59 | |
| 60 | return index; |
| 61 | } |
| 62 | |
| 63 | struct string_list_item *string_list_insert(struct string_list *list, const char *string) |
| 64 | { |
| 65 | size_t index = add_entry(list, string); |
| 66 | |
| 67 | return list->items + index; |
| 68 | } |
| 69 | |
| 70 | void string_list_remove(struct string_list *list, const char *string, |
| 71 | int free_util) |
| 72 | { |
| 73 | bool exact_match; |
| 74 | int i = get_entry_index(list, string, &exact_match); |
| 75 | |
| 76 | if (exact_match) { |
| 77 | if (list->strdup_strings) |
| 78 | free(list->items[i].string); |
| 79 | if (free_util) |
| 80 | free(list->items[i].util); |
| 81 | |
| 82 | list->nr--; |
| 83 | MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i); |
| 84 | } |
| 85 | } |
| 86 | |
| 87 | bool string_list_has_string(const struct string_list *list, const char *string) |
| 88 | { |
| 89 | bool exact_match; |
| 90 | get_entry_index(list, string, &exact_match); |
| 91 | return exact_match; |
| 92 | } |
| 93 | |
| 94 | size_t string_list_find_insert_index(const struct string_list *list, const char *string, |
| 95 | bool *exact_match) |
| 96 | { |
| 97 | return get_entry_index(list, string, exact_match); |
| 98 | } |
| 99 | |
| 100 | struct string_list_item *string_list_lookup(struct string_list *list, const char *string) |
| 101 | { |
| 102 | bool exact_match; |
| 103 | size_t i = get_entry_index(list, string, &exact_match); |
| 104 | if (!exact_match) |
| 105 | return NULL; |
| 106 | return list->items + i; |
| 107 | } |
| 108 | |
| 109 | void string_list_remove_duplicates(struct string_list *list, int free_util) |
| 110 | { |
| 111 | if (list->nr > 1) { |
| 112 | size_t dst = 1; |
| 113 | compare_strings_fn cmp = list->cmp ? list->cmp : strcmp; |
| 114 | for (size_t src = 1; src < list->nr; src++) { |
| 115 | if (!cmp(list->items[dst - 1].string, list->items[src].string)) { |
| 116 | if (list->strdup_strings) |
| 117 | free(list->items[src].string); |
| 118 | if (free_util) |
| 119 | free(list->items[src].util); |
| 120 | } else |
| 121 | list->items[dst++] = list->items[src]; |
| 122 | } |
| 123 | list->nr = dst; |
| 124 | } |
| 125 | } |
| 126 | |
| 127 | int for_each_string_list(struct string_list *list, |
| 128 | string_list_each_func_t fn, void *cb_data) |
| 129 | { |
| 130 | int ret = 0; |
| 131 | for (size_t i = 0; i < list->nr; i++) |
| 132 | if ((ret = fn(&list->items[i], cb_data))) |
| 133 | break; |
| 134 | return ret; |
| 135 | } |
| 136 | |
| 137 | void filter_string_list(struct string_list *list, int free_util, |
| 138 | string_list_each_func_t want, void *cb_data) |
| 139 | { |
| 140 | size_t dst = 0; |
| 141 | for (size_t src = 0; src < list->nr; src++) { |
| 142 | if (want(&list->items[src], cb_data)) { |
| 143 | list->items[dst++] = list->items[src]; |
| 144 | } else { |
| 145 | if (list->strdup_strings) |
| 146 | free(list->items[src].string); |
| 147 | if (free_util) |
| 148 | free(list->items[src].util); |
| 149 | } |
| 150 | } |
| 151 | list->nr = dst; |
| 152 | } |
| 153 | |
| 154 | static int item_is_not_empty(struct string_list_item *item, void *data UNUSED) |
| 155 | { |
| 156 | return *item->string != '\0'; |
| 157 | } |
| 158 | |
| 159 | void string_list_remove_empty_items(struct string_list *list, int free_util) |
| 160 | { |
| 161 | filter_string_list(list, free_util, item_is_not_empty, NULL); |
| 162 | } |
| 163 | |
| 164 | void string_list_clear(struct string_list *list, int free_util) |
| 165 | { |
| 166 | if (list->items) { |
| 167 | if (list->strdup_strings) { |
| 168 | for (size_t i = 0; i < list->nr; i++) |
| 169 | free(list->items[i].string); |
| 170 | } |
| 171 | if (free_util) { |
| 172 | for (size_t i = 0; i < list->nr; i++) |
| 173 | free(list->items[i].util); |
| 174 | } |
| 175 | free(list->items); |
| 176 | } |
| 177 | list->items = NULL; |
| 178 | list->nr = list->alloc = 0; |
| 179 | } |
| 180 | |
| 181 | void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc) |
| 182 | { |
| 183 | if (list->items) { |
| 184 | if (clearfunc) { |
| 185 | for (size_t i = 0; i < list->nr; i++) |
| 186 | clearfunc(list->items[i].util, list->items[i].string); |
| 187 | } |
| 188 | if (list->strdup_strings) { |
| 189 | for (size_t i = 0; i < list->nr; i++) |
| 190 | free(list->items[i].string); |
| 191 | } |
| 192 | free(list->items); |
| 193 | } |
| 194 | list->items = NULL; |
| 195 | list->nr = list->alloc = 0; |
| 196 | } |
| 197 | |
| 198 | void string_list_setlen(struct string_list *list, size_t nr) |
| 199 | { |
| 200 | if (list->strdup_strings) |
| 201 | BUG("cannot setlen a string_list which owns its entries"); |
| 202 | if (nr > list->nr) |
| 203 | BUG("cannot grow a string_list with setlen"); |
| 204 | list->nr = nr; |
| 205 | } |
| 206 | |
| 207 | struct string_list_item *string_list_append_nodup(struct string_list *list, |
| 208 | char *string) |
| 209 | { |
| 210 | struct string_list_item *retval; |
| 211 | ALLOC_GROW(list->items, list->nr + 1, list->alloc); |
| 212 | retval = &list->items[list->nr++]; |
| 213 | retval->string = string; |
| 214 | retval->util = NULL; |
| 215 | return retval; |
| 216 | } |
| 217 | |
| 218 | struct string_list_item *string_list_append(struct string_list *list, |
| 219 | const char *string) |
| 220 | { |
| 221 | return string_list_append_nodup( |
| 222 | list, |
| 223 | list->strdup_strings ? xstrdup(string) : (char *)string); |
| 224 | } |
| 225 | |
| 226 | /* |
| 227 | * Encapsulate the compare function pointer because ISO C99 forbids |
| 228 | * casting from void * to a function pointer and vice versa. |
| 229 | */ |
| 230 | struct string_list_sort_ctx |
| 231 | { |
| 232 | compare_strings_fn cmp; |
| 233 | }; |
| 234 | |
| 235 | static int cmp_items(const void *a, const void *b, void *ctx) |
| 236 | { |
| 237 | struct string_list_sort_ctx *sort_ctx = ctx; |
| 238 | const struct string_list_item *one = a; |
| 239 | const struct string_list_item *two = b; |
| 240 | return sort_ctx->cmp(one->string, two->string); |
| 241 | } |
| 242 | |
| 243 | void string_list_sort(struct string_list *list) |
| 244 | { |
| 245 | struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp}; |
| 246 | |
| 247 | QSORT_S(list->items, list->nr, cmp_items, &sort_ctx); |
| 248 | } |
| 249 | |
| 250 | void string_list_sort_u(struct string_list *list, int free_util) |
| 251 | { |
| 252 | string_list_sort(list); |
| 253 | string_list_remove_duplicates(list, free_util); |
| 254 | } |
| 255 | |
| 256 | struct string_list_item *unsorted_string_list_lookup(struct string_list *list, |
| 257 | const char *string) |
| 258 | { |
| 259 | struct string_list_item *item; |
| 260 | compare_strings_fn cmp = list->cmp ? list->cmp : strcmp; |
| 261 | |
| 262 | for_each_string_list_item(item, list) |
| 263 | if (!cmp(string, item->string)) |
| 264 | return item; |
| 265 | return NULL; |
| 266 | } |
| 267 | |
| 268 | int unsorted_string_list_has_string(struct string_list *list, |
| 269 | const char *string) |
| 270 | { |
| 271 | return unsorted_string_list_lookup(list, string) != NULL; |
| 272 | } |
| 273 | |
| 274 | void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util) |
| 275 | { |
| 276 | if (list->strdup_strings) |
| 277 | free(list->items[i].string); |
| 278 | if (free_util) |
| 279 | free(list->items[i].util); |
| 280 | list->items[i] = list->items[list->nr-1]; |
| 281 | list->nr--; |
| 282 | } |
| 283 | |
| 284 | void unsorted_string_list_remove(struct string_list *list, const char *str, |
| 285 | int free_util) |
| 286 | { |
| 287 | struct string_list_item *item = unsorted_string_list_lookup(list, str); |
| 288 | if (item) |
| 289 | unsorted_string_list_delete_item(list, item - list->items, |
| 290 | free_util); |
| 291 | } |
| 292 | |
| 293 | /* |
| 294 | * append a substring [p..end] to list; return number of things it |
| 295 | * appended to the list. |
| 296 | */ |
| 297 | static int append_one(struct string_list *list, |
| 298 | const char *p, const char *end, |
| 299 | int in_place, unsigned flags) |
| 300 | { |
| 301 | if (!end) |
| 302 | end = p + strlen(p); |
| 303 | |
| 304 | if ((flags & STRING_LIST_SPLIT_TRIM)) { |
| 305 | /* rtrim */ |
| 306 | for (; p < end; end--) |
| 307 | if (!isspace(end[-1])) |
| 308 | break; |
| 309 | } |
| 310 | |
| 311 | if ((flags & STRING_LIST_SPLIT_NONEMPTY) && (end <= p)) |
| 312 | return 0; |
| 313 | |
| 314 | if (in_place) { |
| 315 | *((char *)end) = '\0'; |
| 316 | string_list_append(list, p); |
| 317 | } else { |
| 318 | string_list_append_nodup(list, xmemdupz(p, end - p)); |
| 319 | } |
| 320 | return 1; |
| 321 | } |
| 322 | |
| 323 | /* |
| 324 | * Unfortunately this cannot become a public interface, as _in_place() |
| 325 | * wants to have "const char *string" while the other variant wants to |
| 326 | * have "char *string" for type safety. |
| 327 | * |
| 328 | * This accepts "const char *string" to allow both wrappers to use it; |
| 329 | * it internally casts away the constness when in_place is true by |
| 330 | * taking advantage of strpbrk() that takes a "const char *" arg and |
| 331 | * returns "char *" pointer into that const string. Yucky but works ;-). |
| 332 | */ |
| 333 | static int split_string(struct string_list *list, const char *string, const char *delim, |
| 334 | int maxsplit, int in_place, unsigned flags) |
| 335 | { |
| 336 | int count = 0; |
| 337 | const char *p = string; |
| 338 | |
| 339 | if (in_place && list->strdup_strings) |
| 340 | BUG("string_list_split_in_place() called with strdup_strings"); |
| 341 | else if (!in_place && !list->strdup_strings) |
| 342 | BUG("string_list_split() called without strdup_strings"); |
| 343 | |
| 344 | for (;;) { |
| 345 | const char *end; |
| 346 | |
| 347 | if (flags & STRING_LIST_SPLIT_TRIM) { |
| 348 | /* ltrim */ |
| 349 | while (*p && isspace(*p)) |
| 350 | p++; |
| 351 | } |
| 352 | |
| 353 | if (0 <= maxsplit && maxsplit <= count) |
| 354 | end = NULL; |
| 355 | else |
| 356 | end = strpbrk(p, delim); |
| 357 | |
| 358 | count += append_one(list, p, end, in_place, flags); |
| 359 | |
| 360 | if (!end) |
| 361 | return count; |
| 362 | p = end + 1; |
| 363 | } |
| 364 | } |
| 365 | |
| 366 | int string_list_split(struct string_list *list, const char *string, |
| 367 | const char *delim, int maxsplit) |
| 368 | { |
| 369 | return split_string(list, string, delim, maxsplit, 0, 0); |
| 370 | } |
| 371 | |
| 372 | int string_list_split_in_place(struct string_list *list, char *string, |
| 373 | const char *delim, int maxsplit) |
| 374 | { |
| 375 | return split_string(list, string, delim, maxsplit, 1, 0); |
| 376 | } |
| 377 | |
| 378 | int string_list_split_f(struct string_list *list, const char *string, |
| 379 | const char *delim, int maxsplit, unsigned flags) |
| 380 | { |
| 381 | return split_string(list, string, delim, maxsplit, 0, flags); |
| 382 | } |
| 383 | |
| 384 | int string_list_split_in_place_f(struct string_list *list, char *string, |
| 385 | const char *delim, int maxsplit, unsigned flags) |
| 386 | { |
| 387 | return split_string(list, string, delim, maxsplit, 1, flags); |
| 388 | } |