~rcr/rirc

ref: c677d85e88b1397d0eaa9b99ad3acf531f64aa3f rirc/src/utils/tree.h -rw-r--r-- 21.2 KiB
c677d85e — Richard Robbins add -m/--mode flag 6 months ago
                                                                                
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
#ifndef RIRC_UTILS_TREE_H
#define RIRC_UTILS_TREE_H

#include <stddef.h>

#define MAX(A, B) ((A) > (B) ? (A) : (B))

#define TREE_EMPTY(head)       (TREE_ROOT(head) == NULL)
#define TREE_LEFT(elm, field)  (elm)->field.tree_left
#define TREE_RIGHT(elm, field) (elm)->field.tree_right
#define TREE_ROOT(head)        (head)->tree_root

#define AVL_ADD(name, x, y, z)    name##_AVL_ADD(x, y, z)
#define AVL_DEL(name, x, y, z)    name##_AVL_DEL(x, y, z)
#define AVL_GET(name, x, y, z, n) name##_AVL_GET(x, y, z, n)
#define AVL_FOREACH(name, x, y)   name##_AVL_FOREACH(x, y)

#define TREE_HEAD(type) \
    struct type *tree_root

#define TREE_NODE(type)          \
    struct {                     \
        int height;              \
        struct type *tree_left;  \
        struct type *tree_right; \
    }

#define AVL_HEIGHT(elm, field) (elm)->field.height

#define AVL_GENERATE(name, type, field, cmp, ncmp) \
    static struct type* name##_AVL_ADD(struct name*, struct type*, void*);        \
    static struct type* name##_AVL_DEL(struct name*, struct type*, void*);        \
    static struct type* name##_AVL_ADD_REC(struct type*, struct type*, void*);    \
    static struct type* name##_AVL_DEL_REC(struct type**, struct type*, void*);   \
                                                                                  \
static inline void                                                                \
name##_AVL_INIT(struct type *elm)                                                 \
{                                                                                 \
    AVL_HEIGHT(elm, field) = 1;                                                   \
    TREE_RIGHT(elm, field) = TREE_LEFT(elm, field) = NULL;                        \
}                                                                                 \
                                                                                  \
static inline int                                                                 \
name##_AVL_GET_HEIGHT(struct type *elm)                                           \
{                                                                                 \
    return (elm == NULL) ? 0 : AVL_HEIGHT(elm, field);                            \
}                                                                                 \
                                                                                  \
static inline int                                                                 \
name##_AVL_SET_HEIGHT(struct type *elm)                                           \
{                                                                                 \
    int hL = name##_AVL_GET_HEIGHT(TREE_LEFT(elm, field)),                        \
        hR = name##_AVL_GET_HEIGHT(TREE_RIGHT(elm, field));                       \
                                                                                  \
    return (AVL_HEIGHT(elm, field) = 1 + MAX(hL, hR));                            \
}                                                                                 \
                                                                                  \
static inline int                                                                 \
name##_AVL_BALANCE(struct type *elm)                                              \
{                                                                                 \
    name##_AVL_SET_HEIGHT(elm);                                                   \
                                                                                  \
    int hL = name##_AVL_GET_HEIGHT(TREE_LEFT(elm, field)),                        \
        hR = name##_AVL_GET_HEIGHT(TREE_RIGHT(elm, field));                       \
                                                                                  \
    return (hR - hL);                                                             \
}                                                                                 \
                                                                                  \
static inline struct type*                                                        \
name##_AVL_ROTATE_LEFT(struct type *n)                                            \
{                                                                                 \
    struct type *p = TREE_RIGHT(n, field);                                        \
    struct type *b = TREE_LEFT(p, field);                                         \
                                                                                  \
    TREE_LEFT(p, field) = n;                                                      \
    TREE_RIGHT(n, field) = b;                                                     \
                                                                                  \
    name##_AVL_SET_HEIGHT(n);                                                     \
    name##_AVL_SET_HEIGHT(p);                                                     \
                                                                                  \
    return p;                                                                     \
}                                                                                 \
                                                                                  \
