Back to index

tor  0.2.3.19-rc
container.c
Go to the documentation of this file.
00001 /* Copyright (c) 2003-2004, Roger Dingledine
00002  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
00003  * Copyright (c) 2007-2012, The Tor Project, Inc. */
00004 /* See LICENSE for licensing information */
00005 
00014 #include "compat.h"
00015 #include "util.h"
00016 #include "torlog.h"
00017 #include "container.h"
00018 #include "crypto.h"
00019 
00020 #include <stdlib.h>
00021 #include <string.h>
00022 #include <assert.h>
00023 
00024 #include "ht.h"
00025 
00027 #define SMARTLIST_DEFAULT_CAPACITY 16
00028 
00031 smartlist_t *
00032 smartlist_new(void)
00033 {
00034   smartlist_t *sl = tor_malloc(sizeof(smartlist_t));
00035   sl->num_used = 0;
00036   sl->capacity = SMARTLIST_DEFAULT_CAPACITY;
00037   sl->list = tor_malloc(sizeof(void *) * sl->capacity);
00038   return sl;
00039 }
00040 
00044 void
00045 smartlist_free(smartlist_t *sl)
00046 {
00047   if (!sl)
00048     return;
00049   tor_free(sl->list);
00050   tor_free(sl);
00051 }
00052 
00055 void
00056 smartlist_clear(smartlist_t *sl)
00057 {
00058   sl->num_used = 0;
00059 }
00060 
00062 static INLINE void
00063 smartlist_ensure_capacity(smartlist_t *sl, int size)
00064 {
00065 #if SIZEOF_SIZE_T > SIZEOF_INT
00066 #define MAX_CAPACITY (INT_MAX)
00067 #else
00068 #define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*))))
00069 #endif
00070   if (size > sl->capacity) {
00071     int higher = sl->capacity;
00072     if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) {
00073       tor_assert(size <= MAX_CAPACITY);
00074       higher = MAX_CAPACITY;
00075     } else {
00076       while (size > higher)
00077         higher *= 2;
00078     }
00079     sl->capacity = higher;
00080     sl->list = tor_realloc(sl->list, sizeof(void*)*((size_t)sl->capacity));
00081   }
00082 }
00083 
00085 void
00086 smartlist_add(smartlist_t *sl, void *element)
00087 {
00088   smartlist_ensure_capacity(sl, sl->num_used+1);
00089   sl->list[sl->num_used++] = element;
00090 }
00091 
00093 void
00094 smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
00095 {
00096   int new_size = s1->num_used + s2->num_used;
00097   tor_assert(new_size >= s1->num_used); /* check for overflow. */
00098   smartlist_ensure_capacity(s1, new_size);
00099   memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*));
00100   s1->num_used = new_size;
00101 }
00102 
00107 void
00108 smartlist_remove(smartlist_t *sl, const void *element)
00109 {
00110   int i;
00111   if (element == NULL)
00112     return;
00113   for (i=0; i < sl->num_used; i++)
00114     if (sl->list[i] == element) {
00115       sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
00116       i--; /* so we process the new i'th element */
00117     }
00118 }
00119 
00122 void *
00123 smartlist_pop_last(smartlist_t *sl)
00124 {
00125   tor_assert(sl);
00126   if (sl->num_used)
00127     return sl->list[--sl->num_used];
00128   else
00129     return NULL;
00130 }
00131 
00133 void
00134 smartlist_reverse(smartlist_t *sl)
00135 {
00136   int i, j;
00137   void *tmp;
00138   tor_assert(sl);
00139   for (i = 0, j = sl->num_used-1; i < j; ++i, --j) {
00140     tmp = sl->list[i];
00141     sl->list[i] = sl->list[j];
00142     sl->list[j] = tmp;
00143   }
00144 }
00145 
00148 void
00149 smartlist_string_remove(smartlist_t *sl, const char *element)
00150 {
00151   int i;
00152   tor_assert(sl);
00153   tor_assert(element);
00154   for (i = 0; i < sl->num_used; ++i) {
00155     if (!strcmp(element, sl->list[i])) {
00156       tor_free(sl->list[i]);
00157       sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */
00158       i--; /* so we process the new i'th element */
00159     }
00160   }
00161 }
00162 
00165 int
00166 smartlist_isin(const smartlist_t *sl, const void *element)
00167 {
00168   int i;
00169   for (i=0; i < sl->num_used; i++)
00170     if (sl->list[i] == element)
00171       return 1;
00172   return 0;
00173 }
00174 
00178 int
00179 smartlist_string_isin(const smartlist_t *sl, const char *element)
00180 {
00181   int i;
00182   if (!sl) return 0;
00183   for (i=0; i < sl->num_used; i++)
00184     if (strcmp((const char*)sl->list[i],element)==0)
00185       return 1;
00186   return 0;
00187 }
00188 
00191 int
00192 smartlist_string_pos(const smartlist_t *sl, const char *element)
00193 {
00194   int i;
00195   if (!sl) return -1;
00196   for (i=0; i < sl->num_used; i++)
00197     if (strcmp((const char*)sl->list[i],element)==0)
00198       return i;
00199   return -1;
00200 }
00201 
00205 int
00206 smartlist_string_isin_case(const smartlist_t *sl, const char *element)
00207 {
00208   int i;
00209   if (!sl) return 0;
00210   for (i=0; i < sl->num_used; i++)
00211     if (strcasecmp((const char*)sl->list[i],element)==0)
00212       return 1;
00213   return 0;
00214 }
00215 
00219 int
00220 smartlist_string_num_isin(const smartlist_t *sl, int num)
00221 {
00222   char buf[32]; /* long enough for 64-bit int, and then some. */
00223   tor_snprintf(buf,sizeof(buf),"%d", num);
00224   return smartlist_string_isin(sl, buf);
00225 }
00226 
00229 int
00230 smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
00231 {
00232   if (sl1 == NULL)
00233     return sl2 == NULL;
00234   if (sl2 == NULL)
00235     return 0;
00236   if (smartlist_len(sl1) != smartlist_len(sl2))
00237     return 0;
00238   SMARTLIST_FOREACH(sl1, const char *, cp1, {
00239       const char *cp2 = smartlist_get(sl2, cp1_sl_idx);
00240       if (strcmp(cp1, cp2))
00241         return 0;
00242     });
00243   return 1;
00244 }
00245 
00249 int
00250 smartlist_digest_isin(const smartlist_t *sl, const char *element)
00251 {
00252   int i;
00253   if (!sl) return 0;
00254   for (i=0; i < sl->num_used; i++)
00255     if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN))
00256       return 1;
00257   return 0;
00258 }
00259 
00262 int
00263 smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
00264 {
00265   int i;
00266   for (i=0; i < sl2->num_used; i++)
00267     if (smartlist_isin(sl1, sl2->list[i]))
00268       return 1;
00269   return 0;
00270 }
00271 
00275 void
00276 smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
00277 {
00278   int i;
00279   for (i=0; i < sl1->num_used; i++)
00280     if (!smartlist_isin(sl2, sl1->list[i])) {
00281       sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
00282       i--; /* so we process the new i'th element */
00283     }
00284 }
00285 
00289 void
00290 smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
00291 {
00292   int i;
00293   for (i=0; i < sl2->num_used; i++)
00294     smartlist_remove(sl1, sl2->list[i]);
00295 }
00296 
00300 void
00301 smartlist_del(smartlist_t *sl, int idx)
00302 {
00303   tor_assert(sl);
00304   tor_assert(idx>=0);
00305   tor_assert(idx < sl->num_used);
00306   sl->list[idx] = sl->list[--sl->num_used];
00307 }
00308 
00313 void
00314 smartlist_del_keeporder(smartlist_t *sl, int idx)
00315 {
00316   tor_assert(sl);
00317   tor_assert(idx>=0);
00318   tor_assert(idx < sl->num_used);
00319   --sl->num_used;
00320   if (idx < sl->num_used)
00321     memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx));
00322 }
00323 
00328 void
00329 smartlist_insert(smartlist_t *sl, int idx, void *val)
00330 {
00331   tor_assert(sl);
00332   tor_assert(idx>=0);
00333   tor_assert(idx <= sl->num_used);
00334   if (idx == sl->num_used) {
00335     smartlist_add(sl, val);
00336   } else {
00337     smartlist_ensure_capacity(sl, sl->num_used+1);
00338     /* Move other elements away */
00339     if (idx < sl->num_used)
00340       memmove(sl->list + idx + 1, sl->list + idx,
00341               sizeof(void*)*(sl->num_used-idx));
00342     sl->num_used++;
00343     sl->list[idx] = val;
00344   }
00345 }
00346 
00362 int
00363 smartlist_split_string(smartlist_t *sl, const char *str, const char *sep,
00364                        int flags, int max)
00365 {
00366   const char *cp, *end, *next;
00367   int n = 0;
00368 
00369   tor_assert(sl);
00370   tor_assert(str);
00371 
00372   cp = str;
00373   while (1) {
00374     if (flags&SPLIT_SKIP_SPACE) {
00375       while (TOR_ISSPACE(*cp)) ++cp;
00376     }
00377 
00378     if (max>0 && n == max-1) {
00379       end = strchr(cp,'\0');
00380     } else if (sep) {
00381       end = strstr(cp,sep);
00382       if (!end)
00383         end = strchr(cp,'\0');
00384     } else {
00385       for (end = cp; *end && *end != '\t' && *end != ' '; ++end)
00386         ;
00387     }
00388 
00389     tor_assert(end);
00390 
00391     if (!*end) {
00392       next = NULL;
00393     } else if (sep) {
00394       next = end+strlen(sep);
00395     } else {
00396       next = end+1;
00397       while (*next == '\t' || *next == ' ')
00398         ++next;
00399     }
00400 
00401     if (flags&SPLIT_SKIP_SPACE) {
00402       while (end > cp && TOR_ISSPACE(*(end-1)))
00403         --end;
00404     }
00405     if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) {
00406       char *string = tor_strndup(cp, end-cp);
00407       if (flags&SPLIT_STRIP_SPACE)
00408         tor_strstrip(string, " ");
00409       smartlist_add(sl, string);
00410       ++n;
00411     }
00412     if (!next)
00413       break;
00414     cp = next;
00415   }
00416 
00417   return n;
00418 }
00419 
00427 char *
00428 smartlist_join_strings(smartlist_t *sl, const char *join,
00429                        int terminate, size_t *len_out)
00430 {
00431   return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out);
00432 }
00433 
00439 char *
00440 smartlist_join_strings2(smartlist_t *sl, const char *join,
00441                         size_t join_len, int terminate, size_t *len_out)
00442 {
00443   int i;
00444   size_t n = 0;
00445   char *r = NULL, *dst, *src;
00446 
00447   tor_assert(sl);
00448   tor_assert(join);
00449 
00450   if (terminate)
00451     n = join_len;
00452 
00453   for (i = 0; i < sl->num_used; ++i) {
00454     n += strlen(sl->list[i]);
00455     if (i+1 < sl->num_used) /* avoid double-counting the last one */
00456       n += join_len;
00457   }
00458   dst = r = tor_malloc(n+1);
00459   for (i = 0; i < sl->num_used; ) {
00460     for (src = sl->list[i]; *src; )
00461       *dst++ = *src++;
00462     if (++i < sl->num_used) {
00463       memcpy(dst, join, join_len);
00464       dst += join_len;
00465     }
00466   }
00467   if (terminate) {
00468     memcpy(dst, join, join_len);
00469     dst += join_len;
00470   }
00471   *dst = '\0';
00472 
00473   if (len_out)
00474     *len_out = dst-r;
00475   return r;
00476 }
00477 
00482 void
00483 smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b))
00484 {
00485   if (!sl->num_used)
00486     return;
00487   qsort(sl->list, sl->num_used, sizeof(void*),
00488         (int (*)(const void *,const void*))compare);
00489 }
00490 
00495 void *
00496 smartlist_get_most_frequent(const smartlist_t *sl,
00497                             int (*compare)(const void **a, const void **b))
00498 {
00499   const void *most_frequent = NULL;
00500   int most_frequent_count = 0;
00501 
00502   const void *cur = NULL;
00503   int i, count=0;
00504 
00505   if (!sl->num_used)
00506     return NULL;
00507   for (i = 0; i < sl->num_used; ++i) {
00508     const void *item = sl->list[i];
00509     if (cur && 0 == compare(&cur, &item)) {
00510       ++count;
00511     } else {
00512       if (cur && count >= most_frequent_count) {
00513         most_frequent = cur;
00514         most_frequent_count = count;
00515       }
00516       cur = item;
00517       count = 1;
00518     }
00519   }
00520   if (cur && count >= most_frequent_count) {
00521     most_frequent = cur;
00522     most_frequent_count = count;
00523   }
00524   return (void*)most_frequent;
00525 }
00526 
00531 void
00532 smartlist_uniq(smartlist_t *sl,
00533                int (*compare)(const void **a, const void **b),
00534                void (*free_fn)(void *a))
00535 {
00536   int i;
00537   for (i=1; i < sl->num_used; ++i) {
00538     if (compare((const void **)&(sl->list[i-1]),
00539                 (const void **)&(sl->list[i])) == 0) {
00540       if (free_fn)
00541         free_fn(sl->list[i]);
00542       smartlist_del_keeporder(sl, i--);
00543     }
00544   }
00545 }
00546 
00552 void *
00553 smartlist_bsearch(smartlist_t *sl, const void *key,
00554                   int (*compare)(const void *key, const void **member))
00555 {
00556   int found, idx;
00557   idx = smartlist_bsearch_idx(sl, key, compare, &found);
00558   return found ? smartlist_get(sl, idx) : NULL;
00559 }
00560 
00569 int
00570 smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
00571                       int (*compare)(const void *key, const void **member),
00572                       int *found_out)
00573 {
00574   int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid;
00575 
00576   while (lo <= hi) {
00577     mid = (lo + hi) / 2;
00578     cmp = compare(key, (const void**) &(sl->list[mid]));
00579     if (cmp>0) { /* key > sl[mid] */
00580       lo = mid+1;
00581     } else if (cmp<0) { /* key < sl[mid] */
00582       hi = mid-1;
00583     } else { /* key == sl[mid] */
00584       *found_out = 1;
00585       return mid;
00586     }
00587   }
00588   /* lo > hi. */
00589   {
00590     tor_assert(lo >= 0);
00591     if (lo < smartlist_len(sl)) {
00592       cmp = compare(key, (const void**) &(sl->list[lo]));
00593       tor_assert(cmp < 0);
00594     } else if (smartlist_len(sl)) {
00595       cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1]));
00596       tor_assert(cmp > 0);
00597     }
00598   }
00599   *found_out = 0;
00600   return lo;
00601 }
00602 
00604 static int
00605 _compare_string_ptrs(const void **_a, const void **_b)
00606 {
00607   return strcmp((const char*)*_a, (const char*)*_b);
00608 }
00609 
00612 void
00613 smartlist_sort_strings(smartlist_t *sl)
00614 {
00615   smartlist_sort(sl, _compare_string_ptrs);
00616 }
00617 
00619 char *
00620 smartlist_get_most_frequent_string(smartlist_t *sl)
00621 {
00622   return smartlist_get_most_frequent(sl, _compare_string_ptrs);
00623 }
00624 
00627 void
00628 smartlist_uniq_strings(smartlist_t *sl)
00629 {
00630   smartlist_uniq(sl, _compare_string_ptrs, _tor_free);
00631 }
00632 
00633 /* Heap-based priority queue implementation for O(lg N) insert and remove.
00634  * Recall that the heap property is that, for every index I, h[I] <
00635  * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]].
00636  *
00637  * For us to remove items other than the topmost item, each item must store
00638  * its own index within the heap.  When calling the pqueue functions, tell
00639  * them about the offset of the field that stores the index within the item.
00640  *
00641  * Example:
00642  *
00643  *   typedef struct timer_t {
00644  *     struct timeval tv;
00645  *     int heap_index;
00646  *   } timer_t;
00647  *
00648  *   static int compare(const void *p1, const void *p2) {
00649  *     const timer_t *t1 = p1, *t2 = p2;
00650  *     if (t1->tv.tv_sec < t2->tv.tv_sec) {
00651  *        return -1;
00652  *     } else if (t1->tv.tv_sec > t2->tv.tv_sec) {
00653  *        return 1;
00654  *     } else {
00655  *        return t1->tv.tv_usec - t2->tv_usec;
00656  *     }
00657  *   }
00658  *
00659  *   void timer_heap_insert(smartlist_t *heap, timer_t *timer) {
00660  *      smartlist_pqueue_add(heap, compare, STRUCT_OFFSET(timer_t, heap_index),
00661  *         timer);
00662  *   }
00663  *
00664  *   void timer_heap_pop(smartlist_t *heap) {
00665  *      return smartlist_pqueue_pop(heap, compare,
00666  *         STRUCT_OFFSET(timer_t, heap_index));
00667  *   }
00668  */
00669 
00675 //#define LEFT_CHILD(i)  ( ((i)+1)*2 - 1)
00676 //#define RIGHT_CHILD(i) ( ((i)+1)*2 )
00677 //#define PARENT(i)      ( ((i)+1)/2 - 1)
00678 #define LEFT_CHILD(i)  ( 2*(i) + 1 )
00679 #define RIGHT_CHILD(i) ( 2*(i) + 2 )
00680 #define PARENT(i)      ( ((i)-1) / 2 )
00681 
00691 #define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset))
00692 
00693 #define UPDATE_IDX(i)  do {                            \
00694     void *updated = sl->list[i];                       \
00695     *IDXP(updated) = i;                                \
00696   } while (0)
00697 
00698 #define IDX_OF_ITEM(p) (*IDXP(p))
00699 
00704 static INLINE void
00705 smartlist_heapify(smartlist_t *sl,
00706                   int (*compare)(const void *a, const void *b),
00707                   int idx_field_offset,
00708                   int idx)
00709 {
00710   while (1) {
00711     int left_idx = LEFT_CHILD(idx);
00712     int best_idx;
00713 
00714     if (left_idx >= sl->num_used)
00715       return;
00716     if (compare(sl->list[idx],sl->list[left_idx]) < 0)
00717       best_idx = idx;
00718     else
00719       best_idx = left_idx;
00720     if (left_idx+1 < sl->num_used &&
00721         compare(sl->list[left_idx+1],sl->list[best_idx]) < 0)
00722       best_idx = left_idx + 1;
00723 
00724     if (best_idx == idx) {
00725       return;
00726     } else {
00727       void *tmp = sl->list[idx];
00728       sl->list[idx] = sl->list[best_idx];
00729       sl->list[best_idx] = tmp;
00730       UPDATE_IDX(idx);
00731       UPDATE_IDX(best_idx);
00732 
00733       idx = best_idx;
00734     }
00735   }
00736 }
00737 
00743 void
00744 smartlist_pqueue_add(smartlist_t *sl,
00745                      int (*compare)(const void *a, const void *b),
00746                      int idx_field_offset,
00747                      void *item)
00748 {
00749   int idx;
00750   smartlist_add(sl,item);
00751   UPDATE_IDX(sl->num_used-1);
00752 
00753   for (idx = sl->num_used - 1; idx; ) {
00754     int parent = PARENT(idx);
00755     if (compare(sl->list[idx], sl->list[parent]) < 0) {
00756       void *tmp = sl->list[parent];
00757       sl->list[parent] = sl->list[idx];
00758       sl->list[idx] = tmp;
00759       UPDATE_IDX(parent);
00760       UPDATE_IDX(idx);
00761       idx = parent;
00762     } else {
00763       return;
00764     }
00765   }
00766 }
00767 
00772 void *
00773 smartlist_pqueue_pop(smartlist_t *sl,
00774                      int (*compare)(const void *a, const void *b),
00775                      int idx_field_offset)
00776 {
00777   void *top;
00778   tor_assert(sl->num_used);
00779 
00780   top = sl->list[0];
00781   *IDXP(top)=-1;
00782   if (--sl->num_used) {
00783     sl->list[0] = sl->list[sl->num_used];
00784     UPDATE_IDX(0);
00785     smartlist_heapify(sl, compare, idx_field_offset, 0);
00786   }
00787   return top;
00788 }
00789 
00794 void
00795 smartlist_pqueue_remove(smartlist_t *sl,
00796                         int (*compare)(const void *a, const void *b),
00797                         int idx_field_offset,
00798                         void *item)
00799 {
00800   int idx = IDX_OF_ITEM(item);
00801   tor_assert(idx >= 0);
00802   tor_assert(sl->list[idx] == item);
00803   --sl->num_used;
00804   *IDXP(item) = -1;
00805   if (idx == sl->num_used) {
00806     return;
00807   } else {
00808     sl->list[idx] = sl->list[sl->num_used];
00809     UPDATE_IDX(idx);
00810     smartlist_heapify(sl, compare, idx_field_offset, idx);
00811   }
00812 }
00813 
00816 void
00817 smartlist_pqueue_assert_ok(smartlist_t *sl,
00818                            int (*compare)(const void *a, const void *b),
00819                            int idx_field_offset)
00820 {
00821   int i;
00822   for (i = sl->num_used - 1; i >= 0; --i) {
00823     if (i>0)
00824       tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0);
00825     tor_assert(IDX_OF_ITEM(sl->list[i]) == i);
00826   }
00827 }
00828 
00830 static int
00831 _compare_digests(const void **_a, const void **_b)
00832 {
00833   return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN);
00834 }
00835 
00837 void
00838 smartlist_sort_digests(smartlist_t *sl)
00839 {
00840   smartlist_sort(sl, _compare_digests);
00841 }
00842 
00845 void
00846 smartlist_uniq_digests(smartlist_t *sl)
00847 {
00848   smartlist_uniq(sl, _compare_digests, _tor_free);
00849 }
00850 
00852 static int
00853 _compare_digests256(const void **_a, const void **_b)
00854 {
00855   return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN);
00856 }
00857 
00859 void
00860 smartlist_sort_digests256(smartlist_t *sl)
00861 {
00862   smartlist_sort(sl, _compare_digests256);
00863 }
00864 
00867 char *
00868 smartlist_get_most_frequent_digest256(smartlist_t *sl)
00869 {
00870   return smartlist_get_most_frequent(sl, _compare_digests256);
00871 }
00872 
00876 void
00877 smartlist_uniq_digests256(smartlist_t *sl)
00878 {
00879   smartlist_uniq(sl, _compare_digests256, _tor_free);
00880 }
00881 
00886 #define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix)      \
00887   typedef struct prefix ## entry_t {                      \
00888     HT_ENTRY(prefix ## entry_t) node;                     \
00889     void *val;                                            \
00890     keydecl;                                              \
00891   } prefix ## entry_t;                                    \
00892   struct maptype {                                        \
00893     HT_HEAD(prefix ## impl, prefix ## entry_t) head;      \
00894   }
00895 
00896 DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_);
00897 DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_);
00898 
00900 static INLINE int
00901 strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
00902 {
00903   return !strcmp(a->key, b->key);
00904 }
00905 
00907 static INLINE unsigned int
00908 strmap_entry_hash(const strmap_entry_t *a)
00909 {
00910   return ht_string_hash(a->key);
00911 }
00912 
00914 static INLINE int
00915 digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
00916 {
00917   return tor_memeq(a->key, b->key, DIGEST_LEN);
00918 }
00919 
00921 static INLINE unsigned int
00922 digestmap_entry_hash(const digestmap_entry_t *a)
00923 {
00924 #if SIZEOF_INT != 8
00925   const uint32_t *p = (const uint32_t*)a->key;
00926   return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
00927 #else
00928   const uint64_t *p = (const uint64_t*)a->key;
00929   return p[0] ^ p[1];
00930 #endif
00931 }
00932 
00933 HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
00934              strmap_entries_eq)
00935 HT_GENERATE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
00936             strmap_entries_eq, 0.6, malloc, realloc, free)
00937 
00938 HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
00939              digestmap_entries_eq)
00940 HT_GENERATE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
00941             digestmap_entries_eq, 0.6, malloc, realloc, free)
00942 
00945 strmap_t *
00946 strmap_new(void)
00947 {
00948   strmap_t *result;
00949   result = tor_malloc(sizeof(strmap_t));
00950   HT_INIT(strmap_impl, &result->head);
00951   return result;
00952 }
00953 
00956 digestmap_t *
00957 digestmap_new(void)
00958 {
00959   digestmap_t *result;
00960   result = tor_malloc(sizeof(digestmap_t));
00961   HT_INIT(digestmap_impl, &result->head);
00962   return result;
00963 }
00964 
00971 void *
00972 strmap_set(strmap_t *map, const char *key, void *val)
00973 {
00974   strmap_entry_t *resolve;
00975   strmap_entry_t search;
00976   void *oldval;
00977   tor_assert(map);
00978   tor_assert(key);
00979   tor_assert(val);
00980   search.key = (char*)key;
00981   resolve = HT_FIND(strmap_impl, &map->head, &search);
00982   if (resolve) {
00983     oldval = resolve->val;
00984     resolve->val = val;
00985     return oldval;
00986   } else {
00987     resolve = tor_malloc_zero(sizeof(strmap_entry_t));
00988     resolve->key = tor_strdup(key);
00989     resolve->val = val;
00990     tor_assert(!HT_FIND(strmap_impl, &map->head, resolve));
00991     HT_INSERT(strmap_impl, &map->head, resolve);
00992     return NULL;
00993   }
00994 }
00995 
00996 #define OPTIMIZED_DIGESTMAP_SET
00997 
00999 void *
01000 digestmap_set(digestmap_t *map, const char *key, void *val)
01001 {
01002 #ifndef OPTIMIZED_DIGESTMAP_SET
01003   digestmap_entry_t *resolve;
01004 #endif
01005   digestmap_entry_t search;
01006   void *oldval;
01007   tor_assert(map);
01008   tor_assert(key);
01009   tor_assert(val);
01010   memcpy(&search.key, key, DIGEST_LEN);
01011 #ifndef OPTIMIZED_DIGESTMAP_SET
01012   resolve = HT_FIND(digestmap_impl, &map->head, &search);
01013   if (resolve) {
01014     oldval = resolve->val;
01015     resolve->val = val;
01016     return oldval;
01017   } else {
01018     resolve = tor_malloc_zero(sizeof(digestmap_entry_t));
01019     memcpy(resolve->key, key, DIGEST_LEN);
01020     resolve->val = val;
01021     HT_INSERT(digestmap_impl, &map->head, resolve);
01022     return NULL;
01023   }
01024 #else
01025   /* We spend up to 5% of our time in this function, so the code below is
01026    * meant to optimize the check/alloc/set cycle by avoiding the two trips to
01027    * the hash table that we do in the unoptimized code above.  (Each of
01028    * HT_INSERT and HT_FIND calls HT_SET_HASH and HT_FIND_P.)
01029    */
01030   HT_FIND_OR_INSERT_(digestmap_impl, node, digestmap_entry_hash, &(map->head),
01031          digestmap_entry_t, &search, ptr,
01032          {
01033             /* we found an entry. */
01034             oldval = (*ptr)->val;
01035             (*ptr)->val = val;
01036             return oldval;
01037          },
01038          {
01039            /* We didn't find the entry. */
01040            digestmap_entry_t *newent =
01041              tor_malloc_zero(sizeof(digestmap_entry_t));
01042            memcpy(newent->key, key, DIGEST_LEN);
01043            newent->val = val;
01044            HT_FOI_INSERT_(node, &(map->head), &search, newent, ptr);
01045            return NULL;
01046          });
01047 #endif
01048 }
01049 
01053 void *
01054 strmap_get(const strmap_t *map, const char *key)
01055 {
01056   strmap_entry_t *resolve;
01057   strmap_entry_t search;
01058   tor_assert(map);
01059   tor_assert(key);
01060   search.key = (char*)key;
01061   resolve = HT_FIND(strmap_impl, &map->head, &search);
01062   if (resolve) {
01063     return resolve->val;
01064   } else {
01065     return NULL;
01066   }
01067 }
01068 
01070 void *
01071 digestmap_get(const digestmap_t *map, const char *key)
01072 {
01073   digestmap_entry_t *resolve;
01074   digestmap_entry_t search;
01075   tor_assert(map);
01076   tor_assert(key);
01077   memcpy(&search.key, key, DIGEST_LEN);
01078   resolve = HT_FIND(digestmap_impl, &map->head, &search);
01079   if (resolve) {
01080     return resolve->val;
01081   } else {
01082     return NULL;
01083   }
01084 }
01085 
01092 void *
01093 strmap_remove(strmap_t *map, const char *key)
01094 {
01095   strmap_entry_t *resolve;
01096   strmap_entry_t search;
01097   void *oldval;
01098   tor_assert(map);
01099   tor_assert(key);
01100   search.key = (char*)key;
01101   resolve = HT_REMOVE(strmap_impl, &map->head, &search);
01102   if (resolve) {
01103     oldval = resolve->val;
01104     tor_free(resolve->key);
01105     tor_free(resolve);
01106     return oldval;
01107   } else {
01108     return NULL;
01109   }
01110 }
01111 
01113 void *
01114 digestmap_remove(digestmap_t *map, const char *key)
01115 {
01116   digestmap_entry_t *resolve;
01117   digestmap_entry_t search;
01118   void *oldval;
01119   tor_assert(map);
01120   tor_assert(key);
01121   memcpy(&search.key, key, DIGEST_LEN);
01122   resolve = HT_REMOVE(digestmap_impl, &map->head, &search);
01123   if (resolve) {
01124     oldval = resolve->val;
01125     tor_free(resolve);
01126     return oldval;
01127   } else {
01128     return NULL;
01129   }
01130 }
01131 
01133 void *
01134 strmap_set_lc(strmap_t *map, const char *key, void *val)
01135 {
01136   /* We could be a little faster by using strcasecmp instead, and a separate
01137    * type, but I don't think it matters. */
01138   void *v;
01139   char *lc_key = tor_strdup(key);
01140   tor_strlower(lc_key);
01141   v = strmap_set(map,lc_key,val);
01142   tor_free(lc_key);
01143   return v;
01144 }
01145 
01147 void *
01148 strmap_get_lc(const strmap_t *map, const char *key)
01149 {
01150   void *v;
01151   char *lc_key = tor_strdup(key);
01152   tor_strlower(lc_key);
01153   v = strmap_get(map,lc_key);
01154   tor_free(lc_key);
01155   return v;
01156 }
01157 
01159 void *
01160 strmap_remove_lc(strmap_t *map, const char *key)
01161 {
01162   void *v;
01163   char *lc_key = tor_strdup(key);
01164   tor_strlower(lc_key);
01165   v = strmap_remove(map,lc_key);
01166   tor_free(lc_key);
01167   return v;
01168 }
01169 
01196 strmap_iter_t *
01197 strmap_iter_init(strmap_t *map)
01198 {
01199   tor_assert(map);
01200   return HT_START(strmap_impl, &map->head);
01201 }
01202 
01204 digestmap_iter_t *
01205 digestmap_iter_init(digestmap_t *map)
01206 {
01207   tor_assert(map);
01208   return HT_START(digestmap_impl, &map->head);
01209 }
01210 
01213 strmap_iter_t *
01214 strmap_iter_next(strmap_t *map, strmap_iter_t *iter)
01215 {
01216   tor_assert(map);
01217   tor_assert(iter);
01218   return HT_NEXT(strmap_impl, &map->head, iter);
01219 }
01220 
01223 digestmap_iter_t *
01224 digestmap_iter_next(digestmap_t *map, digestmap_iter_t *iter)
01225 {
01226   tor_assert(map);
01227   tor_assert(iter);
01228   return HT_NEXT(digestmap_impl, &map->head, iter);
01229 }
01230 
01234 strmap_iter_t *
01235 strmap_iter_next_rmv(strmap_t *map, strmap_iter_t *iter)
01236 {
01237   strmap_entry_t *rmv;
01238   tor_assert(map);
01239   tor_assert(iter);
01240   tor_assert(*iter);
01241   rmv = *iter;
01242   iter = HT_NEXT_RMV(strmap_impl, &map->head, iter);
01243   tor_free(rmv->key);
01244   tor_free(rmv);
01245   return iter;
01246 }
01247 
01251 digestmap_iter_t *
01252 digestmap_iter_next_rmv(digestmap_t *map, digestmap_iter_t *iter)
01253 {
01254   digestmap_entry_t *rmv;
01255   tor_assert(map);
01256   tor_assert(iter);
01257   tor_assert(*iter);
01258   rmv = *iter;
01259   iter = HT_NEXT_RMV(digestmap_impl, &map->head, iter);
01260   tor_free(rmv);
01261   return iter;
01262 }
01263 
01266 void
01267 strmap_iter_get(strmap_iter_t *iter, const char **keyp, void **valp)
01268 {
01269   tor_assert(iter);
01270   tor_assert(*iter);
01271   tor_assert(keyp);
01272   tor_assert(valp);
01273   *keyp = (*iter)->key;
01274   *valp = (*iter)->val;
01275 }
01276 
01279 void
01280 digestmap_iter_get(digestmap_iter_t *iter, const char **keyp, void **valp)
01281 {
01282   tor_assert(iter);
01283   tor_assert(*iter);
01284   tor_assert(keyp);
01285   tor_assert(valp);
01286   *keyp = (*iter)->key;
01287   *valp = (*iter)->val;
01288 }
01289 
01292 int
01293 strmap_iter_done(strmap_iter_t *iter)
01294 {
01295   return iter == NULL;
01296 }
01297 
01300 int
01301 digestmap_iter_done(digestmap_iter_t *iter)
01302 {
01303   return iter == NULL;
01304 }
01305 
01310 void
01311 strmap_free(strmap_t *map, void (*free_val)(void*))
01312 {
01313   strmap_entry_t **ent, **next, *this;
01314   if (!map)
01315     return;
01316 
01317   for (ent = HT_START(strmap_impl, &map->head); ent != NULL; ent = next) {
01318     this = *ent;
01319     next = HT_NEXT_RMV(strmap_impl, &map->head, ent);
01320     tor_free(this->key);
01321     if (free_val)
01322       free_val(this->val);
01323     tor_free(this);
01324   }
01325   tor_assert(HT_EMPTY(&map->head));
01326   HT_CLEAR(strmap_impl, &map->head);
01327   tor_free(map);
01328 }
01329 
01334 void
01335 digestmap_free(digestmap_t *map, void (*free_val)(void*))
01336 {
01337   digestmap_entry_t **ent, **next, *this;
01338   if (!map)
01339     return;
01340   for (ent = HT_START(digestmap_impl, &map->head); ent != NULL; ent = next) {
01341     this = *ent;
01342     next = HT_NEXT_RMV(digestmap_impl, &map->head, ent);
01343     if (free_val)
01344       free_val(this->val);
01345     tor_free(this);
01346   }
01347   tor_assert(HT_EMPTY(&map->head));
01348   HT_CLEAR(digestmap_impl, &map->head);
01349   tor_free(map);
01350 }
01351 
01354 void
01355 strmap_assert_ok(const strmap_t *map)
01356 {
01357   tor_assert(!strmap_impl_HT_REP_IS_BAD_(&map->head));
01358 }
01361 void
01362 digestmap_assert_ok(const digestmap_t *map)
01363 {
01364   tor_assert(!digestmap_impl_HT_REP_IS_BAD_(&map->head));
01365 }
01366 
01368 int
01369 strmap_isempty(const strmap_t *map)
01370 {
01371   return HT_EMPTY(&map->head);
01372 }
01373 
01375 int
01376 digestmap_isempty(const digestmap_t *map)
01377 {
01378   return HT_EMPTY(&map->head);
01379 }
01380 
01382 int
01383 strmap_size(const strmap_t *map)
01384 {
01385   return HT_SIZE(&map->head);
01386 }
01387 
01389 int
01390 digestmap_size(const digestmap_t *map)
01391 {
01392   return HT_SIZE(&map->head);
01393 }
01394 
01401 #define IMPLEMENT_ORDER_FUNC(funcname, elt_t)                   \
01402   static int                                                    \
01403   _cmp_ ## elt_t(const void *_a, const void *_b)                \
01404   {                                                             \
01405     const elt_t *a = _a, *b = _b;                               \
01406     if (*a<*b)                                                  \
01407       return -1;                                                \
01408     else if (*a>*b)                                             \
01409       return 1;                                                 \
01410     else                                                        \
01411       return 0;                                                 \
01412   }                                                             \
01413   elt_t                                                         \
01414   funcname(elt_t *array, int n_elements, int nth)               \
01415   {                                                             \
01416     tor_assert(nth >= 0);                                       \
01417     tor_assert(nth < n_elements);                               \
01418     qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t);     \
01419     return array[nth];                                          \
01420   }
01421 
01422 IMPLEMENT_ORDER_FUNC(find_nth_int, int)
01423 IMPLEMENT_ORDER_FUNC(find_nth_time, time_t)
01424 IMPLEMENT_ORDER_FUNC(find_nth_double, double)
01425 IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t)
01426 IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t)
01427 IMPLEMENT_ORDER_FUNC(find_nth_long, long)
01428 
01431 digestset_t *
01432 digestset_new(int max_elements)
01433 {
01434   /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k
01435    * is the number of hash functions per entry, m is the bits in the array,
01436    * and n is the number of elements inserted.  For us, k==4, n<=max_elements,
01437    * and m==n_bits= approximately max_elements*32.  This gives
01438    *   P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019
01439    *
01440    * It would be more optimal in space vs false positives to get this false
01441    * positive rate by going for k==13, and m==18.5n, but we also want to
01442    * conserve CPU, and k==13 is pretty big.
01443    */
01444   int n_bits = 1u << (tor_log2(max_elements)+5);
01445   digestset_t *r = tor_malloc(sizeof(digestset_t));
01446   r->mask = n_bits - 1;
01447   r->ba = bitarray_init_zero(n_bits);
01448   return r;
01449 }
01450 
01452 void
01453 digestset_free(digestset_t *set)
01454 {
01455   if (!set)
01456     return;
01457   bitarray_free(set->ba);
01458   tor_free(set);
01459 }
01460