/src/open62541_15/deps/ziptree.c

Source
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 
 *
 *    Copyright 2021-2022 (c) Julius Pfrommer
 */

#include "ziptree.h"

/* Dummy types */
struct zip_elem;
typedef struct zip_elem zip_elem;
typedef ZIP_ENTRY(zip_elem) zip_entry;
typedef ZIP_HEAD(, zip_elem) zip_head;

/* Access macros */
#define ZIP_ENTRY_PTR(x) ((zip_entry*)((char*)x + fieldoffset))
#define ZIP_KEY_PTR(x) (const void*)((const char*)x + keyoffset)

/* Hash pointers to keep the tie-breeaking of equal keys (mostly) uncorrelated
 * from the rank (pointer order). Hashing code taken from sdbm-hash
 * (http://www.cse.yorku.ca/~oz/hash.html). */
static unsigned int
__ZIP_PTR_HASH(const void *p) {
    unsigned int h = 0;
    const unsigned char *data = (const unsigned char*)&p;
    for(size_t i = 0; i < (sizeof(void*) / sizeof(char)); i++)
        h = data[i] + (h << 6) + (h << 16) - h;
    return h;
}

static ZIP_INLINE enum ZIP_CMP
__ZIP_RANK_CMP(const void *p1, const void *p2) {
    /* assert(p1 != p2); */
    unsigned int h1 = __ZIP_PTR_HASH(p1);
    unsigned int h2 = __ZIP_PTR_HASH(p2);
    if(h1 == h2)
        return (p1 < p2) ? ZIP_CMP_LESS : ZIP_CMP_MORE;
    return (h1 < h2) ? ZIP_CMP_LESS : ZIP_CMP_MORE;
}

static ZIP_INLINE enum ZIP_CMP
__ZIP_UNIQUE_CMP(zip_cmp_cb cmp, const void *p1, const void *p2) {
    if(p1 == p2)
        return ZIP_CMP_EQ;
    enum ZIP_CMP order = cmp(p1, p2);
    if(order == ZIP_CMP_EQ)
        return (p1 < p2) ? ZIP_CMP_LESS : ZIP_CMP_MORE;
    return order;
}

#if 0
#include <assert.h>
ZIP_UNUSED static ZIP_INLINE void
__ZIP_VALIDATE(zip_cmp_cb cmp, unsigned short fieldoffset,
               unsigned short keyoffset, void *elm,
               void *min_elm, void *max_elm) {
    if(!elm)
        return;
    enum ZIP_CMP c1 = __ZIP_UNIQUE_CMP(cmp, ZIP_KEY_PTR(min_elm), ZIP_KEY_PTR(elm));
    assert((elm == min_elm && c1 == ZIP_CMP_EQ) || c1 == ZIP_CMP_LESS);

    enum ZIP_CMP c2 = __ZIP_UNIQUE_CMP(cmp, ZIP_KEY_PTR(max_elm), ZIP_KEY_PTR(elm));
    assert((elm == max_elm && c2 == ZIP_CMP_EQ) || c2 == ZIP_CMP_MORE);

    assert(!ZIP_ENTRY_PTR(elm)->right ||
           __ZIP_RANK_CMP(elm, ZIP_ENTRY_PTR(elm)->right) == ZIP_CMP_MORE);
    assert(!ZIP_ENTRY_PTR(elm)->left ||
           __ZIP_RANK_CMP(elm, ZIP_ENTRY_PTR(elm)->left) == ZIP_CMP_MORE);

    __ZIP_VALIDATE(cmp, fieldoffset, keyoffset, ZIP_ENTRY_PTR(elm)->right, elm, max_elm);
    __ZIP_VALIDATE(cmp, fieldoffset, keyoffset, ZIP_ENTRY_PTR(elm)->left, min_elm, elm);
}
#endif

/* Walk down the right-side spine of cur. Elements that are larger than x_key
 * are moved under x->right. */
