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