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.

265 lines
9.8KB

  1. #ifndef STRING_LIST_H
  2. #define STRING_LIST_H
  3. /**
  4. * The string_list API offers a data structure and functions to handle
  5. * sorted and unsorted arrays of strings. A "sorted" list is one whose
  6. * entries are sorted by string value in `strcmp()` order.
  7. *
  8. * The caller:
  9. *
  10. * . Allocates and clears a `struct string_list` variable.
  11. *
  12. * . Initializes the members. You might want to set the flag `strdup_strings`
  13. * if the strings should be strdup()ed. For example, this is necessary
  14. * when you add something like git_path("..."), since that function returns
  15. * a static buffer that will change with the next call to git_path().
  16. *
  17. * If you need something advanced, you can manually malloc() the `items`
  18. * member (you need this if you add things later) and you should set the
  19. * `nr` and `alloc` members in that case, too.
  20. *
  21. * . Adds new items to the list, using `string_list_append`,
  22. * `string_list_append_nodup`, `string_list_insert`,
  23. * `string_list_split`, and/or `string_list_split_in_place`.
  24. *
  25. * . Can check if a string is in the list using `string_list_has_string` or
  26. * `unsorted_string_list_has_string` and get it from the list using
  27. * `string_list_lookup` for sorted lists.
  28. *
  29. * . Can sort an unsorted list using `string_list_sort`.
  30. *
  31. * . Can remove duplicate items from a sorted list using
  32. * `string_list_remove_duplicates`.
  33. *
  34. * . Can remove individual items of an unsorted list using
  35. * `unsorted_string_list_delete_item`.
  36. *
  37. * . Can remove items not matching a criterion from a sorted or unsorted
  38. * list using `filter_string_list`, or remove empty strings using
  39. * `string_list_remove_empty_items`.
  40. *
  41. * . Finally it should free the list using `string_list_clear`.
  42. *
  43. * Example:
  44. *
  45. * struct string_list list = STRING_LIST_INIT_NODUP;
  46. * int i;
  47. *
  48. * string_list_append(&list, "foo");
  49. * string_list_append(&list, "bar");
  50. * for (i = 0; i < list.nr; i++)
  51. * printf("%s\n", list.items[i].string)
  52. *
  53. * NOTE: It is more efficient to build an unsorted list and sort it
  54. * afterwards, instead of building a sorted list (`O(n log n)` instead of
  55. * `O(n^2)`).
  56. *
  57. * However, if you use the list to check if a certain string was added
  58. * already, you should not do that (using unsorted_string_list_has_string()),
  59. * because the complexity would be quadratic again (but with a worse factor).
  60. */
  61. /**
  62. * Represents an item of the list. The `string` member is a pointer to the
  63. * string, and you may use the `util` member for any purpose, if you want.
  64. */
  65. struct string_list_item {
  66. char *string;
  67. void *util;
  68. };
  69. typedef int (*compare_strings_fn)(const char *, const char *);
  70. /**
  71. * Represents the list itself.
  72. *
  73. * . The array of items are available via the `items` member.
  74. * . The `nr` member contains the number of items stored in the list.
  75. * . The `alloc` member is used to avoid reallocating at every insertion.
  76. * You should not tamper with it.
  77. * . Setting the `strdup_strings` member to 1 will strdup() the strings
  78. * before adding them, see above.
  79. * . The `compare_strings_fn` member is used to specify a custom compare
  80. * function, otherwise `strcmp()` is used as the default function.
  81. */
  82. struct string_list {
  83. struct string_list_item *items;
  84. unsigned int nr, alloc;
  85. unsigned int strdup_strings:1;
  86. compare_strings_fn cmp; /* NULL uses strcmp() */
  87. };
  88. #define STRING_LIST_INIT_NODUP { NULL, 0, 0, 0, NULL }
  89. #define STRING_LIST_INIT_DUP { NULL, 0, 0, 1, NULL }
  90. /* General functions which work with both sorted and unsorted lists. */
  91. /**
  92. * Initialize the members of the string_list, set `strdup_strings`
  93. * member according to the value of the second parameter.
  94. */
  95. void string_list_init(struct string_list *list, int strdup_strings);
  96. /** Callback function type for for_each_string_list */
  97. typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
  98. /**
  99. * Apply `want` to each item in `list`, retaining only the ones for which
  100. * the function returns true. If `free_util` is true, call free() on
  101. * the util members of any items that have to be deleted. Preserve
  102. * the order of the items that are retained.
  103. */
  104. void filter_string_list(struct string_list *list, int free_util,
  105. string_list_each_func_t want, void *cb_data);
  106. /**
  107. * Free a string_list. The `string` pointer of the items will be freed
  108. * in case the `strdup_strings` member of the string_list is set. The
  109. * second parameter controls if the `util` pointer of the items should
  110. * be freed or not.
  111. */
  112. void string_list_clear(struct string_list *list, int free_util);
  113. /**
  114. * Callback type for `string_list_clear_func`. The string associated
  115. * with the util pointer is passed as the second argument
  116. */
  117. typedef void (*string_list_clear_func_t)(void *p, const char *str);
  118. /** Call a custom clear function on each util pointer */
  119. void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc);
  120. /**
  121. * Apply `func` to each item. If `func` returns nonzero, the
  122. * iteration aborts and the return value is propagated.
  123. */
  124. int for_each_string_list(struct string_list *list,
  125. string_list_each_func_t func, void *cb_data);
  126. /** Iterate over each item, as a macro. */
  127. #define for_each_string_list_item(item,list) \
  128. for (item = (list)->items; \
  129. item && item < (list)->items + (list)->nr; \
  130. ++item)
  131. /**
  132. * Remove any empty strings from the list. If free_util is true, call
  133. * free() on the util members of any items that have to be deleted.
  134. * Preserve the order of the items that are retained.
  135. */
  136. void string_list_remove_empty_items(struct string_list *list, int free_util);
  137. /* Use these functions only on sorted lists: */
  138. /** Determine if the string_list has a given string or not. */
  139. int string_list_has_string(const struct string_list *list, const char *string);
  140. int string_list_find_insert_index(const struct string_list *list, const char *string,
  141. int negative_existing_index);
  142. /**
  143. * Insert a new element to the string_list. The returned pointer can
  144. * be handy if you want to write something to the `util` pointer of
  145. * the string_list_item containing the just added string. If the given
  146. * string already exists the insertion will be skipped and the pointer
  147. * to the existing item returned.
  148. *
  149. * Since this function uses xrealloc() (which die()s if it fails) if the
  150. * list needs to grow, it is safe not to check the pointer. I.e. you may
  151. * write `string_list_insert(...)->util = ...;`.
  152. */
  153. struct string_list_item *string_list_insert(struct string_list *list, const char *string);
  154. /**
  155. * Remove the given string from the sorted list. If the string
  156. * doesn't exist, the list is not altered.
  157. */
  158. void string_list_remove(struct string_list *list, const char *string,
  159. int free_util);
  160. /**
  161. * Check if the given string is part of a sorted list. If it is part of the list,
  162. * return the coresponding string_list_item, NULL otherwise.
  163. */
  164. struct string_list_item *string_list_lookup(struct string_list *list, const char *string);
  165. /*
  166. * Remove all but the first of consecutive entries with the same
  167. * string value. If free_util is true, call free() on the util
  168. * members of any items that have to be deleted.
  169. */
  170. void string_list_remove_duplicates(struct string_list *sorted_list, int free_util);
  171. /* Use these functions only on unsorted lists: */
  172. /**
  173. * Add string to the end of list. If list->strdup_string is set, then
  174. * string is copied; otherwise the new string_list_entry refers to the
  175. * input string.
  176. */
  177. struct string_list_item *string_list_append(struct string_list *list, const char *string);
  178. /**
  179. * Like string_list_append(), except string is never copied. When
  180. * list->strdup_strings is set, this function can be used to hand
  181. * ownership of a malloc()ed string to list without making an extra
  182. * copy.
  183. */
  184. struct string_list_item *string_list_append_nodup(struct string_list *list, char *string);
  185. /**
  186. * Sort the list's entries by string value in `strcmp()` order.
  187. */
  188. void string_list_sort(struct string_list *list);
  189. /**
  190. * Like `string_list_has_string()` but for unsorted lists. Linear in
  191. * size of the list.
  192. */
  193. int unsorted_string_list_has_string(struct string_list *list, const char *string);
  194. /**
  195. * Like `string_list_lookup()` but for unsorted lists. Linear in size
  196. * of the list.
  197. */
  198. struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
  199. const char *string);
  200. /**
  201. * Remove an item from a string_list. The `string` pointer of the
  202. * items will be freed in case the `strdup_strings` member of the
  203. * string_list is set. The third parameter controls if the `util`
  204. * pointer of the items should be freed or not.
  205. */
  206. void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util);
  207. /**
  208. * Split string into substrings on character `delim` and append the
  209. * substrings to `list`. The input string is not modified.
  210. * list->strdup_strings must be set, as new memory needs to be
  211. * allocated to hold the substrings. If maxsplit is non-negative,
  212. * then split at most maxsplit times. Return the number of substrings
  213. * appended to list.
  214. *
  215. * Examples:
  216. * string_list_split(l, "foo:bar:baz", ':', -1) -> ["foo", "bar", "baz"]
  217. * string_list_split(l, "foo:bar:baz", ':', 0) -> ["foo:bar:baz"]
  218. * string_list_split(l, "foo:bar:baz", ':', 1) -> ["foo", "bar:baz"]
  219. * string_list_split(l, "foo:bar:", ':', -1) -> ["foo", "bar", ""]
  220. * string_list_split(l, "", ':', -1) -> [""]
  221. * string_list_split(l, ":", ':', -1) -> ["", ""]
  222. */
  223. int string_list_split(struct string_list *list, const char *string,
  224. int delim, int maxsplit);
  225. /*
  226. * Like string_list_split(), except that string is split in-place: the
  227. * delimiter characters in string are overwritten with NULs, and the
  228. * new string_list_items point into string (which therefore must not
  229. * be modified or freed while the string_list is in use).
  230. * list->strdup_strings must *not* be set.
  231. */
  232. int string_list_split_in_place(struct string_list *list, char *string,
  233. int delim, int maxsplit);
  234. #endif /* STRING_LIST_H */