X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Frasterize;a=blobdiff_plain;f=map.h;fp=map.h;h=9b408b045ac708963e7cab387ce0ad30a44b3203;hp=0000000000000000000000000000000000000000;hb=c875478cdd823c7df8fdc859941bd9e5948c9315;hpb=82087d9bb9e28c2375008bde4453f6c019419697

diff --git a/map.h b/map.h
new file mode 100644
index 0000000..9b408b0
--- /dev/null
+++ b/map.h
@@ -0,0 +1,120 @@
+
+/*
+ * CS5600 University of Utah
+ * Charles McGarvey
+ * mcgarvey@eng.utah.edu
+ */
+
+#ifndef _MAP_H_
+#define _MAP_H_
+
+#include "rbtree.h"
+
+
+/*
+ * An associative array backed by a red-black tree.
+ */
+typedef rbtree_t map_t;
+
+
+/*
+ * These macros generate the code that can be used for type-safe interaction
+ * with the red-black tree.  The interface is like an associative array.
+ * There are different macros for generating the declarations and definitions
+ * separately or together, depending on which module(s) you want the static
+ * code to be.  To create a map, you need to specify at least the type of the
+ * key and the type of the value.  You may also need to specify a namespace
+ * and a comparison statement (especially if the key isn't a primitive number
+ * type).
+ */
+
+
+#define DECLARE_MAP_TYPE(K, V) DECLARE_MAP_TYPE(K##_t, V##_t, K##_##V)
+#define DECLARE_MAP_TYPE2(K, V, N) \
+int map_##N##_search_fn(rbtree_node_t** np, void* data); \
+typedef struct map_##N##_data \
+{ \
+    const K key; \
+    V   val; \
+} map_##N##_data_t; \
+INLINE_MAYBE map_t* map_##N##_alloc() \
+{ \
+    return rbtree_alloc(sizeof(map_##N##_data_t), map_##N##_search_fn); \
+} \
+INLINE_MAYBE map_##N##_data_t* \
+map_##N##_insert(map_t* m, K k, V v) \
+{ \
+    map_##N##_data_t d = {k, v}; \
+    rbtree_node_t* n = rbtree_insert(m, &d); \
+    if (!n) return NULL; \
+    return (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
+} \
+INLINE_MAYBE V* \
+map_##N##_delete(map_t* m, K k) \
+{ \
+    rbtree_node_t* n = rbtree_delete(m, &k); \
+    if (!n) return NULL; \
+    map_##N##_data_t* dp = (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
+    return &(dp->val); \
+} \
+INLINE_MAYBE V* \
+map_##N##_search(map_t* m, K k) \
+{ \
+    rbtree_node_t* n = rbtree_search(m, &k); \
+    if (!n) return NULL; \
+    map_##N##_data_t* dp = (map_##N##_data_t*)RBTREE_NODE_DATA(n); \
+    return &(dp->val); \
+} \
+typedef void (*map_##N##_call_fn_t)(const K* k, V* v); \
+INLINE_MAYBE void \
+map_##N##_call_recurse(rbtree_node_t* n, map_##N##_call_fn_t fn) \
+{ \
+    if (n == rbtree_sentinel) return; \
+    map_##N##_call_recurse(n->left, fn); \
+    map_##N##_data_t* d = RBTREE_NODE_DATA(n); \
+    fn(&d->key, &d->val); \
+    map_##N##_call_recurse(n->right, fn); \
+} \
+INLINE_MAYBE void \
+map_##N##_call(const map_t* t, map_##N##_call_fn_t fn) \
+{ \
+    map_##N##_call_recurse(t->root, fn); \
+}
+
+
+#define DEFINE_MAP_TYPE(K, V) DEFINE_MAP_TYPE2(K##_t, V##_t, K##_##V)
+#define DEFINE_MAP_TYPE2(K, V, N) DEFINE_MAP_TYPE3(K, V, N, *a - *b)
+#define DEFINE_MAP_TYPE3(K, V, N, C) \
+int map_##N##_search_fn(rbtree_node_t** np, void* data) \
+{ \
+    K* a = (K*)data; \
+    rbtree_node_t* n = *np; \
+    int c = -1; \
+    while (n != rbtree_sentinel) \
+    { \
+        K* b = (K*)RBTREE_NODE_DATA(n); \
+        *np = n; \
+        c = (C); \
+        if (c == 0) break; \
+        else if (c < 0) n = n->left; \
+        else n = n->right; \
+    } \
+    return c; \
+}
+
+
+#define DECLARE_AND_DEFINE_MAP_TYPE(K, V) \
+    DECLARE_MAP_TYPE(K, V) \
+    DEFINE_MAP_TYPE(K, V)
+
+#define DECLARE_AND_DEFINE_MAP_TYPE2(K, V, N) \
+    DECLARE_MAP_TYPE2(K, V, N) \
+    DEFINE_MAP_TYPE2(K, V, N)
+
+#define DECLARE_AND_DEFINE_MAP_TYPE3(K, V, N, C) \
+    DECLARE_MAP_TYPE2(K, V, N) \
+    DEFINE_MAP_TYPE3(K, V, N, C)
+
+
+#endif // _MAP_H_
+