container.c 35.7 KB
Newer Older
1
2
/* Copyright (c) 2003-2004, Roger Dingledine
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
Karsten Loesing's avatar
Karsten Loesing committed
3
 * Copyright (c) 2007-2009, The Tor Project, Inc. */
4
5
/* See LICENSE for licensing information */

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

14
15
16
17
#include "compat.h"
#include "util.h"
#include "log.h"
#include "container.h"
18
#include "crypto.h"
19
20
21

#include <stdlib.h>
#include <string.h>
22
#include <assert.h>
23

24
25
#include "ht.h"

26
/** All newly allocated smartlists have this capacity. */
27
#define SMARTLIST_DEFAULT_CAPACITY 16
28
29
30

/** Allocate and return an empty smartlist.
 */
31
smartlist_t *
32
33
smartlist_create(void)
{
34
35
36
37
38
39
40
41
42
43
  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.
 */
44
void
45
46
smartlist_free(smartlist_t *sl)
{
47
48
  if (!sl)
    return;
49
50
  tor_free(sl->list);
  tor_free(sl);
51
52
53
54
}

/** Remove all elements from the list.
 */
55
void
56
57
smartlist_clear(smartlist_t *sl)
{
58
59
60
  sl->num_used = 0;
}

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

/** Append element to the end of the list. */
void
smartlist_add(smartlist_t *sl, void *element)
{
  smartlist_ensure_capacity(sl, sl->num_used+1);
80
81
82
83
  sl->list[sl->num_used++] = element;
}

/** Append each element from S2 to the end of S1. */
84
void
85
smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
86
{
87
88
89
  int new_size = s1->num_used + s2->num_used;
  tor_assert(new_size >= s1->num_used); /* check for overflow. */
  smartlist_ensure_capacity(s1, new_size);
90
  memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
91
  s1->num_used = new_size;
92
93
}

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

111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/** 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;
  }
}

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

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

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

180
181
/** If <b>element</b> is equal to an element of <b>sl</b>, return that
 * element's index.  Otherwise, return -1. */
182
183
184
185
186
187
188
189
190
191
192
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;
}

193
194
195
196
197
198
199
200
201
202
203
204
205
206
/** 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;
}

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

218
219
220
221
222
223
224
225
226
227
228
229
230
231
/** 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;
}

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

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

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

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

/**
321
 * Split a string <b>str</b> along all occurrences of <b>sep</b>,
322
323
324
325
326
327
328
329
330
331
332
 * 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 <b>flags</b>&amp;SPLIT_STRIP_SPACE is true, strip spaces from each
 * split string.
 *
 * If max>0, divide the string into no more than <b>max</b> pieces. If
 * <b>sep</b> is NULL, split on any sequence of horizontal space.
333
 */
334
335
336
int
smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
                       int flags, int max)
337
338
339
340
341
342
343
344
345
346
{
  const char *cp, *end, *next;
  int n = 0;

  tor_assert(sl);
  tor_assert(str);

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

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

361
362
    tor_assert(end);

363
364
    if (!*end) {
      next = NULL;
365
    } else if (sep) {
366
      next = end+strlen(sep);
367
368
369
370
    } else {
      next = end+1;
      while (*next == '\t' || *next == ' ')
        ++next;
371
372
373
    }

    if (flags&SPLIT_SKIP_SPACE) {
374
      while (end > cp && TOR_ISSPACE(*(end-1)))
375
376
377
        --end;
    }
    if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
378
379
380
381
      char *string = tor_strndup(cp, end-cp);
      if (flags&SPLIT_STRIP_SPACE)
        tor_strstrip(string, " ");
      smartlist_add(sl, string);
382
383
384
385
386
387
388
389
390
391
392
393
394
      ++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>.
395
396
397
 * 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.
398
 */
399
400
401
char *
smartlist_join_strings(smartlist_t *sl, const char *join,
                       int terminate, size_t *len_out)
402
403
404
405
{
  return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
}

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

  tor_assert(sl);
  tor_assert(join);
421

Roger Dingledine's avatar
Roger Dingledine committed
422
423
  if (terminate)
    n = join_len;
424

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

  if (len_out)
    *len_out = dst-r;
447
448
449
  return r;
}

450
451
452
453
454
455
456
457
458
459
460
461
462
/** 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);
}

463
464
465
466
467
468
469
470
471
472
473
/** Given a smartlist <b>sl</b> sorted with the function <b>compare</b>,
 * return the most frequent member in the list.  Break ties in favor of
 * later elements.  If the list is empty, return NULL.
 */
