container.c 38.3 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
/* 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]].
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
 *
 * For us to remove items other than the topmost item, each item must store
 * its own index within the heap.  When calling the pqueue functions, tell
 * them about the offset of the field that stores the index within the item.
 *
 * Example:
 *
 *   typedef struct timer_t {
 *     struct timeval tv;
 *     int heap_index;
 *   } timer_t;
 *
 *   static int compare(const void *p1, const void *p2) {
 *     const timer_t *t1 = p1, *t2 = p2;
 *     if (t1->tv.tv_sec < t2->tv.tv_sec) {
 *        return -1;
 *     } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
 *        return 1;
 *     } else {
 *        return t1->tv.tv_usec - t2->tv_usec;
 *     }
 *   }
 *
 *   void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
 *      smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index),
 *         timer);
 *   }
 *
 *   void timer_heap_pop(smartlist_t *heap) {
 *      return smartlist_pqueue_pop(heap, compare,
 *         STRUCT_OFFSET(timer_t, heap_index));
 *   }
640
 */
641

642
643
644
645
646
647
648
649
650
/* 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 )

651
652
653
654
655
656
657
658
659
#define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))

#define UPDATE_IDX(i)  do {                            \
    void *updated = sl->list[i];                       \
    *IDXP(updated) = i;                                \
  } while (0)

#define IDX_OF_ITEM(p) (*IDXP(p))

660
661
662
/** 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. */
663
664
665
static INLINE void
smartlist_heapify(smartlist_t *sl,
                  int (*compare)(const void *a, const void *b),
666
                  int idx_field_offset,
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
                  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;
689
690
      UPDATE_IDX(idx);
      UPDATE_IDX(best_idx);
691
692
693
694
695
696

      idx = best_idx;
    }
  }
}

697
698
699
700
701
/** Insert <b>item</b> into the heap stored in <b>sl</b>, where order is
 * determined by <b>compare</b> and the offset of the item in the heap is
 * stored in an int-typed field at position <b>idx_field_offset</b> within
 * item.
 */
702
703
704
void
smartlist_pqueue_add(smartlist_t *sl,
                     int (*compare)(const void *a, const void *b),
705
                     int idx_field_offset,
706
707
708
709
                     void *item)
{
  int idx;
  smartlist_add(sl,item);
710
  UPDATE_IDX(sl->num_used-1);
711
712
713
714
715
716
717

  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;
718
719
      UPDATE_IDX(parent);
      UPDATE_IDX(idx);
720
721
722
723
724
725
726
      idx = parent;
    } else {
      return;
    }
  }
}

727
/** Remove and return the top-priority item from the heap stored in <b>sl</b>,
728
729
730
 * where order is determined by <b>compare</b> and the item's position in is
 * stored at position <b>idx_field_offset</b> within the item.  <b>sl</b> must
 * not be empty. */
731
732
void *
smartlist_pqueue_pop(smartlist_t *sl,
733
734
                     int (*compare)(const void *a, const void *b),
                     int idx_field_offset)
735
736
737
738
739
{
  void *top;
  tor_assert(sl->num_used);

  top = sl->list[0];
740
  *IDXP(top)=-1;
741
742
  if (--sl->num_used) {
    sl->list[0] = sl->list[sl->num_used];
743
744
    UPDATE_IDX(0);
    smartlist_heapify(sl, compare, idx_field_offset, 0);
745
746
747
748
  }
  return top;
}

749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
/** Remove the item <b>item</b> from the heap stored in <b>sl</b>,
 * where order is determined by <b>compare</b> and the item's position in is
 * stored at position <b>idx_field_offset</b> within the item.  <b>sl</b> must
 * not be empty. */
void
smartlist_pqueue_remove(smartlist_t *sl,
                        int (*compare)(const void *a, const void *b),
                        int idx_field_offset,
                        void *item)
{
  int idx = IDX_OF_ITEM(item);
  tor_assert(idx >= 0);
  tor_assert(sl->list[idx] == item);
  --sl->num_used;
  *IDXP(item) = -1;
  if (idx == sl->num_used) {
    return;
  } else {
    sl->list[idx] = sl->list[sl->num_used];
    UPDATE_IDX(idx);
    smartlist_heapify(sl, compare, idx_field_offset, idx);
  }
}

773
774
/** Assert that the heap property is correctly maintained by the heap stored
 * in <b>sl</b>, where order is determined by <b>compare</b>. */