static void
__ZIP_INSERT_MOVE_RIGHT(zip_cmp_cb cmp, unsigned short fieldoffset,
                        unsigned short keyoffset, const void *x_key,
                        zip_elem **fix_edge, zip_elem *cur) {
    while(ZIP_ENTRY_PTR(cur)->right) {
        zip_elem *move_candidate = ZIP_ENTRY_PTR(cur)->right;
        if(__ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(move_candidate)) == ZIP_CMP_MORE) {
            cur = ZIP_ENTRY_PTR(cur)->right;
            continue;
        }
        ZIP_ENTRY_PTR(cur)->right = ZIP_ENTRY_PTR(move_candidate)->left;
        ZIP_ENTRY_PTR(move_candidate)->left = NULL;
        *fix_edge = move_candidate;
        fix_edge = &ZIP_ENTRY_PTR(move_candidate)->left;
    }
}

static void
__ZIP_INSERT_MOVE_LEFT(zip_cmp_cb cmp, unsigned short fieldoffset,
                       unsigned short keyoffset, const void *x_key,
                       zip_elem **fix_edge, zip_elem *cur) {
    while(ZIP_ENTRY_PTR(cur)->left) {
        zip_elem *move_candidate = ZIP_ENTRY_PTR(cur)->left;
        if(__ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(move_candidate)) == ZIP_CMP_LESS) {
            cur = ZIP_ENTRY_PTR(cur)->left;
            continue;
        }
        ZIP_ENTRY_PTR(cur)->left = ZIP_ENTRY_PTR(move_candidate)->right;
        ZIP_ENTRY_PTR(move_candidate)->right = NULL;
        *fix_edge = move_candidate;
        fix_edge = &ZIP_ENTRY_PTR(move_candidate)->right;
    }
}

void
__ZIP_INSERT(void *h, zip_cmp_cb cmp, unsigned short fieldoffset,
             unsigned short keyoffset, void *elm) {
    zip_elem *x = (zip_elem*)elm;
    ZIP_ENTRY_PTR(x)->left = NULL;
    ZIP_ENTRY_PTR(x)->right = NULL;

    const void *x_key = ZIP_KEY_PTR(x);
    zip_head *head = (zip_head*)h;
    if(!head->root) {
        head->root = x;
        return;
    }

    /* Go down the tree to find the top element "cur" that has a rank smaller
     * than "x" */
    zip_elem *prev = NULL;
    zip_elem *cur = head->root;
    enum ZIP_CMP cur_order, prev_order = ZIP_CMP_EQ;
    do {
        cur_order = __ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(cur));
        if(cur_order == ZIP_CMP_EQ)
            return; /* x is already inserted */
        if(__ZIP_RANK_CMP(cur, x) == ZIP_CMP_LESS)
            break;
        prev = cur;
        prev_order = cur_order;
        cur = (cur_order == ZIP_CMP_MORE) ?
            ZIP_ENTRY_PTR(cur)->right : ZIP_ENTRY_PTR(cur)->left;
    } while(cur);

    /* Insert "x" instead of "cur" under its parent "prev" */
    if(cur == head->root) {
        head->root = x;
    } else {
        if(prev_order == ZIP_CMP_MORE)
            ZIP_ENTRY_PTR(prev)->right = x;
        else
            ZIP_ENTRY_PTR(prev)->left = x;
    }

    if(!cur)
        return;

    /* Re-insert "cur" under "x". Repair by moving elements that ended up on the
     * wrong side of "x". */
    if(cur_order == ZIP_CMP_MORE) {
        ZIP_ENTRY_PTR(x)->left = cur;
        __ZIP_INSERT_MOVE_RIGHT(cmp, fieldoffset, keyoffset,
                                x_key, &ZIP_ENTRY_PTR(x)->right, cur);
    } else {
        ZIP_ENTRY_PTR(x)->right = cur;
        __ZIP_INSERT_MOVE_LEFT(cmp, fieldoffset, keyoffset,
                               x_key, &ZIP_ENTRY_PTR(x)->left, cur);
    }
}

