Dogcows Code - chaz/rasterize/blob - map.h

   1
   2 /*
   3  * CS5600 University of Utah
   4  * Charles McGarvey
   5  * mcgarvey@eng.utah.edu
   6  */
   7
   8 #ifndef _MAP_H_
   9 #define _MAP_H_
  10
  11 #include "rbtree.h"
  12
  13
  14 /*
  15  * An associative array backed by a red-black tree.
  16  */
  17 typedef rbtree_t map_t;
  18
  19
  20 /*
  21  * These macros generate the code that can be used for type-safe interaction
  22  * with the red-black tree.  The interface is like an associative array.
  23  * There are different macros for generating the declarations and definitions
  24  * separately or together, depending on which module(s) you want the static
  25  * code to be.  To create a map, you need to specify at least the type of the
  26  * key and the type of the value.  You may also need to specify a namespace
  27  * and a comparison statement (especially if the key isn't a primitive number
  28  * type).
  29  */
  30
  31
  32 #define DECLARE_MAP_TYPE(K, V) DECLARE_MAP_TYPE(K##_t, V##_t, K##_##V)
  33 #define DECLARE_MAP_TYPE2(K, V, N) \
  34 int map_##N##_search_fn(rbtree_node_t** np, void* data); \
  35 typedef struct map_##N##_data \
  36 { \
  37     const K key; \
  38     V   val; \
  39 } map_##N##_data_t; \
  40 INLINE_MAYBE map_t* map_##N##_alloc() \
  41 { \
  42     return rbtree_alloc(sizeof(map_##N##_data_t), map_##N##_search_fn); \
  43 } \
  44 INLINE_MAYBE map_##N##_data_t* \
  45 map_##N##_insert(map_t* m, K k, V v) \
  46 { \
  47     map_##N##_data_t d = {k, v}; \
  48     rbtree_node_t* n = rbtree_insert(m, &d); \
  49     if (!n) return NULL; \
  50     return (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
  51 } \
  52 INLINE_MAYBE V* \
  53 map_##N##_delete(map_t* m, K k) \
  54 { \
  55     rbtree_node_t* n = rbtree_delete(m, &k); \
  56     if (!n) return NULL; \
  57     map_##N##_data_t* dp = (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
  58     return &(dp->val); \
  59 } \
  60 INLINE_MAYBE V* \
  61 map_##N##_search(map_t* m, K k) \
  62 { \
  63     rbtree_node_t* n = rbtree_search(m, &k); \
  64     if (!n) return NULL; \
  65     map_##N##_data_t* dp = (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
  66     return &(dp->val); \
  67 } \
  68 typedef void (*map_##N##_call_fn_t)(const K* k, V* v); \
  69 INLINE_MAYBE void \
  70 map_##N##_call_recurse(rbtree_node_t* n, map_##N##_call_fn_t fn) \
  71 { \
  72     if (n == rbtree_sentinel) return; \
  73     map_##N##_call_recurse(n->left, fn); \
  74     map_##N##_data_t* d = RBTREE_NODE_DATA(n); \
  75     fn(&d->key, &d->val); \
  76     map_##N##_call_recurse(n->right, fn); \
  77 } \
  78 INLINE_MAYBE void \
  79 map_##N##_call(const map_t* t, map_##N##_call_fn_t fn) \
  80 { \
  81     map_##N##_call_recurse(t->root, fn); \
  82 }
  83
  84
  85 #define DEFINE_MAP_TYPE(K, V) DEFINE_MAP_TYPE2(K##_t, V##_t, K##_##V)
  86 #define DEFINE_MAP_TYPE2(K, V, N) DEFINE_MAP_TYPE3(K, V, N, *a - *b)
  87 #define DEFINE_MAP_TYPE3(K, V, N, C) \
  88 int map_##N##_search_fn(rbtree_node_t** np, void* data) \
  89 { \
  90     K* a = (K*)data; \
  91     rbtree_node_t* n = *np; \
  92     int c = -1; \
  93     while (n != rbtree_sentinel) \
  94     { \
  95         K* b = (K*)RBTREE_NODE_DATA(n); \
  96         *np = n; \
  97         c = (C); \
  98         if (c == 0) break; \
  99         else if (c < 0) n = n->left; \
 100         else n = n->right; \
 101     } \
 102     return c; \
 103 }
 104
 105
 106 #define DECLARE_AND_DEFINE_MAP_TYPE(K, V) \
 107     DECLARE_MAP_TYPE(K, V) \
 108     DEFINE_MAP_TYPE(K, V)
 109
 110 #define DECLARE_AND_DEFINE_MAP_TYPE2(K, V, N) \
 111     DECLARE_MAP_TYPE2(K, V, N) \
 112     DEFINE_MAP_TYPE2(K, V, N)
 113
 114 #define DECLARE_AND_DEFINE_MAP_TYPE3(K, V, N, C) \
 115     DECLARE_MAP_TYPE2(K, V, N) \
 116     DEFINE_MAP_TYPE3(K, V, N, C)
 117
 118
 119 #endif // _MAP_H_
 120