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

8
9
10
/**
 * \file container.c
 * \brief Implements a smartlist (a resizable array) along
11
12
13
 * with helper functions to use smartlists.  Also includes
 * hash table implementations of a string-to-void* map, and of
 * a digest-to-void* map.
14
15
 **/

16
17
18
19
#include "compat.h"
#include "util.h"
#include "log.h"
#include "container.h"
20
#include "crypto.h"
21
22
23
24
25
26

#ifdef HAVE_CTYPE_H
#include <ctype.h>
#endif
#include <stdlib.h>
#include <string.h>
27
#include <assert.h>
28

29
30
#include "ht.h"

31
32
33
34
35
36
/* All newly allocated smartlists have this capacity.
 */
#define SMARTLIST_DEFAULT_CAPACITY 32

/** Allocate and return an empty smartlist.
 */
37
smartlist_t *
38
39
smartlist_create(void)
{
40
41
42
43
44
45
46
47
48
49
  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.
 */
50
void
51
52
smartlist_free(smartlist_t *sl)
{
53
54
  tor_free(sl->list);
  tor_free(sl);
55
56
57
58
59
60
61
62
}

/** 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.
 */
63
64
65
void
smartlist_set_capacity(smartlist_t *sl, int n)
{
66
67
68
69
70
71
72
73
74
75
  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.
 */
76
void
77
78
smartlist_clear(smartlist_t *sl)
{
79
80
81
  sl->num_used = 0;
}

82
83
84
/** Make sure that <b>sl</b> can hold at least <b>size</b> entries. */
static INLINE void
smartlist_ensure_capacity(smartlist_t *sl, int size)
85
{
86
  if (size > sl->capacity) {
87
    int higher = sl->capacity * 2;
88
89
    while (size > higher)
      higher *= 2;
90
91
    tor_assert(higher > sl->capacity); /* detect overflow */
    sl->capacity = higher;
92
93
    sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
  }
94
95
96
97
98
99
100
}

/** Append element to the end of the list. */
void
smartlist_add(smartlist_t *sl, void *element)
{
  smartlist_ensure_capacity(sl, sl->num_used+1);
101
102
103
104
  sl->list[sl->num_used++] = element;
}

/** Append each element from S2 to the end of S1. */
105
void
106
smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
107
{
108
109
110
  smartlist_ensure_capacity(s1, s1->num_used + s2->num_used);
  memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
  s1->num_used += s2->num_used;
111
112
}

113
114
115
/** 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.
116
 */
117
void
118
smartlist_remove(smartlist_t *sl, const void *element)
119
{
120
  int i;
121
  if (element == NULL)
122
    return;
123
124
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element) {
125
126
127
128
129
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
}

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

147
148
/** Return true iff some element E of sl has E==element.
 */
149
int
150
smartlist_isin(const smartlist_t *sl, const void *element)
151
{
152
  int i;
153
154
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element)
155
156
157
158
      return 1;
  return 0;
}

159
160
161
162
163
164
/** Return true iff <b>sl</b> has some element E such that
 * !strcmp(E,<b>element</b>)
 */
int
smartlist_string_isin(const smartlist_t *sl, const char *element)
{
165
  int i;
166
  if (!sl) return 0;
167
168
  for (i=0; i < sl->num_used; i++)
    if (strcmp((const char*)sl->list[i],element)==0)
169
170
171
172
      return 1;
  return 0;
}

173
174
175
176
177
178
/** Return true iff <b>sl</b> has some element E such that E is equal
 * to the decimal encoding of <b>num</b>.
 */
int
smartlist_string_num_isin(const smartlist_t *sl, int num)
{
179
180
181
182
183
  char buf[16];
  tor_snprintf(buf,sizeof(buf),"%d", num);
  return smartlist_string_isin(sl, buf);
}

184
185
/** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
 */
186
187
188
int
smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
{
189
  int i;
190
191
  for (i=0; i < sl2->num_used; i++)
    if (smartlist_isin(sl1, sl2->list[i]))
192
193
194
195
196
197
198
      return 1;
  return 0;
}

/** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
 * Does not preserve the order of sl1.
 */
199
200
201
void
smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
{
202
  int i;
203
204
  for (i=0; i < sl1->num_used; i++)
    if (!smartlist_isin(sl2, sl1->list[i])) {
205
206
207
208
209
210
211
212
      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.
 */
213
214
215
void
smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
{
216
  int i;
217
  for (i=0; i < sl2->num_used; i++)
218
219
220
221
222
223
224
    smartlist_remove(sl1, sl2->list[i]);
}

/** 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.
 */
225
226
void
smartlist_del(smartlist_t *sl, int idx)
227
228
229
230
231
232
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx < sl->num_used);
  sl->list[idx] = sl->list[--sl->num_used];
}
Roger Dingledine's avatar
Roger Dingledine committed
233

234
235
236
237
/** 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.
 */
238
239
void
smartlist_del_keeporder(smartlist_t *sl, int idx)
240
241
242
243
244
245
246
247
{
  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));
}
Roger Dingledine's avatar
Roger Dingledine committed
248

