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 Levonstatic 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 Levonstatic 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 Levonstatic 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 Levonstatic 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