void *
__ZIP_REMOVE(void *h, zip_cmp_cb cmp, unsigned short fieldoffset,
             unsigned short keyoffset, void *elm) {
    zip_head *head = (zip_head*)h;
    zip_elem *x = (zip_elem*)elm;
    zip_elem *cur = head->root;
    if(!cur)
        return NULL;

    const void *x_key = ZIP_KEY_PTR(x);
    zip_elem **prev_edge = &head->root;
    enum ZIP_CMP cur_order = __ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(cur));
    while(cur_order != ZIP_CMP_EQ) {
        prev_edge = (cur_order == ZIP_CMP_LESS) ?
            &ZIP_ENTRY_PTR(cur)->left : &ZIP_ENTRY_PTR(cur)->right;
        cur = *prev_edge;
        if(!cur)
            return NULL;
        cur_order = __ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(cur));
    }
    *prev_edge = (zip_elem*)__ZIP_ZIP(fieldoffset,
                                      ZIP_ENTRY_PTR(cur)->left,
                                      ZIP_ENTRY_PTR(cur)->right);
    return cur;
}

void *
__ZIP_ITER(unsigned short fieldoffset, zip_iter_cb cb,
           void *context, void *elm) {
    if(!elm)
        return NULL;
    zip_elem *left = ZIP_ENTRY_PTR(elm)->left;
    zip_elem *right = ZIP_ENTRY_PTR(elm)->right;
    void *res = __ZIP_ITER(fieldoffset, cb, context, left);
    if(res)
        return res;
    res = cb(context, elm);
    if(res)
        return res;
    return __ZIP_ITER(fieldoffset, cb, context, right);
}

void *
__ZIP_ITER_KEY(zip_cmp_cb cmp, unsigned short fieldoffset,
               unsigned short keyoffset, const void *key,
               zip_iter_cb cb, void *context, void *elm) {
    if(!elm)
        return NULL;

    void *res;
    enum ZIP_CMP eq = cmp(key, ZIP_KEY_PTR(elm));
    if(eq != ZIP_CMP_MORE) {
        res = __ZIP_ITER_KEY(cmp, fieldoffset, keyoffset, key,
                             cb, context, ZIP_ENTRY_PTR(elm)->left);
        if(res)
            return res;
    }

    if(eq == ZIP_CMP_EQ) {
        res = cb(context, elm);
        if(res)
            return res;
    }

    if(eq != ZIP_CMP_LESS) {
        res = __ZIP_ITER_KEY(cmp, fieldoffset, keyoffset, key,
                             cb, context, ZIP_ENTRY_PTR(elm)->right);
        if(res)
            return res;
    }

    return NULL;
}

void *
__ZIP_ZIP(unsigned short fieldoffset, void *left, void *right) {
    if(!left)
        return right;
    if(!right)
        return left;
    zip_elem *l = (zip_elem*)left;
    zip_elem *r = (zip_elem*)right;
    zip_elem *root = NULL;
    zip_elem **prev_edge = &root;
    while(l && r) {
        if(__ZIP_RANK_CMP(l, r) == ZIP_CMP_LESS) {
            *prev_edge = r;
            prev_edge = &ZIP_ENTRY_PTR(r)->left;
            r = ZIP_ENTRY_PTR(r)->left;
        } else {
            *prev_edge = l;
            prev_edge = &ZIP_ENTRY_PTR(l)->right;
            l = ZIP_ENTRY_PTR(l)->right;
        }
    }
    *prev_edge = (l) ? l : r;
    return root;
}

/* Walk down from cur and move all elements <= split-key to the left side. All
 * elements that are moved over have to be below left_rightmost. Returns the
 * hierarchy of elements that remain on the right side. */
static void
__ZIP_UNZIP_MOVE_LEFT(zip_cmp_cb cmp, unsigned short fieldoffset,
                      unsigned short keyoffset, const void *key,
                      zip_elem **fix_edge, zip_elem *cur) {
    while(ZIP_ENTRY_PTR(cur)->left) {
        zip_elem *next = ZIP_ENTRY_PTR(cur)->left;
        if(cmp(key, ZIP_KEY_PTR(next)) == ZIP_CMP_LESS) {
            cur = next;
            continue;
        }
        *fix_edge = next;
        ZIP_ENTRY_PTR(cur)->left = ZIP_ENTRY_PTR(next)->right;
        ZIP_ENTRY_PTR(next)->right = NULL;
        fix_edge = &ZIP_ENTRY_PTR(next)->right;
    }
}

