add support for 3d scenes, depth testing, lighting
[chaz/rasterize] / 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
This page took 0.043473 seconds and 4 git commands to generate.