123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113 |
- #ifndef _XS_SET_H
- #define _XS_SET_H
- typedef struct _xs_set {
- int elems;
- int used;
- int *hash;
- xs_list *list;
- } xs_set;
- void xs_set_init(xs_set *s);
- xs_list *xs_set_result(xs_set *s);
- void xs_set_free(xs_set *s);
- int xs_set_add(xs_set *s, const xs_val *data);
- #ifdef XS_IMPLEMENTATION
- void xs_set_init(xs_set *s)
- {
-
- s->elems = 256;
- s->used = 0;
- s->hash = xs_realloc(NULL, s->elems * sizeof(int));
- s->list = xs_list_new();
- memset(s->hash, '\0', s->elems * sizeof(int));
- }
- xs_list *xs_set_result(xs_set *s)
- {
- xs_list *list = s->list;
- s->list = NULL;
- s->hash = xs_free(s->hash);
- return list;
- }
- void xs_set_free(xs_set *s)
- {
- xs_free(xs_set_result(s));
- }
- static int _store_hash(xs_set *s, const char *data, int value)
- {
- unsigned int hash, i;
- int sz = xs_size(data);
- hash = xs_hash_func(data, sz);
- while (s->hash[(i = hash % s->elems)]) {
-
- char *p = &s->list[s->hash[i]];
-
- if (memcmp(p, data, sz) == 0)
- return 0;
-
- hash++;
- }
-
- s->hash[i] = value;
- s->used++;
- return 1;
- }
- int xs_set_add(xs_set *s, const xs_val *data)
- {
-
- if (s->used >= s->elems / 2) {
- const xs_val *v;
-
- s->elems *= 2;
- s->used = 0;
- s->hash = xs_realloc(s->hash, s->elems * sizeof(int));
- memset(s->hash, '\0', s->elems * sizeof(int));
-
- xs_list_foreach(s->list, v)
- _store_hash(s, v, v - s->list);
- }
- int ret = _store_hash(s, data, xs_size(s->list));
-
- if (ret)
- s->list = xs_list_append(s->list, data);
- return ret;
- }
- #endif
- #endif
|