tor  0.4.2.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-2019, The Tor Project, Inc. */
4 /* See LICENSE for licensing information */
5 
13 #include "lib/err/torerr.h"
14 #include "lib/malloc/malloc.h"
16 
17 #include <stdlib.h>
18 #include <string.h>
19 
21 #define SMARTLIST_DEFAULT_CAPACITY 16
22 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 }
void smartlist_grow(smartlist_t *sl, size_t new_size)
void smartlist_add_strdup(struct smartlist_t *sl, const char *string)
void smartlist_add(smartlist_t *sl, void *element)
void * smartlist_pop_last(smartlist_t *sl)
int smartlist_contains(const smartlist_t *sl, const void *element)
#define tor_free(p)
Definition: malloc.h:52
void ** list
#define SMARTLIST_DEFAULT_CAPACITY
Headers for util_malloc.c.
Top-level declarations for the smartlist_t dynamic array type.
void smartlist_del_keeporder(smartlist_t *sl, int idx)
void smartlist_remove(smartlist_t *sl, const void *element)
void smartlist_del(smartlist_t *sl, int idx)
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
Headers for torerr.c.
void smartlist_remove_keeporder(smartlist_t *sl, const void *element)
void smartlist_insert(smartlist_t *sl, int idx, void *val)
void smartlist_clear(smartlist_t *sl)
static void smartlist_ensure_capacity(smartlist_t *sl, size_t size)
MOCK_IMPL(smartlist_t *, smartlist_new,(void))