container.h 28.9 KB
Newer Older
1
2
/* Copyright (c) 2003-2004, Roger Dingledine
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
3
 * Copyright (c) 2007-2013, The Tor Project, Inc. */
4
5
/* See LICENSE for licensing information */

6
7
#ifndef TOR_CONTAINER_H
#define TOR_CONTAINER_H
8

Nick Mathewson's avatar
Nick Mathewson committed
9
#include "util.h"
10
#include "siphash.h"
11

12
13
14
/** A resizeable list of pointers, with associated helpful functionality.
 *
 * The members of this struct are exposed only so that macros and inlines can
Nick Mathewson's avatar
Nick Mathewson committed
15
 * use them; all access to smartlist internals should go through the functions
16
17
 * and macros defined here.
 **/
18
typedef struct smartlist_t {
19
  /** @{ */
20
21
22
23
24
25
26
  /** <b>list</b> has enough capacity to store exactly <b>capacity</b> elements
   * before it needs to be resized.  Only the first <b>num_used</b> (\<=
   * capacity) elements point to valid data.
   */
  void **list;
  int num_used;
  int capacity;
27
  /** @} */
28
} smartlist_t;
29

30
smartlist_t *smartlist_new(void);
31
32
33
34
void smartlist_free(smartlist_t *sl);
void smartlist_clear(smartlist_t *sl);
void smartlist_add(smartlist_t *sl, void *element);
void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2);
35
void smartlist_remove(smartlist_t *sl, const void *element);
36
37
void *smartlist_pop_last(smartlist_t *sl);
void smartlist_reverse(smartlist_t *sl);
38
void smartlist_string_remove(smartlist_t *sl, const char *element);
Nick Mathewson's avatar
Nick Mathewson committed
39
40
int smartlist_contains(const smartlist_t *sl, const void *element);
int smartlist_contains_string(const smartlist_t *sl, const char *element);
Sebastian Hahn's avatar
Sebastian Hahn committed
41
int smartlist_string_pos(const smartlist_t *, const char *elt);
Nick Mathewson's avatar
Nick Mathewson committed
42
43
int smartlist_contains_string_case(const smartlist_t *sl, const char *element);
int smartlist_contains_int_as_string(const smartlist_t *sl, int num);
Sebastian Hahn's avatar
Sebastian Hahn committed
44
int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2);
Nick Mathewson's avatar
Nick Mathewson committed
45
int smartlist_contains_digest(const smartlist_t *sl, const char *element);
46
int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2);
Sebastian Hahn's avatar
Sebastian Hahn committed
47
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2);
48
49
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2);
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2);
50

51
/* smartlist_choose() is defined in crypto.[ch] */
52
#ifdef DEBUG_SMARTLIST
53
54
/** Return the number of items in sl.
 */
Sebastian Hahn's avatar
Sebastian Hahn committed
55
static INLINE int smartlist_len(const smartlist_t *sl);
56
static INLINE int smartlist_len(const smartlist_t *sl) {
57
58
59
60
61
  tor_assert(sl);
  return (sl)->num_used;
}
/** Return the <b>idx</b>th element of sl.
 */
Sebastian Hahn's avatar
Sebastian Hahn committed
62
static INLINE void *smartlist_get(const smartlist_t *sl, int idx);
63
static INLINE void *smartlist_get(const smartlist_t *sl, int idx) {
64
65
  tor_assert(sl);
  tor_assert(idx>=0);
Peter Palfrader's avatar
Peter Palfrader committed
66
  tor_assert(sl->num_used > idx);
67
68
  return sl->list[idx];
}
69
static INLINE void smartlist_set(smartlist_t *sl, int idx, void *val) {
70
71
  tor_assert(sl);
  tor_assert(idx>=0);
Peter Palfrader's avatar
Peter Palfrader committed
72
  tor_assert(sl->num_used > idx);
73
74
  sl->list[idx] = val;
}
75
76
77
78
79
80
#else
#define smartlist_len(sl) ((sl)->num_used)
#define smartlist_get(sl, idx) ((sl)->list[idx])
#define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val))
#endif

81
82
/** Exchange the elements at indices <b>idx1</b> and <b>idx2</b> of the
 * smartlist <b>sl</b>. */
