Sparse set implements set operations like add, remove & test in O(1).
More importantly it also allow to reset the set as a whole in O(1).
It's very handy for a few things.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
Makefile | 1 +
sset.c | 28 ++++++++++++++++++++++++++++
sset.h | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 85 insertions(+)
create mode 100644 sset.c
create mode 100644 sset.h
diff --git a/Makefile b/Makefile
index 329e792ff..dae6a07b1 100644
--- a/Makefile
+++ b/Makefile
@@ -56,6 +56,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 000000000..e9681e00d
--- /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 000000000..69cee18a2
--- /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
--
2.16.2
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
