xref: /illumos-gate/usr/src/tools/smatch/src/sset.h (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
1 // SPDX-License-Identifier: MIT
2 
3 #ifndef SSET_H
4 #define SSET_H
5 
6 /*
7  * sset.h - an all O(1) implementation of sparse sets as presented in:
8  *	"An Efficient Representation for Sparse Sets"
9  *	by Preston Briggs and Linda Torczon
10  *
11  * Copyright (C) 2017 - Luc Van Oostenryck
12  */
13 
14 #include <stdbool.h>
15 
16 struct sset {
17 	unsigned int nbr;
18 	unsigned int off;
19 	unsigned int size;
20 	unsigned int sets[0];
21 };
22 
23 extern struct sset *sset_init(unsigned int size, unsigned int off);
24 extern void sset_free(struct sset *s);
25 
26 
sset_reset(struct sset * s)27 static inline void sset_reset(struct sset *s)
28 {
29 	s->nbr = 0;
30 }
31 
sset_add(struct sset * s,unsigned int idx)32 static inline void sset_add(struct sset *s, unsigned int idx)
33 {
34 	unsigned int __idx = idx - s->off;
35 	unsigned int n = s->nbr++;
36 	s->sets[__idx] = n;
37 	s->sets[s->size + n] = __idx;
38 }
39 
sset_test(struct sset * s,unsigned int idx)40 static inline bool sset_test(struct sset *s, unsigned int idx)
41 {
42 	unsigned int __idx = idx - s->off;
43 	unsigned int n = s->sets[__idx];
44 
45 	return (n < s->nbr) && (s->sets[s->size + n] == __idx);
46 }
47 
sset_testset(struct sset * s,unsigned int idx)48 static inline bool sset_testset(struct sset *s, unsigned int idx)
49 {
50 	if (sset_test(s, idx))
51 		return true;
52 	sset_add(s, idx);
53 	return false;
54 }
55 
56 #endif
57