sset.c

   1 // SPDX-License-Identifier: MIT
   2 //
   3 // sset.c - an all O(1) implementation of sparse sets as presented in:
   4 //      "An Efficient Representation for Sparse Sets"
   5 //      by Preston Briggs and Linda Torczon
   6 //
   7 // Copyright (C) 2017 - Luc Van Oostenryck
   8
   9 #include "sset.h"
  10 #include "lib.h"
  11 #include <stdlib.h>
  12
  13
  14 struct sset *sset_init(unsigned int first, unsigned int last)
  15 {
  16         unsigned int size = last - first + 1;
  17         struct sset *s = malloc(sizeof(*s) + size * 2 * sizeof(s->sets[0]));
  18
  19         s->size = size;
  20         s->off = first;
  21         s->nbr = 0;
  22         return s;
  23 }
  24
  25 void sset_free(struct sset *s)
  26 {
  27         free(s);
  28 }