xs_set.h (2338B)
1 /* copyright (c) 2022 - 2025 grunfink et al. / MIT license */ 2 3 #ifndef _XS_SET_H 4 5 #define _XS_SET_H 6 7 typedef struct _xs_set { 8 int elems; /* number of hash entries */ 9 int used; /* number of used hash entries */ 10 int *hash; /* hashed offsets */ 11 xs_list *list; /* list of stored data */ 12 } xs_set; 13 14 void xs_set_init(xs_set *s); 15 xs_list *xs_set_result(xs_set *s); 16 void xs_set_free(xs_set *s); 17 int xs_set_add(xs_set *s, const xs_val *data); 18 19 20 #ifdef XS_IMPLEMENTATION 21 22 23 void xs_set_init(xs_set *s) 24 /* initializes a set */ 25 { 26 /* arbitrary default */ 27 s->elems = 0; 28 s->used = 0; 29 s->hash = NULL; 30 s->list = NULL; 31 } 32 33 34 xs_list *xs_set_result(xs_set *s) 35 /* returns the set as a list and frees it */ 36 { 37 xs_list *list = s->list; 38 s->list = NULL; 39 s->hash = xs_free(s->hash); 40 41 return list; 42 } 43 44 45 void xs_set_free(xs_set *s) 46 /* frees a set, dropping the list */ 47 { 48 xs_free(xs_set_result(s)); 49 } 50 51 52 static int _store_hash(xs_set *s, const char *data, int value) 53 { 54 unsigned int hash, i; 55 int sz = xs_size(data); 56 57 hash = xs_hash_func(data, sz); 58 59 while (s->hash[(i = hash % s->elems)]) { 60 /* get the pointer to the stored data */ 61 char *p = &s->list[s->hash[i]]; 62 63 /* already here? */ 64 if (memcmp(p, data, sz) == 0) 65 return 0; 66 67 /* try next value */ 68 hash++; 69 } 70 71 /* store the new value */ 72 s->hash[i] = value; 73 74 s->used++; 75 76 return 1; 77 } 78 79 80 int xs_set_add(xs_set *s, const xs_val *data) 81 /* adds the data to the set */ 82 /* returns: 1 if added, 0 if already there */ 83 { 84 /* is it 'full'? */ 85 if (s->used >= s->elems / 2) { 86 const xs_val *v; 87 88 /* expand! */ 89 s->elems = s->elems ? s->elems * 2 : 256; 90 s->used = 0; 91 s->hash = xs_realloc(s->hash, s->elems * sizeof(int)); 92 if (!s->list) 93 s->list = xs_list_new(); 94 95 memset(s->hash, '\0', s->elems * sizeof(int)); 96 97 /* add the list elements back */ 98 xs_list_foreach(s->list, v) 99 _store_hash(s, v, v - s->list); 100 } 101 102 int ret = _store_hash(s, data, xs_size(s->list)); 103 104 /* if it's new, add the data */ 105 if (ret) 106 s->list = xs_list_append(s->list, data); 107 108 return ret; 109 } 110 111 #endif /* XS_IMPLEMENTATION */ 112 113 #endif /* XS_SET_H */