249
250
251
252
/** 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.
 */
253
254
void
smartlist_insert(smartlist_t *sl, int idx, void *val)
255
256
257
258
259
260
261
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx <= sl->num_used);
  if (idx == sl->num_used) {
    smartlist_add(sl, val);
  } else {
262
    smartlist_ensure_capacity(sl, sl->num_used+1);
263
264
265
266
267
268
269
270
271
272
    /* 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
int
smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
                       int flags, int max)
284
285
286
287
288
289
290
291
292
293
{
  const char *cp, *end, *next;
  int n = 0;

  tor_assert(sl);
  tor_assert(str);

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

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

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

    if (flags&SPLIT_SKIP_SPACE) {
319
      while (end > cp && TOR_ISSPACE(*(end-1)))
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
        --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>.
337
338
339
 * 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.
340
 */
341
342
343
char *
smartlist_join_strings(smartlist_t *sl, const char *join,
                       int terminate, size_t *len_out)
344
345
346
347
{
  return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
}

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

  tor_assert(sl);
  tor_assert(join);
363

Roger Dingledine's avatar
Roger Dingledine committed
364
365
  if (terminate)
    n = join_len;
366

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

  if (len_out)
    *len_out = dst-r;
389
390
391
  return r;
}

392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
/** Sort the members of <b>sl</b> into an order defined by
 * the ordering function <b>compare</b>, which returns less then 0 if a
 * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b.
 */
void
smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
{
  if (!sl->num_used)
    return;
  qsort(sl->list, sl->num_used, sizeof(void*),
        (int (*)(const void *,const void*))compare);
}

/** Assuming the members of <b>sl</b> are in order, return a pointer to the
 * member which matches <b>key</b>.  Ordering and matching are defined by a
 * <b>compare</b> function, which returns 0 on a match; less than 0 if key is
 * less than member, and greater than 0 if key is greater then member.
 */
void *
smartlist_bsearch(smartlist_t *sl, const void *key,
                  int (*compare)(const void *key, const void **member))
{
  void ** r;
  if (!sl->num_used)
    return NULL;

  r = bsearch(key, sl->list, sl->num_used, sizeof(void*),
              (int (*)(const void *, const void *))compare);
  return r ? *r : NULL;
}

423
/** Helper: compare two const char **s. */
424
static int
425
_compare_string_ptrs(const void **_a, const void **_b)
426
{
427
  return strcmp((const char*)*_a, (const char*)*_b);
428
429
}

430
431
/** Sort a smartlist <b>sl</b> containing strings into lexically ascending
 * order. */
432
433
434
435
436
437
void
smartlist_sort_strings(smartlist_t *sl)
{
  smartlist_sort(sl, _compare_string_ptrs);
}

438
439
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
  typedef struct prefix ## entry_t {                      \
440
    HT_ENTRY(prefix ## entry_t) node;                     \
441
    void *val;                                            \
442
    keydecl;                                              \
443
444
  } prefix ## entry_t;                                    \
  struct maptype {                                        \
445
    HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
446
  };
447

448
449
DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
450

451
/** Helper: compare strmap_t_entry objects by key value. */
452
453
454
455
456
457
458
459
static INLINE int
strmap_entries_eq(strmap_entry_t *a, strmap_entry_t *b)
{
  return !strcmp(a->key, b->key);
}

static INLINE unsigned int
strmap_entry_hash(strmap_entry_t *a)
460
{
461
  return ht_string_hash(a->key);
462
463
}

464
/** Helper: compare digestmap_entry_t objects by key value. */
465
466
static INLINE int
digestmap_entries_eq(digestmap_entry_t *a, digestmap_entry_t *b)
467
{
468
  return !memcmp(a->key, b->key, DIGEST_LEN);
469
470
}

471
472
473
474
475
476
477
static INLINE unsigned int
digestmap_entry_hash(digestmap_entry_t *a)
{
  uint32_t *p = (uint32_t*)a->key;
  return ht_improve_hash(p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4]);
}

