container.c 31.1 KB
Newer Older
1
2
/* Copyright (c) 2003-2004, Roger Dingledine
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3
 * Copyright (c) 2007-2008, The Tor Project, Inc. */
4
5
/* See LICENSE for licensing information */
/* $Id$ */
6
7
const char container_c_id[] =
  "$Id$";
8

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

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

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

30
31
#include "ht.h"

32
/** All newly allocated smartlists have this capacity. */
33
34
35
36
#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
  tor_assert(sl != NULL);
54
55
  tor_free(sl->list);
  tor_free(sl);
56
57
58
59
}

/** Remove all elements from the list.
 */
60
void
61
62
smartlist_clear(smartlist_t *sl)
{
63
64
65
  sl->num_used = 0;
}

66
67
68
/** 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)
69
{
70
  if (size > sl->capacity) {
71
    int higher = sl->capacity * 2;
72
73
    while (size > higher)
      higher *= 2;
74
    tor_assert(higher > 0); /* detect overflow */
75
    sl->capacity = higher;
76
77
    sl->list = tor_realloc(sl->list, sizeof(void*)*sl->capacity);
  }
78
79
80
81
82
83
84
}

/** Append element to the end of the list. */
void
smartlist_add(smartlist_t *sl, void *element)
{
  smartlist_ensure_capacity(sl, sl->num_used+1);
85
86
87
88
  sl->list[sl->num_used++] = element;
}

/** Append each element from S2 to the end of S1. */
89
void
90
smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
91
{
92
93
94
  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;
95
96
}

97
98
99
/** 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.
100
 */
101
void
102
smartlist_remove(smartlist_t *sl, const void *element)
103
{
104
  int i;
105
  if (element == NULL)
106
    return;
107
108
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element) {
109
110
111
112
113
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
    }
}

114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/** If <b>sl</b> is nonempty, remove and return the final element.  Otherwise,
 * return NULL. */
void *
smartlist_pop_last(smartlist_t *sl)
{
  tor_assert(sl);
  if (sl->num_used)
    return sl->list[--sl->num_used];
  else
    return NULL;
}

/** Reverse the order of the items in <b>sl</b>. */
void
smartlist_reverse(smartlist_t *sl)
{
  int i, j;
  void *tmp;
  tor_assert(sl);
  for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
    tmp = sl->list[i];
    sl->list[i] = sl->list[j];
    sl->list[j] = tmp;
  }
}

140
/** If there are any strings in sl equal to element, remove and free them.
141
142
143
144
145
 * Does not preserve order. */
void
smartlist_string_remove(smartlist_t *sl, const char *element)
{
  int i;
146
147
148
  tor_assert(sl);
  tor_assert(element);
  for (i = 0; i < sl->num_used; ++i) {
149
    if (!strcmp(element, sl->list[i])) {
150
      tor_free(sl->list[i]);
151
152
      sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
      i--; /* so we process the new i'th element */
153
154
155
156
    }
  }
}

157
158
/** Return true iff some element E of sl has E==element.
 */
159
int
160
smartlist_isin(const smartlist_t *sl, const void *element)
161
{
162
  int i;
163
164
  for (i=0; i < sl->num_used; i++)
    if (sl->list[i] == element)
165
166
167
168
      return 1;
  return 0;
}

169
170
171
172
173
174
/** 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)
{
175
  int i;
176
  if (!sl) return 0;
177
178
  for (i=0; i < sl->num_used; i++)
    if (strcmp((const char*)sl->list[i],element)==0)
179
180
181
182
      return 1;
  return 0;
}

183
184
/** If <b>element</b> is equal to an element of <b>sl</b>, return that
 * element's index.  Otherwise, return -1. */
185
186
187
188
189
190
191
192
193
194
195
int
smartlist_string_pos(const smartlist_t *sl, const char *element)
{
  int i;
  if (!sl) return -1;
  for (i=0; i < sl->num_used; i++)
    if (strcmp((const char*)sl->list[i],element)==0)
      return i;
  return -1;
}

