tor  0.4.0.1-alpha
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 
92 void
93 smartlist_add(smartlist_t *sl, void *element)
94 {
95  smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1);
96  sl->list[sl->num_used++] = element;
97 }
98 
100 void
102 {
103  size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used;
104  raw_assert(new_size >= (size_t) s1->num_used); /* check for overflow. */
105  smartlist_ensure_capacity(s1, new_size);
106  memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
107  raw_assert(new_size <= INT_MAX); /* redundant. */
108  s1->num_used = (int) new_size;
109 }
110 
112 void
113 smartlist_add_strdup(struct smartlist_t *sl, const char *string)
114 {
115  char *copy;
116 
117  copy = tor_strdup(string);
118 
119  smartlist_add(sl, copy);
120 }
121 
126 void
127 smartlist_remove(smartlist_t *sl, const void *element)
128 {
129  int i;
130  if (element == NULL)
131  return;
132  for (i=0; i < sl->num_used; i++)
133  if (sl->list[i] == element) {
134  sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
135  i--; /* so we process the new i'th element */
136  sl->list[sl->num_used] = NULL;
137  }
138 }
139 
142 void
143 smartlist_remove_keeporder(smartlist_t *sl, const void *element)
144 {
145  int i, j, num_used_orig = sl->num_used;
146  if (element == NULL)
147  return;
148 
149  for (i=j=0; j < num_used_orig; ++j) {
150  if (sl->list[j] == element) {
151  --sl->num_used;
152  } else {
153  sl->list[i++] = sl->list[j];
154  }
155  }
156 }
157 
160 void *
162 {
163  raw_assert(sl);
164  if (sl->num_used) {
165  void *tmp = sl->list[--sl->num_used];
166  sl->list[sl->num_used] = NULL;
167  return tmp;
168  } else
169  return NULL;
170 }
171 
174 int
175 smartlist_contains(const smartlist_t *sl, const void *element)
176 {
177  int i;
178  for (i=0; i < sl->num_used; i++)
179  if (sl->list[i] == element)
180  return 1;
181  return 0;
182 }
183 
187 void
189 {
190  raw_assert(sl);
191  raw_assert(idx>=0);
192  raw_assert(idx < sl->num_used);
193  sl->list[idx] = sl->list[--sl->num_used];
194  sl->list[sl->num_used] = NULL;
195 }
196 
201 void
203 {
204  raw_assert(sl);
205  raw_assert(idx>=0);
206  raw_assert(idx < sl->num_used);
207  --sl->num_used;
208  if (idx < sl->num_used)
209  memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
210  sl->list[sl->num_used] = NULL;
211 }
212 
217 void
218 smartlist_insert(smartlist_t *sl, int idx, void *val)
219 {
220  raw_assert(sl);
221  raw_assert(idx>=0);
222  raw_assert(idx <= sl->num_used);
223  if (idx == sl->num_used) {
224  smartlist_add(sl, val);
225  } else {
226  smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1);
227  /* Move other elements away */
228  if (idx < sl->num_used)
229  memmove(sl->list + idx + 1, sl->list + idx,
230  sizeof(void*)*(sl->num_used-idx));
231  sl->num_used++;
232  sl->list[idx] = val;
233  }
234 }
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))