478
HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
479
             strmap_entries_eq);
480
HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
481
            strmap_entries_eq, 0.6, malloc, realloc, free);
482

483
HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
484
             digestmap_entries_eq);
485
HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
486
            digestmap_entries_eq, 0.6, malloc, realloc, free);
487

488
/** Constructor to create a new empty map from strings to void*'s.
489
 */
490
491
strmap_t *
strmap_new(void)
492
493
494
{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
495
  HT_INIT(&result->head);
496
497
498
  return result;
}

499
/** Constructor to create a new empty map from digests to void*'s.
500
501
502
503
504
505
 */
digestmap_t *
digestmap_new(void)
{
  digestmap_t *result;
  result = tor_malloc(sizeof(digestmap_t));
506
  HT_INIT(&result->head);
507
508
509
  return result;
}

510
511
512
/** 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.
 *
513
514
 * This function makes a copy of <b>key</b> if necessary, but not of
 * <b>val</b>.
515
 */
516
517
void *
strmap_set(strmap_t *map, const char *key, void *val)
518
519
520
521
522
523
524
525
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  search.key = (char*)key;
526
  resolve = HT_FIND(strmap_impl, &map->head, &search);
527
528
529
530
531
532
533
534
  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;
535
536
    tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
    HT_INSERT(strmap_impl, &map->head, resolve);
537
538
539
540
    return NULL;
  }
}

541
/** Like strmap_set() above but for digestmaps. */
542
543
544
545
546
547
548
549
550
551
void *
digestmap_set(digestmap_t *map, const char *key, void *val)
{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  memcpy(&search.key, key, DIGEST_LEN);
552
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
553
554
555
556
557
558
559
560
  if (resolve) {
    oldval = resolve->val;
    resolve->val = val;
    return oldval;
  } else {
    resolve = tor_malloc_zero(sizeof(digestmap_entry_t));
    memcpy(resolve->key, key, DIGEST_LEN);
    resolve->val = val;
561
    HT_INSERT(digestmap_impl, &map->head, resolve);
562
563
564
565
    return NULL;
  }
}

566
567
568
/** Return the current value associated with <b>key</b>, or NULL if no
 * value is set.
 */
569
570
void *
strmap_get(strmap_t *map, const char *key)
571
572
573
574
575
576
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
577
  resolve = HT_FIND(strmap_impl, &map->head, &search);
578
579
580
581
582
583
584
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

585
/** Like strmap_get() above but for digestmaps. */
586
587
588
589
590
591
592
593
void *
digestmap_get(digestmap_t *map, const char *key)
{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  memcpy(&search.key, key, DIGEST_LEN);
594
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
595
596
597
598
599
600
601
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

602
603
604
605
606
607
/** 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.
 */
608
609
void *
strmap_remove(strmap_t *map, const char *key)
610
611
612
613
614
615
616
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
617
  resolve = HT_REMOVE(strmap_impl, &map->head, &search);
618
619
620
621
622
623
624
625
626
627
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve->key);
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

628
/** Like strmap_remove() above but for digestmaps. */
629
630
631
632
633
634
635
636
637
void *
digestmap_remove(digestmap_t *map, const char *key)
{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  memcpy(&search.key, key, DIGEST_LEN);
638
  resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
639
640
641
642
643
644
645
646
647
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

648
/** Same as strmap_set, but first converts <b>key</b> to lowercase. */
649
650
void *
strmap_set_lc(strmap_t *map, const char *key, void *val)
651
652
653
654
655
656
657
658
659
660
{
  /* 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;
}
661

662
/** Same as strmap_get, but first converts <b>key</b> to lowercase. */
663
664
void *
strmap_get_lc(strmap_t *map, const char *key)
665
666
667
668
669
670
671
672
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_get(map,lc_key);
  tor_free(lc_key);
  return v;
}
673

674
/** Same as strmap_remove, but first converts <b>key</b> to lowercase */
675
676
void *
strmap_remove_lc(strmap_t *map, const char *key)
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_remove(map,lc_key);
  tor_free(lc_key);
  return v;
}

/** 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 {
705
 *       for (;*cp;cp++) *cp = toupper(*cp);
706
707
708
709
710
711
 *       iter = strmap_iter_next(iter);
 *    }
 * }
 * \endcode
 *
 */
712
713
strmap_iter_t *
strmap_iter_init(strmap_t *map)
714
715
{
  tor_assert(map);
716
  return HT_START(strmap_impl, &map->head);
717
}
718
719
720
721
722