196
197
198
199
200
201
202
203
204
205
206
207
208
209
/** Return true iff <b>sl</b> has some element E such that
 * !strcasecmp(E,<b>element</b>)
 */
int
smartlist_string_isin_case(const smartlist_t *sl, const char *element)
{
  int i;
  if (!sl) return 0;
  for (i=0; i < sl->num_used; i++)
    if (strcasecmp((const char*)sl->list[i],element)==0)
      return 1;
  return 0;
}

210
211
212
213
214
215
/** 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)
{
216
217
218
219
220
  char buf[16];
  tor_snprintf(buf,sizeof(buf),"%d", num);
  return smartlist_string_isin(sl, buf);
}

221
222
223
224
225
226
227
228
229
230
231
232
233
234
/** Return true iff <b>sl</b> has some element E such that
 * !memcmp(E,<b>element</b>,DIGEST_LEN)
 */
int
smartlist_digest_isin(const smartlist_t *sl, const char *element)
{
  int i;
  if (!sl) return 0;
  for (i=0; i < sl->num_used; i++)
    if (memcmp((const char*)sl->list[i],element,DIGEST_LEN)==0)
      return 1;
  return 0;
}

235
236
/** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
 */
237
238
239
int
smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
{
240
  int i;
241
242
  for (i=0; i < sl2->num_used; i++)
    if (smartlist_isin(sl1, sl2->list[i]))
243
244
245
246
247
248
249
      return 1;
  return 0;
}

/** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
 * Does not preserve the order of sl1.
 */