static void
__ZIP_UNZIP_MOVE_RIGHT(zip_cmp_cb cmp, unsigned short fieldoffset,
                       unsigned short keyoffset, const void *key,
                       zip_elem **fix_edge, zip_elem *cur) {
    while(ZIP_ENTRY_PTR(cur)->right) {
        zip_elem *next = ZIP_ENTRY_PTR(cur)->right;
        if(cmp(key, ZIP_KEY_PTR(next)) != ZIP_CMP_LESS) {
            cur = next;
            continue;
        }
        *fix_edge = next;
        ZIP_ENTRY_PTR(cur)->right = ZIP_ENTRY_PTR(next)->left;
        ZIP_ENTRY_PTR(next)->left = NULL;
        fix_edge = &ZIP_ENTRY_PTR(next)->left;
    }
}

/* Split the tree into a left side with keys <= split-key and a right side with
 * key > split-key. */
void
__ZIP_UNZIP(zip_cmp_cb cmp, unsigned short fieldoffset,
            unsigned short keyoffset, const void *key,
            void *h, void *l, void *r) {
    zip_elem *prev;
    zip_head *head = (zip_head*)h;
    zip_head *left = (zip_head*)l;
    zip_head *right = (zip_head*)r;
    if(!head->root) {
        left->root = NULL;
        right->root = NULL;
        return;
    }
    zip_elem *cur = head->root;
    if(cmp(key, ZIP_KEY_PTR(cur)) != ZIP_CMP_LESS) {
        left->root = cur;
        do {
            prev = cur;
            cur = ZIP_ENTRY_PTR(cur)->right;
            if(!cur) {
                right->root = NULL;
                return;
            }
        } while(cmp(key, ZIP_KEY_PTR(cur)) != ZIP_CMP_LESS);
        ZIP_ENTRY_PTR(prev)->right = NULL;
        right->root = cur;
        __ZIP_UNZIP_MOVE_LEFT(cmp, fieldoffset, keyoffset, key,
                              &ZIP_ENTRY_PTR(prev)->right, cur);
    } else {
        right->root = cur;
        do {
            prev = cur;
            cur = ZIP_ENTRY_PTR(cur)->left;
            if(!cur) {
                left->root = NULL;
                return;
            }
        } while(cmp(key, ZIP_KEY_PTR(cur)) == ZIP_CMP_LESS);
        ZIP_ENTRY_PTR(prev)->left = NULL;
        left->root = cur;
        __ZIP_UNZIP_MOVE_RIGHT(cmp, fieldoffset, keyoffset, key,
                               &ZIP_ENTRY_PTR(prev)->left, cur);
    }
}

Coverage Report

Created: 2026-05-30 06:22

