THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

322 lines
7.6KB

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