blob: 69cee18a27688e01410337c63f323083ddf7a72e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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
|
