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