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)27static inline void sset_reset(struct sset *s) 28 { 29 s->nbr = 0; 30 } 31 sset_add(struct sset * s,unsigned int idx)32static 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)40static 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)48static 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