container.c 17.5 KB
Newer Older
Nick Mathewson's avatar
Nick Mathewson committed
1
2
/* Copyright 2003-2004 Roger Dingledine
   Copyright 2004-2005 Roger Dingledine, Nick Mathewson */
3
4
/* See LICENSE for licensing information */
/* $Id$ */
5
const char container_c_id[] = "$Id$";
6

7
8
9
10
11
12
13
/**
 * \file container.c
 * \brief Implements a smartlist (a resizable array) along
 * with helper functions to use smartlists.  Also includes a
 * splay-tree implementation of the string-to-void* map.
 **/

14
15
16
17
18
19
20
21
22
23
24
#include "compat.h"
#include "util.h"
#include "log.h"
#include "../or/tree.h"
#include "container.h"

#ifdef HAVE_CTYPE_H
#include <ctype.h>
#endif
#include <stdlib.h>
#include <string.h>
25
#include <assert.h>
26
27
28
29
30

/* All newly allocated smartlists have this capacity.
 */
#define SMARTLIST_DEFAULT_CAPACITY 32

31
#ifndef FAST_SMARTLIST
32
33
34
35
36
37
38
39
40
struct smartlist_t {
  /** <b>list</b> has enough capacity to store exactly <b>capacity</b> elements
   * before it needs to be resized.  Only the first <b>num_used</b> (\<=
   * capacity) elements point to valid data.
   */
  void **list;
  int num_used;
  int capacity;
};
41
#endif
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/** Allocate and return an empty smartlist.
 */
smartlist_t *smartlist_create() {
  smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
  sl->num_used = 0;
  sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
  sl->list = tor_malloc(sizeof(void *) * sl->capacity);
  return sl;
}

/** Deallocate a smartlist.  Does not release storage associated with the
 * list's elements.
 */
void smartlist_free(smartlist_t *sl) {
  free(sl->list);
  free(sl);
}

/** Change the capacity of the smartlist to <b>n</b>, so that we can grow
 * the list up to <b>n</b> elements with no further reallocation or wasted
 * space.  If <b>n</b> is less than or equal to the number of elements
 * currently in the list, reduce the list's capacity as much as
 * possible without losing elements.
 */
void smartlist_set_capacity(smartlist_t *sl, int n) {
  if (n < sl->num_used)
    n = sl->num_used;
  if (sl->capacity != n) {
    sl->capacity = n;
    sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
  }
}

/** Remove all elements from the list.
 */
void smartlist_clear(smartlist_t *sl) {
  sl->num_used = 0;
}

/** Set the list's new length to <b>len</b> (which must be \<= the list's
 * current size). Remove the last smartlist_len(sl)-len elements from the
 * list.
 */
void smartlist_truncate(smartlist_t *sl, int len)
{
  tor_assert(len <= sl->num_used);
  sl->num_used = len;
}

/** Append element to the end of the list. */
void smartlist_add(smartlist_t *sl, void *element) {
  if (sl->num_used >= sl->capacity) {
95
96
97
    int higher = sl->capacity * 2;
    tor_assert(higher > sl->capacity); /* detect overflow */
    sl->capacity = higher;
98
99
100
101
102
103
104
105
106
107
108
    sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
  }
  sl->list[sl->num_used++] = element;
}

/** Append each element from S2 to the end of S1. */
void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2)
{
  SMARTLIST_FOREACH(s2, void *, element, smartlist_add(sl, element));
}

109
110
111
/** Remove all elements E from sl such that E==element.  Preserve
 * the order of any elements before E, but elements after E can be
 * rearranged.
112
113
114
 */
void smartlist_remove(smartlist_t *sl, void *element) {
  int i;
115
  if (element == NULL)
116
    return;
117
118
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element) {
119
120
121
122
123
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
}

124
/** If there are any strings in sl equal to element, remove them.
125
126
127
128
129
 * Does not preserve order. */
