LCOV - code coverage report
Current view: top level - lib/generic - map.c Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 171 185 92.4 %
Date: 2019-03-12 03:31:59
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * critbit89 - A crit-bit tree implementation for strings in C89
       3             :  * Written by Jonas Gehring <jonas@jgehring.net>
       4             :  * Implemented key-value storing by Marek Vavrusa <marek.vavrusa@nic.cz>
       5             :  *
       6             :  * The code makes the assumption that malloc returns pointers aligned at at
       7             :  * least a two-byte boundary. Since the C standard requires that malloc return
       8             :  * pointers that can store any type, there are no commonly-used toolchains for
       9             :  * which this assumption is false.
      10             :  *
      11             :  * See https://github.com/agl/critbit/blob/master/critbit.pdf for reference.
      12             :  */
      13             : 
      14             : #include <errno.h>
      15             : #include <string.h>
      16             : #include <stdlib.h>
      17             : 
      18             : #include "map.h"
      19             : #include "lib/utils.h"
      20             : 
      21             :  /* Exports */
      22             : #if defined _WIN32 || defined __CYGWIN__
      23             :   #define EXPORT __attribute__ ((dllexport))
      24             : #else
      25             :   #define EXPORT __attribute__ ((visibility ("default")))
      26             : #endif
      27             : 
      28             : #ifdef _MSC_VER /* MSVC */
      29             :  typedef unsigned __int8 uint8_t;
      30             :  typedef unsigned __int32 uint32_t;
      31             :  #ifdef _WIN64
      32             :   typedef signed __int64 intptr_t;
      33             :  #else
      34             :   typedef _W64 signed int intptr_t;
      35             :  #endif
      36             : #else /* Not MSVC */
      37             :  #include <stdint.h>
      38             : #endif
      39             : 
      40             : typedef struct {
      41             :         void* value;
      42             :         uint8_t key[];
      43             : } cb_data_t;
      44             : 
      45             : typedef struct {
      46             :         void *child[2];
      47             :         uint32_t byte;
      48             :         uint8_t otherbits;
      49             : } cb_node_t;
      50             : 
      51             : /* Return true if ptr is internal node. */
      52       76093 : static inline int ref_is_internal(const uint8_t *p)
      53             : {
      54      210504 :         return 1 & (intptr_t)p;
      55             : }
      56             : 
      57             : /* Get internal node. */
      58        4098 : static inline cb_node_t *ref_get_internal(uint8_t *p)
      59             : {
      60        5067 :         return (cb_node_t *)(p - 1);
      61             : }
      62             : 
      63             : /* Static helper functions */
      64         611 : static void cbt_traverse_delete(map_t *map, void *top)
      65             : {
      66          10 :         uint8_t *p = top;
      67         611 :         if (ref_is_internal(p)) {
      68           0 :                 cb_node_t *q = ref_get_internal(p);
      69         299 :                 cbt_traverse_delete(map, q->child[0]);
      70         299 :                 cbt_traverse_delete(map, q->child[1]);
      71         299 :                 mm_free(map->pool, q);
      72             :         } else {
      73         312 :                 mm_free(map->pool, p);
      74             :         }
      75         611 : }
      76             : 
      77        7104 : static int cbt_traverse_prefixed(void *top,
      78             :         int (*callback)(const char *, void *, void *), void *baton)
      79             : {
      80          16 :         uint8_t *p = top;
      81          16 :         cb_data_t *x = (cb_data_t *)top;
      82             : 
      83        7104 :         if (ref_is_internal(p)) {
      84           0 :                 cb_node_t *q = ref_get_internal(p);
      85           0 :                 int ret = 0;
      86             : 
      87        3540 :                 ret = cbt_traverse_prefixed(q->child[0], callback, baton);
      88        3540 :                 if (ret != 0) {
      89           0 :                         return ret;
      90             :                 }
      91        3540 :                 ret = cbt_traverse_prefixed(q->child[1], callback, baton);
      92        3540 :                 if (ret != 0) {
      93           0 :                         return ret;
      94             :                 }
      95        3540 :                 return 0;
      96             :         }
      97             : 
      98        3564 :         return (callback)((const char *)x->key, x->value, baton);
      99             : }
     100             : 
     101        3565 : static cb_data_t *cbt_make_data(map_t *map, const uint8_t *str, size_t len, void *value)
     102             : {
     103        3565 :         cb_data_t *x = mm_alloc(map->pool, sizeof(cb_data_t) + len);
     104        3565 :         if (x != NULL) {
     105        3565 :                 x->value = value;
     106        3565 :                 memcpy(x->key, str, len);
     107             :         }
     108        3565 :         return x;
     109             : }
     110             : 
     111             : /*! Like map_contains, but also set the value, if passed and found. */
     112      148010 : static int cbt_get(map_t *map, const char *str, void **value)
     113             : {
     114      142033 :         const uint8_t *ubytes = (void *)str;
     115      148010 :         const size_t ulen = strlen(str);
     116      148010 :         uint8_t *p = map->root;
     117      142033 :         cb_data_t *x = NULL;
     118             : 
     119      148010 :         if (p == NULL) {
     120       70657 :                 return 0;
     121             :         }
     122             : 
     123      131872 :         while (ref_is_internal(p)) {
     124        2349 :                 cb_node_t *q = ref_get_internal(p);
     125        2349 :                 uint8_t c = 0;
     126             :                 int direction;
     127             : 
     128       55029 :                 if (q->byte < ulen) {
     129       55025 :                         c = ubytes[q->byte];
     130             :                 }
     131       55029 :                 direction = (1 + (q->otherbits | c)) >> 8;
     132             : 
     133       55029 :                 p = q->child[direction];
     134             :         }
     135             : 
     136       71376 :         x = (cb_data_t *)p;
     137       76843 :         if (strcmp(str, (const char *)x->key) == 0) {
     138       26030 :                 if (value != NULL) {
     139       26030 :                         *value = x->value;
     140             :                 }
     141       23991 :                 return 1;
     142             :         }
     143             : 
     144       47385 :         return 0;
     145             : }
     146             : 
     147             : /*! Returns non-zero if map contains str */
     148         605 : EXPORT int map_contains(map_t *map, const char *str)
     149             : {
     150         605 :         return cbt_get(map, str, NULL);
     151             : }
     152             : 
     153      147616 : EXPORT void *map_get(map_t *map, const char *str)
     154             : {
     155      147616 :         void *v = NULL;
     156      147616 :         cbt_get(map, str, &v);
     157      147616 :         return v;
     158             : }
     159             : 
     160        4080 : EXPORT int map_set(map_t *map, const char *str, void *val)
     161             : {
     162         209 :         const uint8_t *const ubytes = (void *)str;
     163        4080 :         const size_t ulen = strlen(str);
     164        4080 :         uint8_t *p = map->root;
     165         209 :         uint8_t c = 0, *x = NULL;
     166         209 :         uint32_t newbyte = 0;
     167         209 :         uint32_t newotherbits = 0;
     168         209 :         int direction = 0, newdirection = 0;
     169         209 :         cb_node_t *newnode = NULL;
     170         209 :         cb_data_t *data = NULL;
     171         209 :         void **wherep = NULL;
     172             : 
     173        4080 :         if (p == NULL) {
     174          45 :                 map->root = cbt_make_data(map, (const uint8_t *)str, ulen + 1, val);
     175          45 :                 if (map->root == NULL) {
     176           0 :                         return ENOMEM;
     177             :                 }
     178          44 :                 return 0;
     179             :         }
     180             : 
     181       35986 :         while (ref_is_internal(p)) {
     182         521 :                 cb_node_t *q = ref_get_internal(p);
     183         521 :                 c = 0;
     184       31951 :                 if (q->byte < ulen) {
     185       31946 :                         c = ubytes[q->byte];
     186             :                 }
     187       31951 :                 direction = (1 + (q->otherbits | c)) >> 8;
     188             : 
     189       31951 :                 p = q->child[direction];
     190             :         }
     191             : 
     192         183 :         data = (cb_data_t *)p;
     193       67154 :         for (newbyte = 0; newbyte < ulen; ++newbyte) {
     194       70395 :                 if (data->key[newbyte] != ubytes[newbyte]) {
     195        3925 :                         newotherbits = data->key[newbyte] ^ ubytes[newbyte];
     196        3925 :                         goto different_byte_found;
     197             :                 }
     198             :         }
     199             : 
     200         110 :         if (data->key[newbyte] != 0) {
     201           1 :                 newotherbits = data->key[newbyte];
     202           1 :                 goto different_byte_found;
     203             :         }
     204         109 :         data->value = val;
     205         109 :         return 1;
     206             : 
     207         584 : different_byte_found:
     208        3926 :         newotherbits |= newotherbits >> 1;
     209        3926 :         newotherbits |= newotherbits >> 2;
     210        3926 :         newotherbits |= newotherbits >> 4;
     211        3926 :         newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;
     212        3926 :         c = data->key[newbyte];
     213        3926 :         newdirection = (1 + (newotherbits | c)) >> 8;
     214             : 
     215        3926 :         newnode = mm_alloc(map->pool, sizeof(cb_node_t));
     216        3926 :         if (newnode == NULL) {
     217           0 :                 return ENOMEM;
     218             :         }
     219             : 
     220        3926 :         x = (uint8_t *)cbt_make_data(map, ubytes, ulen + 1, val);
     221        3926 :         if (x == NULL) {
     222           0 :                 mm_free(map->pool, newnode);
     223           0 :                 return ENOMEM;
     224             :         }
     225             : 
     226        3926 :         newnode->byte = newbyte;
     227        3926 :         newnode->otherbits = newotherbits;
     228        3926 :         newnode->child[1 - newdirection] = x;
     229             : 
     230             :         /* Insert into map */
     231        3926 :         wherep = &map->root;
     232       29140 :         for (;;) {
     233             :                 cb_node_t *q;
     234       33066 :                 p = *wherep;
     235       33066 :                 if (!ref_is_internal(p)) {
     236         119 :                         break;
     237             :                 }
     238             : 
     239         498 :                 q = ref_get_internal(p);
     240       30174 :                 if (q->byte > newbyte) {
     241          36 :                         break;
     242             :                 }
     243       29561 :                 if (q->byte == newbyte && q->otherbits > newotherbits) {
     244          28 :                         break;
     245             :                 }
     246             : 
     247         434 :                 c = 0;
     248       29140 :                 if (q->byte < ulen) {
     249       29140 :                         c = ubytes[q->byte];
     250             :                 }
     251       29140 :                 direction = (1 + (q->otherbits | c)) >> 8;
     252       29140 :                 wherep = q->child + direction;
     253             :         }
     254             : 
     255        3926 :         newnode->child[newdirection] = *wherep;
     256        3926 :         *wherep = (void *)(1 + (char *)newnode);
     257        3926 :         return 0;
     258             : }
     259             : 
     260             : /*! Deletes str from the map, returns 0 on success */
     261         389 : EXPORT int map_del(map_t *map, const char *str)
     262             : {
     263         278 :         const uint8_t *ubytes = (void *)str;
     264         389 :         const size_t ulen = strlen(str);
     265         389 :         uint8_t *p = map->root;
     266         278 :         void **wherep = NULL, **whereq = NULL;
     267         278 :         cb_node_t *q = NULL;
     268         278 :         cb_data_t *data = NULL;
     269         278 :         int direction = 0;
     270             : 
     271         389 :         if (map->root == NULL) {
     272           3 :                 return 1;
     273             :         }
     274         385 :         wherep = &map->root;
     275             : 
     276        1790 :         while (ref_is_internal(p)) {
     277         730 :                 uint8_t c = 0;
     278         730 :                 whereq = wherep;
     279         730 :                 q = ref_get_internal(p);
     280             : 
     281        1400 :                 if (q->byte < ulen) {
     282        1400 :                         c = ubytes[q->byte];
     283             :                 }
     284        1400 :                 direction = (1 + (q->otherbits | c)) >> 8;
     285        1400 :                 wherep = q->child + direction;
     286        1400 :                 p = *wherep;
     287             :         }
     288             : 
     289         275 :         data = (cb_data_t *)p;
     290         385 :         if (strcmp(str, (const char *)data->key) != 0) {
     291          76 :                 return 1;
     292             :         }
     293         307 :         mm_free(map->pool, p);
     294             : 
     295         307 :         if (!whereq) {
     296          22 :                 map->root = NULL;
     297          22 :                 return 0;
     298             :         }
     299             : 
     300         285 :         *whereq = q->child[1 - direction];
     301         285 :         mm_free(map->pool, q);
     302         285 :         return 0;
     303             : }
     304             : 
     305             : /*! Clears the given map */
     306          38 : EXPORT void map_clear(map_t *map)
     307             : {
     308          38 :         if (map->root) {
     309          13 :                 cbt_traverse_delete(map, map->root);
     310             :         }
     311          38 :         map->root = NULL;
     312          38 : }
     313             : 
     314             : /*! Calls callback for all strings in map with the given prefix */
     315          64 : EXPORT int map_walk_prefixed(map_t *map, const char *prefix,
     316             :         int (*callback)(const char *, void *, void *), void *baton)
     317             : {
     318          64 :         if (!map) {
     319           0 :                 return 0;
     320             :         }
     321             : 
     322          20 :         const uint8_t *ubytes = (void *)prefix;
     323          64 :         const size_t ulen = strlen(prefix);
     324          64 :         uint8_t *p = map->root;
     325          20 :         uint8_t *top = p;
     326          20 :         cb_data_t *data = NULL;
     327             : 
     328          64 :         if (p == NULL) {
     329           4 :                 return 0;
     330             :         }
     331             : 
     332          80 :         while (ref_is_internal(p)) {
     333           0 :                 cb_node_t *q = ref_get_internal(p);
     334           0 :                 uint8_t c = 0;
     335             :                 int direction;
     336             : 
     337          54 :                 if (q->byte < ulen) {
     338          12 :                         c = ubytes[q->byte];
     339             :                 }
     340          54 :                 direction = (1 + (q->otherbits | c)) >> 8;
     341             : 
     342          54 :                 p = q->child[direction];
     343          54 :                 if (q->byte < ulen) {
     344           0 :                         top = p;
     345             :                 }
     346             :         }
     347             : 
     348          16 :         data = (cb_data_t *)p;
     349          26 :         if (strlen((const char *)data->key) < ulen || memcmp(data->key, prefix, ulen) != 0) {
     350           0 :                 return 0; /* No strings match */
     351             :         }
     352             : 
     353          24 :         return cbt_traverse_prefixed(top, callback, baton);
     354             : }

Generated by: LCOV version 1.13