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 DEFINE_MAP_TYPE(K, V) DEFINE_MAP_TYPE2(K##_t, V##_t, K##_##V)
  33 #define DEFINE_MAP_TYPE2(K, V, N) DEFINE_MAP_TYPE3(K, V, N, *a - *b)
  34 #define DEFINE_MAP_TYPE3(K, V, N, C) \
  35 typedef struct map_##N##_data \
  36 { \
  37     const K key; \
  38     V   val; \
  39 } map_##N##_data_t; \
  40 INLINE_MAYBE \
  41 int map_##N##_search_fn(rbtree_node_t** np, void* data) \
  42 { \
  43     K* a = (K*)data; \
  44     rbtree_node_t* n = *np; \
  45     int c = -1; \
  46     while (n != rbtree_sentinel) \
  47     { \
  48         K* b = (K*)RBTREE_NODE_DATA(n); \
  49         *np = n; \
  50         c = (C); \
  51         if (c == 0) break; \
  52         else if (c < 0) n = n->left; \
  53         else n = n->right; \
  54     } \
  55     return c; \
  56 } \
  57 INLINE_MAYBE \
  58 map_t* map_##N##_alloc() \
  59 { \
  60     return rbtree_alloc(sizeof(map_##N##_data_t), map_##N##_search_fn); \
  61 } \
  62 INLINE_MAYBE \
  63 map_##N##_data_t* map_##N##_insert(map_t* m, K k, V v) \
  64 { \
  65     map_##N##_data_t d = {k, v}; \
  66     rbtree_node_t* n = rbtree_insert(m, &d); \
  67     if (!n) return NULL; \
  68     return (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
  69 } \
  70 INLINE_MAYBE \
  71 V* map_##N##_delete(map_t* m, K k) \
  72 { \
  73     rbtree_node_t* n = rbtree_delete(m, &k); \
  74     if (!n) return NULL; \
  75     map_##N##_data_t* dp = (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
  76     return &(dp->val); \
  77 } \
  78 INLINE_MAYBE \
  79 V* map_##N##_search(map_t* m, K k) \
  80 { \
  81     rbtree_node_t* n = rbtree_search(m, &k); \
  82     if (!n) return NULL; \
  83     map_##N##_data_t* dp = (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
  84     return &(dp->val); \
  85 } \
  86 typedef void (*map_##N##_call_fn_t)(const K* k, V* v); \
  87 INLINE_MAYBE \
  88 void map_##N##_call_recurse(rbtree_node_t* n, map_##N##_call_fn_t fn) \
  89 { \
  90     if (n == rbtree_sentinel) return; \
  91     map_##N##_call_recurse(n->left, fn); \
  92     map_##N##_data_t* d = RBTREE_NODE_DATA(n); \
  93     fn(&d->key, &d->val); \
  94     map_##N##_call_recurse(n->right, fn); \
  95 } \
  96 INLINE_MAYBE \
  97 void map_##N##_call(const map_t* t, map_##N##_call_fn_t fn) \
  98 { \
  99     map_##N##_call_recurse(t->root, fn); \
 100 }
 101
 102
 103 #endif // _MAP_H_
 104