[13] | 1 | /* |
---|
| 2 | * Revision Control Information |
---|
| 3 | * |
---|
| 4 | * $Id: var_set.c,v 1.3 2002/08/25 05:30:13 fabio Exp $ |
---|
| 5 | * |
---|
| 6 | */ |
---|
| 7 | #include "util.h" |
---|
| 8 | #include "var_set.h" |
---|
| 9 | |
---|
| 10 | var_set_t *var_set_new(int size) |
---|
| 11 | { |
---|
| 12 | var_set_t *result = ALLOC(var_set_t, 1); |
---|
| 13 | |
---|
| 14 | result->n_elts = size; |
---|
| 15 | result->n_words = size / VAR_SET_WORD_SIZE + ((size % VAR_SET_WORD_SIZE == 0) ? 0 : 1); |
---|
| 16 | result->data = ALLOC(unsigned int, result->n_words); |
---|
| 17 | (void) var_set_clear(result); |
---|
| 18 | return result; |
---|
| 19 | } |
---|
| 20 | |
---|
| 21 | var_set_t *var_set_copy(var_set_t *set) |
---|
| 22 | { |
---|
| 23 | int i; |
---|
| 24 | var_set_t *result = ALLOC(var_set_t, 1); |
---|
| 25 | |
---|
| 26 | *result = *set; |
---|
| 27 | result->data = ALLOC(unsigned int, result->n_words); |
---|
| 28 | for (i = 0; i < result->n_words; i++) |
---|
| 29 | result->data[i] = set->data[i]; |
---|
| 30 | return result; |
---|
| 31 | } |
---|
| 32 | |
---|
| 33 | var_set_t *var_set_assign(var_set_t *result, var_set_t *set) |
---|
| 34 | { |
---|
| 35 | int i; |
---|
| 36 | |
---|
| 37 | assert(result->n_elts == set->n_elts); |
---|
| 38 | for (i = 0; i < result->n_words; i++) |
---|
| 39 | result->data[i] = set->data[i]; |
---|
| 40 | return result; |
---|
| 41 | } |
---|
| 42 | |
---|
| 43 | void var_set_free(var_set_t *set) |
---|
| 44 | { |
---|
| 45 | FREE(set->data); |
---|
| 46 | FREE(set); |
---|
| 47 | } |
---|
| 48 | |
---|
| 49 | static int size_array[256]; |
---|
| 50 | |
---|
| 51 | static void init_size_array(void) |
---|
| 52 | { |
---|
| 53 | int i; |
---|
| 54 | unsigned j; |
---|
| 55 | int count; |
---|
| 56 | |
---|
| 57 | for (i = 0; i < 256; i++) { |
---|
| 58 | count = 0; |
---|
| 59 | for (j = 0; j < VAR_SET_WORD_SIZE; j++) { |
---|
| 60 | count += VAR_SET_EXTRACT_BIT(i, j); |
---|
| 61 | } |
---|
| 62 | size_array[i] = count; |
---|
| 63 | } |
---|
| 64 | } |
---|
| 65 | |
---|
| 66 | int var_set_n_elts(var_set_t *set) |
---|
| 67 | { |
---|
| 68 | register int i, j; |
---|
| 69 | register unsigned int value; |
---|
| 70 | int n_bytes = VAR_SET_WORD_SIZE / VAR_SET_BYTE_SIZE; |
---|
| 71 | int count = 0; |
---|
| 72 | |
---|
| 73 | if (size_array[1] == 0) init_size_array(); |
---|
| 74 | for (i = 0; i < set->n_words; i++) { |
---|
| 75 | value = set->data[i]; |
---|
| 76 | for (j = 0; j < n_bytes; j++) { |
---|
| 77 | count += size_array[value & 0xff]; |
---|
| 78 | value >>= VAR_SET_BYTE_SIZE; |
---|
| 79 | } |
---|
| 80 | } |
---|
| 81 | return count; |
---|
| 82 | } |
---|
| 83 | |
---|
| 84 | var_set_t *var_set_or(var_set_t *result, var_set_t *a, var_set_t *b) |
---|
| 85 | { |
---|
| 86 | int i; |
---|
| 87 | assert(result->n_elts == a->n_elts); |
---|
| 88 | assert(result->n_elts == b->n_elts); |
---|
| 89 | for (i = 0; i < result->n_words; i++) |
---|
| 90 | result->data[i] = a->data[i] | b->data[i]; |
---|
| 91 | return result; |
---|
| 92 | } |
---|
| 93 | |
---|
| 94 | var_set_t *var_set_and(var_set_t *result, var_set_t *a, var_set_t *b) |
---|
| 95 | { |
---|
| 96 | int i; |
---|
| 97 | assert(result->n_elts == a->n_elts); |
---|
| 98 | assert(result->n_elts == b->n_elts); |
---|
| 99 | for (i = 0; i < result->n_words; i++) |
---|
| 100 | result->data[i] = a->data[i] & b->data[i]; |
---|
| 101 | return result; |
---|
| 102 | } |
---|
| 103 | |
---|
| 104 | var_set_t *var_set_not(var_set_t *result, var_set_t *a) |
---|
| 105 | { |
---|
| 106 | int i; |
---|
| 107 | unsigned int mask; |
---|
| 108 | |
---|
| 109 | assert(result->n_elts == a->n_elts); |
---|
| 110 | for (i = 0; i < a->n_words; i++) |
---|
| 111 | result->data[i] = ~a->data[i]; |
---|
| 112 | mask = (unsigned int) VAR_SET_ALL_ONES >> (a->n_words * VAR_SET_WORD_SIZE - a->n_elts); |
---|
| 113 | result->data[a->n_words - 1] &= mask; |
---|
| 114 | return result; |
---|
| 115 | } |
---|
| 116 | |
---|
| 117 | int var_set_get_elt(var_set_t *set, int index) |
---|
| 118 | { |
---|
| 119 | assert(index >= 0 && index < set->n_elts); |
---|
| 120 | return VAR_SET_EXTRACT_BIT(set->data[index / VAR_SET_WORD_SIZE], index % VAR_SET_WORD_SIZE); |
---|
| 121 | } |
---|
| 122 | |
---|
| 123 | void var_set_set_elt(var_set_t *set, int index) |
---|
| 124 | { |
---|
| 125 | unsigned int *value; |
---|
| 126 | assert(index >= 0 && index < set->n_elts); |
---|
| 127 | value = &(set->data[index / VAR_SET_WORD_SIZE]); |
---|
| 128 | *value = *value | (1 << (index % VAR_SET_WORD_SIZE)); |
---|
| 129 | } |
---|
| 130 | |
---|
| 131 | void var_set_clear_elt(var_set_t *set, int index) |
---|
| 132 | { |
---|
| 133 | unsigned int *value; |
---|
| 134 | assert(index >= 0 && index < set->n_elts); |
---|
| 135 | value = &(set->data[index / VAR_SET_WORD_SIZE]); |
---|
| 136 | *value = *value & ~(1 << (index % VAR_SET_WORD_SIZE)); |
---|
| 137 | } |
---|
| 138 | |
---|
| 139 | void var_set_clear(var_set_t *set) |
---|
| 140 | { |
---|
| 141 | int i; |
---|
| 142 | |
---|
| 143 | for (i = 0; i < set->n_words; i++) |
---|
| 144 | set->data[i] = 0; |
---|
| 145 | } |
---|
| 146 | |
---|
| 147 | int var_set_intersect(var_set_t *a, var_set_t *b) |
---|
| 148 | { |
---|
| 149 | int i; |
---|
| 150 | assert(a->n_elts == b->n_elts); |
---|
| 151 | for (i = 0; i < a->n_words; i++) |
---|
| 152 | if (a->data[i] & b->data[i]) return 1; |
---|
| 153 | return 0; |
---|
| 154 | } |
---|
| 155 | |
---|
| 156 | int var_set_is_empty(var_set_t *a) |
---|
| 157 | { |
---|
| 158 | int i; |
---|
| 159 | for (i = 0; i < a->n_words; i++) |
---|
| 160 | if (a->data[i]) return 0; |
---|
| 161 | return 1; |
---|
| 162 | } |
---|
| 163 | |
---|
| 164 | int var_set_is_full(var_set_t *a) |
---|
| 165 | { |
---|
| 166 | int i; |
---|
| 167 | unsigned value; |
---|
| 168 | for (i = 0; i < a->n_words - 1; i++) |
---|
| 169 | if (a->data[i] != VAR_SET_ALL_ONES) return 0; |
---|
| 170 | value = VAR_SET_ALL_ONES >> (a->n_words * VAR_SET_WORD_SIZE - a->n_elts); |
---|
| 171 | return (a->data[a->n_words - 1] == value); |
---|
| 172 | } |
---|
| 173 | |
---|
| 174 | void var_set_print(FILE *fp, var_set_t *set) |
---|
| 175 | { |
---|
| 176 | int i; |
---|
| 177 | for (i = 0; i < set->n_elts; i++) { |
---|
| 178 | fprintf(fp, "%d ", var_set_get_elt(set, i)); |
---|
| 179 | } |
---|
| 180 | fprintf(fp, "\n"); |
---|
| 181 | } |
---|
| 182 | |
---|
| 183 | /* returns 1 if equal, 0 otherwise */ |
---|
| 184 | |
---|
| 185 | int var_set_equal(var_set_t *a, var_set_t *b) |
---|
| 186 | { |
---|
| 187 | int i; |
---|
| 188 | |
---|
| 189 | assert(a->n_elts == b->n_elts); |
---|
| 190 | for (i = 0; i < a->n_words; i++) |
---|
| 191 | if (a->data[i] != b->data[i]) return 0; |
---|
| 192 | return 1; |
---|
| 193 | } |
---|
| 194 | |
---|
| 195 | /* returns 0 if equal, 1 otherwise */ |
---|
| 196 | |
---|
| 197 | int var_set_cmp(char *obj1, char *obj2) |
---|
| 198 | { |
---|
| 199 | int i; |
---|
| 200 | var_set_t *a = (var_set_t *) obj1; |
---|
| 201 | var_set_t *b = (var_set_t *) obj2; |
---|
| 202 | |
---|
| 203 | assert(a->n_elts == b->n_elts); |
---|
| 204 | for (i = 0; i < a->n_words; i++) |
---|
| 205 | if (a->data[i] != b->data[i]) return 1; |
---|
| 206 | return 0; |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | /* to be used when sets are used as keys in hash tables */ |
---|
| 210 | unsigned int var_set_hash(var_set_t *set) |
---|
| 211 | { |
---|
| 212 | int i; |
---|
| 213 | unsigned int result = 0; |
---|
| 214 | |
---|
| 215 | for (i = 0; i < set->n_words; i++) |
---|
| 216 | result += (unsigned int) set->data[i]; |
---|
| 217 | return result; |
---|
| 218 | } |
---|