smallset.h (3414B)
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 * Compute the set subtraction of two sets. 77 * 78 * This assumes that all three sets are subsets of the 79 * same [n]. Otherwise assertions will fail. Note that 80 * any of the pointers are allowed to be equal. 81 * 82 * @param out pointer to the set where to write difference 83 * @param a pointer to set to subtract from 84 * @param b pointer to set to subtract 85 */ 86 void smallset_minus(smallset *out, smallset *a, smallset *b); 87 88 /** 89 * Writes the smallset to a string. 90 * 91 * The string buffer must already be allocated, and the 92 * parameter n indicates the maximum number of bytes that 93 * may be written to the buffer, including termingating \0. 94 * 95 * String is reprensented in trad notation: e.g. 96 * {}, {1,3}, {0,16,19} 97 * 98 * @param str pointer to the first char of the write buffer 99 * @param n limit on the number of bytes to be written 100 * @param s pointer to the smallset 101 */ 102 void smallset_tonstr(char *str, size_t n, smallset *s); 103 104 /** 105 * Get an element that is in the set. 106 * 107 * Returns the smallest element from the set. If no element 108 * is in the set (i.e. it is empty) then this returns the 109 * SMALLSET_IS_EMPTY value (== UINT64_MAX). 110 * 111 * @param s pointer to the smallset to get elem from 112 */ 113 uint64_t smallset_getone(smallset *s); 114 115 /** 116 * Empty a set. 117 * 118 * Empties a set by removing all elements. 119 * 120 * @param s pointer to the smallset to empty 121 */ 122 void smallset_empty(smallset *s); 123 124 /** 125 * Get the cardinality of a set. 126 * 127 * @param s the set to get the cardinality of 128 * @return the cardinality 129 */ 130 uint64_t smallset_cardinality(smallset *s); 131 132 #endif