250
251
252
void
smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
{
253
  int i;
254
255
  for (i=0; i < sl1->num_used; i++)
    if (!smartlist_isin(sl2, sl1->list[i])) {
256
257
258
259
260
261
262
263
      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.
 */
264
265
266
void
smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
{
267
  int i;
268
  for (i=0; i < sl2->num_used; i++)
269
270
271
272
273
274
275
    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.
 */
276
277
void
smartlist_del(smartlist_t *sl, int idx)
278
279
280
281
282
283
{
  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
284

285
286
287
288
/** 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.
 */
289
290
void
smartlist_del_keeporder(smartlist_t *sl, int idx)
291
292
293
294
295
296
297
298
{
  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
299

300
301
302
303
/** 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.
 */
304
305
void
smartlist_insert(smartlist_t *sl, int idx, void *val)
306
307
308
309
310
311
312
{
  tor_assert(sl);
  tor_assert(idx>=0);
  tor_assert(idx <= sl->num_used);
  if (idx == sl->num_used) {
    smartlist_add(sl, val);
  } else {
313
    smartlist_ensure_capacity(sl, sl->num_used+1);
314
315
316
317
318
319
320
321
322
323
    /* 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;
  }
}

/**
324
 * Split a string <b>str</b> along all occurrences of <b>sep</b>,
325
326
327
328
329
 * 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>
330
 * pieces.  If <b>sep</b> is NULL, split on any sequence of horizontal space.
331
 */
332
333
334
int
smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
                       int flags, int max)
335
336
337
338
339
340
341
342
343
344
{
  const char *cp, *end, *next;
  int n = 0;

  tor_assert(sl);
  tor_assert(str);

  cp = str;
  while (1) {
    if (flags&SPLIT_SKIP_SPACE) {
345
      while (TOR_ISSPACE(*cp)) ++cp;
346
347
348
349
    }

    if (max>0 && n == max-1) {
      end = strchr(cp,'\0');
350
    } else if (sep) {
351
352
353
      end = strstr(cp,sep);
      if (!end)
        end = strchr(cp,'\0');
354
355
356
    } else {
      for (end = cp; *end && *end != '\t' && *end != ' '; ++end)
        ;
357
    }
358

359
360
    if (!*end) {
      next = NULL;
361
    } else if (sep) {
362
      next = end+strlen(sep);
363
364
365
366
    } else {
      next = end+1;
      while (*next == '\t' || *next == ' ')
        ++next;
367
368
369
    }

    if (flags&SPLIT_SKIP_SPACE) {
370
      while (end > cp && TOR_ISSPACE(*(end-1)))
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
        --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>.
388
389
390
 * 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.
391
 */
392
393
394
char *
smartlist_join_strings(smartlist_t *sl, const char *join,
                       int terminate, size_t *len_out)
395
396
397
398
{
  return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
}

Roger Dingledine's avatar
Roger Dingledine committed
399
/** As smartlist_join_strings, but instead of separating/terminated with a
400
 * NUL-terminated string <b>join</b>, uses the <b>join_len</b>-byte sequence
401
 * at <b>join</b>.  (Useful for generating a sequence of NUL-terminated
402
403
 * strings.)
 */
404
405
406
char *
smartlist_join_strings2(smartlist_t *sl, const char *join,
                        size_t join_len, int terminate, size_t *len_out)
407
408
{
  int i;
409
  size_t n = 0;
410
411
412
413
  char *r = NULL, *dst, *src;

  tor_assert(sl);
  tor_assert(join);
414

Roger Dingledine's avatar
Roger Dingledine committed
415
416
  if (terminate)
    n = join_len;
417

418
419
  for (i = 0; i < sl->num_used; ++i) {
    n += strlen(sl->list[i]);
Roger Dingledine's avatar
Roger Dingledine committed
420
421
    if (i+1 < sl->num_used) /* avoid double-counting the last one */
      n += join_len;
422
423
424
425
426
  }
  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
427
    if (++i < sl->num_used) {
428
429
      memcpy(dst, join, join_len);
      dst += join_len;
430
431
    }
  }
Roger Dingledine's avatar
Roger Dingledine committed
432
  if (terminate) {
433
434
435
    memcpy(dst, join, join_len);
    dst += join_len;
  }
436
  *dst = '\0';
437
438
439

  if (len_out)
    *len_out = dst-r;
440
441
442
  return r;
}

443
444
445
446
447
448
449
450
451
452
453
454
455
/** 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);
}

456
457
/** Given a sorted smartlist <b>sl</b> and the comparison function used to
 * sort it, remove all duplicate members.  If free_fn is provided, calls
458
 * free_fn on each duplicate.  Otherwise, just removes them.  Preserves order.
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
 */
void
smartlist_uniq(smartlist_t *sl,
               int (*compare)(const void **a, const void **b),
               void (*free_fn)(void *a))
{
  int i;
  for (i=1; i < sl->num_used; ++i) {
    if (compare((const void **)&(sl->list[i-1]),
                (const void **)&(sl->list[i])) == 0) {
      if (free_fn)
        free_fn(sl->list[i]);
      smartlist_del_keeporder(sl, i--);
    }
  }
}

476
/** Assuming the members of <b>sl</b> are in order, return a pointer to the
477
478
 * member that matches <b>key</b>.  Ordering and matching are defined by a
 * <b>compare</b> function that returns 0 on a match; less than 0 if key is
479
480
481
482
483
484
 * 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))
{
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
  int found, idx;
  idx = smartlist_bsearch_idx(sl, key, compare, &found);
  return found ? smartlist_get(sl, idx) : NULL;
}

/** Assuming the members of <b>sl</b> are in order, return the index of the
 * member that matches <b>key</b>.  If no member matches, return the index of
 * the first member greater than <b>key</b>, or smartlist_len(sl) if no member
 * is greater than <b>key</b>.  Set <b>found_out</b> to true on a match, to
 * false otherwise.  Ordering and matching are defined by a <b>compare</b>
 * function that returns 0 on a match; less than 0 if key is less than member,
 * and greater than 0 if key is greater then member.
 */
int
smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
                      int (*compare)(const void *key, const void **member),
                      int *found_out)
{
  int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid;

  while (lo <= hi) {
    mid = (lo + hi) / 2;
    cmp = compare(key, (const void**) &(sl->list[mid]));
    if (cmp>0) { /* key > sl[mid] */
      lo = mid+1;
    } else if (cmp<0) { /* key < sl[mid] */
      hi = mid-1;
    } else { /* key == sl[mid] */
      *found_out = 1;
      return mid;
    }
  }
  /* lo > hi. */
  {
    tor_assert(lo >= 0);
    if (lo < smartlist_len(sl)) {
      cmp = compare(key, (const void**) &(sl->list[lo]));
      tor_assert(cmp < 0);
    } else if (smartlist_len(sl)) {
      cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1]));
      tor_assert(cmp > 0);
    }
  }
  *found_out = 0;
  return lo;
530
531
}

532
/** Helper: compare two const char **s. */
533
static int
534
_compare_string_ptrs(const void **_a, const void **_b)
535
{
536
  return strcmp((const char*)*_a, (const char*)*_b);
537
538
}

539
540
/** Sort a smartlist <b>sl</b> containing strings into lexically ascending
 * order. */
541
542
543
544
545
546
void
smartlist_sort_strings(smartlist_t *sl)
{
  smartlist_sort(sl, _compare_string_ptrs);
}

547
548
549
550
551
/** Remove duplicate strings from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_strings(smartlist_t *sl)
{
552
  smartlist_uniq(sl, _compare_string_ptrs, _tor_free);
553
554
}

555
556
557
558
/* Heap-based priority queue implementation for O(lg N) insert and remove.
 * Recall that the heap property is that, for every index I, h[I] <
 * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
 */
559

560
561
562
563
564
565
566
567
568
569
570
571
/* For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x]
 * = 2*x + 1.  But this is C, so we have to adjust a little. */
//#define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
//#define RIGHT_CHILD(i) ( ((i)+1)*2 )
//#define PARENT(i)      ( ((i)+1)/2 - 1)
#define LEFT_CHILD(i)  ( 2*(i) + 1 )
#define RIGHT_CHILD(i) ( 2*(i) + 2 )
#define PARENT(i)      ( ((i)-1) / 2 )

/** Helper. <b>sl</b> may have at most one violation of the heap property:
 * the item at <b>idx</b> may be greater than one or both of its children.
 * Restore the heap property. */
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
static INLINE void
smartlist_heapify(smartlist_t *sl,
                  int (*compare)(const void *a, const void *b),
                  int idx)
{
  while (1) {
    int left_idx = LEFT_CHILD(idx);
    int best_idx;

    if (left_idx >= sl->num_used)
      return;
    if (compare(sl->list[idx],sl->list[left_idx]) < 0)
      best_idx = idx;
    else
      best_idx = left_idx;
    if (left_idx+1 < sl->num_used &&
        compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
      best_idx = left_idx + 1;

    if (best_idx == idx) {
      return;
    } else {
      void *tmp = sl->list[idx];
      sl->list[idx] = sl->list[best_idx];
      sl->list[best_idx] = tmp;

      idx = best_idx;
    }
  }
}

603
/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
Roger Dingledine's avatar
Roger Dingledine committed
604
 * is determined by <b>compare</b>. */
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
void
smartlist_pqueue_add(smartlist_t *sl,
                     int (*compare)(const void *a, const void *b),
                     void *item)
{
  int idx;
  smartlist_add(sl,item);

  for (idx = sl->num_used - 1; idx; ) {
    int parent = PARENT(idx);
    if (compare(sl->list[idx], sl->list[parent]) < 0) {
      void *tmp = sl->list[parent];
      sl->list[parent] = sl->list[idx];
      sl->list[idx] = tmp;
      idx = parent;
    } else {
      return;
    }
  }
}

626
627
628
/** Remove and return the top-priority item from the heap stored in <b>sl</b>,
 * where order is determined by <b>compare</b>.  <b>sl</b> must not be
 * empty. */
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
void *
smartlist_pqueue_pop(smartlist_t *sl,
                     int (*compare)(const void *a, const void *b))
{
  void *top;
  tor_assert(sl->num_used);

  top = sl->list[0];
  if (--sl->num_used) {
    sl->list[0] = sl->list[sl->num_used];
    smartlist_heapify(sl, compare, 0);
  }
  return top;
}

644
645
/** Assert that the heap property is correctly maintained by the heap stored
 * in <b>sl</b>, where order is determined by <b>compare</b>. */
646
647
648
649
650
651
652
653
654
655
void
smartlist_pqueue_assert_ok(smartlist_t *sl,
                           int (*compare)(const void *a, const void *b))
{
  int i;
  for (i = sl->num_used - 1; i > 0; --i) {
    tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
  }
}

656
657
658
659
660
661
662
663
664
665
666
/** Helper: compare two DIGEST_LEN digests. */
static int
_compare_digests(const void **_a, const void **_b)
{
  return memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
}

/** Sort the list of DIGEST_LEN-byte digests into ascending order. */
void
smartlist_sort_digests(smartlist_t *sl)
{
667
  smartlist_sort(sl, _compare_digests);
668
669
}

670
671
672
673
674
/** Remove duplicate digests from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_digests(smartlist_t *sl)
{
675
  smartlist_uniq(sl, _compare_digests, _tor_free);
676
677
}

678
679
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
  typedef struct prefix ## entry_t {                      \
680
    HT_ENTRY(prefix ## entry_t) node;                     \
681
    void *val;                                            \
682
    keydecl;                                              \
683
684
  } prefix ## entry_t;                                    \
  struct maptype {                                        \
685
    HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
686
  }
687

688
689
DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
690

691
/** Helper: compare strmap_entry_t objects by key value. */
692
static INLINE int
693
strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
694
695
696
697
{
  return !strcmp(a->key, b->key);
}

Roger Dingledine's avatar
Roger Dingledine committed
698
/** Helper: return a hash value for a strmap_entry_t. */
699
static INLINE unsigned int
700
strmap_entry_hash(const strmap_entry_t *a)
701
{
702
  return ht_string_hash(a->key);
703
704
}

705
/** Helper: compare digestmap_entry_t objects by key value. */
706
static INLINE int
707
digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
708
{
709
  return !memcmp(a->key, b->key, DIGEST_LEN);
710
711
}

Roger Dingledine's avatar
Roger Dingledine committed
712
/** Helper: return a hash value for a digest_map_t. */
713
static INLINE unsigned int
714
digestmap_entry_hash(const digestmap_entry_t *a)
715
{
716
717
718
719
720
721
722
#if SIZEOF_INT != 8
  const uint32_t *p = (const uint32_t*)a->key;
  return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
#else
  const uint64_t *p = (const uint64_t*)a->key;
  return p[0] ^ p[1];
#endif
723
724
}

725
HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
726
             strmap_entries_eq)
727
HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
728
            strmap_entries_eq, 0.6, malloc, realloc, free)
729

730
HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
731
             digestmap_entries_eq)
732
HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
733
            digestmap_entries_eq, 0.6, malloc, realloc, free)
734

735
/** Constructor to create a new empty map from strings to void*'s.
736
 */
737
738
strmap_t *
strmap_new(void)
739
740
741
{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
742
  HT_INIT(strmap_impl, &result->head);
743
744
745
  return result;
}

746
/** Constructor to create a new empty map from digests to void*'s.
747
748
749
750
751
752
 */
digestmap_t *
digestmap_new(void)
{
  digestmap_t *result;
  result = tor_malloc(sizeof(digestmap_t));
753
  HT_INIT(digestmap_impl, &result->head);
754
755
756
  return result;
}

757
758
759
/** 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.
 *
760
761
 * This function makes a copy of <b>key</b> if necessary, but not of
 * <b>val</b>.
762
 */
763
764
void *
strmap_set(strmap_t *map, const char *key, void *val)
765
766
767
768
769
770
771
772
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  search.key = (char*)key;
773
  resolve = HT_FIND(strmap_impl, &map->head, &search);
774
775
776
777
778
779
780
781
  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;
782
783
    tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
    HT_INSERT(strmap_impl, &map->head, resolve);
784
785
786
787
    return NULL;
  }
}

