Tor  0.4.7.0-alpha-dev
smartlist_core.c
Go to the documentation of this file.
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"
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  */
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,
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
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
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
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
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
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
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
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
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 *
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
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
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
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
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 }
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
void smartlist_grow(smartlist_t *sl, size_t new_size)
void smartlist_insert(smartlist_t *sl, int idx, void *val)
void smartlist_remove_keeporder(smartlist_t *sl, const void *element)
void * smartlist_pop_last(smartlist_t *sl)
static void smartlist_ensure_capacity(smartlist_t *sl, size_t size)
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
smartlist_t * smartlist_new(void)
void smartlist_add_strdup(struct smartlist_t *sl, const char *string)
int smartlist_contains(const smartlist_t *sl, const void *element)
void smartlist_add(smartlist_t *sl, void *element)
void smartlist_clear(smartlist_t *sl)
#define SMARTLIST_DEFAULT_CAPACITY
void smartlist_remove(smartlist_t *sl, const void *element)
void smartlist_free_(smartlist_t *sl)
void smartlist_del(smartlist_t *sl, int idx)
void smartlist_del_keeporder(smartlist_t *sl, int idx)
Top-level declarations for the smartlist_t dynamic array type.
void ** list
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
Headers for torerr.c.