Line	Count	Source
1		/* This Source Code Form is subject to the terms of the Mozilla Public
2		* License, v. 2.0. If a copy of the MPL was not distributed with this
3		* file, You can obtain one at http://mozilla.org/MPL/2.0/.
4		*
5		* Copyright 2021-2022 (c) Julius Pfrommer
6		*/
7
8		#include "ziptree.h"
9
10		/* Dummy types */
11		struct zip_elem;
12		typedef struct zip_elem zip_elem;
13		typedef ZIP_ENTRY(zip_elem) zip_entry;
14		typedef ZIP_HEAD(, zip_elem) zip_head;
15
16		/* Access macros */
17	1.20G	#define ZIP_ENTRY_PTR(x) ((zip_entry)((char)x + fieldoffset))
18	605M	#define ZIP_KEY_PTR(x) (const void)((const char)x + keyoffset)
19
20		/* Hash pointers to keep the tie-breeaking of equal keys (mostly) uncorrelated
21		* from the rank (pointer order). Hashing code taken from sdbm-hash
22		* (http://www.cse.yorku.ca/~oz/hash.html). */
23		static unsigned int
24	579M	__ZIP_PTR_HASH(const void *p) {
25	579M	unsigned int h = 0;
26	579M	const unsigned char data = (const unsigned char)&p;
27	5.21G	for(size_t i = 0; i < (sizeof(void*) / sizeof(char)); i++)
28	4.63G	h = data[i] + (h << 6) + (h << 16) - h;
29	579M	return h;
30	579M	}
31
32		static ZIP_INLINE enum ZIP_CMP
33	289M	__ZIP_RANK_CMP(const void p1, const void p2) {
34		/* assert(p1 != p2); */
35	289M	unsigned int h1 = __ZIP_PTR_HASH(p1);
36	289M	unsigned int h2 = __ZIP_PTR_HASH(p2);
37	289M	if(h1 == h2)
38	0	return (p1 < p2) ? ZIP_CMP_LESS : ZIP_CMP_MORE;
39	289M	return (h1 < h2) ? ZIP_CMP_LESS : ZIP_CMP_MORE;
40	289M	}
41
42		static ZIP_INLINE enum ZIP_CMP
43	430M	__ZIP_UNIQUE_CMP(zip_cmp_cb cmp, const void p1, const void p2) {
44	430M	if(p1 == p2)
45	68.0M	return ZIP_CMP_EQ;
46	362M	enum ZIP_CMP order = cmp(p1, p2);
47	362M	if(order == ZIP_CMP_EQ)
48	8.89M	return (p1 < p2) ? ZIP_CMP_LESS : ZIP_CMP_MORE;
49	353M	return order;
50	362M	}
51
52		#if 0
53		#include <assert.h>
54		ZIP_UNUSED static ZIP_INLINE void
55		__ZIP_VALIDATE(zip_cmp_cb cmp, unsigned short fieldoffset,
56		unsigned short keyoffset, void *elm,
57		void min_elm, void max_elm) {
58		if(!elm)
59		return;
60		enum ZIP_CMP c1 = __ZIP_UNIQUE_CMP(cmp, ZIP_KEY_PTR(min_elm), ZIP_KEY_PTR(elm));
61		assert((elm == min_elm && c1 == ZIP_CMP_EQ) \|\| c1 == ZIP_CMP_LESS);
62
63		enum ZIP_CMP c2 = __ZIP_UNIQUE_CMP(cmp, ZIP_KEY_PTR(max_elm), ZIP_KEY_PTR(elm));
64		assert((elm == max_elm && c2 == ZIP_CMP_EQ) \|\| c2 == ZIP_CMP_MORE);
65
66		assert(!ZIP_ENTRY_PTR(elm)->right \|\|
67		__ZIP_RANK_CMP(elm, ZIP_ENTRY_PTR(elm)->right) == ZIP_CMP_MORE);
68		assert(!ZIP_ENTRY_PTR(elm)->left \|\|
69		__ZIP_RANK_CMP(elm, ZIP_ENTRY_PTR(elm)->left) == ZIP_CMP_MORE);
70
71		__ZIP_VALIDATE(cmp, fieldoffset, keyoffset, ZIP_ENTRY_PTR(elm)->right, elm, max_elm);
72		__ZIP_VALIDATE(cmp, fieldoffset, keyoffset, ZIP_ENTRY_PTR(elm)->left, min_elm, elm);
73		}
74		#endif
75
76		/* Walk down the right-side spine of cur. Elements that are larger than x_key
77		* are moved under x->right. */
78		static void
79		__ZIP_INSERT_MOVE_RIGHT(zip_cmp_cb cmp, unsigned short fieldoffset,
80		unsigned short keyoffset, const void *x_key,
81	17.3M	zip_elem *fix_edge, zip_elem cur) {
82	40.3M	while(ZIP_ENTRY_PTR(cur)->right) {
83	22.9M	zip_elem *move_candidate = ZIP_ENTRY_PTR(cur)->right;
84	22.9M	if(__ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(move_candidate)) == ZIP_CMP_MORE) {
85	9.39M	cur = ZIP_ENTRY_PTR(cur)->right;
86	9.39M	continue;
87	9.39M	}
88	13.5M	ZIP_ENTRY_PTR(cur)->right = ZIP_ENTRY_PTR(move_candidate)->left;
89	13.5M	ZIP_ENTRY_PTR(move_candidate)->left = NULL;
90	13.5M	*fix_edge = move_candidate;
91	13.5M	fix_edge = &ZIP_ENTRY_PTR(move_candidate)->left;
92	13.5M	}
93	17.3M	}
94
95		static void
96		__ZIP_INSERT_MOVE_LEFT(zip_cmp_cb cmp, unsigned short fieldoffset,
97		unsigned short keyoffset, const void *x_key,
98	44.5M	zip_elem *fix_edge, zip_elem cur) {
99	74.1M	while(ZIP_ENTRY_PTR(cur)->left) {
100	29.6M	zip_elem *move_candidate = ZIP_ENTRY_PTR(cur)->left;
101	29.6M	if(__ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(move_candidate)) == ZIP_CMP_LESS) {
102	16.3M	cur = ZIP_ENTRY_PTR(cur)->left;
103	16.3M	continue;
104	16.3M	}
105	13.2M	ZIP_ENTRY_PTR(cur)->left = ZIP_ENTRY_PTR(move_candidate)->right;
106	13.2M	ZIP_ENTRY_PTR(move_candidate)->right = NULL;
107	13.2M	*fix_edge = move_candidate;
108	13.2M	fix_edge = &ZIP_ENTRY_PTR(move_candidate)->right;
109	13.2M	}
110	44.5M	}
111
112		void
113		__ZIP_INSERT(void *h, zip_cmp_cb cmp, unsigned short fieldoffset,
114	107M	unsigned short keyoffset, void *elm) {
115	107M	zip_elem x = (zip_elem)elm;
116	107M	ZIP_ENTRY_PTR(x)->left = NULL;
117	107M	ZIP_ENTRY_PTR(x)->right = NULL;
118
119	107M	const void *x_key = ZIP_KEY_PTR(x);
120	107M	zip_head head = (zip_head)h;
121	107M	if(!head->root) {
122	19.5M	head->root = x;
123	19.5M	return;
124	19.5M	}
125
126		/* Go down the tree to find the top element "cur" that has a rank smaller
127		* than "x" */
128	88.1M	zip_elem *prev = NULL;
129	88.1M	zip_elem *cur = head->root;
130	88.1M	enum ZIP_CMP cur_order, prev_order = ZIP_CMP_EQ;
131	279M	do {
132	279M	cur_order = __ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(cur));
133	279M	if(cur_order == ZIP_CMP_EQ)
134	0	return; /* x is already inserted */
135	279M	if(__ZIP_RANK_CMP(cur, x) == ZIP_CMP_LESS)
136	61.9M	break;
137	217M	prev = cur;
138	217M	prev_order = cur_order;
139	217M	cur = (cur_order == ZIP_CMP_MORE) ?
140	118M	ZIP_ENTRY_PTR(cur)->right : ZIP_ENTRY_PTR(cur)->left;
141	217M	} while(cur);
142
143		/* Insert "x" instead of "cur" under its parent "prev" */
144	88.1M	if(cur == head->root) {
145	34.6M	head->root = x;
146	53.5M	} else {
147	53.5M	if(prev_order == ZIP_CMP_MORE)
148	16.7M	ZIP_ENTRY_PTR(prev)->right = x;
149	36.8M	else
150	36.8M	ZIP_ENTRY_PTR(prev)->left = x;
151	53.5M	}
152
153	88.1M	if(!cur)
154	26.2M	return;
155
156		/* Re-insert "cur" under "x". Repair by moving elements that ended up on the
157		* wrong side of "x". */
158	61.9M	if(cur_order == ZIP_CMP_MORE) {
159	17.3M	ZIP_ENTRY_PTR(x)->left = cur;
160	17.3M	__ZIP_INSERT_MOVE_RIGHT(cmp, fieldoffset, keyoffset,
161	17.3M	x_key, &ZIP_ENTRY_PTR(x)->right, cur);
162	44.5M	} else {
163	44.5M	ZIP_ENTRY_PTR(x)->right = cur;
164	44.5M	__ZIP_INSERT_MOVE_LEFT(cmp, fieldoffset, keyoffset,
165	44.5M	x_key, &ZIP_ENTRY_PTR(x)->left, cur);
166	44.5M	}
167	61.9M	}
168
169		void *
170		__ZIP_REMOVE(void *h, zip_cmp_cb cmp, unsigned short fieldoffset,
171	68.0M	unsigned short keyoffset, void *elm) {
172	68.0M	zip_head head = (zip_head)h;
173	68.0M	zip_elem x = (zip_elem)elm;
174	68.0M	zip_elem *cur = head->root;
175	68.0M	if(!cur)
176	0	return NULL;
177
178	68.0M	const void *x_key = ZIP_KEY_PTR(x);
179	68.0M	zip_elem **prev_edge = &head->root;
180	68.0M	enum ZIP_CMP cur_order = __ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(cur));
181	98.5M	while(cur_order != ZIP_CMP_EQ) {
182	30.4M	prev_edge = (cur_order == ZIP_CMP_LESS) ?
183	24.3M	&ZIP_ENTRY_PTR(cur)->left : &ZIP_ENTRY_PTR(cur)->right;
184	30.4M	cur = *prev_edge;
185	30.4M	if(!cur)
186	0	return NULL;
187	30.4M	cur_order = __ZIP_UNIQUE_CMP(cmp, x_key, ZIP_KEY_PTR(cur));
188	30.4M	}
189	68.0M	prev_edge = (zip_elem)__ZIP_ZIP(fieldoffset,
190	68.0M	ZIP_ENTRY_PTR(cur)->left,
191	68.0M	ZIP_ENTRY_PTR(cur)->right);
192	68.0M	return cur;
193	68.0M	}
194
195		void *
196		__ZIP_ITER(unsigned short fieldoffset, zip_iter_cb cb,
197	106M	void context, void elm) {
198	106M	if(!elm)
199	51.5M	return NULL;
200	54.8M	zip_elem *left = ZIP_ENTRY_PTR(elm)->left;
201	54.8M	zip_elem *right = ZIP_ENTRY_PTR(elm)->right;
202	54.8M	void *res = __ZIP_ITER(fieldoffset, cb, context, left);
203	54.8M	if(res)
204	3.58M	return res;
205	51.2M	res = cb(context, elm);
206	51.2M	if(res)
207	1.48M	return res;
208	49.7M	return __ZIP_ITER(fieldoffset, cb, context, right);
209	51.2M	}
210
211		void *
212		__ZIP_ITER_KEY(zip_cmp_cb cmp, unsigned short fieldoffset,
213		unsigned short keyoffset, const void *key,
214	6.14k	zip_iter_cb cb, void context, void elm) {
215	6.14k	if(!elm)
216	2.81k	return NULL;
217
218	3.32k	void *res;
219	3.32k	enum ZIP_CMP eq = cmp(key, ZIP_KEY_PTR(elm));
220	3.32k	if(eq != ZIP_CMP_MORE) {
221	3.32k	res = __ZIP_ITER_KEY(cmp, fieldoffset, keyoffset, key,
222	3.32k	cb, context, ZIP_ENTRY_PTR(elm)->left);
223	3.32k	if(res)
224	1.45k	return res;
225	3.32k	}
226
227	1.87k	if(eq == ZIP_CMP_EQ) {
228	1.87k	res = cb(context, elm);
229	1.87k	if(res)
230	1.87k	return res;
231	1.87k	}
232
233	0	if(eq != ZIP_CMP_LESS) {
234	0	res = __ZIP_ITER_KEY(cmp, fieldoffset, keyoffset, key,
235	0	cb, context, ZIP_ENTRY_PTR(elm)->right);
236	0	if(res)
237	0	return res;
238	0	}
239
240	0	return NULL;
241	0	}
242
243		void *
244	68.0M	__ZIP_ZIP(unsigned short fieldoffset, void left, void right) {
245	68.0M	if(!left)
246	55.7M	return right;
247	12.3M	if(!right)
248	3.42M	return left;
249	8.89M	zip_elem l = (zip_elem)left;
250	8.89M	zip_elem r = (zip_elem)right;
251	8.89M	zip_elem *root = NULL;
252	8.89M	zip_elem **prev_edge = &root;
253	19.7M	while(l && r) {
254	10.8M	if(__ZIP_RANK_CMP(l, r) == ZIP_CMP_LESS) {
255	6.32M	*prev_edge = r;
256	6.32M	prev_edge = &ZIP_ENTRY_PTR(r)->left;
257	6.32M	r = ZIP_ENTRY_PTR(r)->left;
258	6.32M	} else {
259	4.49M	*prev_edge = l;
260	4.49M	prev_edge = &ZIP_ENTRY_PTR(l)->right;
261	4.49M	l = ZIP_ENTRY_PTR(l)->right;
262	4.49M	}
263	10.8M	}
264	8.89M	*prev_edge = (l) ? l : r;
265	8.89M	return root;
266	12.3M	}
267
268		/* Walk down from cur and move all elements <= split-key to the left side. All
269		* elements that are moved over have to be below left_rightmost. Returns the
270		* hierarchy of elements that remain on the right side. */
271		static void
272		__ZIP_UNZIP_MOVE_LEFT(zip_cmp_cb cmp, unsigned short fieldoffset,
273		unsigned short keyoffset, const void *key,
274	0	zip_elem *fix_edge, zip_elem cur) {
275	0	while(ZIP_ENTRY_PTR(cur)->left) {
276	0	zip_elem *next = ZIP_ENTRY_PTR(cur)->left;
277	0	if(cmp(key, ZIP_KEY_PTR(next)) == ZIP_CMP_LESS) {
278	0	cur = next;
279	0	continue;
280	0	}
281	0	*fix_edge = next;
282	0	ZIP_ENTRY_PTR(cur)->left = ZIP_ENTRY_PTR(next)->right;
283	0	ZIP_ENTRY_PTR(next)->right = NULL;
284	0	fix_edge = &ZIP_ENTRY_PTR(next)->right;
285	0	}
286	0	}
287
288		static void
289		__ZIP_UNZIP_MOVE_RIGHT(zip_cmp_cb cmp, unsigned short fieldoffset,
290		unsigned short keyoffset, const void *key,
291	0	zip_elem *fix_edge, zip_elem cur) {
292	0	while(ZIP_ENTRY_PTR(cur)->right) {
293	0	zip_elem *next = ZIP_ENTRY_PTR(cur)->right;
294	0	if(cmp(key, ZIP_KEY_PTR(next)) != ZIP_CMP_LESS) {
295	0	cur = next;
296	0	continue;
297	0	}
298	0	*fix_edge = next;
299	0	ZIP_ENTRY_PTR(cur)->right = ZIP_ENTRY_PTR(next)->left;
300	0	ZIP_ENTRY_PTR(next)->left = NULL;
301	0	fix_edge = &ZIP_ENTRY_PTR(next)->left;
302	0	}
303	0	}
304
305		/* Split the tree into a left side with keys <= split-key and a right side with
306		* key > split-key. */
307		void
308		__ZIP_UNZIP(zip_cmp_cb cmp, unsigned short fieldoffset,
309		unsigned short keyoffset, const void *key,
310	8.47k	void h, void l, void *r) {
311	8.47k	zip_elem *prev;
312	8.47k	zip_head head = (zip_head)h;
313	8.47k	zip_head left = (zip_head)l;
314	8.47k	zip_head right = (zip_head)r;
315	8.47k	if(!head->root) {
316	7.29k	left->root = NULL;
317	7.29k	right->root = NULL;
318	7.29k	return;
319	7.29k	}
320	1.18k	zip_elem *cur = head->root;
321	1.18k	if(cmp(key, ZIP_KEY_PTR(cur)) != ZIP_CMP_LESS) {
322	0	left->root = cur;
323	0	do {
324	0	prev = cur;
325	0	cur = ZIP_ENTRY_PTR(cur)->right;
326	0	if(!cur) {
327	0	right->root = NULL;
328	0	return;
329	0	}
330	0	} while(cmp(key, ZIP_KEY_PTR(cur)) != ZIP_CMP_LESS);
331	0	ZIP_ENTRY_PTR(prev)->right = NULL;
332	0	right->root = cur;
333	0	__ZIP_UNZIP_MOVE_LEFT(cmp, fieldoffset, keyoffset, key,
334	0	&ZIP_ENTRY_PTR(prev)->right, cur);
335	1.18k	} else {
336	1.18k	right->root = cur;
337	3.13k	do {
338	3.13k	prev = cur;
339	3.13k	cur = ZIP_ENTRY_PTR(cur)->left;
340	3.13k	if(!cur) {
341	1.18k	left->root = NULL;
342	1.18k	return;
343	1.18k	}
344	3.13k	} while(cmp(key, ZIP_KEY_PTR(cur)) == ZIP_CMP_LESS);
345	0	ZIP_ENTRY_PTR(prev)->left = NULL;
346	0	left->root = cur;
347	0	__ZIP_UNZIP_MOVE_RIGHT(cmp, fieldoffset, keyoffset, key,
348	0	&ZIP_ENTRY_PTR(prev)->left, cur);
349	0	}
350	1.18k	}