Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 1 | #include "cache.h" |
| 2 | #include "string-list.h" |
| 3 | |
Tanay Abhra | 3ed3f5f | 2014-07-18 02:18:59 -0700 | [diff] [blame] | 4 | void string_list_init(struct string_list *list, int strdup_strings) |
| 5 | { |
| 6 | memset(list, 0, sizeof(*list)); |
| 7 | list->strdup_strings = strdup_strings; |
| 8 | } |
| 9 | |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 10 | /* if there is no exact match, point to the index where the entry could be |
| 11 | * inserted */ |
| 12 | static int get_entry_index(const struct string_list *list, const char *string, |
| 13 | int *exact_match) |
| 14 | { |
| 15 | int left = -1, right = list->nr; |
Junio C Hamano | 8dd5afc | 2013-01-07 12:24:55 -0800 | [diff] [blame] | 16 | compare_strings_fn cmp = list->cmp ? list->cmp : strcmp; |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 17 | |
| 18 | while (left + 1 < right) { |
Derrick Stolee | 19716b2 | 2017-10-08 14:29:37 -0400 | [diff] [blame] | 19 | int middle = left + (right - left) / 2; |
Junio C Hamano | 8dd5afc | 2013-01-07 12:24:55 -0800 | [diff] [blame] | 20 | int compare = cmp(string, list->items[middle].string); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 21 | if (compare < 0) |
| 22 | right = middle; |
| 23 | else if (compare > 0) |
| 24 | left = middle; |
| 25 | else { |
| 26 | *exact_match = 1; |
| 27 | return middle; |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | *exact_match = 0; |
| 32 | return right; |
| 33 | } |
| 34 | |
| 35 | /* returns -1-index if already exists */ |
Marius Storm-Olsen | cfa1ee6 | 2009-02-08 15:34:28 +0100 | [diff] [blame] | 36 | static int add_entry(int insert_at, struct string_list *list, const char *string) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 37 | { |
Marius Storm-Olsen | cfa1ee6 | 2009-02-08 15:34:28 +0100 | [diff] [blame] | 38 | int exact_match = 0; |
| 39 | int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 40 | |
| 41 | if (exact_match) |
| 42 | return -1 - index; |
| 43 | |
Jeff Hostetler | 950a234 | 2017-04-14 19:51:52 +0000 | [diff] [blame] | 44 | ALLOC_GROW(list->items, list->nr+1, list->alloc); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 45 | if (index < list->nr) |
René Scharfe | f331ab9 | 2017-07-15 22:00:45 +0200 | [diff] [blame] | 46 | MOVE_ARRAY(list->items + index + 1, list->items + index, |
| 47 | list->nr - index); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 48 | list->items[index].string = list->strdup_strings ? |
| 49 | xstrdup(string) : (char *)string; |
| 50 | list->items[index].util = NULL; |
| 51 | list->nr++; |
| 52 | |
| 53 | return index; |
| 54 | } |
| 55 | |
Julian Phillips | 78a395d | 2010-06-26 00:41:35 +0100 | [diff] [blame] | 56 | struct string_list_item *string_list_insert(struct string_list *list, const char *string) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 57 | { |
Stefan Beller | f8c4ab6 | 2014-11-24 13:22:04 -0800 | [diff] [blame] | 58 | int index = add_entry(-1, list, string); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 59 | |
| 60 | if (index < 0) |
| 61 | index = -1 - index; |
| 62 | |
| 63 | return list->items + index; |
| 64 | } |
| 65 | |
Brandon Williams | 3a30033 | 2017-04-19 16:13:21 -0700 | [diff] [blame] | 66 | void string_list_remove(struct string_list *list, const char *string, |
| 67 | int free_util) |
| 68 | { |
| 69 | int exact_match; |
| 70 | int i = get_entry_index(list, string, &exact_match); |
| 71 | |
| 72 | if (exact_match) { |
| 73 | if (list->strdup_strings) |
| 74 | free(list->items[i].string); |
| 75 | if (free_util) |
| 76 | free(list->items[i].util); |
| 77 | |
| 78 | list->nr--; |
René Scharfe | f331ab9 | 2017-07-15 22:00:45 +0200 | [diff] [blame] | 79 | MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i); |
Brandon Williams | 3a30033 | 2017-04-19 16:13:21 -0700 | [diff] [blame] | 80 | } |
| 81 | } |
| 82 | |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 83 | int string_list_has_string(const struct string_list *list, const char *string) |
| 84 | { |
| 85 | int exact_match; |
| 86 | get_entry_index(list, string, &exact_match); |
| 87 | return exact_match; |
| 88 | } |
| 89 | |
Marius Storm-Olsen | cfa1ee6 | 2009-02-08 15:34:28 +0100 | [diff] [blame] | 90 | int string_list_find_insert_index(const struct string_list *list, const char *string, |
| 91 | int negative_existing_index) |
| 92 | { |
| 93 | int exact_match; |
| 94 | int index = get_entry_index(list, string, &exact_match); |
| 95 | if (exact_match) |
| 96 | index = -1 - (negative_existing_index ? index : 0); |
| 97 | return index; |
| 98 | } |
| 99 | |
Julian Phillips | e8c8b71 | 2010-06-26 00:41:37 +0100 | [diff] [blame] | 100 | struct string_list_item *string_list_lookup(struct string_list *list, const char *string) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 101 | { |
| 102 | int exact_match, i = get_entry_index(list, string, &exact_match); |
| 103 | if (!exact_match) |
| 104 | return NULL; |
| 105 | return list->items + i; |
| 106 | } |
| 107 | |
Michael Haggerty | 31d5451 | 2012-09-12 16:04:45 +0200 | [diff] [blame] | 108 | void string_list_remove_duplicates(struct string_list *list, int free_util) |
| 109 | { |
| 110 | if (list->nr > 1) { |
| 111 | int src, dst; |
Junio C Hamano | 8dd5afc | 2013-01-07 12:24:55 -0800 | [diff] [blame] | 112 | compare_strings_fn cmp = list->cmp ? list->cmp : strcmp; |
Michael Haggerty | 31d5451 | 2012-09-12 16:04:45 +0200 | [diff] [blame] | 113 | for (src = dst = 1; src < list->nr; src++) { |
Junio C Hamano | 8dd5afc | 2013-01-07 12:24:55 -0800 | [diff] [blame] | 114 | if (!cmp(list->items[dst - 1].string, list->items[src].string)) { |
Michael Haggerty | 31d5451 | 2012-09-12 16:04:45 +0200 | [diff] [blame] | 115 | if (list->strdup_strings) |
| 116 | free(list->items[src].string); |
| 117 | if (free_util) |
| 118 | free(list->items[src].util); |
| 119 | } else |
| 120 | list->items[dst++] = list->items[src]; |
| 121 | } |
| 122 | list->nr = dst; |
| 123 | } |
| 124 | } |
| 125 | |
Julian Phillips | b684e97 | 2010-06-26 00:41:34 +0100 | [diff] [blame] | 126 | int for_each_string_list(struct string_list *list, |
| 127 | string_list_each_func_t fn, void *cb_data) |
Jay Soffian | c6f5a7a | 2009-02-25 03:32:18 -0500 | [diff] [blame] | 128 | { |
| 129 | int i, ret = 0; |
| 130 | for (i = 0; i < list->nr; i++) |
| 131 | if ((ret = fn(&list->items[i], cb_data))) |
| 132 | break; |
| 133 | return ret; |
| 134 | } |
| 135 | |
Michael Haggerty | eb5f0c7 | 2012-09-12 16:04:44 +0200 | [diff] [blame] | 136 | void filter_string_list(struct string_list *list, int free_util, |
| 137 | string_list_each_func_t want, void *cb_data) |
| 138 | { |
| 139 | int src, dst = 0; |
| 140 | for (src = 0; src < list->nr; src++) { |
| 141 | if (want(&list->items[src], cb_data)) { |
| 142 | list->items[dst++] = list->items[src]; |
| 143 | } else { |
| 144 | if (list->strdup_strings) |
| 145 | free(list->items[src].string); |
| 146 | if (free_util) |
| 147 | free(list->items[src].util); |
| 148 | } |
| 149 | } |
| 150 | list->nr = dst; |
| 151 | } |
| 152 | |
Michael Haggerty | 6bb2a13 | 2012-11-04 08:07:06 +0100 | [diff] [blame] | 153 | static int item_is_not_empty(struct string_list_item *item, void *unused) |
| 154 | { |
| 155 | return *item->string != '\0'; |
| 156 | } |
| 157 | |
Nguyễn Thái Ngọc Duy | 3b33576 | 2018-12-09 11:25:21 +0100 | [diff] [blame] | 158 | void string_list_remove_empty_items(struct string_list *list, int free_util) |
| 159 | { |
Michael Haggerty | 6bb2a13 | 2012-11-04 08:07:06 +0100 | [diff] [blame] | 160 | filter_string_list(list, free_util, item_is_not_empty, NULL); |
| 161 | } |
| 162 | |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 163 | void string_list_clear(struct string_list *list, int free_util) |
| 164 | { |
| 165 | if (list->items) { |
| 166 | int i; |
| 167 | if (list->strdup_strings) { |
| 168 | for (i = 0; i < list->nr; i++) |
| 169 | free(list->items[i].string); |
| 170 | } |
| 171 | if (free_util) { |
| 172 | for (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 | |
Marius Storm-Olsen | cfa1ee6 | 2009-02-08 15:34:28 +0100 | [diff] [blame] | 181 | void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc) |
| 182 | { |
| 183 | if (list->items) { |
| 184 | int i; |
| 185 | if (clearfunc) { |
| 186 | for (i = 0; i < list->nr; i++) |
| 187 | clearfunc(list->items[i].util, list->items[i].string); |
| 188 | } |
| 189 | if (list->strdup_strings) { |
| 190 | for (i = 0; i < list->nr; i++) |
| 191 | free(list->items[i].string); |
| 192 | } |
| 193 | free(list->items); |
| 194 | } |
| 195 | list->items = NULL; |
| 196 | list->nr = list->alloc = 0; |
| 197 | } |
| 198 | |
Michael Haggerty | e448fed | 2012-09-12 16:04:42 +0200 | [diff] [blame] | 199 | struct string_list_item *string_list_append_nodup(struct string_list *list, |
| 200 | char *string) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 201 | { |
Michael Haggerty | e448fed | 2012-09-12 16:04:42 +0200 | [diff] [blame] | 202 | struct string_list_item *retval; |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 203 | ALLOC_GROW(list->items, list->nr + 1, list->alloc); |
Michael Haggerty | e448fed | 2012-09-12 16:04:42 +0200 | [diff] [blame] | 204 | retval = &list->items[list->nr++]; |
| 205 | retval->string = string; |
| 206 | retval->util = NULL; |
| 207 | return retval; |
| 208 | } |
| 209 | |
| 210 | struct string_list_item *string_list_append(struct string_list *list, |
| 211 | const char *string) |
| 212 | { |
| 213 | return string_list_append_nodup( |
| 214 | list, |
| 215 | list->strdup_strings ? xstrdup(string) : (char *)string); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 216 | } |
| 217 | |
Beat Bolli | b6d3f5a | 2018-07-09 21:25:36 +0200 | [diff] [blame] | 218 | /* |
| 219 | * Encapsulate the compare function pointer because ISO C99 forbids |
| 220 | * casting from void * to a function pointer and vice versa. |
| 221 | */ |
| 222 | struct string_list_sort_ctx |
| 223 | { |
| 224 | compare_strings_fn cmp; |
| 225 | }; |
| 226 | |
René Scharfe | 5ebd947 | 2017-01-22 18:57:09 +0100 | [diff] [blame] | 227 | static int cmp_items(const void *a, const void *b, void *ctx) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 228 | { |
Beat Bolli | b6d3f5a | 2018-07-09 21:25:36 +0200 | [diff] [blame] | 229 | struct string_list_sort_ctx *sort_ctx = ctx; |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 230 | const struct string_list_item *one = a; |
| 231 | const struct string_list_item *two = b; |
Beat Bolli | b6d3f5a | 2018-07-09 21:25:36 +0200 | [diff] [blame] | 232 | return sort_ctx->cmp(one->string, two->string); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 233 | } |
| 234 | |
Michael Haggerty | 3383e19 | 2014-11-25 09:02:35 +0100 | [diff] [blame] | 235 | void string_list_sort(struct string_list *list) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 236 | { |
Beat Bolli | b6d3f5a | 2018-07-09 21:25:36 +0200 | [diff] [blame] | 237 | struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp}; |
| 238 | |
| 239 | QSORT_S(list->items, list->nr, cmp_items, &sort_ctx); |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 240 | } |
| 241 | |
Stephen Boyd | e242148 | 2010-03-24 00:16:02 -0700 | [diff] [blame] | 242 | struct string_list_item *unsorted_string_list_lookup(struct string_list *list, |
| 243 | const char *string) |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 244 | { |
Ralf Thielow | d16df0c | 2016-04-25 19:40:00 +0200 | [diff] [blame] | 245 | struct string_list_item *item; |
Junio C Hamano | 8dd5afc | 2013-01-07 12:24:55 -0800 | [diff] [blame] | 246 | compare_strings_fn cmp = list->cmp ? list->cmp : strcmp; |
| 247 | |
Ralf Thielow | d16df0c | 2016-04-25 19:40:00 +0200 | [diff] [blame] | 248 | for_each_string_list_item(item, list) |
| 249 | if (!cmp(string, item->string)) |
| 250 | return item; |
Stephen Boyd | e242148 | 2010-03-24 00:16:02 -0700 | [diff] [blame] | 251 | return NULL; |
| 252 | } |
| 253 | |
| 254 | int unsorted_string_list_has_string(struct string_list *list, |
| 255 | const char *string) |
| 256 | { |
| 257 | return unsorted_string_list_lookup(list, string) != NULL; |
Johannes Schindelin | c455c87 | 2008-07-21 19:03:49 +0100 | [diff] [blame] | 258 | } |
| 259 | |
Johannes Sixt | 86d4b52 | 2011-08-11 23:20:00 -0600 | [diff] [blame] | 260 | void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util) |
| 261 | { |
| 262 | if (list->strdup_strings) |
| 263 | free(list->items[i].string); |
| 264 | if (free_util) |
| 265 | free(list->items[i].util); |
| 266 | list->items[i] = list->items[list->nr-1]; |
| 267 | list->nr--; |
| 268 | } |
Michael Haggerty | ff919f9 | 2012-09-12 16:04:43 +0200 | [diff] [blame] | 269 | |
| 270 | int string_list_split(struct string_list *list, const char *string, |
| 271 | int delim, int maxsplit) |
| 272 | { |
| 273 | int count = 0; |
| 274 | const char *p = string, *end; |
| 275 | |
| 276 | if (!list->strdup_strings) |
| 277 | die("internal error in string_list_split(): " |
| 278 | "list->strdup_strings must be set"); |
| 279 | for (;;) { |
| 280 | count++; |
| 281 | if (maxsplit >= 0 && count > maxsplit) { |
| 282 | string_list_append(list, p); |
| 283 | return count; |
| 284 | } |
| 285 | end = strchr(p, delim); |
| 286 | if (end) { |
| 287 | string_list_append_nodup(list, xmemdupz(p, end - p)); |
| 288 | p = end + 1; |
| 289 | } else { |
| 290 | string_list_append(list, p); |
| 291 | return count; |
| 292 | } |
| 293 | } |
| 294 | } |
| 295 | |
| 296 | int string_list_split_in_place(struct string_list *list, char *string, |
| 297 | int delim, int maxsplit) |
| 298 | { |
| 299 | int count = 0; |
| 300 | char *p = string, *end; |
| 301 | |
| 302 | if (list->strdup_strings) |
| 303 | die("internal error in string_list_split_in_place(): " |
| 304 | "list->strdup_strings must not be set"); |
| 305 | for (;;) { |
| 306 | count++; |
| 307 | if (maxsplit >= 0 && count > maxsplit) { |
| 308 | string_list_append(list, p); |
| 309 | return count; |
| 310 | } |
| 311 | end = strchr(p, delim); |
| 312 | if (end) { |
| 313 | *end = '\0'; |
| 314 | string_list_append(list, p); |
| 315 | p = end + 1; |
| 316 | } else { |
| 317 | string_list_append(list, p); |
| 318 | return count; |
| 319 | } |
| 320 | } |
| 321 | } |