smallset.h (2993B)
1 /** 2 * Implementation of "small sets" (subsets of [n], where n is not big). 3 */ 4 #ifndef SMALLSET_H_ 5 #define SMALLSET_H_ 6 7 #include <assert.h> 8 #include <stdint.h> 9 #include <stdio.h> 10 #include <stdlib.h> 11 #include <string.h> 12 13 #define SMALLSET_IS_EMPTY UINT64_MAX 14 15 typedef struct { 16 size_t bits; 17 uint8_t *data; 18 } smallset; 19 20 /** 21 * Intializes a small set. 22 * 23 * The set is a subset of some fixed [n]. 24 * Allocates memory that needs to be smallset_clear'd. 25 * 26 * @param s pointer to the smallset to be inited 27 * @param bits specifies that the set is a subset of [bits] 28 */ 29 void smallset_init(smallset *s, const size_t bits); 30 31 /** 32 * Clears a set. 33 * 34 * @param s pointer to the smallset to clear 35 */ 36 void smallset_clear(smallset *s); 37 38 /** 39 * Insert an element into a set. 40 * 41 * Inserts an element x \in [n] into a smallset. If the 42 * element is already in the set the set is unchanged. 43 * Assertions will fail of x \not\in [n]. 44 * 45 * @param s pointer to the set to insert into 46 * @param x element to insert into the set 47 */ 48 void smallset_insert(smallset *s, const uint64_t x); 49 50 /** 51 * Check if an element is in a set. 52 * 53 * Checks if the element x is in the set pointed to by 54 * s. Assumes that x \in [n] (or assertions will fail). 55 * 56 * @param s pointer to the set to check in 57 * @param x the element to check for 58 * @returns a nonzero value iff x is in the set 59 */ 60 int smallset_lookup(smallset *s, const uint64_t x); 61 62 /** 63 * Compute the intersection of two sets. 64 * 65 * This assumes that all three sets are subsets of the 66 * same [n]. Otherwise assertions will fail. Note that 67 * any of the pointers are allowed to be equal. 68 * 69 * @param out pointer to the set where to write intersection 70 * @param a pointer to one of the intersect sets 71 * @param b pointer to the other intersect set 72 */ 73 void smallset_intersection(smallset *out, smallset *a, smallset *b); 74 75 /** 76 * Writes the smallset to a string. 77 * 78 * The string buffer must already be allocated, and the 79 * parameter n indicates the maximum number of bytes that 80 * may be written to the buffer, including termingating \0. 81 * 82 * String is reprensented in trad notation: e.g. 83 * {}, {1,3}, {0,16,19} 84 * 85 * @param str pointer to the first char of the write buffer 86 * @param n limit on the number of bytes to be written 87 * @param s pointer to the smallset 88 */ 89 void smallset_tonstr(char *str, size_t n, smallset *s); 90 91 /** 92 * Get an element that is in the set. 93 * 94 * Returns the smallest element from the set. If no element 95 * is in the set (i.e. it is empty) then this returns the 96 * SMALLSET_IS_EMPTY value (== UINT64_MAX). 97 * 98 * @param s pointer to the smallset to get elem from 99 */ 100 uint64_t smallset_getone(smallset *s); 101 102 /** 103 * Empty a set. 104 * 105 * Empties a set by removing all elements. 106 * 107 * @param s pointer to the smallset to empty 108 */ 109 void smallset_empty(smallset *s); 110 111 /** 112 * Get the cardinality of a set. 113 * 114 * @param s the set to get the cardinality of 115 * @return the cardinality 116 */ 117 uint64_t smallset_cardinality(smallset *s); 118 119 #endif