string-list.c

   1 #define DISABLE_SIGN_COMPARE_WARNINGS
   2
   3 #include "git-compat-util.h"
   4 #include "string-list.h"
   5
   6 void string_list_init_nodup(struct string_list *list)
   7 {
   8         struct string_list blank = STRING_LIST_INIT_NODUP;
   9         memcpy(list, &blank, sizeof(*list));
  10 }
  11
  12 void string_list_init_dup(struct string_list *list)
  13 {
  14         struct string_list blank = STRING_LIST_INIT_DUP;
  15         memcpy(list, &blank, sizeof(*list));
  16 }
  17
  18 /* if there is no exact match, point to the index where the entry could be
  19  * inserted */
  20 static int get_entry_index(const struct string_list *list, const char *string,
  21                 int *exact_match)
  22 {
  23         int left = -1, right = list->nr;
  24         compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
  25
  26         while (left + 1 < right) {
  27                 int middle = left + (right - left) / 2;
  28                 int compare = cmp(string, list->items[middle].string);
  29                 if (compare < 0)
  30                         right = middle;
  31                 else if (compare > 0)
  32                         left = middle;
  33                 else {
  34                         *exact_match = 1;
  35                         return middle;
  36                 }
  37         }
  38
  39         *exact_match = 0;
  40         return right;
  41 }
  42
  43 /* returns -1-index if already exists */
  44 static int add_entry(int insert_at, struct string_list *list, const char *string)
  45 {
  46         int exact_match = 0;
  47         int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match);
  48
  49         if (exact_match)
  50                 return -1 - index;
  51
  52         ALLOC_GROW(list->items, list->nr+1, list->alloc);
  53         if (index < list->nr)
  54                 MOVE_ARRAY(list->items + index + 1, list->items + index,
  55                            list->nr - index);
  56         list->items[index].string = list->strdup_strings ?
  57                 xstrdup(string) : (char *)string;
  58         list->items[index].util = NULL;
  59         list->nr++;
  60
  61         return index;
  62 }
  63
  64 struct string_list_item *string_list_insert(struct string_list *list, const char *string)
  65 {
  66         int index = add_entry(-1, list, string);
  67
  68         if (index < 0)
  69                 index = -1 - index;
  70
  71         return list->items + index;
  72 }
  73
  74 void string_list_remove(struct string_list *list, const char *string,
  75                         int free_util)
  76 {
  77         int exact_match;
  78         int i = get_entry_index(list, string, &exact_match);
  79
  80         if (exact_match) {
  81                 if (list->strdup_strings)
  82                         free(list->items[i].string);
  83                 if (free_util)
  84                         free(list->items[i].util);
  85
  86                 list->nr--;
  87                 MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i);
  88         }
  89 }
  90
  91 int string_list_has_string(const struct string_list *list, const char *string)
  92 {
  93         int exact_match;
  94         get_entry_index(list, string, &exact_match);
  95         return exact_match;
  96 }
  97
  98 int string_list_find_insert_index(const struct string_list *list, const char *string,
  99                                   int negative_existing_index)
 100 {
 101         int exact_match;
 102         int index = get_entry_index(list, string, &exact_match);
 103         if (exact_match)
 104                 index = -1 - (negative_existing_index ? index : 0);
 105         return index;
 106 }
 107
 108 struct string_list_item *string_list_lookup(struct string_list *list, const char *string)
 109 {
 110         int exact_match, i = get_entry_index(list, string, &exact_match);
 111         if (!exact_match)
 112                 return NULL;
 113         return list->items + i;
 114 }
 115
 116 void string_list_remove_duplicates(struct string_list *list, int free_util)
 117 {
 118         if (list->nr > 1) {
 119                 int src, dst;
 120                 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
 121                 for (src = dst = 1; src < list->nr; src++) {
 122                         if (!cmp(list->items[dst - 1].string, list->items[src].string)) {
 123                                 if (list->strdup_strings)
 124                                         free(list->items[src].string);
 125                                 if (free_util)
 126                                         free(list->items[src].util);
 127                         } else
 128                                 list->items[dst++] = list->items[src];
 129                 }
 130                 list->nr = dst;
 131         }
 132 }
 133
 134 int for_each_string_list(struct string_list *list,
 135                          string_list_each_func_t fn, void *cb_data)
 136 {
 137         int i, ret = 0;
 138         for (i = 0; i < list->nr; i++)
 139                 if ((ret = fn(&list->items[i], cb_data)))
 140                         break;
 141         return ret;
 142 }
 143
 144 void filter_string_list(struct string_list *list, int free_util,
 145                         string_list_each_func_t want, void *cb_data)
 146 {
 147         int src, dst = 0;
 148         for (src = 0; src < list->nr; src++) {
 149                 if (want(&list->items[src], cb_data)) {
 150                         list->items[dst++] = list->items[src];
 151                 } else {
 152                         if (list->strdup_strings)
 153                                 free(list->items[src].string);
 154                         if (free_util)
 155                                 free(list->items[src].util);
 156                 }
 157         }
 158         list->nr = dst;
 159 }
 160
 161 static int item_is_not_empty(struct string_list_item *item, void *data UNUSED)
 162 {
 163         return *item->string != '\0';
 164 }
 165
 166 void string_list_remove_empty_items(struct string_list *list, int free_util)
 167 {
 168         filter_string_list(list, free_util, item_is_not_empty, NULL);
 169 }
 170
 171 void string_list_clear(struct string_list *list, int free_util)
 172 {
 173         if (list->items) {
 174                 int i;
 175                 if (list->strdup_strings) {
 176                         for (i = 0; i < list->nr; i++)
 177                                 free(list->items[i].string);
 178                 }
 179                 if (free_util) {
 180                         for (i = 0; i < list->nr; i++)
 181                                 free(list->items[i].util);
 182                 }
 183                 free(list->items);
 184         }
 185         list->items = NULL;
 186         list->nr = list->alloc = 0;
 187 }
 188
 189 void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc)
 190 {
 191         if (list->items) {
 192                 int i;
 193                 if (clearfunc) {
 194                         for (i = 0; i < list->nr; i++)
 195                                 clearfunc(list->items[i].util, list->items[i].string);
 196                 }
 197                 if (list->strdup_strings) {
 198                         for (i = 0; i < list->nr; i++)
 199                                 free(list->items[i].string);
 200                 }
 201                 free(list->items);
 202         }
 203         list->items = NULL;
 204         list->nr = list->alloc = 0;
 205 }
 206
 207 void string_list_setlen(struct string_list *list, size_t nr)
 208 {
 209         if (list->strdup_strings)
 210                 BUG("cannot setlen a string_list which owns its entries");
 211         if (nr > list->nr)
 212                 BUG("cannot grow a string_list with setlen");
 213         list->nr = nr;
 214 }
 215
 216 struct string_list_item *string_list_append_nodup(struct string_list *list,
 217                                                   char *string)
 218 {
 219         struct string_list_item *retval;
 220         ALLOC_GROW(list->items, list->nr + 1, list->alloc);
 221         retval = &list->items[list->nr++];
 222         retval->string = string;
 223         retval->util = NULL;
 224         return retval;
 225 }
 226
 227 struct string_list_item *string_list_append(struct string_list *list,
 228                                             const char *string)
 229 {
 230         return string_list_append_nodup(
 231                         list,
 232                         list->strdup_strings ? xstrdup(string) : (char *)string);
 233 }
 234
 235 /*
 236  * Encapsulate the compare function pointer because ISO C99 forbids
 237  * casting from void * to a function pointer and vice versa.
 238  */
 239 struct string_list_sort_ctx
 240 {
 241         compare_strings_fn cmp;
 242 };
 243
 244 static int cmp_items(const void *a, const void *b, void *ctx)
 245 {
 246         struct string_list_sort_ctx *sort_ctx = ctx;
 247         const struct string_list_item *one = a;
 248         const struct string_list_item *two = b;
 249         return sort_ctx->cmp(one->string, two->string);
 250 }
 251
 252 void string_list_sort(struct string_list *list)
 253 {
 254         struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp};
 255
 256         QSORT_S(list->items, list->nr, cmp_items, &sort_ctx);
 257 }
 258
 259 struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
 260                                                      const char *string)
 261 {
 262         struct string_list_item *item;
 263         compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
 264
 265         for_each_string_list_item(item, list)
 266                 if (!cmp(string, item->string))
 267                         return item;
 268         return NULL;
 269 }
 270
 271 int unsorted_string_list_has_string(struct string_list *list,
 272                                     const char *string)
 273 {
 274         return unsorted_string_list_lookup(list, string) != NULL;
 275 }
 276
 277 void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util)
 278 {
 279         if (list->strdup_strings)
 280                 free(list->items[i].string);
 281         if (free_util)
 282                 free(list->items[i].util);
 283         list->items[i] = list->items[list->nr-1];
 284         list->nr--;
 285 }
 286
 287 int string_list_split(struct string_list *list, const char *string,
 288                       int delim, int maxsplit)
 289 {
 290         int count = 0;
 291         const char *p = string, *end;
 292
 293         if (!list->strdup_strings)
 294                 die("internal error in string_list_split(): "
 295                     "list->strdup_strings must be set");
 296         for (;;) {
 297                 count++;
 298                 if (maxsplit >= 0 && count > maxsplit) {
 299                         string_list_append(list, p);
 300                         return count;
 301                 }
 302                 end = strchr(p, delim);
 303                 if (end) {
 304                         string_list_append_nodup(list, xmemdupz(p, end - p));
 305                         p = end + 1;
 306                 } else {
 307                         string_list_append(list, p);
 308                         return count;
 309                 }
 310         }
 311 }
 312
 313 int string_list_split_in_place(struct string_list *list, char *string,
 314                                const char *delim, int maxsplit)
 315 {
 316         int count = 0;
 317         char *p = string, *end;
 318
 319         if (list->strdup_strings)
 320                 die("internal error in string_list_split_in_place(): "
 321                     "list->strdup_strings must not be set");
 322         for (;;) {
 323                 count++;
 324                 if (maxsplit >= 0 && count > maxsplit) {
 325                         string_list_append(list, p);
 326                         return count;
 327                 }
 328                 end = strpbrk(p, delim);
 329                 if (end) {
 330                         *end = '\0';
 331                         string_list_append(list, p);
 332                         p = end + 1;
 333                 } else {
 334                         string_list_append(list, p);
 335                         return count;
 336                 }
 337         }
 338 }