From 1c346cdcbe0ad5f0630a0baf68eefe0c5b808804 Mon Sep 17 00:00:00 2001
From: David Given <dg@cowlark.com>
Date: Fri, 16 Dec 2016 16:45:52 +0100
Subject: [PATCH] Add a set-based hashtable; change the register allocator to
 use it for vertices.

---
 mach/proto/mcg/pass_registerallocator.c | 27 +++++++++----------
 modules/src/data/set.c                  | 36 +++++++++++++++++++++++++
 modules/src/data/set.h                  | 32 ++++++++++++++++++++++
 3 files changed, 81 insertions(+), 14 deletions(-)
 create mode 100644 modules/src/data/set.c
 create mode 100644 modules/src/data/set.h

diff --git a/mach/proto/mcg/pass_registerallocator.c b/mach/proto/mcg/pass_registerallocator.c
index 8c8678fb9..6c015cf3e 100644
--- a/mach/proto/mcg/pass_registerallocator.c
+++ b/mach/proto/mcg/pass_registerallocator.c
@@ -1,5 +1,6 @@
 #include "mcg.h"
 #include "bigraph.h"
+#include "set.h"
 #include <limits.h>
 
 /* This is based around the elegant graph colouring algorithm here:
@@ -27,7 +28,7 @@ struct vref
 static struct heap anode_heap;
 static struct graph interferenceg;
 static struct graph preferenceg;
-static ARRAYOF(struct anode) vertices;
+static struct set vertices;
 static ARRAYOF(struct anode) simplified;
 #if 0
 struct assignment
@@ -958,12 +959,15 @@ static void dump_interference_graph(void)
         }
     }
 
-    for (i=0; i<vertices.count; i++)
     {
-        struct anode* anode = vertices.item[i];
-        fprintf(regalloc_dot_file, "\t\"");
-        dump_anode(anode);
-        fprintf(regalloc_dot_file, "\" [color=green];\n");
+        struct set_iterator sit = {};
+        while (set_next(&vertices, &sit))
+        {
+            struct anode* anode = sit.item;
+            fprintf(regalloc_dot_file, "\t\"");
+            dump_anode(anode);
+            fprintf(regalloc_dot_file, "\" [color=green];\n");
+        }
     }
 
     fprintf(regalloc_dot_file, "}\n");
@@ -1060,18 +1064,18 @@ static void collect_vertices(void)
 {
     int i;
 
-    vertices.count = 0;
+    set_reset(&vertices);
 
     {
         struct vertex_iterator vit = {};
         while (graph_next_vertex(&interferenceg, &vit))
-            array_appendu(&vertices, vit.data);
+            set_add(&vertices, vit.data);
     }
 
     {
         struct vertex_iterator vit = {};
         while (graph_next_vertex(&preferenceg, &vit))
-            array_appendu(&vertices, vit.data);
+            set_add(&vertices, vit.data);
     }
 }
 
@@ -1185,11 +1189,6 @@ static void iterate(void)
 
 static void assign_registers(void)
 {
-    int i;
-    for (i=0; i<vertices.count; i++)
-    {
-        struct anode* anode = vertices.item[i];
-    }
 }
 
 void pass_register_allocator(void)
diff --git a/modules/src/data/set.c b/modules/src/data/set.c
new file mode 100644
index 000000000..9c0a87a76
--- /dev/null
+++ b/modules/src/data/set.c
@@ -0,0 +1,36 @@
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdbool.h>
+#include "set.h"
+
+void set_reset(struct set* s)
+{
+	hashtable_reset(&s->table);
+}
+
+void set_add(struct set* s, void* item)
+{
+	hashtable_put(&s->table, item, item);
+}
+
+bool set_remove(struct set* s, void* item)
+{
+	return hashtable_remove(&s->table, item);
+}
+
+bool set_contains(struct set* s, void* item)
+{
+	return hashtable_contains(&s->table, item);
+}
+
+void* set_pop(struct set* s)
+{
+	return hashtable_pop(&s->table);
+}
+
+void* set_next(struct set* s, struct set_iterator* sit)
+{
+	sit->item = hashtable_next(&s->table, &sit->hit);
+	return sit->item;
+}
+
diff --git a/modules/src/data/set.h b/modules/src/data/set.h
new file mode 100644
index 000000000..998e0035c
--- /dev/null
+++ b/modules/src/data/set.h
@@ -0,0 +1,32 @@
+#ifndef SET_H
+#define SET_H
+
+/* A hashtable-based identity set. */
+
+#include "hashtable.h"
+
+struct set
+{
+	struct hashtable table;
+};
+
+extern void set_reset(struct set* s);
+
+extern void set_add(struct set* s, void* item);
+extern bool set_remove(struct set* s, void* item);
+extern bool set_contains(struct set* s, void* item);
+extern void* set_pop(struct set* s);
+
+struct set_iterator
+{
+	/* Public */
+	void* item;
+
+	/* Private */
+	struct hashtable_iterator hit;
+};
+
+extern void* set_next(struct set* s, struct set_iterator* sit);
+
+#endif
+
-- 
2.34.1