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