3 files changed, 85 insertions, 0 deletions
diff --git a/Makefile b/Makefile
index d27ecda1..256fd329 100644
--- a/Makefile
+++ b/Makefile
@@ -57,6 +57,7 @@ LIB_OBJS += scope.o
 LIB_OBJS += show-parse.o
 LIB_OBJS += simplify.o
 LIB_OBJS += sort.o
+LIB_OBJS += sset.o
 LIB_OBJS += stats.o
 LIB_OBJS += storage.o
 LIB_OBJS += symbol.o
diff --git a/sset.c b/sset.c
new file mode 100644
index 00000000..e9681e00
--- /dev/null
+++ b/sset.c
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: MIT
+//
+// sset.c - an all O(1) implementation of sparse sets as presented in:
+//	"An Efficient Representation for Sparse Sets"
+//	by Preston Briggs and Linda Torczon
+//
+// Copyright (C) 2017 - Luc Van Oostenryck
+
+#include "sset.h"
+#include "lib.h"
+#include <stdlib.h>
+
+
+struct sset *sset_init(unsigned int first, unsigned int last)
+{
+	unsigned int size = last - first + 1;
+	struct sset *s = malloc(sizeof(*s) + size * 2 * sizeof(s->sets[0]));
+
+	s->size = size;
+	s->off = first;
+	s->nbr = 0;
+	return s;
+}
+
+void sset_free(struct sset *s)
+{
+	free(s);
+}
diff --git a/sset.h b/sset.h
new file mode 100644
index 00000000..69cee18a
--- /dev/null
+++ b/sset.h
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: MIT
+
+#ifndef SSET_H
+#define SSET_H
+
+/*
+ * sset.h - an all O(1) implementation of sparse sets as presented in:
+ *	"An Efficient Representation for Sparse Sets"
+ *	by Preston Briggs and Linda Torczon
+ *
+ * Copyright (C) 2017 - Luc Van Oostenryck
+ */
+
+#include <stdbool.h>
+
+struct sset {
+	unsigned int nbr;
+	unsigned int off;
+	unsigned int size;
+	unsigned int sets[0];
+};
+
+extern struct sset *sset_init(unsigned int size, unsigned int off);
+extern void sset_free(struct sset *s);
+
+
+static inline void sset_reset(struct sset *s)
+{
+	s->nbr = 0;
+}
+
+static inline void sset_add(struct sset *s, unsigned int idx)
+{
+	unsigned int __idx = idx - s->off;
+	unsigned int n = s->nbr++;
+	s->sets[__idx] = n;
+	s->sets[s->size + n] = __idx;
+}
+
+static inline bool sset_test(struct sset *s, unsigned int idx)
+{
+	unsigned int __idx = idx - s->off;
+	unsigned int n = s->sets[__idx];
+
+	return (n < s->nbr) && (s->sets[s->size + n] == __idx);
+}
+
+static inline bool sset_testset(struct sset *s, unsigned int idx)
+{
+	if (sset_test(s, idx))
+		return true;
+	sset_add(s, idx);
+	return false;
+}
+
+#endif