void *
smartlist_get_most_frequent(const smartlist_t *sl,
                            int (*compare)(const void **a, const void **b))
{
  const void *most_frequent = NULL;
  int most_frequent_count = 0;

474
  const void *cur = NULL;
475
476
477
478
479
480
  int i, count=0;

  if (!sl->num_used)
    return NULL;
  for (i = 0; i < sl->num_used; ++i) {
    const void *item = sl->list[i];
481
    if (cur && 0 == compare(&cur, &item)) {
482
483
484
      ++count;
    } else {
      if (cur && count >= most_frequent_count) {
485
        most_frequent = cur;
486
487
        most_frequent_count = count;
      }
488
      cur = item;
489
490
491
492
      count = 1;
    }
  }
  if (cur && count >= most_frequent_count) {
493
    most_frequent = cur;
494
495
496
497
498
    most_frequent_count = count;
  }
  return (void*)most_frequent;
}

499
500
/** 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
501
 * free_fn on each duplicate.  Otherwise, just removes them.  Preserves order.
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
 */
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--);
    }
  }
}

519
/** Assuming the members of <b>sl</b> are in order, return a pointer to the
520
521
 * 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
522
523
524
525
526
527
 * 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))
{
528
  int found, idx;
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
  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;
573
574
}

575
/** Helper: compare two const char **s. */
576
static int
577
_compare_string_ptrs(const void **_a, const void **_b)
578
{
579
  return strcmp((const char*)*_a, (const char*)*_b);
580
581
}

582
583
/** Sort a smartlist <b>sl</b> containing strings into lexically ascending
 * order. */
584
585
586
587
588
589
void
smartlist_sort_strings(smartlist_t *sl)
{
  smartlist_sort(sl, _compare_string_ptrs);
}

590
591
592
593
594
595
596
/** Return the most frequent string in the sorted list <b>sl</b> */
char *
smartlist_get_most_frequent_string(smartlist_t *sl)
{
  return smartlist_get_most_frequent(sl, _compare_string_ptrs);
}

597
598
599
600
601
/** Remove duplicate strings from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_strings(smartlist_t *sl)
{
602
  smartlist_uniq(sl, _compare_string_ptrs, _tor_free);
603
604
}

605
606
607
608
/* 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]].
 */
609

610
611
612
613
614
615
616
617
618
619
620
621
/* 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. */
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
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;
    }
  }
}

653
/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order
Roger Dingledine's avatar
Roger Dingledine committed
654
 * is determined by <b>compare</b>. */
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
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;
    }
  }
}

676
677
678
/** 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. */
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
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;
}

694
695
/** Assert that the heap property is correctly maintained by the heap stored
 * in <b>sl</b>, where order is determined by <b>compare</b>. */
696
697
698
699
700
701
702
703
704
705
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);
  }
}

706
707
708
709
710
711
712
713
714
715
716
/** 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)
{
717
  smartlist_sort(sl, _compare_digests);
718
719
}

720
721
722
723
724
/** Remove duplicate digests from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_digests(smartlist_t *sl)
{
725
  smartlist_uniq(sl, _compare_digests, _tor_free);
726
727
}

728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
/** Helper: compare two DIGEST256_LEN digests. */
static int
_compare_digests256(const void **_a, const void **_b)
{
  return memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
}

/** Sort the list of DIGEST256_LEN-byte digests into ascending order. */
void
smartlist_sort_digests256(smartlist_t *sl)
{
  smartlist_sort(sl, _compare_digests256);
}

/** Return the most frequent member of the sorted list of DIGEST256_LEN
 * digests in <b>sl</b> */
char *
smartlist_get_most_frequent_digest256(smartlist_t *sl)
{
  return smartlist_get_most_frequent(sl, _compare_digests256);
}

/** Remove duplicate 256-bit digests from a sorted list, and free them with
 * tor_free().
 */
void
smartlist_uniq_digests256(smartlist_t *sl)
{
  smartlist_uniq(sl, _compare_digests256, _tor_free);
}

759
760
761
762
/** Helper: Declare an entry type and a map type to implement a mapping using
 * ht.h.  The map type will be called <b>maptype</b>.  The key part of each
 * entry is declared using the C declaration <b>keydecl</b>.  All functions
 * and types associated with the map get prefixed with <b>prefix</b> */
763
764
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
  typedef struct prefix ## entry_t {                      \
765
    HT_ENTRY(prefix ## entry_t) node;                     \
766
    void *val;                                            \
767
    keydecl;                                              \
768
769
  } prefix ## entry_t;                                    \
  struct maptype {                                        \
770
    HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
771
  }
772

773
774
DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
775

