container.h 28.5 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
#ifndef _TOR_CONTAINER_H
#define _TOR_CONTAINER_H
8

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

11
12
13
/** 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
14
 * use them; all access to smartlist internals should go through the functions
15
16
 * and macros defined here.
 **/
17
typedef struct smartlist_t {
18
19
20
21
22
23
24
  /** <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;
25
} smartlist_t;
26
27
28
29
30
31

smartlist_t *smartlist_create(void);
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);
32
void smartlist_remove(smartlist_t *sl, const void *element);
33
34
void *smartlist_pop_last(smartlist_t *sl);
void smartlist_reverse(smartlist_t *sl);
35
void smartlist_string_remove(smartlist_t *sl, const char *element);
36
int smartlist_isin(const smartlist_t *sl, const void *element) ATTR_PURE;
37
38
int smartlist_string_isin(const smartlist_t *sl, const char *element)
  ATTR_PURE;
39
int smartlist_string_pos(const smartlist_t *, const char *elt) ATTR_PURE;
40
41
int smartlist_string_isin_case(const smartlist_t *sl, const char *element)
  ATTR_PURE;
42
int smartlist_string_num_isin(const smartlist_t *sl, int num) ATTR_PURE;
43
44
int smartlist_digest_isin(const smartlist_t *sl, const char *element)
  ATTR_PURE;
45
46
int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
  ATTR_PURE;
47
48
void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2);
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2);
49

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

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

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

102
void smartlist_sort_strings(smartlist_t *sl);
103
void smartlist_sort_digests(smartlist_t *sl);
104
105
106
107
108
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);

109
110
void smartlist_uniq_strings(smartlist_t *sl);
void smartlist_uniq_digests(smartlist_t *sl);
111
void smartlist_uniq_digests256(smartlist_t *sl);
112
void *smartlist_bsearch(smartlist_t *sl, const void *key,
113
                        int (*compare)(const void *key, const void **member))
114
  ATTR_PURE;
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
147
/** 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
 * execute the statement <b>cmd</b>.  Inside the loop, the loop index can
148
149
150
151
152
153
 * be accessed as <b>var</b>_sl_idx and the length of the list can be accessed
 * as <b>var</b>_sl_len.
 *
 * 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
158
159
160
161
162
 *
 * Example use:
 * <pre>
 *   smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
 *   SMARTLIST_FOREACH(list, char *, cp,
 *   {
 *     printf("%d: %s\n", cp_sl_idx, cp);
 *     tor_free(cp);
 *   });
163
164
165
166
167
168
169
170
171
 *   smartlist_free(list);
 * </pre>
 *
 * Example use (advanced):
 * <pre>
 *   SMARTLIST_FOREACH(list, char *, cp,
 *   {
 *     if (!strcmp(cp, "junk")) {
 *       tor_free(cp);
172
 *       SMARTLIST_DEL_CURRENT(list, cp);
173
174
 *     }
 *   });
175
176
 * </pre>
 */
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
209
210
/* 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>
 */
211
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)  \
212
  STMT_BEGIN                                                    \
213
    int var ## _sl_idx, var ## _sl_len=(sl)->num_used;          \
214
    type var;                                                   \
215
    for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len;   \
216
         ++var ## _sl_idx) {                                    \
217
218
219
      var = (sl)->list[var ## _sl_idx];

#define SMARTLIST_FOREACH_END(var)              \
220
    var = NULL;                                 \
221
222
223
224
225
226
  } STMT_END

#define SMARTLIST_FOREACH(sl, type, var, cmd)                   \
  SMARTLIST_FOREACH_BEGIN(sl,type,var) {                        \
    cmd;                                                        \
  } SMARTLIST_FOREACH_END(var)
227

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

238
239
240
241
242
243
244
245
246
/** 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

247
/* Helper: Given two lists of items, possibly of different types, such that
Nick Mathewson's avatar
Nick Mathewson committed
248
 * both lists are sorted on some common field (as determined by a comparison
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
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
 * 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,
 *                     memcmp(rs->identity_digest, ri->identity_digest, 20),
 *                     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);
 *      rs_ri_cmp = memcmp(rs->identity_digest, ri->identity_digest, 20);
 *      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

321
322
#define DECLARE_MAP_FNS(maptype, keytype, prefix)                       \
  typedef struct maptype maptype;                                       \
323
  typedef struct prefix##entry_t *prefix##iter_t;                       \
324
325
  maptype* prefix##new(void);                                           \
  void* prefix##set(maptype *map, keytype key, void *val);              \
326
  void* prefix##get(const maptype *map, keytype key);                   \
327
328
  void* prefix##remove(maptype *map, keytype key);                      \
  void prefix##free(maptype *map, void (*free_val)(void*));             \
329
330
  int prefix##isempty(const maptype *map);                              \
  int prefix##size(const maptype *map);                                 \
331
332
333
334
  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); \
335
  int prefix##iter_done(prefix##iter_t *iter);                          \
336
  void prefix##assert_ok(const maptype *map)
337

338
/* Map from const char * to void *. Implemented with a hash table. */
339
DECLARE_MAP_FNS(strmap_t, const char *, strmap_);
340
/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */
341
DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_);
342

343
#undef DECLARE_MAP_FNS
344

345
/** Iterates over the key-value pairs in a map <b>map</b> in order.
346
347
348
349
350
351
352
353
354
 * <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.
 */
355
356
357
358
359
360
361
362
363
364
365
366
367
368
/* 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
 *   }
 * }
 */
369
370
#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar)      \
  STMT_BEGIN                                                            \