83
static INLINE void smartlist_swap(smartlist_t *sl, int idx1, int idx2)
84
85
86
87
88
89
90
91
{
  if (idx1 != idx2) {
    void *elt = smartlist_get(sl, idx1);
    smartlist_set(sl, idx1, smartlist_get(sl, idx2));
    smartlist_set(sl, idx2, elt);
  }
}

92
93
void smartlist_del(smartlist_t *sl, int idx);
void smartlist_del_keeporder(smartlist_t *sl, int idx);
94
void smartlist_insert(smartlist_t *sl, int idx, void *val);
95
96
void smartlist_sort(smartlist_t *sl,
                    int (*compare)(const void **a, const void **b));
97
98
void *smartlist_get_most_frequent(const smartlist_t *sl,
                    int (*compare)(const void **a, const void **b));
99
100
101
void smartlist_uniq(smartlist_t *sl,
                    int (*compare)(const void **a, const void **b),
                    void (*free_fn)(void *elt));
102

103
void smartlist_sort_strings(smartlist_t *sl);
104
void smartlist_sort_digests(smartlist_t *sl);
105
106
107
108
109
void smartlist_sort_digests256(smartlist_t *sl);

char *smartlist_get_most_frequent_string(smartlist_t *sl);
char *smartlist_get_most_frequent_digest256(smartlist_t *sl);

110
111
void smartlist_uniq_strings(smartlist_t *sl);
void smartlist_uniq_digests(smartlist_t *sl);
112
void smartlist_uniq_digests256(smartlist_t *sl);
113
void *smartlist_bsearch(smartlist_t *sl, const void *key,
Sebastian Hahn's avatar
Sebastian Hahn committed
114
                        int (*compare)(const void *key, const void **member));
115
116
int smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
                          int (*compare)(const void *key, const void **member),
117
                          int *found_out);
118

119
120
void smartlist_pqueue_add(smartlist_t *sl,
                          int (*compare)(const void *a, const void *b),
121
                          int idx_field_offset,
122
123
                          void *item);
void *smartlist_pqueue_pop(smartlist_t *sl,
124
125
126
127
128
129
                           int (*compare)(const void *a, const void *b),
                           int idx_field_offset);
void smartlist_pqueue_remove(smartlist_t *sl,
                             int (*compare)(const void *a, const void *b),
                             int idx_field_offset,
                             void *item);
130
void smartlist_pqueue_assert_ok(smartlist_t *sl,
131
132
                                int (*compare)(const void *a, const void *b),
                                int idx_field_offset);
133

134
135
#define SPLIT_SKIP_SPACE   0x01
#define SPLIT_IGNORE_BLANK 0x02
136
#define SPLIT_STRIP_SPACE  0x04
137
138
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
                           int flags, int max);
139
char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate,
140
                             size_t *len_out) ATTR_MALLOC;
141
char *smartlist_join_strings2(smartlist_t *sl, const char *join,
142
143
                              size_t join_len, int terminate, size_t *len_out)
  ATTR_MALLOC;
144

145
146
/** Iterate over the items in a smartlist <b>sl</b>, in order.  For each item,
 * assign it to a new local variable of type <b>type</b> named <b>var</b>, and
147
148
149
 * execute the statements inside the loop body.  Inside the loop, the loop
 * index can be accessed as <b>var</b>_sl_idx and the length of the list can
 * be accessed as <b>var</b>_sl_len.
150
151
152
153
 *
 * NOTE: Do not change the length of the list while the loop is in progress,
 * unless you adjust the _sl_len variable correspondingly.  See second example
 * below.
154
155
156
157
 *
 * Example use:
 * <pre>
 *   smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
158
 *   SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
159
160
 *     printf("%d: %s\n", cp_sl_idx, cp);
 *     tor_free(cp);
161
 *   } SMARTLIST_FOREACH_END(cp);
162
163
164
165
166
 *   smartlist_free(list);
 * </pre>
 *
 * Example use (advanced):
 * <pre>
167
 *   SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
168
169
 *     if (!strcmp(cp, "junk")) {
 *       tor_free(cp);
170
 *       SMARTLIST_DEL_CURRENT(list, cp);
171
 *     }
172
 *   } SMARTLIST_FOREACH_END(cp);
173
174
 * </pre>
 */
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
/* Note: these macros use token pasting, and reach into smartlist internals.
 * This can make them a little daunting. Here's the approximate unpacking of
 * the above examples, for entertainment value:
 *
 * <pre>
 * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
 * {
 *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
 *   char *cp;
 *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
 *     cp = smartlist_get(list, cp_sl_idx);
 *     printf("%d: %s\n", cp_sl_idx, cp);
 *     tor_free(cp);
 *   }
 * }
 * smartlist_free(list);
 * </pre>
 *
 * <pre>
 * {
 *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
 *   char *cp;
 *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
 *     cp = smartlist_get(list, cp_sl_idx);
 *     if (!strcmp(cp, "junk")) {
 *       tor_free(cp);
 *       smartlist_del(list, cp_sl_idx);
 *       --cp_sl_idx;
 *       --cp_sl_len;
 *     }
 *   }
 * }
 * </pre>
 */