static inline struct type*                                                        \
name##_AVL_ROTATE_RIGHT(struct type *n)                                           \
{                                                                                 \
    struct type *p = TREE_LEFT(n, field);                                         \
    struct type *b = TREE_RIGHT(p, field);                                        \
                                                                                  \
    TREE_RIGHT(p, field) = n;                                                     \
    TREE_LEFT(n, field) = b;                                                      \
                                                                                  \
    name##_AVL_SET_HEIGHT(n);                                                     \
    name##_AVL_SET_HEIGHT(p);                                                     \
                                                                                  \
    return p;                                                                     \
}                                                                                 \
                                                                                  \
static void                                                                       \
name##_AVL_FOREACH_REC(struct type *elm, void (*f)(struct type*))                 \
{                                                                                 \
    if (elm) {                                                                    \
        name##_AVL_FOREACH_REC(TREE_LEFT(elm, field), f);                         \
        name##_AVL_FOREACH_REC(TREE_RIGHT(elm, field), f);                        \
        f(elm);                                                                   \
    }                                                                             \
}                                                                                 \
                                                                                  \
static inline void                                                                \
name##_AVL_FOREACH(struct name *head, void (*f)(struct type*))                    \
{                                                                                 \
    name##_AVL_FOREACH_REC(TREE_ROOT(head), f);                                   \
}                                                                                 \
                                                                                  \
static struct type*                                                               \
name##_AVL_GET(struct name *head, struct type *elm, void *arg, size_t n)          \
{                                                                                 \
    int comp;                                                                     \
    struct type *tmp = TREE_ROOT(head);                                           \
                                                                                  \
    /* TODO: this can all be one func, with a1, a2, a3 as arguments   */          \
    while (tmp && (comp = (n ? ncmp(elm, tmp, arg, n) : cmp(elm, tmp, arg))))     \
        tmp = (comp > 0) ? TREE_RIGHT(tmp, field) : TREE_LEFT(tmp, field);        \
                                                                                  \
    return tmp;                                                                   \
}                                                                                 \
                                                                                  \
static struct type*                                                               \
name##_AVL_ADD(struct name *head, struct type *elm, void *arg)                    \
{                                                                                 \
    name##_AVL_INIT(elm);                                                         \
                                                                                  \
    struct type *r = name##_AVL_ADD_REC(TREE_ROOT(head), elm, arg);               \
                                                                                  \
    if (r == NULL)                                                                \
        return NULL;                                                              \
                                                                                  \
    TREE_ROOT(head) = r;                                                          \
                                                                                  \
    return elm;                                                                   \
}                                                                                 \
                                                                                  \