void
smartlist_string_remove(smartlist_t *sl, const char *element)
{
  int i;
130
131
132
  tor_assert(sl);
  tor_assert(element);
  for (i = 0; i < sl->num_used; ++i) {
133
    if (!strcmp(element, sl->list[i])) {
134
135
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
136
137
138
139
    }
  }
}

140
141
142
143
/** Return true iff some element E of sl has E==element.
 */
int smartlist_isin(const smartlist_t *sl, void *element) {
  int i;
144
145
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element)
146
147
148
149
150
151
      return 1;
  return 0;
}

int smartlist_string_isin(const smartlist_t *sl, const char *element) {
  int i;
152
153
  for (i=0; i < sl->num_used; i++)
    if (strcmp((const char*)sl->list[i],element)==0)
154
155
156
157
      return 1;
  return 0;
}

158
159
160
161
162
163
int smartlist_string_num_isin(const smartlist_t *sl, int num) {
  char buf[16];
  tor_snprintf(buf,sizeof(buf),"%d", num);
  return smartlist_string_isin(sl, buf);
}

164
165
166
167
/** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
 */
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2) {
  int i;
168
169
  for (i=0; i < sl2->num_used; i++)
    if (smartlist_isin(sl1, sl2->list[i]))
170
171
172
173
174
175
176
177
178
      return 1;
  return 0;
}

/** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
 * Does not preserve the order of sl1.
 */
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) {
  int i;
179
180
  for (i=0; i < sl1->num_used; i++)
    if (!smartlist_isin(sl2, sl1->list[i])) {
181
182
183
184
185
186
187
188
189
190
      sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
}

/** Remove every element E of sl1 such that smartlist_isin(sl2,E).
 * Does not preserve the order of sl1.
 */
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) {
  int i;
191
  for (i=0; i < sl2->num_used; i++)
192
193
194
    smartlist_remove(sl1, sl2->list[i]);
}

195
#ifndef FAST_SMARTLIST
196
197
198
199
200
201
202
203
204
/** Return the <b>idx</b>th element of sl.
 */
void *smartlist_get(const smartlist_t *sl, int idx)
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  return sl->list[idx];
}
Roger Dingledine's avatar
Roger Dingledine committed
205
/** Change the value of the <b>idx</b>th element of sl to <b>val</b>.
206
 */
207
void smartlist_set(smartlist_t *sl, int idx, void *val)
208
209
210
211
212
213
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  sl->list[idx] = val;
}
214
215
216
217
218
219
220
/** Return the number of items in sl.
 */
int smartlist_len(const smartlist_t *sl)
{
  return sl->num_used;
}
#endif
221

222
223
224
225
/** Remove the <b>idx</b>th element of sl; if idx is not the last
 * element, swap the last element of sl into the <b>idx</b>th space.
 * Return the old value of the <b>idx</b>th element.
 */
226
void smartlist_del(smartlist_t *sl, int idx)
227
228
229
230
231
232
233
234
235
236
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  sl->list[idx] = sl->list[--sl->num_used];
}
/** Remove the <b>idx</b>th element of sl; if idx is not the last element,
 * moving all subsequent elements back one space. Return the old value
 * of the <b>idx</b>th element.
 */
237
void smartlist_del_keeporder(smartlist_t *sl, int idx)
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  --sl->num_used;
  if (idx < sl->num_used)
    memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
}
/** Insert the value <b>val</b> as the new <b>idx</b>th element of
 * <b>sl</b>, moving all items previously at <b>idx</b> or later
 * forward one space.
 */
void smartlist_insert(smartlist_t *sl, int idx, void *val)
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx <= sl->num_used);
  if (idx == sl->num_used) {
    smartlist_add(sl, val);
  } else {
    /* Ensure sufficient capacity */
    if (sl->num_used >= sl->capacity) {
      sl->capacity *= 2;
      sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
    }
    /* Move other elements away */
    if (idx < sl->num_used)
      memmove(sl->list + idx + 1, sl->list + idx,
              sizeof(void*)*(sl->num_used-idx));
    sl->num_used++;
    sl->list[idx] = val;
  }
}