209
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)  \
210
  STMT_BEGIN                                                    \
211
    int var ## _sl_idx, var ## _sl_len=(sl)->num_used;          \
212
    type var;                                                   \
213
    for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len;   \
214
         ++var ## _sl_idx) {                                    \
215
216
217
      var = (sl)->list[var ## _sl_idx];

#define SMARTLIST_FOREACH_END(var)              \
218
    var = NULL;                                 \
219
220
  } STMT_END

221
222
223
224
225
226
227
228
/**
 * An alias for SMARTLIST_FOREACH_BEGIN and SMARTLIST_FOREACH_END, using
 * <b>cmd</b> as the loop body.  This wrapper is here for convenience with
 * very short loops.
 *
 * By convention, we do not use this for loops which nest, or for loops over
 * 10 lines or so.  Use SMARTLIST_FOREACH_{BEGIN,END} for those.
 */
229
230
231
232
#define SMARTLIST_FOREACH(sl, type, var, cmd)                   \
  SMARTLIST_FOREACH_BEGIN(sl,type,var) {                        \
    cmd;                                                        \
  } SMARTLIST_FOREACH_END(var)
233

234
/** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
235
 * with the variable <b>var</b>, remove the current element in a way that
236
237
 * won't confuse the loop. */
#define SMARTLIST_DEL_CURRENT(sl, var)          \
238
  STMT_BEGIN                                    \