371
372
373
374
    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)) {       \
375
376
377
      keytype keyvar;                                                   \
      void *valvar##_voidp;                                             \
      valtype valvar;                                                   \
378
      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
379
380
      valvar = valvar##_voidp;

381
382
383
384
385
386
387
388
389
/** 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.
 **/
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
/* 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;
 *     }
 *   }
 * }
 */
409
410
#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \
  STMT_BEGIN                                                            \
411
    prefix##iter_t *keyvar##_iter;                                      \
412
    int keyvar##_del=0;                                                 \
413
414
415
416
417
    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)) {                     \
418
419
420
421
      keytype keyvar;                                                   \
      void *valvar##_voidp;                                             \
      valtype valvar;                                                   \
      keyvar##_del=0;                                                   \
422
      prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp);        \
423
424
      valvar = valvar##_voidp;

425
426
/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon
 * member of the map.  */
427
428
429
430
431
#define MAP_DEL_CURRENT(keyvar)                   \
  STMT_BEGIN                                      \
    keyvar##_del = 1;                             \
  STMT_END

432
/** Used to end a MAP_FOREACH() block. */
433
434
#define MAP_FOREACH_END } STMT_END ;

435
436
437
438
439
440
/** 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.
 */
441
442
#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar)                 \
  MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)
443
444
445
446
447
448
449
450
451

/** 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.
 */
452
453
#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar)          \
  MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)
454
/** Used to end a DIGESTMAP_FOREACH() block. */
455
456
#define DIGESTMAP_FOREACH_END MAP_FOREACH_END

457
458
459
460
461
462
#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

463
void* strmap_set_lc(strmap_t *map, const char *key, void *val);
464
void* strmap_get_lc(const strmap_t *map, const char *key);
465
466
void* strmap_remove_lc(strmap_t *map, const char *key);

467
468
469
470
471
472
473
#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();                                   \
  }                                                                     \
474
475
476
477
  static INLINE digestmap_t* prefix##to_digestmap(maptype *map)         \
  {                                                                     \
    return (digestmap_t*)map;                                           \
  }                                                                     \
478
479
480
481
482
483
484
485
486
487
488
  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)  \
  {                                                                     \
489
    return (valtype*)digestmap_remove((digestmap_t*)map, key);          \
490
491
492
493
494
495
496
497
498
499
500
  }                                                                     \
  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)                          \
  {                                                                     \
501
    return digestmap_size((digestmap_t*)map);                           \
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
  }                                                                     \
  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);                \
  }

532
533
534
535
536
#if SIZEOF_INT == 4
#define BITARRAY_SHIFT 5
#elif SIZEOF_INT == 8
#define BITARRAY_SHIFT 6
#else
537
#error "int is neither 4 nor 8 bytes. I can't deal with that."
538
#endif
539
#define BITARRAY_MASK ((1u<<BITARRAY_SHIFT)-1)
540

541
/** A random-access array of one-bit-wide elements. */
542
543
544
typedef unsigned int bitarray_t;
/** Create a new bit array that can hold <b>n_bits</b> bits. */
static INLINE bitarray_t *
545
bitarray_init_zero(unsigned int n_bits)
546
{
547
548
  /* round up to the next int. */
  size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT;
549
550
  return tor_malloc_zero(sz*sizeof(unsigned int));
}
551
552
553
/** 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. */
554
static INLINE bitarray_t *
555
556
bitarray_expand(bitarray_t *ba,
                unsigned int n_bits_old, unsigned int n_bits_new)
557
{
558
559
  size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT;
  size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT;
560
561
562
  char *ptr;
  if (sz_new <= sz_old)
    return ba;
563
564
565
  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. */
566
567
  memset(ptr+sz_old*sizeof(unsigned int), 0,
         (sz_new-sz_old)*sizeof(unsigned int));
568
569
  return (bitarray_t*) ptr;
}
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
/** 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));
}

596
597
598
599
600
601
602
603
604
605
606
607
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
/** A set of digests, implemented as a Bloom filter. */
typedef struct {
  int mask; /* One less than the number of bits in <b>ba</b>; always one less
             * than a power of two. */
  bitarray_t *ba; /* A bit array to implement the Bloom filter. */
} 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)
{
  const uint32_t *p = (const uint32_t *)digest;
  const uint32_t d1 = p[0] + (p[1]>>16);
  const uint32_t d2 = p[1] + (p[2]>>16);
  const uint32_t d3 = p[2] + (p[3]>>16);
  const uint32_t d4 = p[3] + (p[0]>>16);
  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
digestset_isin(const digestset_t *set, const char *digest)
{
  const uint32_t *p = (const uint32_t *)digest;
  const uint32_t d1 = p[0] + (p[1]>>16);
  const uint32_t d2 = p[1] + (p[2]>>16);
  const uint32_t d3 = p[2] + (p[3]>>16);
  const uint32_t d4 = p[3] + (p[0]>>16);
  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);

639
640
641
642
643
644
645
/* 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);
646
int32_t find_nth_int32(int32_t *array, int n_elements, int nth);
647
uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth);
648
long find_nth_long(long *array, int n_elements, int nth);
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
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);
}
669
670
671
672
673
static INLINE int32_t
median_int32(int32_t *array, int n_elements)
{
  return find_nth_int32(array, n_elements, (n_elements-1)/2);
}
674
675
676
677
678
static INLINE long
median_long(long *array, int n_elements)
{
  return find_nth_long(array, n_elements, (n_elements-1)/2);
}
679

680
#endif
681