"Fossies" - the Fresh Open Source Software Archive

Member "calcurse-4.5.1/src/htable.h" (5 Jan 2019, 26040 Bytes) of package /linux/privat/calcurse-4.5.1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "htable.h" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 4.2.1_vs_4.2.2.

    1 /*
    2  * Copyright (c) 2004-2017 calcurse Development Team <misc@calcurse.org>
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    8  *
    9  *      - Redistributions of source code must retain the above
   10  *        copyright notice, this list of conditions and the
   11  *        following disclaimer.
   12  *
   13  *      - Redistributions in binary form must reproduce the above
   14  *        copyright notice, this list of conditions and the
   15  *        following disclaimer in the documentation and/or other
   16  *        materials provided with the distribution.
   17  *
   18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
   28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   29  */
   30 
   31 #ifndef HTABLE_H
   32 #define HTABLE_H
   33 
   34 #include <stdint.h>
   35 #include <string.h>
   36 
   37 /*
   38  * This file defines data structures for hash tables.
   39  *
   40  * Hash tables are ideal for applications with datasets needing lots of adding,
   41  * searching or removal, as those are normally constant-time operations.
   42  * The primary operation it supports efficiently is a lookup: given a key (e.g.
   43  * a person's name), find the corresponding value (e.g. that person's telephone
   44  * number). It works by transforming the key using a hash function into a hash,
   45  * a number that is used as an index in an array to locate the desired location
   46  * ("bucket") where the values should be.
   47  *
   48  * Hash tables support the efficient insertion of new entries, in expected O(1)
   49  * time. The time spent in searching depends on the hash function and the load
   50  * of the hash table; both insertion and search approach O(1) time with well
   51  * chosen values and hashes.
   52  *
   53  * The collision resolution technique used here is direct chaining, implemented
   54  * using singly linked lists (the worst-case time is O(n)).
   55  *
   56  * This was chosen because performance degradation is linear as the table
   57  * fills, so there is almost no need to resize table
   58  * (for example, a chaining hash table containing twice its recommended
   59  * capacity of data would only be about twice as slow on average as the same
   60  * table at its recommended capacity).
   61  */
   62 
   63 #define HTABLE_HEAD(name, size, type)                                         \
   64 struct name {                                                                 \
   65   uint32_t      noitems;     /* Number of items stored in hash table. */      \
   66   uint32_t      nosingle;    /* Number of items alone in their bucket. */     \
   67   uint32_t      nofreebkts;  /* Number of free buckets. */                    \
   68   struct type  *bkts[size];  /* Pointers to user-defined data structures. */  \
   69 }
   70 
   71 #define HTABLE_ENTRY(type)                                                    \
   72 struct type   *next     /* To build the bucket chain list. */
   73 
   74 #define HTABLE_SIZE(head)                                                     \
   75   (sizeof (*(head)->bkts) ? sizeof ((head)->bkts) / sizeof (*(head)->bkts) : 0)
   76 
   77 #define HTABLE_COUNT(head)                                                    \
   78   ((head)->noitems ? (head)->noitems : 0)
   79 
   80 #define HTABLE_EMPTY(head)                                                    \
   81   (HTABLE_COUNT((head)) == 0 ? 1 : 0)
   82 
   83 #define HTABLE_COLLS(head)                                                    \
   84   ((head)->noitems ? 100.0 - 100 * (head)->nosingle / (head)->noitems : 0)
   85 
   86 #define HTABLE_LOAD(head)                                                     \
   87   (HTABLE_SIZE((head)) ?                                                      \
   88    100.0 - 100.0 * (head)->nofreebkts / HTABLE_SIZE((head)) : 0)
   89 
   90 #define HTABLE_INITIALIZER(head)                                              \
   91   { 0,                    /* noitems */                                       \
   92     0,                    /* nosingle */                                      \
   93     HTABLE_SIZE((head))   /* nofreebkts */                                    \
   94   }
   95 
   96 #define HTABLE_INIT(head) do {                                                \
   97   bzero ((head), sizeof (*(head)));                                           \
   98   (head)->nofreebkts = HTABLE_SIZE((head));                                   \
   99 } while (0)
  100 
  101 /*
  102  * Generate prototypes.
  103  */
  104 #define HTABLE_PROTOTYPE(name, type)                                          \
  105 struct type *name##_HTABLE_INSERT(struct name *, struct type *);              \
  106 struct type *name##_HTABLE_REMOVE(struct name *, struct type *);              \
  107 struct type *name##_HTABLE_LOOKUP(struct name *, struct type *);              \
  108 uint32_t name##_HTABLE_FIND_BKT(struct name *, struct type *);                \
  109 int name##_HTABLE_CHAIN_LEN(struct name *, uint32_t);                         \
  110 struct type *name##_HTABLE_FIRST_FROM(struct name *, int);                    \
  111 struct type *name##_HTABLE_NEXT(struct name *, struct type *);
  112 
  113 /*
  114  * Generate function bodies.
  115  */
  116 #define HTABLE_GENERATE(name, type, key, cmp)                                 \
  117 uint32_t                                                                      \
  118 name##_HTABLE_FIND_BKT(struct name *head, struct type *elm)                   \
  119 {                                                                             \
  120   uint32_t __bkt;                                                             \
  121   const char *__key;                                                                \
  122   int __len;                                                                  \
  123                                                                               \
  124   (key) (elm, &__key, &__len);                                                \
  125   HTABLE_HASH(__key, __len, HTABLE_SIZE(head), __bkt);                        \
  126                                                                               \
  127   return __bkt;                                                               \
  128 }                                                                             \
  129                                                                               \
  130 int                                                                           \
  131 name##_HTABLE_CHAIN_LEN(struct name *head, uint32_t bkt)                      \
  132 {                                                                             \
  133   struct type *__bktp;                                                        \
  134   int __len;                                                                  \
  135                                                                               \
  136   __len = 0;                                                                  \
  137   for (__bktp = (head)->bkts[(bkt)]; __bktp != NULL; __bktp = __bktp->next)   \
  138     __len++;                                                                  \
  139                                                                               \
  140   return __len;                                                               \
  141 }                                                                             \
  142                                                                               \
  143 struct type *                                                                 \
  144 name##_HTABLE_INSERT(struct name *head, struct type *elm)                     \
  145 {                                                                             \
  146   struct type *__bktp, **__bktpp;                                             \
  147   uint32_t __bkt, __pos;                                                      \
  148                                                                               \
  149   __pos = 0;                                                                  \
  150   __bkt = name##_HTABLE_FIND_BKT(head, elm);                                  \
  151   __bktpp = &head->bkts[__bkt];                                               \
  152   while ((__bktp = *__bktpp))                                                 \
  153     {                                                                         \
  154       if (!(cmp)(elm, __bktp))                                                \
  155         return NULL;                                                          \
  156       else                                                                    \
  157         {                                                                     \
  158           __pos++;                                                            \
  159           __bktpp = &__bktp->next;                                            \
  160         }                                                                     \
  161     }                                                                         \
  162   __bktp = elm;                                                               \
  163   __bktp->next = NULL;                                                        \
  164   *__bktpp = __bktp;                                                          \
  165   head->noitems++;                                                            \
  166   switch (__pos)                                                              \
  167     {                                                                         \
  168     case 0:                                                                   \
  169       head->nosingle++;                                                       \
  170       head->nofreebkts--;                                                     \
  171       break;                                                                  \
  172     case 1:                                                                   \
  173       head->nosingle--;                                                       \
  174       break;                                                                  \
  175     default:                                                                  \
  176       break;                                                                  \
  177     }                                                                         \
  178                                                                               \
  179   return __bktp;                                                              \
  180 }                                                                             \
  181                                                                               \
  182 struct type *                                                                 \
  183 name##_HTABLE_REMOVE(struct name *head, struct type *elm)                     \
  184 {                                                                             \
  185   struct type *__bktp, **__bktpp;                                             \
  186   uint32_t __bkt, __pos;                                                      \
  187                                                                               \
  188   __pos = 0;                                                                  \
  189   __bkt = name##_HTABLE_FIND_BKT(head, elm);                                  \
  190   __bktpp = &head->bkts[__bkt];                                               \
  191   while ((__bktp = *__bktpp))                                                 \
  192     {                                                                         \
  193       if (!(cmp)(elm, __bktp))                                                \
  194         {                                                                     \
  195           *__bktpp = __bktp->next;                                            \
  196           elm = __bktp;                                                       \
  197           head->noitems--;                                                    \
  198           if (__pos <= 1)      /* Need to scan list to know if we have */     \
  199             {                  /* a free bucket or a single item.      */     \
  200               int __len;                                                      \
  201                                                                               \
  202               __len = name##_HTABLE_CHAIN_LEN(head, __bkt);                   \
  203               switch (__len)                                                  \
  204                 {                                                             \
  205                 case 0:                                                       \
  206                   head->nofreebkts++;                                         \
  207                   head->nosingle--;                                           \
  208                   break;                                                      \
  209                 case 1:                                                       \
  210                   head->nosingle++;                                           \
  211                   break;                                                      \
  212                 }                                                             \
  213             }                                                                 \
  214           return elm;                                                         \
  215         }                                                                     \
  216       __pos++;                                                                \
  217       __bktpp = &__bktp->next;                                                \
  218     }                                                                         \
  219   return NULL;                                                                \
  220 }                                                                             \
  221                                                                               \
  222 struct type *                                                                 \
  223 name##_HTABLE_LOOKUP(struct name *head, struct type *elm)                     \
  224 {                                                                             \
  225   struct type *__bktp, **__bktpp;                                             \
  226   uint32_t __bkt;                                                             \
  227                                                                               \
  228   __bkt = name##_HTABLE_FIND_BKT(head, elm);                                  \
  229   __bktpp = &head->bkts[__bkt];                                               \
  230   while ((__bktp = *__bktpp))                                                 \
  231     {                                                                         \
  232       if (!(cmp)(elm, __bktp))                                                \
  233         return __bktp;                                                        \
  234       else                                                                    \
  235         __bktpp = &__bktp->next;                                              \
  236     }                                                                         \
  237                                                                               \
  238   return NULL;                                                                \
  239 }                                                                             \
  240                                                                               \
  241 struct type *                                                                 \
  242 name##_HTABLE_FIRST_FROM(struct name *head, int bkt)                          \
  243 {                                                                             \
  244   struct type *__bktp;                                                        \
  245                                                                               \
  246   while (bkt < HTABLE_SIZE(head))                                             \
  247     {                                                                         \
  248       if ((__bktp = head->bkts[bkt]))                                         \
  249         return __bktp;                                                        \
  250       else                                                                    \
  251         bkt++;                                                                \
  252     }                                                                         \
  253                                                                               \
  254   return NULL;                                                                \
  255 }                                                                             \
  256                                                                               \
  257 struct type *                                                                 \
  258 name##_HTABLE_NEXT(struct name *head, struct type *elm)                       \
  259 {                                                                             \
  260   struct type *__elmp, *__bktp, **__bktpp;                                    \
  261   uint32_t __bkt;                                                             \
  262                                                                               \
  263   __elmp = NULL;                                                              \
  264   __bkt = name##_HTABLE_FIND_BKT(head, elm);                                  \
  265   __bktpp = &head->bkts[__bkt];                                               \
  266   while ((__bktp = *__bktpp))                                                 \
  267     {                                                                         \
  268       if (!(cmp)(elm, __bktp))                                                \
  269         {                                                                     \
  270           __elmp = __bktp;                                                    \
  271           break;                                                              \
  272         }                                                                     \
  273       else                                                                    \
  274         __bktpp = &__bktp->next;                                              \
  275     }                                                                         \
  276                                                                               \
  277   if (!__elmp)                                                                \
  278     return NULL;                                                              \
  279   else if (__elmp->next)                                                      \
  280     return __elmp->next;                                                      \
  281   else                                                                        \
  282     return name##_HTABLE_FIRST_FROM(head, ++__bkt);                           \
  283 }
  284 
  285 #define FIRST_BKT  0
  286 
  287 #define HTABLE_INSERT(name, x, y)       name##_HTABLE_INSERT(x, y)
  288 #define HTABLE_REMOVE(name, x, y)       name##_HTABLE_REMOVE(x, y)
  289 #define HTABLE_LOOKUP(name, x, y)       name##_HTABLE_LOOKUP(x, y)
  290 #define HTABLE_FIRST_FROM(name, x, y)   (HTABLE_EMPTY(x) ? NULL               \
  291                                          : name##_HTABLE_FIRST_FROM(x, y))
  292 #define HTABLE_FIRST(name, x)           HTABLE_FIRST_FROM(name, x, FIRST_BKT)
  293 #define HTABLE_NEXT(name, x, y)         (HTABLE_EMPTY(x) ? NULL               \
  294                                          : name##_HTABLE_NEXT(x, y))
  295 
  296 #define HTABLE_FOREACH(x, name, head)                                         \
  297   for ((x) = HTABLE_FIRST(name, head);                                        \
  298        (x) != NULL;                                                           \
  299        (x) = HTABLE_NEXT(name, head, x))
  300 
  301 /*
  302  * Hash functions.
  303  */
  304 #ifdef HASH_FUNCTION
  305 #define HTABLE_HASH HASH_FUNCTION
  306 #else
  307 #define HTABLE_HASH HASH_JEN
  308 #endif
  309 
  310 #define HASH_JEN_MIX(a, b, c) do {                                            \
  311   a -= b; a -= c; a ^= (c >> 13);                                             \
  312   b -= c; b -= a; b ^= (a << 8);                                              \
  313   c -= a; c -= b; c ^= (b >> 13);                                             \
  314   a -= b; a -= c; a ^= (c >> 12);                                             \
  315   b -= c; b -= a; b ^= (a << 16);                                             \
  316   c -= a; c -= b; c ^= (b >> 5);                                              \
  317   a -= b; a -= c; a ^= (c >> 3);                                              \
  318   b -= c; b -= a; b ^= (a << 10);                                             \
  319   c -= a; c -= b; c ^= (b >> 15);                                             \
  320 } while (0)
  321 
  322 #define HASH_JEN(key, keylen, num_bkts, bkt) do {                             \
  323   register uint32_t i, j, k, hash;                                            \
  324                                                                               \
  325   hash = 0xfeedbeef;                                                          \
  326   i = j = 0x9e3779b9;                                                         \
  327   k = keylen;                                                                 \
  328   while (k >= 12)                                                             \
  329     {                                                                         \
  330       i += (key[0] + ((unsigned)key[1] << 8)                                  \
  331             + ((unsigned)key[2] << 16)                                        \
  332             + ((unsigned)key[3] << 24));                                      \
  333       j += (key[4] + ((unsigned)key[5] << 8)                                  \
  334             + ((unsigned)key[6] << 16)                                        \
  335             + ((unsigned)key[7] << 24 ));                                     \
  336       hash += (key[8] + ((unsigned)key[9] << 8)                               \
  337                + ((unsigned)key[10] << 16)                                    \
  338                + ((unsigned)key[11] << 24));                                  \
  339                                                                               \
  340       HASH_JEN_MIX (i, j, hash);                                              \
  341                                                                               \
  342       key += 12;                                                              \
  343       k -= 12;                                                                \
  344     }                                                                         \
  345   hash += keylen;                                                             \
  346   switch (k)                                                                  \
  347     {                                                                         \
  348     case 11:                                                                  \
  349       hash += ((unsigned)key[10] << 24);                                      \
  350     case 10:                                                                  \
  351       hash += ((unsigned)key[9] << 16);                                       \
  352     case 9:                                                                   \
  353       hash += ((unsigned)key[8] << 8);                                        \
  354     case 8:                                                                   \
  355       j += ((unsigned)key[7] << 24);                                          \
  356     case 7:                                                                   \
  357       j += ((unsigned)key[6] << 16);                                          \
  358     case 6:                                                                   \
  359       j += ((unsigned)key[5] << 8);                                           \
  360     case 5:                                                                   \
  361       j += key[4];                                                            \
  362     case 4:                                                                   \
  363       i += ((unsigned)key[3] << 24);                                          \
  364     case 3:                                                                   \
  365       i += ((unsigned)key[2] << 16);                                          \
  366     case 2:                                                                   \
  367       i += ((unsigned)key[1] << 8);                                           \
  368     case 1:                                                                   \
  369       i += key[0];                                                            \
  370     }                                                                         \
  371   HASH_JEN_MIX (i, j, hash);                                                  \
  372   bkt = hash % (num_bkts);                                                    \
  373 } while (0)
  374 
  375 #define HASH_OAT(key, keylen, num_bkts, bkt) do {                             \
  376   register uint32_t hash;                                                     \
  377   int i;                                                                      \
  378                                                                               \
  379   hash = 0;                                                                   \
  380   for (i = 0; i < keylen; i++)                                                \
  381     {                                                                         \
  382       hash += key[i];                                                         \
  383       hash += (hash << 10);                                                   \
  384       hash ^= (hash >> 6);                                                    \
  385     }                                                                         \
  386   hash += (hash << 3);                                                        \
  387   hash ^= (hash >> 11);                                                       \
  388   hash += (hash << 15);                                                       \
  389   bkt = hash % (num_bkts);                                                    \
  390 } while (0)
  391 
  392 #endif /* !HTABLE_H */