239
240
241
    smartlist_del(sl, var ## _sl_idx);          \
    --var ## _sl_idx;                           \
    --var ## _sl_len;                           \
242
  STMT_END
243

244
245
246
247
248
249
250
251
252
/** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed
 * with the variable <b>var</b>, replace the current element with <b>val</b>.
 * Does not deallocate the current value of <b>var</b>.
 */
#define SMARTLIST_REPLACE_CURRENT(sl, var, val) \
  STMT_BEGIN                                    \
    smartlist_set(sl, var ## _sl_idx, val);     \
  STMT_END

253
/* Helper: Given two lists of items, possibly of different types, such that
Nick Mathewson's avatar
Nick Mathewson committed
254
 * both lists are sorted on some common field (as determined by a comparison
255
256
257
258
259
260
261
262
263
264
265
 * expression <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no
 * duplicates on the common field, loop through the lists in lockstep, and
 * execute <b>unmatched_var2</b> on items in var2 that do not appear in
 * var1.
 *
 * WARNING: It isn't safe to add remove elements from either list while the
 * loop is in progress.
 *
 * Example use:
 *  SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs,
 *                     routerinfo_list, routerinfo_t *, ri,
266
 *                    tor_memcmp(rs->identity_digest, ri->identity_digest, 20),
267
268
269
270
271
272
273
274
275
276
277
278
279
280
 *                     log_info(LD_GENERAL,"No match for %s", ri->nickname)) {
 *    log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs);
 * } SMARTLIST_FOREACH_JOIN_END(rs, ri);
 **/
/* The example above unpacks (approximately) to:
 *  int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list);
 *  int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list);
 *  int rs_ri_cmp;
 *  routerstatus_t *rs;
 *  routerinfo_t *ri;
 *  for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) {
 *    ri = smartlist_get(routerinfo_list, ri_sl_idx);
 *    while (rs_sl_idx < rs_sl_len) {
 *      rs = smartlist_get(routerstatus_list, rs_sl_idx);
281
 *      rs_ri_cmp = tor_memcmp(rs->identity_digest, ri->identity_digest, 20);
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
 *      if (rs_ri_cmp > 0) {
 *        break;
 *      } else if (rs_ri_cmp == 0) {
 *        goto matched_ri;
 *      } else {
 *        ++rs_sl_idx;
 *      }
 *    }
 *    log_info(LD_GENERAL,"No match for %s", ri->nickname);
 *    continue;
 *   matched_ri: {
 *    log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs);
 *    }
 *  }
 */
#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2,      \
                                cmpexpr, unmatched_var2)                \
  STMT_BEGIN                                                            \
  int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used;             \
  int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used;             \
  int var1 ## _ ## var2 ## _cmp;                                        \
  type1 var1;                                                           \
  type2 var2;                                                           \
  for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) {              \
    var2 = (sl2)->list[var2##_sl_idx];                                  \
    while (var1##_sl_idx < var1##_sl_len) {                             \
      var1 = (sl1)->list[var1##_sl_idx];                                \
      var1##_##var2##_cmp = (cmpexpr);                                  \
      if (var1##_##var2##_cmp > 0) {                                    \
        break;                                                          \
      } else if (var1##_##var2##_cmp == 0) {                            \
        goto matched_##var2;                                            \
      } else {                                                          \
        ++var1##_sl_idx;                                                \
      }                                                                 \
    }                                                                   \
    /* Ran out of v1, or no match for var2. */                          \
    unmatched_var2;                                                     \
    continue;                                                           \
    matched_##var2: ;                                                   \

#define SMARTLIST_FOREACH_JOIN_END(var1, var2)  \
  }                                             \
  STMT_END

327
328
#define DECLARE_MAP_FNS(maptype, keytype, prefix)                       \
  typedef struct maptype maptype;                                       \
329
  typedef struct prefix##entry_t *prefix##iter_t;                       \
330
331
  maptype* prefix##new(void);                                           \
  void* prefix##set(maptype *map, keytype key, void *val);              \
332
  void* prefix##get(const maptype *map, keytype key);                   \
333
334
  void* prefix##remove(maptype *map, keytype key);                      \
  void prefix##free(maptype *map, void (*free_val)(void*));             \
335
336
  int prefix##isempty(const maptype *map);                              \
  int prefix##size(const maptype *map);                                 \
337
338
339
340
  prefix##iter_t *prefix##iter_init(maptype *map);                      \
  prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \
  prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \
  void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \
341
  int prefix##iter_done(prefix##iter_t *iter);                          \
342
  void prefix##assert_ok(const maptype *map)
343

344
/* Map from const char * to void *. Implemented with a hash table. */
345
DECLARE_MAP_FNS(strmap_t, const char *, strmap_);
346
/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */
347
DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_);
348

349
#undef DECLARE_MAP_FNS
350

351
/** Iterates over the key-value pairs in a map <b>map</b> in order.
352
353
354
355
356
357
358
359
360
 * <b>prefix</b> is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_).
 * The map's keys and values are of type keytype and valtype respectively;
 * each iteration assigns them to keyvar and valvar.
 *
 * Example use:
 *   MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
 *     // use k and r
 *   } MAP_FOREACH_END.
 */
361
362
363
364
365
366
367
368
369
370
371
372
373
374
/* Unpacks to, approximately:
 * {
 *   digestmap_iter_t *k_iter;
 *   for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
 *        k_iter = digestmap_iter_next(m, k_iter)) {
 *     const char *k;
 *     void *r_voidp;
 *     routerinfo_t *r;
 *     digestmap_iter_get(k_iter, &k, &r_voidp);
 *     r = r_voidp;
 *     // use k and r
 *   }
 * }
 */
375
376
#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar)      \
  STMT_BEGIN                                                            \
377
378
379
380
    prefix##iter_t *keyvar##_iter;                                      \
    for (keyvar##_iter = prefix##iter_init(map);                        \
         !prefix##iter_done(keyvar##_iter);                             \
         keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) {       \
381
382
383
      keytype keyvar;                                                   \
      void *valvar##_voidp;                                             \
      valtype valvar;                                                   \
384
      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
385
386
      valvar = valvar##_voidp;

387
388
389
390
391
392
393
394
395
/** As MAP_FOREACH, except allows members to be removed from the map
 * during the iteration via MAP_DEL_CURRENT.  Example use:
 *
 * Example use:
 *   MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
 *      if (is_very_old(r))
 *       MAP_DEL_CURRENT(k);
 *   } MAP_FOREACH_END.
 **/
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
/* Unpacks to, approximately:
 * {
 *   digestmap_iter_t *k_iter;
 *   int k_del=0;
 *   for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter);
 *        k_iter = k_del ? digestmap_iter_next(m, k_iter)
 *                       : digestmap_iter_next_rmv(m, k_iter)) {
 *     const char *k;
 *     void *r_voidp;
 *     routerinfo_t *r;
 *     k_del=0;
 *     digestmap_iter_get(k_iter, &k, &r_voidp);
 *     r = r_voidp;
 *     if (is_very_old(r)) {
 *       k_del = 1;
 *     }
 *   }
 * }
 */
415
416
#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \
  STMT_BEGIN                                                            \
417
    prefix##iter_t *keyvar##_iter;                                      \
418
    int keyvar##_del=0;                                                 \
419
420
421
422
423
    for (keyvar##_iter = prefix##iter_init(map);                        \
         !prefix##iter_done(keyvar##_iter);                             \
         keyvar##_iter = keyvar##_del ?                                 \
           prefix##iter_next_rmv(map, keyvar##_iter) :                  \
           prefix##iter_next(map, keyvar##_iter)) {                     \
424
425
426
427
      keytype keyvar;                                                   \
      void *valvar##_voidp;                                             \
      valtype valvar;                                                   \
      keyvar##_del=0;                                                   \
428
      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
429
430
      valvar = valvar##_voidp;

431
432
/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon
 * member of the map.  */
433
434
435
436
437
#define MAP_DEL_CURRENT(keyvar)                   \
  STMT_BEGIN                                      \
    keyvar##_del = 1;                             \
  STMT_END

438
/** Used to end a MAP_FOREACH() block. */
439
440
#define MAP_FOREACH_END } STMT_END ;

441
442
443
444
445
446
/** As MAP_FOREACH, but does not require declaration of prefix or keytype.
 * Example use:
 *   DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) {
 *     // use k and r
 *   } DIGESTMAP_FOREACH_END.
 */
447
448
#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar)                 \
  MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)
449
450
451
452
453
454
455
456
457

/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or
 * keytype.
 * Example use:
 *   DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) {
 *      if (is_very_old(r))
 *       MAP_DEL_CURRENT(k);
 *   } DIGESTMAP_FOREACH_END.
 */
458
459
#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)          \
  MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)
