smartlist_core.c 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234
  1. /* Copyright (c) 2003-2004, Roger Dingledine
  2. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  3. * Copyright (c) 2007-2018, The Tor Project, Inc. */
  4. /* See LICENSE for licensing information */
  5. /**
  6. * \file smartlist_core.c
  7. * \brief Implements the core functionality of a smartlist (a resizeable
  8. * dynamic array). For more functionality and helper functions, see the
  9. * container library.
  10. **/
  11. #include "lib/err/torerr.h"
  12. #include "lib/malloc/malloc.h"
  13. #include "lib/smartlist_core/smartlist_core.h"
  14. #include <stdlib.h>
  15. #include <string.h>
  16. /** All newly allocated smartlists have this capacity. */
  17. #define SMARTLIST_DEFAULT_CAPACITY 16
  18. /** Allocate and return an empty smartlist.
  19. */
  20. MOCK_IMPL(smartlist_t *,
  21. smartlist_new,(void))
  22. {
  23. smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
  24. sl->num_used = 0;
  25. sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
  26. sl->list = tor_calloc(sizeof(void *), sl->capacity);
  27. return sl;
  28. }
  29. /** Deallocate a smartlist. Does not release storage associated with the
  30. * list's elements.
  31. */
  32. MOCK_IMPL(void,
  33. smartlist_free_,(smartlist_t *sl))
  34. {
  35. if (!sl)
  36. return;
  37. tor_free(sl->list);
  38. tor_free(sl);
  39. }
  40. /** Remove all elements from the list.
  41. */
  42. void
  43. smartlist_clear(smartlist_t *sl)
  44. {
  45. memset(sl->list, 0, sizeof(void *) * sl->num_used);
  46. sl->num_used = 0;
  47. }
  48. #if SIZE_MAX < INT_MAX
  49. #error "We don't support systems where size_t is smaller than int."
  50. #endif
  51. /** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
  52. static inline void
  53. smartlist_ensure_capacity(smartlist_t *sl, size_t size)
  54. {
  55. /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */
  56. #if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX
  57. #define MAX_CAPACITY (INT_MAX)
  58. #else
  59. #define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*))))
  60. #endif
  61. raw_assert(size <= MAX_CAPACITY);
  62. if (size > (size_t) sl->capacity) {
  63. size_t higher = (size_t) sl->capacity;
  64. if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {
  65. higher = MAX_CAPACITY;
  66. } else {
  67. while (size > higher)
  68. higher *= 2;
  69. }
  70. sl->list = tor_reallocarray(sl->list, sizeof(void *),
  71. ((size_t)higher));
  72. memset(sl->list + sl->capacity, 0,
  73. sizeof(void *) * (higher - sl->capacity));
  74. sl->capacity = (int) higher;
  75. }
  76. #undef ASSERT_CAPACITY
  77. #undef MAX_CAPACITY
  78. }
  79. /** Append element to the end of the list. */
  80. void
  81. smartlist_add(smartlist_t *sl, void *element)
  82. {
  83. smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1);
  84. sl->list[sl->num_used++] = element;
  85. }
  86. /** Append each element from S2 to the end of S1. */
  87. void
  88. smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
  89. {
  90. size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used;
  91. raw_assert(new_size >= (size_t) s1->num_used); /* check for overflow. */
  92. smartlist_ensure_capacity(s1, new_size);
  93. memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
  94. raw_assert(new_size <= INT_MAX); /* redundant. */
  95. s1->num_used = (int) new_size;
  96. }
  97. /** Append a copy of string to sl */
  98. void
  99. smartlist_add_strdup(struct smartlist_t *sl, const char *string)
  100. {
  101. char *copy;
  102. copy = tor_strdup(string);
  103. smartlist_add(sl, copy);
  104. }
  105. /** Remove all elements E from sl such that E==element. Preserve
  106. * the order of any elements before E, but elements after E can be
  107. * rearranged.
  108. */
  109. void
  110. smartlist_remove(smartlist_t *sl, const void *element)
  111. {
  112. int i;
  113. if (element == NULL)
  114. return;
  115. for (i=0; i < sl->num_used; i++)
  116. if (sl->list[i] == element) {
  117. sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
  118. i--; /* so we process the new i'th element */
  119. sl->list[sl->num_used] = NULL;
  120. }
  121. }
  122. /** As <b>smartlist_remove</b>, but do not change the order of
  123. * any elements not removed */
  124. void
  125. smartlist_remove_keeporder(smartlist_t *sl, const void *element)
  126. {
  127. int i, j, num_used_orig = sl->num_used;
  128. if (element == NULL)
  129. return;
  130. for (i=j=0; j < num_used_orig; ++j) {
  131. if (sl->list[j] == element) {
  132. --sl->num_used;
  133. } else {
  134. sl->list[i++] = sl->list[j];
  135. }
  136. }
  137. }
  138. /** If <b>sl</b> is nonempty, remove and return the final element. Otherwise,
  139. * return NULL. */
  140. void *
  141. smartlist_pop_last(smartlist_t *sl)
  142. {
  143. raw_assert(sl);
  144. if (sl->num_used) {
  145. void *tmp = sl->list[--sl->num_used];
  146. sl->list[sl->num_used] = NULL;
  147. return tmp;
  148. } else
  149. return NULL;
  150. }
  151. /** Return true iff some element E of sl has E==element.
  152. */
  153. int
  154. smartlist_contains(const smartlist_t *sl, const void *element)
  155. {
  156. int i;
  157. for (i=0; i < sl->num_used; i++)
  158. if (sl->list[i] == element)
  159. return 1;
  160. return 0;
  161. }
  162. /** Remove the <b>idx</b>th element of sl; if idx is not the last
  163. * element, swap the last element of sl into the <b>idx</b>th space.
  164. */
  165. void
  166. smartlist_del(smartlist_t *sl, int idx)
  167. {
  168. raw_assert(sl);
  169. raw_assert(idx>=0);
  170. raw_assert(idx < sl->num_used);
  171. sl->list[idx] = sl->list[--sl->num_used];
  172. sl->list[sl->num_used] = NULL;
  173. }
  174. /** Remove the <b>idx</b>th element of sl; if idx is not the last element,
  175. * moving all subsequent elements back one space. Return the old value
  176. * of the <b>idx</b>th element.
  177. */
  178. void
  179. smartlist_del_keeporder(smartlist_t *sl, int idx)
  180. {
  181. raw_assert(sl);
  182. raw_assert(idx>=0);
  183. raw_assert(idx < sl->num_used);
  184. --sl->num_used;
  185. if (idx < sl->num_used)
  186. memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
  187. sl->list[sl->num_used] = NULL;
  188. }
  189. /** Insert the value <b>val</b> as the new <b>idx</b>th element of
  190. * <b>sl</b>, moving all items previously at <b>idx</b> or later
  191. * forward one space.
  192. */
  193. void
  194. smartlist_insert(smartlist_t *sl, int idx, void *val)
  195. {
  196. raw_assert(sl);
  197. raw_assert(idx>=0);
  198. raw_assert(idx <= sl->num_used);
  199. if (idx == sl->num_used) {
  200. smartlist_add(sl, val);
  201. } else {
  202. smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1);
  203. /* Move other elements away */
  204. if (idx < sl->num_used)
  205. memmove(sl->list + idx + 1, sl->list + idx,
  206. sizeof(void*)*(sl->num_used-idx));
  207. sl->num_used++;
  208. sl->list[idx] = val;
  209. }
  210. }