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