-
Notifications
You must be signed in to change notification settings - Fork 693
/
intset.h
135 lines (116 loc) · 3.46 KB
/
intset.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/* A specialized unordered_set implementation for literals, where bucket_count
* is defined at initialization rather than increased automatically.
*/
#include <stddef.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#ifndef INTSET_NAME
#error "Please #define INTSET_NAME ... before including intset.h"
#endif
#ifndef INTSET_TYPE
#error "Please #define INTSET_TYPE ... before including intset.h"
#endif
/* macros to generate unique names from INTSET_NAME */
#ifndef INTSET_CONCAT
#define INTSET_CONCAT_(a, b) a ## b
#define INTSET_CONCAT(a, b) INTSET_CONCAT_(a, b)
#define INTSET_FUNC_(a, b) INTSET_CONCAT(a, _ ## b)
#endif
#define INTSET_FUNC(name) INTSET_FUNC_(INTSET_NAME, name)
#define INTSET_BUCKET INTSET_CONCAT(INTSET_NAME, Bucket)
#define INTSET_UNION INTSET_CONCAT(INTSET_NAME, Union)
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4200)
#endif
typedef struct {
size_t count;
union INTSET_UNION {
INTSET_TYPE val;
INTSET_TYPE *data;
} v;
} INTSET_BUCKET;
typedef struct {
size_t bucket_count;
INTSET_BUCKET buckets[];
} INTSET_NAME;
static INTSET_NAME *INTSET_FUNC(new)(size_t buckets)
{
size_t i, size;
INTSET_NAME *set;
if (buckets < 1)
buckets = 1;
if ((SIZE_MAX - sizeof(INTSET_NAME)) / sizeof(INTSET_BUCKET) < buckets)
return NULL;
size = sizeof(INTSET_NAME) + buckets * sizeof(INTSET_BUCKET);
set = (INTSET_NAME*)malloc(size);
if (!set)
return NULL;
memset(set, 0, size); /* gcc -fanalyzer does not understand this sets all buckets' count to 0 */
for (i = 0; i < buckets; i++) {
set->buckets[i].count = 0;
}
set->bucket_count = buckets;
return set;
}
static void INTSET_FUNC(free)(INTSET_NAME *set)
{
size_t i;
if (!set)
return;
for (i = 0; i < set->bucket_count; i++) {
if (set->buckets[i].count > 1)
free(set->buckets[i].v.data);
}
free(set);
}
static bool INTSET_FUNC(contains)(INTSET_NAME *set, INTSET_TYPE val)
{
size_t i;
INTSET_BUCKET* bucket = &set->buckets[(size_t)val % set->bucket_count];
if (bucket->count == 1)
return bucket->v.val == val;
for (i = 0; i < bucket->count; ++i) {
if (bucket->v.data[i] == val)
return true;
}
return false;
}
static bool INTSET_FUNC(add)(INTSET_NAME *set, INTSET_TYPE val)
{
INTSET_BUCKET* bucket;
if (INTSET_FUNC(contains)(set, val))
return true; /* ok */
bucket = &set->buckets[(size_t)val % set->bucket_count];
if (bucket->count == 0) {
bucket->v.val = val;
bucket->count = 1;
} else if (bucket->count == 1) {
INTSET_TYPE old = bucket->v.val;
bucket->v.data = (INTSET_TYPE*)malloc(2 * sizeof(INTSET_TYPE));
if (!bucket->v.data) {
bucket->v.val = old;
return false; /* error */
}
bucket->v.data[0] = old;
bucket->v.data[1] = val;
bucket->count = 2;
} else {
size_t new_bucket_size;
INTSET_TYPE* new_bucket_data;
new_bucket_size = (bucket->count + 1) * sizeof(INTSET_TYPE);
new_bucket_data = (INTSET_TYPE*)realloc(bucket->v.data, new_bucket_size);
if (!new_bucket_data)
return false; /* error */
bucket->v.data = new_bucket_data;
bucket->v.data[bucket->count++] = val;
}
return true; /* success */
}
#if defined(_MSC_VER)
#pragma warning(pop)
#endif
#undef INTSET_FUNC
#undef INTSET_BUCKET
#undef INTSET_UNION