static struct type*                                                               \
name##_AVL_ADD_REC(struct type *n, struct type *elm, void *arg)                   \
{                                                                                 \
    int comp, balance;                                                            \
    struct type *tmp;                                                             \
                                                                                  \
    if (n == NULL)                                                                \
        return elm;                                                               \
                                                                                  \
    if ((comp = cmp(elm, n, arg)) == 0) {                                         \
        return NULL;                                                              \
    } else if (comp > 0) {                                                        \
                                                                                  \
        if ((tmp = name##_AVL_ADD_REC(TREE_RIGHT(n, field), elm, arg)) == NULL)   \
            return NULL;                                                          \
                                                                                  \
        TREE_RIGHT(n, field) = tmp;                                               \
                                                                                  \
    } else if (comp < 0) {                                                        \
                                                                                  \
        if ((tmp = name##_AVL_ADD_REC(TREE_LEFT(n, field), elm, arg)) == NULL)    \
            return NULL;                                                          \
                                                                                  \
        TREE_LEFT(n, field) = tmp;                                                \
    }                                                                             \
                                                                                  \
    balance = name##_AVL_BALANCE(n);                                              \
                                                                                  \
    if (balance > 1) {                                                            \
                                                                                  \
        if ((cmp(elm, TREE_RIGHT(n, field), arg)) < 0)                            \
            TREE_RIGHT(n, field) = name##_AVL_ROTATE_RIGHT(TREE_RIGHT(n, field)); \
                                                                                  \
        return name##_AVL_ROTATE_LEFT(n);                                         \
    }                                                                             \
                                                                                  \
    if (balance < -1) {                                                           \
                                                                                  \
        if ((cmp(elm, TREE_LEFT(n, field), arg)) > 0)                             \
            TREE_LEFT(n, field) = name##_AVL_ROTATE_LEFT(TREE_LEFT(n, field));    \
                                                                                  \
        return name##_AVL_ROTATE_RIGHT(n);                                        \
    }                                                                             \
                                                                                  \
    return n;                                                                     \
}                                                                                 \
                                                                                  \
static struct type*                                                               \
name##_AVL_DEL(struct name *head, struct type *elm, void *arg)                    \
{                                                                                 \
    return name##_AVL_DEL_REC(&TREE_ROOT(head), elm, arg);                        \
}                                                                                 \
                                                                                  \
static struct type*                                                               \
name##_AVL_DEL_REC(struct type **p, struct type *elm, void *arg)                  \
{                                                                                 \
    int comp, balance;                                                            \
    struct type *n = *p;                                                          \
    struct type *ret = NULL;                                                      \
                                                                                  \
    if (n == NULL)                                                                \
        return NULL;                                                              \
                                                                                  \
    if ((comp = cmp(elm, n, arg)) == 0) {                                         \
                                                                                  \
        ret = n;                                                                  \
                                                                                  \
        if (TREE_LEFT(n, field) && TREE_RIGHT(n, field)) {                        \
                                                                                  \
            struct type *swap   = TREE_RIGHT(n, field),                           \
                        *swap_p = TREE_RIGHT(n, field);                           \
                                                                                  \
            while (TREE_LEFT(swap, field)) {                                      \
                swap_p = swap;                                                    \
                swap = TREE_LEFT(swap, field);                                    \
            }                                                                     \
                                                                                  \
            if (swap_p == swap) {                                                 \
                TREE_LEFT(swap, field) = TREE_LEFT(n, field);                     \
            } else {                                                              \
                struct type *swap_l = TREE_LEFT(swap, field),                     \
                            *swap_r = TREE_RIGHT(swap, field);                    \
                                                                                  \
                TREE_LEFT(swap, field) = TREE_LEFT(n, field);                     \
                TREE_RIGHT(swap, field) = TREE_RIGHT(n, field);                   \
                                                                                  \
                TREE_LEFT(n, field) = swap_l;                                     \
                TREE_RIGHT(n, field) = swap_r;                                    \
                                                                                  \
                TREE_LEFT(swap_p, field) = n;                                     \
                                                                                  \
                name##_AVL_DEL_REC(&TREE_RIGHT(swap, field), elm, arg);           \
            }                                                                     \
                                                                                  \
            *p = n = swap;                                                        \
        } else if (TREE_LEFT(n, field))  {                                        \
            *p = TREE_LEFT(n, field);                                             \
        } else if (TREE_RIGHT(n, field)) {                                        \
            *p = TREE_RIGHT(n, field);                                            \
        } else {                                                                  \
            *p = NULL;                                                            \
        }                                                                         \
    } else if (comp < 0) {                                                        \
        ret = name##_AVL_DEL_REC(&TREE_LEFT(n, field), elm, arg);                 \
    } else if (comp > 0) {                                                        \
        ret = name##_AVL_DEL_REC(&TREE_RIGHT(n, field), elm, arg);                \
    }                                                                             \
                                                                                  \
    if (ret == NULL)                                                              \
        return NULL;                                                              \
                                                                                  \
    balance = name##_AVL_BALANCE(n);                                              \
                                                                                  \
    if (balance > 1) {                                                            \
        int hrl = name##_AVL_GET_HEIGHT(TREE_LEFT(TREE_RIGHT(n, field), field)),  \
            hrr = name##_AVL_GET_HEIGHT(TREE_RIGHT(TREE_RIGHT(n, field), field)); \
                                                                                  \
        if ((hrl - hrr) > 0) {                                                    \
            TREE_RIGHT(n, field) = name##_AVL_ROTATE_RIGHT(TREE_RIGHT(n, field)); \
        }                                                                         \
                                                                                  \
        *p = name##_AVL_ROTATE_LEFT(n);                                           \
    }                                                                             \
                                                                                  \
    if (balance < -1) {                                                           \
        int hll = name##_AVL_GET_HEIGHT(TREE_LEFT(TREE_LEFT(n, field), field)),   \
            hlr = name##_AVL_GET_HEIGHT(TREE_RIGHT(TREE_LEFT(n, field), field));  \
                                                                                  \
        if ((hll - hlr) < 0) {                                                    \
            TREE_LEFT(n, field) = name##_AVL_ROTATE_LEFT(TREE_LEFT(n, field));    \
        }                                                                         \
                                                                                  \
        *p = name##_AVL_ROTATE_RIGHT(n);                                          \
    }                                                                             \
                                                                                  \
    return ret;                                                                   \
}

#endif