1 files changed, 56 insertions, 0 deletions
diff --git a/usr/src/tools/smatch/src/sset.h b/usr/src/tools/smatch/src/sset.h
new file mode 100644
index 0000000000..69cee18a27
--- /dev/null
+++ b/usr/src/tools/smatch/src/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