775
776
void
smartlist_pqueue_assert_ok(smartlist_t *sl,
777
778
                           int (*compare)(const void *a, const void *b),
                           int idx_field_offset)
779
780
{
  int i;
781
782
783
784
  for (i = sl->num_used - 1; i >= 0; --i) {
    if (i>0)
      tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
    tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
785
786
787
  }
}

788
789
790
791
792
793
794
795
796
797
798
/** 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)
{
799
  smartlist_sort(sl, _compare_digests);
800
801
}

802
803
804
805
806
/** Remove duplicate digests from a sorted list, and free them with tor_free().
 */
void
smartlist_uniq_digests(smartlist_t *sl)
{
807
  smartlist_uniq(sl, _compare_digests, _tor_free);
808
809
}

810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
/** 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);
}

841
842
843
844
/** 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> */
845
846
#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
  typedef struct prefix ## entry_t {                      \
847
    HT_ENTRY(prefix ## entry_t) node;                     \
848
    void *val;                                            \
849
    keydecl;                                              \
850
851
  } prefix ## entry_t;                                    \
  struct maptype {                                        \
852
    HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
853
  }
854

855
856
DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
857

858
/** Helper: compare strmap_entry_t objects by key value. */
859
static INLINE int
860
strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
861
862
863
864
{
  return !strcmp(a->key, b->key);
}

Roger Dingledine's avatar
Roger Dingledine committed
865
/** Helper: return a hash value for a strmap_entry_t. */
866
static INLINE unsigned int
867
strmap_entry_hash(const strmap_entry_t *a)
868
{
869
  return ht_string_hash(a->key);
870
871
}

872
/** Helper: compare digestmap_entry_t objects by key value. */
873
static INLINE int
874
digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
875
{
876
  return !memcmp(a->key, b->key, DIGEST_LEN);
877
878
}

Roger Dingledine's avatar
Roger Dingledine committed
879
/** Helper: return a hash value for a digest_map_t. */
880
static INLINE unsigned int
881
digestmap_entry_hash(const digestmap_entry_t *a)
882
{
883
884
885
886
887
888
889
#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
890
891
}

892
HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
893
             strmap_entries_eq)
894
HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
895
            strmap_entries_eq, 0.6, malloc, realloc, free)
896

897
HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
898
             digestmap_entries_eq)
899
HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
900
            digestmap_entries_eq, 0.6, malloc, realloc, free)
901

902
/** Constructor to create a new empty map from strings to void*'s.
903
 */
904
905
strmap_t *
strmap_new(void)
906
907
908
{
  strmap_t *result;
  result = tor_malloc(sizeof(strmap_t));
909
  HT_INIT(strmap_impl, &result->head);
910
911
912
  return result;
}

913
/** Constructor to create a new empty map from digests to void*'s.
914
915
916
917
918
919
 */
digestmap_t *
digestmap_new(void)
{
  digestmap_t *result;
  result = tor_malloc(sizeof(digestmap_t));
920
  HT_INIT(digestmap_impl, &result->head);
921
922
923
  return result;
}

924
925
926
/** 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.
 *
927
928
 * This function makes a copy of <b>key</b> if necessary, but not of
 * <b>val</b>.
929
 */
930
931
void *
strmap_set(strmap_t *map, const char *key, void *val)
932
933
934
935
936
937
938
939
{
  strmap_entry_t *resolve;
  strmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  search.key = (char*)key;
940
  resolve = HT_FIND(strmap_impl, &map->head, &search);
941
942
943
944
945
946
947
948
  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;
949
950
    tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
    HT_INSERT(strmap_impl, &map->head, resolve);
951
952
953
954
    return NULL;
  }
}

955
956
#define OPTIMIZED_DIGESTMAP_SET

957
/** Like strmap_set() above but for digestmaps. */
958
959
960
void *
digestmap_set(digestmap_t *map, const char *key, void *val)
{
961
#ifndef OPTIMIZED_DIGESTMAP_SET
962
  digestmap_entry_t *resolve;
963
#endif
964
965
966
967
968
969
  digestmap_entry_t search;
  void *oldval;
  tor_assert(map);
  tor_assert(key);
  tor_assert(val);
  memcpy(&search.key, key, DIGEST_LEN);
970
#ifndef OPTIMIZED_DIGESTMAP_SET
971
  resolve = HT_FIND(digestmap_impl, &map->head, &search);
972
973
974
975
976
977
978
979
  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;
980
    HT_INSERT(digestmap_impl, &map->head, resolve);
981
982
    return NULL;
  }
983
#else
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
  /* 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));