776
/** Helper: compare strmap_entry_t objects by key value. */
777
static INLINE int
778
strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
779
780
781
782
{
  return !strcmp(a->key, b->key);
}

Roger Dingledine's avatar
Roger Dingledine committed
783
/** Helper: return a hash value for a strmap_entry_t. */
784
static INLINE unsigned int
785
strmap_entry_hash(const strmap_entry_t *a)
786
{
787
  return ht_string_hash(a->key);
788
789
}

790
/** Helper: compare digestmap_entry_t objects by key value. */
791
static INLINE int
792
digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
793
{
794
  return !memcmp(a->key, b->key, DIGEST_LEN);
795
796
}

Roger Dingledine's avatar
Roger Dingledine committed
797
/** Helper: return a hash value for a digest_map_t. */
798
static INLINE unsigned int
799
digestmap_entry_hash(const digestmap_entry_t *a)
800
{
801
802
803
804
805
806
807
#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
808
809
}

810
HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
811
             strmap_entries_eq)
812
HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
813
            strmap_entries_eq, 0.6, malloc, realloc, free)
814

815
HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
816
             digestmap_entries_eq)
817
HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
818
            digestmap_entries_eq, 0.6, malloc, realloc, free)
819

820
/** Constructor to create a new empty map from strings to void*'s.
821
 */
822
823
strmap_t *
strmap_new(void)
824
825
826
{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
827
  HT_INIT(strmap_impl, &result->head);
828
829
830
  return result;
}

831
/** Constructor to create a new empty map from digests to void*'s.
832
833
834
835
836
837
 */
digestmap_t *
digestmap_new(void)
{
  digestmap_t *result;
  result = tor_malloc(sizeof(digestmap_t));
838
  HT_INIT(digestmap_impl, &result->head);
839
840
841
  return result;
}

842
843
844
/** 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.
 *
845
846
 * This function makes a copy of <b>key</b> if necessary, but not of
 * <b>val</b>.
847
 */
848
849
void *
strmap_set(strmap_t *map, const char *key, void *val)
850
851
852
853
854
855
856
857
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  search.key = (char*)key;
858
  resolve = HT_FIND(strmap_impl, &map->head, &search);
859
860
861
862
863
864
865
866
  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;
867
868
    tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
    HT_INSERT(strmap_impl, &map->head, resolve);
869
870
871
872
    return NULL;
  }
}

873
874
#define OPTIMIZED_DIGESTMAP_SET

875
/** Like strmap_set() above but for digestmaps. */
876
877
878
void *
digestmap_set(digestmap_t *map, const char *key, void *val)
{
879
#ifndef OPTIMIZED_DIGESTMAP_SET
880
  digestmap_entry_t *resolve;
881
#endif
882
883
884
885
886
887
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  memcpy(&search.key, key, DIGEST_LEN);
888
#ifndef OPTIMIZED_DIGESTMAP_SET
889
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
890
891
892
893
894
895
896
897
  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;
898
    HT_INSERT(digestmap_impl, &map->head, resolve);
899
900
    return NULL;
  }
901
#else
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
  /* 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;
         });
924
#endif
925
926
}

927
928
929
/** Return the current value associated with <b>key</b>, or NULL if no
 * value is set.
 */
930
void *
931
strmap_get(const strmap_t *map, const char *key)
932
933
934
935
936
937
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
938
  resolve = HT_FIND(strmap_impl, &map->head, &search);
939
940
941
942
943
944
945
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

946
/** Like strmap_get() above but for digestmaps. */
947
void *
948
digestmap_get(const digestmap_t *map, const char *key)
949
950
951
952
953
954
{
  digestmap_entry_t *resolve;
  digestmap_entry_t search;
  tor_assert(map);
  tor_assert(key);
  memcpy(&search.key, key, DIGEST_LEN);
955
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
956
957
958
959
960
961
962
  if (resolve) {
    return resolve->val;
  } else {
    return NULL;
  }
}

963
964
965
966
967
968
/** 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.
 */
969
970
void *
strmap_remove(strmap_t *map, const char *key)
971
972
973
974
975
976
977
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  search.key = (char*)key;
978
  resolve = HT_REMOVE(strmap_impl, &map->head, &search);
979
980
981
982
983
984
985
986
987
988
  if (resolve) {
    oldval = resolve->val;
    tor_free(resolve->key);
    tor_free(resolve);
    return oldval;
  } else {
    return NULL;
  }
}

989
/** Like strmap_remove() above but for digestmaps. */
990
991
992
993
994
995
996
997
998
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);
999
  resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
1000
  if (resolve) {