string-list.c

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