460
/** Used to end a DIGESTMAP_FOREACH() block. */
461
462
#define DIGESTMAP_FOREACH_END MAP_FOREACH_END

463
464
465
466
467
468
#define STRMAP_FOREACH(map, keyvar, valtype, valvar)                 \
  MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar)
#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)          \
  MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar)
#define STRMAP_FOREACH_END MAP_FOREACH_END

469
void* strmap_set_lc(strmap_t *map, const char *key, void *val);
470
void* strmap_get_lc(const strmap_t *map, const char *key);
471
472
void* strmap_remove_lc(strmap_t *map, const char *key);

473
474
475
476
477
478
479
#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype)           \
  typedef struct maptype maptype;                                       \
  typedef struct prefix##iter_t prefix##iter_t;                         \
  static INLINE maptype* prefix##new(void)                              \
  {                                                                     \
    return (maptype*)digestmap_new();                                   \
  }                                                                     \
480
481
482
483
  static INLINE digestmap_t* prefix##to_digestmap(maptype *map)         \
  {                                                                     \
    return (digestmap_t*)map;                                           \
  }                                                                     \
484
485
486
487
488
489
490
491
492
493
494
  static INLINE valtype* prefix##get(maptype *map, const char *key)     \
  {                                                                     \
    return (valtype*)digestmap_get((digestmap_t*)map, key);             \
  }                                                                     \
  static INLINE valtype* prefix##set(maptype *map, const char *key,     \
                                     valtype *val)                      \
  {                                                                     \
    return (valtype*)digestmap_set((digestmap_t*)map, key, val);        \
  }                                                                     \
  static INLINE valtype* prefix##remove(maptype *map, const char *key)  \
  {                                                                     \
495
    return (valtype*)digestmap_remove((digestmap_t*)map, key);          \
496
497
498
499
500
501
502
503
504
505
506
  }                                                                     \
  static INLINE void prefix##free(maptype *map, void (*free_val)(void*)) \
  {                                                                     \
    digestmap_free((digestmap_t*)map, free_val);                        \
  }                                                                     \
  static INLINE int prefix##isempty(maptype *map)                       \
  {                                                                     \
    return digestmap_isempty((digestmap_t*)map);                        \
  }                                                                     \
  static INLINE int prefix##size(maptype *map)                          \
  {                                                                     \
507
    return digestmap_size((digestmap_t*)map);                           \
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
  }                                                                     \
  static INLINE prefix##iter_t *prefix##iter_init(maptype *map)         \
  {                                                                     \
    return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map);    \
  }                                                                     \
  static INLINE prefix##iter_t *prefix##iter_next(maptype *map,         \
                                                  prefix##iter_t *iter) \
  {                                                                     \
    return (prefix##iter_t*) digestmap_iter_next(                       \
                       (digestmap_t*)map, (digestmap_iter_t*)iter);     \
  }                                                                     \
  static INLINE prefix##iter_t *prefix##iter_next_rmv(maptype *map,     \
                                                  prefix##iter_t *iter) \
  {                                                                     \
    return (prefix##iter_t*) digestmap_iter_next_rmv(                   \
                       (digestmap_t*)map, (digestmap_iter_t*)iter);     \
  }                                                                     \
  static INLINE void prefix##iter_get(prefix##iter_t *iter,             \
                                      const char **keyp,                \
                                      valtype **valp)                   \
  {                                                                     \
    void *v;                                                            \
    digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v);             \
    *valp = v;                                                          \
  }                                                                     \
  static INLINE int prefix##iter_done(prefix##iter_t *iter)             \
  {                                                                     \
    return digestmap_iter_done((digestmap_iter_t*)iter);                \
  }