/**
273
 * Split a string <b>str</b> along all occurrences of <b>sep</b>,
274
275
276
277
278
 * adding the split strings, in order, to <b>sl</b>.  If
 * <b>flags</b>&amp;SPLIT_SKIP_SPACE is true, remove initial and
 * trailing space from each entry.  If
 * <b>flags</b>&amp;SPLIT_IGNORE_BLANK is true, remove any entries of
 * length 0.  If max>0, divide the string into no more than <b>max</b>
279
 * pieces.  If <b>sep</b> is NULL, split on any sequence of horizontal space.
280
281
282
283
284
285
286
287
288
289
290
291
292
 */
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
                           int flags, int max)
{
  const char *cp, *end, *next;
  int n = 0;

  tor_assert(sl);
  tor_assert(str);

  cp = str;
  while (1) {
    if (flags&SPLIT_SKIP_SPACE) {
293
      while (TOR_ISSPACE(*cp)) ++cp;
294
295
296
297
    }

    if (max>0 && n == max-1) {
      end = strchr(cp,'\0');
298
    } else if (sep) {
299
300
301
      end = strstr(cp,sep);
      if (!end)
        end = strchr(cp,'\0');
302
303
304
    } else {
      for (end = cp; *end && *end != '\t' && *end != ' '; ++end)
        ;
305
    }
306

307
308
    if (!*end) {
      next = NULL;
309
    } else if (sep) {
310
      next = end+strlen(sep);
311
312
313
314
    } else {
      next = end+1;
      while (*next == '\t' || *next == ' ')
        ++next;
315
316
317
    }

    if (flags&SPLIT_SKIP_SPACE) {
318
      while (end > cp && TOR_ISSPACE(*(end-1)))
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
        --end;
    }
    if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
      smartlist_add(sl, tor_strndup(cp, end-cp));
      ++n;
    }
    if (!next)
      break;
    cp = next;
  }

  return n;
}

/** Allocate and return a new string containing the concatenation of
 * the elements of <b>sl</b>, in order, separated by <b>join</b>.  If
 * <b>terminate</b> is true, also terminate the string with <b>join</b>.
336
337
338
 * If <b>len_out</b> is not NULL, set <b>len_out</b> to the length of
 * the returned string. Requires that every element of <b>sl</b> is
 * NUL-terminated string.
339
 */
340
341
342
343
344
345
char *smartlist_join_strings(smartlist_t *sl, const char *join,
                             int terminate, size_t *len_out)
{
  return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
}

Roger Dingledine's avatar
Roger Dingledine committed
346
/** As smartlist_join_strings, but instead of separating/terminated with a
347
 * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
348
 * at <b>join</b>.  (Useful for generating a sequence of NUL-terminated
349
350
351
352
 * strings.)
 */
char *smartlist_join_strings2(smartlist_t *sl, const char *join,
                              size_t join_len, int terminate, size_t *len_out)
353
354
{
  int i;
355
  size_t n = 0;
356
357
358
359
  char *r = NULL, *dst, *src;

  tor_assert(sl);
  tor_assert(join);
360

Roger Dingledine's avatar
Roger Dingledine committed
361
362
  if (terminate)
    n = join_len;
363

364
365
  for (i = 0; i < sl->num_used; ++i) {
    n += strlen(sl->list[i]);
Roger Dingledine's avatar
Roger Dingledine committed
366
367
    if (i+1 < sl->num_used) /* avoid double-counting the last one */
      n += join_len;
368
369
370
371
372
  }
  dst = r = tor_malloc(n+1);
  for (i = 0; i < sl->num_used; ) {
    for (src = sl->list[i]; *src; )
      *dst++ = *src++;
Roger Dingledine's avatar
Roger Dingledine committed
373
    if (++i < sl->num_used) {
374
375
      memcpy(dst, join, join_len);
      dst += join_len;
376
377
    }
  }
Roger Dingledine's avatar
Roger Dingledine committed
378
  if (terminate) {
379
380
381
    memcpy(dst, join, join_len);
    dst += join_len;
  }
382
  *dst = '\0';
383
384
385

  if (len_out)
    *len_out = dst-r;
386
387
388
389
390
  return r;
}