788
789
#define OPTIMIZED_DIGESTMAP_SET

790
/** Like strmap_set() above but for digestmaps. */
791
792
793
void *
digestmap_set(digestmap_t *map, const char *key, void *val)
{
794
#ifndef OPTIMIZED_DIGESTMAP_SET
795
  digestmap_entry_t *resolve;
796
#endif
797
798
799
800
801
802
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  memcpy(&search.key, key, DIGEST_LEN);
803
#ifndef OPTIMIZED_DIGESTMAP_SET
804
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
805
806
807
808
809
810
811
812
  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;
813
    HT_INSERT(digestmap_impl, &map->head, resolve);
814
815
    return NULL;
  }
816
#else
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
  /* We spend up to 5% of our time in this function, so the code below is
   * meant to optimize the check/alloc/set cycle by avoiding the two trips to
   * the hash table that we do in the unoptimized code above.  (Each of
   * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
   */
  _HT_FIND_OR_INSERT(digestmap_impl, node, digestmap_entry_hash, &(map->head),
         digestmap_entry_t, &search, ptr,
         {
            /* we found an entry. */
            oldval = (*ptr)->val;
            (*ptr)->val = val;
            return oldval;
         },
         {
           /* We didn't find the entry. */
           digestmap_entry_t *newent =
             tor_malloc_zero(sizeof(digestmap_entry_t));
           memcpy(newent->key, key, DIGEST_LEN);
           newent->val = val;
           _HT_FOI_INSERT(node, &(map->head), &search, newent, ptr);
           return NULL;
         });
