sset.h

   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
  27 static inline void sset_reset(struct sset *s)
  28 {
  29         s->nbr = 0;
  30 }
  31
  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
  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
  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