/* Splay-tree implementation of string-to-void* map
 */
391
typedef struct strmap_entry_t {
392
393
394
  SPLAY_ENTRY(strmap_entry_t) node;
  char *key;
  void *val;
395
} strmap_entry_t;
396
397
398
399
400

struct strmap_t {
  SPLAY_HEAD(strmap_tree, strmap_entry_t) head;
};

401
402
static int compare_strmap_entries(strmap_entry_t *a,
                                  strmap_entry_t *b)
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
{
  return strcmp(a->key, b->key);
}

SPLAY_PROTOTYPE(strmap_tree, strmap_entry_t, node, compare_strmap_entries);
SPLAY_GENERATE(strmap_tree, strmap_entry_t, node, compare_strmap_entries);

/** Create a new empty map from strings to void*'s.
 */
strmap_t* strmap_new(void)
{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
  SPLAY_INIT(&result->head);
  return result;
}

/** Set the current value for <b>key</b> to <b>val</b>.  Returns the previous
 * value for <b>key</b> if one was set, or NULL if one was not.
 *
 * This function makes a copy of <b>key</b> if necessary, but not of <b>val</b>.
 */
void* strmap_set(strmap_t *map, const char *key, void *val)
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  search.key = (char*)key;
  resolve = SPLAY_FIND(strmap_tree, &map->head, &search);
  if (resolve) {
    oldval = resolve->val;
    resolve->val = val;
    return oldval;
  } else {
    resolve = tor_malloc_zero(sizeof(strmap_entry_t));
    resolve->key = tor_strdup(key);
    resolve->val = val;
    SPLAY_INSERT(strmap_tree, &map->head, resolve);
    return NULL;
  }
}

/** Return the current value associated with <b>key</b>, or NULL if no
 * value is set.
 */
void* strmap_get(strmap_t *map, const char *key)
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
  resolve = SPLAY_FIND(strmap_tree, &map->head, &search);
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

/** Remove the value currently associated with <b>key</b> from the map.
 * Return the value if one was set, or NULL if there was no entry for
 * <b>key</b>.
 *
 * Note: you must free any storage associated with the returned value.
 */
void* strmap_remove(strmap_t *map, const char *key)
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
  resolve = SPLAY_FIND(strmap_tree, &map->head, &search);
  if (resolve) {
    oldval = resolve->val;
    SPLAY_REMOVE(strmap_tree, &map->head, resolve);
    tor_free(resolve->key);
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

/** Same as strmap_set, but first converts <b>key</b> to lowercase. */
void* strmap_set_lc(strmap_t *map, const char *key, void *val)
{
  /* We could be a little faster by using strcasecmp instead, and a separate
   * type, but I don't think it matters. */
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_set(map,lc_key,val);
  tor_free(lc_key);
  return v;
}
/** Same as strmap_get, but first converts <b>key</b> to lowercase. */
void* strmap_get_lc(strmap_t *map, const char *key)
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_get(map,lc_key);
  tor_free(lc_key);
  return v;
}
/** Same as strmap_remove, but first converts <b>key</b> to lowercase */
void* strmap_remove_lc(strmap_t *map, const char *key)
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_remove(map,lc_key);
  tor_free(lc_key);
  return v;
}

/** Invoke fn() on every entry of the map, in order.  For every entry,
 * fn() is invoked with that entry's key, that entry's value, and the
 * value of <b>data</b> supplied to strmap_foreach.  fn() must return a new
 * (possibly unmodified) value for each entry: if fn() returns NULL, the
 * entry is removed.
 *
 * Example:
 * \code
 *   static void* upcase_and_remove_empty_vals(const char *key, void *val,
 *                                             void* data) {
 *     char *cp = (char*)val;
 *     if (!*cp) {  // val is an empty string.
 *       free(val);
 *       return NULL;
 *     } else {
 *       for (; *cp; cp++)
 *         *cp = toupper(*cp);
 *       }
 *       return val;
 *     }
 *   }
 *
 *   ...
 *
 *   strmap_foreach(map, upcase_and_remove_empty_vals, NULL);
 * \endcode
 */