538
539
540
541
542
#if SIZEOF_INT == 4
#define BITARRAY_SHIFT 5
#elif SIZEOF_INT == 8
#define BITARRAY_SHIFT 6
#else
543
#error "int is neither 4 nor 8 bytes. I can't deal with that."
544
#endif
545
#define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1)
546

547
/** A random-access array of one-bit-wide elements. */
548
549
550
typedef unsigned int bitarray_t;
/** Create a new bit array that can hold <b>n_bits</b> bits. */
static INLINE bitarray_t *
551
bitarray_init_zero(unsigned int n_bits)
552
{
553
554
  /* round up to the next int. */
  size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
555
556
  return tor_malloc_zero(sz*sizeof(unsigned int));
}
557
558
559
/** Expand <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>,
 * clearing all new bits.  Returns a possibly changed pointer to the
 * bitarray. */
560
static INLINE bitarray_t *
561
562
bitarray_expand(bitarray_t *ba,
                unsigned int n_bits_old, unsigned int n_bits_new)
563
{
564
565
  size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
  size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
566
567
568
  char *ptr;
  if (sz_new <= sz_old)
    return ba;
569
570
571
  ptr = tor_realloc(ba, sz_new*sizeof(unsigned int));
  /* This memset does nothing to the older excess bytes.  But they were
   * already set to 0 by bitarry_init_zero. */
572
573
  memset(ptr+sz_old*sizeof(unsigned int), 0,
         (sz_new-sz_old)*sizeof(unsigned int));
574
575
  return (bitarray_t*) ptr;
}
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
/** Free the bit array <b>ba</b>. */
static INLINE void
bitarray_free(bitarray_t *ba)
{
  tor_free(ba);
}
/** Set the <b>bit</b>th bit in <b>b</b> to 1. */
static INLINE void
bitarray_set(bitarray_t *b, int bit)
{
  b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK));
}
/** Set the <b>bit</b>th bit in <b>b</b> to 0. */
static INLINE void
bitarray_clear(bitarray_t *b, int bit)
{
  b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK));
}
/** Return true iff <b>bit</b>th bit in <b>b</b> is nonzero.  NOTE: does
 * not necessarily return 1 on true. */
