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