void strmap_foreach(strmap_t *map,
                    void* (*fn)(const char *key, void *val, void *data),
                    void *data)
{
  strmap_entry_t *ptr, *next;
  tor_assert(map);
  tor_assert(fn);
  for (ptr = SPLAY_MIN(strmap_tree, &map->head); ptr != NULL; ptr = next) {
    /* This remove-in-place usage is specifically blessed in tree(3). */
    next = SPLAY_NEXT(strmap_tree, &map->head, ptr);
    ptr->val = fn(ptr->key, ptr->val, data);
    if (!ptr->val) {
      SPLAY_REMOVE(strmap_tree, &map->head, ptr);
      tor_free(ptr->key);
      tor_free(ptr);
    }
  }
}

/** return an <b>iterator</b> pointer to the front of a map.
 *
 * Iterator example:
 *
 * \code
 * // uppercase values in "map", removing empty values.
 *
 * strmap_iter_t *iter;
 * const char *key;
 * void *val;
 * char *cp;
 *
 * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) {
 *    strmap_iter_get(iter, &key, &val);
 *    cp = (char*)val;
 *    if (!*cp) {
 *       iter = strmap_iter_next_rmv(iter);
 *       free(val);
 *    } else {
590
 *       for (;*cp;cp++) *cp = toupper(*cp);
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
 *       iter = strmap_iter_next(iter);
 *    }
 * }
 * \endcode
 *
 */
strmap_iter_t *strmap_iter_init(strmap_t *map)
{
  tor_assert(map);
  return SPLAY_MIN(strmap_tree, &map->head);
}
/** Advance the iterator <b>iter</b> for map a single step to the next entry.
 */
strmap_iter_t *strmap_iter_next(strmap_t *map, strmap_iter_t *iter)
{
  tor_assert(map);
  tor_assert(iter);
  return SPLAY_NEXT(strmap_tree, &map->head, iter);
}
/** Advance the iterator <b>iter</b> a single step to the next entry, removing
 * the current entry.
 */
strmap_iter_t *strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter)
{
  strmap_iter_t *next;
  tor_assert(map);
  tor_assert(iter);
  next = SPLAY_NEXT(strmap_tree, &map->head, iter);
  SPLAY_REMOVE(strmap_tree, &map->head, iter);
  tor_free(iter->key);
  tor_free(iter);
  return next;
}
/** Set *keyp and *valp to the current entry pointed to by iter.
 */
void strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp)
{
  tor_assert(iter);
  tor_assert(keyp);
  tor_assert(valp);
  *keyp = iter->key;
  *valp = iter->val;
}
/** Return true iff iter has advanced past the last entry of map.
 */
int strmap_iter_done(strmap_iter_t *iter)
{
  return iter == NULL;
}
/** Remove all entries from <b>map</b>, and deallocate storage for those entries.
 * If free_val is provided, it is invoked on every value in <b>map</b>.
 */
643
644
void
strmap_free(strmap_t *map, void (*free_val)(void*))
645
646
647
648
649
650
651
{
  strmap_entry_t *ent, *next;
  for (ent = SPLAY_MIN(strmap_tree, &map->head); ent != NULL; ent = next) {
    next = SPLAY_NEXT(strmap_tree, &map->head, ent);
    SPLAY_REMOVE(strmap_tree, &map->head, ent);
    tor_free(ent->key);
    if (free_val)
652
      free_val(ent->val);
653
    tor_free(ent);
654
655
656
657
658
659
660
661
662
  }
  tor_assert(SPLAY_EMPTY(&map->head));
  tor_free(map);
}

int strmap_isempty(strmap_t *map)
{
  return SPLAY_EMPTY(&map->head);
}
663