839
#endif
840
841
}

842
843
844
/** Return the current value associated with <b>key</b>, or NULL if no
 * value is set.
 */
845
void *
846
strmap_get(const strmap_t *map, const char *key)
847
848
849
850
851
852
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
853
  resolve = HT_FIND(strmap_impl, &map->head, &search);
854
855
856
857
858
859
860
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

861
/** Like strmap_get() above but for digestmaps. */
862
void *
863
digestmap_get(const digestmap_t *map, const char *key)
864
865
866
867
868
869
{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  memcpy(&search.key, key, DIGEST_LEN);
870
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
871
872
873
874
875
876
877
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

878
879
880
881
882
883
/** 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.
 */
884
885
void *
strmap_remove(strmap_t *map, const char *key)
886
887
888
889
890
891
892
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
893
  resolve = HT_REMOVE(strmap_impl, &map->head, &search);
894
895
896
897
898
899
900
901
902
903
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve->key);
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

904
/** Like strmap_remove() above but for digestmaps. */
905
906
907
908
909
910
911
912
913
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);
914
  resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
915
916
917
918
919
920
921
922
923
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

924
/** Same as strmap_set, but first converts <b>key</b> to lowercase. */
925
926
void *
strmap_set_lc(strmap_t *map, const char *key, void *val)
927
928
929
930
931
932
933
934
935
936
{
  /* 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;
}
937

938
/** Same as strmap_get, but first converts <b>key</b> to lowercase. */
939
void *
940
strmap_get_lc(const strmap_t *map, const char *key)
941
942
943
944
945
946
947
948
{
  void *v;
  char *lc_key = tor_strdup(key);
  tor_strlower(lc_key);
  v = strmap_get(map,lc_key);
  tor_free(lc_key);
  return v;
}
949

950
/** Same as strmap_remove, but first converts <b>key</b> to lowercase */
951
952
void *
strmap_remove_lc(strmap_t *map, const char *key)
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
{
  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) {
978
 *       iter = strmap_iter_next_rmv(map,iter);
979
980
 *       free(val);
 *    } else {
981
 *       for (;*cp;cp++) *cp = TOR_TOUPPER(*cp);
982
 *       iter = strmap_iter_next(map,iter);
983
984
985
986
987
 *    }
 * }
 * \endcode
 *
 */
988
989
strmap_iter_t *
strmap_iter_init(strmap_t *map)
990
991
{
  tor_assert(map);
992
  return HT_START(strmap_impl, &map->head);
993
}
994
995
996
997
998

digestmap_iter_t *
digestmap_iter_init(digestmap_t *map)
{
  tor_assert(map);
999
  return HT_START(digestmap_impl, &map->head);
1000
}
For faster browsing, not all history is shown. View entire blame