1/* copyright (c) 2022 - 2024 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_add(xs_set *s, const xs_val *data);
 18
 19
 20#ifdef XS_IMPLEMENTATION
 21
 22
 23void xs_set_init(xs_set *s)
 24/* initializes a set */
 25{
 26    /* arbitrary default */
 27    s->elems = 256;
 28    s->used  = 0;
 29    s->hash  = xs_realloc(NULL, s->elems * sizeof(int));
 30    s->list  = xs_list_new();
 31
 32    memset(s->hash, '\0', s->elems * sizeof(int));
 33}
 34
 35
 36xs_list *xs_set_result(xs_set *s)
 37/* returns the set as a list and frees it */
 38{
 39    xs_list *list = s->list;
 40    s->list = NULL;
 41    s->hash = xs_free(s->hash);
 42
 43    return list;
 44}
 45
 46
 47void xs_set_free(xs_set *s)
 48/* frees a set, dropping the list */
 49{
 50    xs_free(xs_set_result(s));
 51}
 52
 53
 54static int _store_hash(xs_set *s, const char *data, int value)
 55{
 56    unsigned int hash, i;
 57    int sz = xs_size(data);
 58
 59    hash = xs_hash_func(data, sz);
 60
 61    while (s->hash[(i = hash % s->elems)]) {
 62        /* get the pointer to the stored data */
 63        char *p = &s->list[s->hash[i]];
 64
 65        /* already here? */
 66        if (memcmp(p, data, sz) == 0)
 67            return 0;
 68
 69        /* try next value */
 70        hash++;
 71    }
 72
 73    /* store the new value */
 74    s->hash[i] = value;
 75
 76    s->used++;
 77
 78    return 1;
 79}
 80
 81
 82int xs_set_add(xs_set *s, const xs_val *data)
 83/* adds the data to the set */
 84/* returns: 1 if added, 0 if already there */
 85{
 86    /* is it 'full'? */
 87    if (s->used >= s->elems / 2) {
 88        const xs_val *v;
 89
 90        /* expand! */
 91        s->elems *= 2;
 92        s->used  = 0;
 93        s->hash  = xs_realloc(s->hash, s->elems * sizeof(int));
 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 */