static INLINE unsigned int
bitarray_is_set(bitarray_t *b, int bit)
{
  return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
}

602
603
/** A set of digests, implemented as a Bloom filter. */
typedef struct {
604
  int mask; /**< One less than the number of bits in <b>ba</b>; always one less
605
             * than a power of two. */
606
  bitarray_t *ba; /**< A bit array to implement the Bloom filter. */
607
608
609
610
611
612
613
} digestset_t;

#define BIT(n) ((n) & set->mask)
/** Add the digest <b>digest</b> to <b>set</b>. */
static INLINE void
digestset_add(digestset_t *set, const char *digest)
{
614
615
616
617
618
  const uint64_t x = siphash24g(digest, 20);
  const uint32_t d1 = (uint32_t) x;
  const uint32_t d2 = (uint32_t)( (x>>16) + x);
  const uint32_t d3 = (uint32_t)( (x>>32) + x);
  const uint32_t d4 = (uint32_t)( (x>>48) + x);
619
620
621
622
623
624
625
626
627
  bitarray_set(set->ba, BIT(d1));
  bitarray_set(set->ba, BIT(d2));
  bitarray_set(set->ba, BIT(d3));
  bitarray_set(set->ba, BIT(d4));
}

/** If <b>digest</b> is in <b>set</b>, return nonzero.  Otherwise,
 * <em>probably</em> return zero. */
static INLINE int
Nick Mathewson's avatar
Nick Mathewson committed
628
digestset_contains(const digestset_t *set, const char *digest)
629
{
630
631
632
633
634
  const uint64_t x = siphash24g(digest, 20);
  const uint32_t d1 = (uint32_t) x;
  const uint32_t d2 = (uint32_t)( (x>>16) + x);
  const uint32_t d3 = (uint32_t)( (x>>32) + x);
  const uint32_t d4 = (uint32_t)( (x>>48) + x);
635
636
637
638
639
640
641
642
643
644
  return bitarray_is_set(set->ba, BIT(d1)) &&
         bitarray_is_set(set->ba, BIT(d2)) &&
         bitarray_is_set(set->ba, BIT(d3)) &&
         bitarray_is_set(set->ba, BIT(d4));
}
#undef BIT

digestset_t *digestset_new(int max_elements);
void digestset_free(digestset_t* set);

645
646
647
648
649
650
651
/* These functions, given an <b>array</b> of <b>n_elements</b>, return the
 * <b>nth</b> lowest element. <b>nth</b>=0 gives the lowest element;
 * <b>n_elements</b>-1 gives the highest; and (<b>n_elements</b>-1) / 2 gives
 * the median.  As a side effect, the elements of <b>array</b> are sorted. */
int find_nth_int(int *array, int n_elements, int nth);
time_t find_nth_time(time_t *array, int n_elements, int nth);
double find_nth_double(double *array, int n_elements, int nth);
652
int32_t find_nth_int32(int32_t *array, int n_elements, int nth);
653
uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth);
654
long find_nth_long(long *array, int n_elements, int nth);
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
static INLINE int
median_int(int *array, int n_elements)
{
  return find_nth_int(array, n_elements, (n_elements-1)/2);
}
static INLINE time_t
median_time(time_t *array, int n_elements)
{
  return find_nth_time(array, n_elements, (n_elements-1)/2);
}
static INLINE double
median_double(double *array, int n_elements)
{
  return find_nth_double(array, n_elements, (n_elements-1)/2);
}
static INLINE uint32_t
median_uint32(uint32_t *array, int n_elements)
{
  return find_nth_uint32(array, n_elements, (n_elements-1)/2);
}
675
676
677
678
679
static INLINE int32_t
median_int32(int32_t *array, int n_elements)
{
  return find_nth_int32(array, n_elements, (n_elements-1)/2);
}
680

681
#endif
682