]>
Dogcows Code - chaz/rasterize/blob - map.h
3 * CS5600 University of Utah
5 * mcgarvey@eng.utah.edu
15 * An associative array backed by a red-black tree.
17 typedef rbtree_t map_t
;
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
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 \
41 int map_##N##_search_fn(rbtree_node_t** np, void* data) \
44 rbtree_node_t* n = *np; \
46 while (n != rbtree_sentinel) \
48 K* b = (K*)RBTREE_NODE_DATA(n); \
52 else if (c < 0) n = n->left; \
58 map_t* map_##N##_alloc() \
60 return rbtree_alloc(sizeof(map_##N##_data_t), map_##N##_search_fn); \
63 map_##N##_data_t* map_##N##_insert(map_t* m, K k, V v) \
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); \
71 V* map_##N##_delete(map_t* m, K k) \
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); \
79 V* map_##N##_search(map_t* m, K k) \
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); \
86 typedef void (*map_##N##_call_fn_t)(const K* k, V* v); \
88 void map_##N##_call_recurse(rbtree_node_t* n, map_##N##_call_fn_t fn) \
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); \
97 void map_##N##_call(const map_t* t, map_##N##_call_fn_t fn) \
99 map_##N##_call_recurse(t->root, fn); \
This page took 0.038811 seconds and 4 git commands to generate.