digestmap_iter_t *
digestmap_iter_init(digestmap_t *map)
{
  tor_assert(map);
723
  return HT_START(digestmap_impl, &map->head);
724
725
}

726
727
/** Advance the iterator <b>iter</b> for map a single step to the next entry.
 */
728
729
strmap_iter_t *
strmap_iter_next(strmap_t *map, strmap_iter_t *iter)
730
731
732
{
  tor_assert(map);
  tor_assert(iter);
733
  return HT_NEXT(strmap_impl, &map->head, iter);
734
}
735
736
737
738
739
740

digestmap_iter_t *
digestmap_iter_next(digestmap_t *map, digestmap_iter_t *iter)
{
  tor_assert(map);
  tor_assert(iter);
741
  return HT_NEXT(digestmap_impl, &map->head, iter);
742
743
}

744
745
746
/** Advance the iterator <b>iter</b> a single step to the next entry, removing
 * the current entry.
 */
747
748
strmap_iter_t *
strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter)
749
{
750
  strmap_entry_t *rmv;
751
752
  tor_assert(map);
  tor_assert(iter);
753
754
  tor_assert(*iter);
  rmv = *iter;
755
  iter = HT_NEXT_RMV(strmap_impl, &map->head, iter);
756
757
758
  tor_free(rmv->key);
  tor_free(rmv);
  return iter;
759
}
760
761
762
763

digestmap_iter_t *
digestmap_iter_next_rmv(digestmap_t *map, digestmap_iter_t *iter)
{
764
  digestmap_entry_t *rmv;
765
766
  tor_assert(map);
  tor_assert(iter);
767
768
  tor_assert(*iter);
  rmv = *iter;
769
  iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter);
770
771
  tor_free(rmv);
  return iter;
772
773
}

774
775
/** Set *keyp and *valp to the current entry pointed to by iter.
 */
776
777
void
strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp)
778
779
{
  tor_assert(iter);
780
  tor_assert(*iter);
781
782
  tor_assert(keyp);
  tor_assert(valp);
783
784
  *keyp = (*iter)->key;
  *valp = (*iter)->val;
785
}
786
787
788
789
790

void
digestmap_iter_get(digestmap_iter_t *iter, const char **keyp, void **valp)
{
  tor_assert(iter);
791
  tor_assert(*iter);
792
793
  tor_assert(keyp);
  tor_assert(valp);
794
795
  *keyp = (*iter)->key;
  *valp = (*iter)->val;
796
797
}

798
799
/** Return true iff iter has advanced past the last entry of map.
 */
800
801
int
strmap_iter_done(strmap_iter_t *iter)
802
803
804
{
  return iter == NULL;
}
805
806
807
808
809
810
int
digestmap_iter_done(digestmap_iter_t *iter)
{
  return iter == NULL;
}

811
812
813
/** 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>.
814
 */
815
816
void
strmap_free(strmap_t *map, void (*free_val)(void*))
817
{
818
  strmap_entry_t **ent, **next, *this;
819
  for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) {
820
    this = *ent;
821
    next = HT_NEXT_RMV(strmap_impl, &map->head, ent);
822
    tor_free(this->key);
823
    if (free_val)
824
825
      free_val(this->val);
    tor_free(this);
826
  }
827
  tor_assert(HT_EMPTY(&map->head));
828
  HT_CLEAR(strmap_impl, &map->head);
829
830
  tor_free(map);
}
831
832
833
void
digestmap_free(digestmap_t *map, void (*free_val)(void*))
{
834
  digestmap_entry_t **ent, **next, *this;
835
  for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) {
836
    this = *ent;
837
    next = HT_NEXT_RMV(digestmap_impl, &map->head, ent);
838
    if (free_val)
839
840
      free_val(this->val);
    tor_free(this);
841
  }
842
  tor_assert(HT_EMPTY(&map->head));
843
  HT_CLEAR(digestmap_impl, &map->head);
844
845
846
  tor_free(map);
}

847
/** Return true iff <b>map</b> has no entries. */
848
849
int
strmap_isempty(strmap_t *map)
850
{
851
  return HT_EMPTY(&map->head);
852
}
853

854
855
856
int
digestmap_isempty(digestmap_t *map)
{
857
  return HT_EMPTY(&map->head);
858
859
}

860
861
862
863
864
865
866
867
868
869
870
871
int
strmap_size(strmap_t *map)
{
  return HT_SIZE(&map->head);
}

int
digestmap_size(digestmap_t *map)
{
  return HT_SIZE(&map->head);
}