Bug Summary

File:got/../lib/object_idset.c
Warning:line 106, column 2
Potential leak of memory pointed to by 'new'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd6.9 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name object_idset.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/local/lib/clang/11.1.0 -I /home/ben/Projects/got/got/../include -I /home/ben/Projects/got/got/../lib -D GOT_LIBEXECDIR=/home/ben/bin -D GOT_VERSION=0.53-current -internal-isystem /usr/local/lib/clang/11.1.0/include -internal-externc-isystem /usr/include -O0 -fdebug-compilation-dir /home/ben/Projects/got/got/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -o /home/ben/Projects/got/scan/2021-05-28-230913-68537-1 -x c /home/ben/Projects/got/got/../lib/object_idset.c
1/*
2 * Copyright (c) 2018, 2019 Stefan Sperling <stsp@openbsd.org>
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17#include <sys/queue.h>
18#include <sys/tree.h>
19
20#include <stdlib.h>
21#include <string.h>
22#include <sha1.h>
23#include <stdio.h>
24#include <zlib.h>
25#include <limits.h>
26#include <time.h>
27
28#include "got_object.h"
29#include "got_error.h"
30
31#include "got_lib_delta.h"
32#include "got_lib_inflate.h"
33#include "got_lib_object.h"
34#include "got_lib_object_idset.h"
35
36struct got_object_idset_element {
37 RB_ENTRY(got_object_idset_element)struct { struct got_object_idset_element *rbe_left; struct got_object_idset_element
*rbe_right; struct got_object_idset_element *rbe_parent; int
rbe_color; } entry;
38 struct got_object_id id;
39 void *data; /* API user data */
40};
41
42RB_HEAD(got_object_idset_tree, got_object_idset_element)struct got_object_idset_tree { struct got_object_idset_element
*rbh_root; };
43
44static int
45cmp_elements(const struct got_object_idset_element *e1,
46 const struct got_object_idset_element *e2)
47{
48 return got_object_id_cmp(&e1->id, &e2->id);
49}
50
51RB_PROTOTYPE(got_object_idset_tree, got_object_idset_element, entry,void got_object_idset_tree_RB_INSERT_COLOR(struct got_object_idset_tree
*, struct got_object_idset_element *); void got_object_idset_tree_RB_REMOVE_COLOR
(struct got_object_idset_tree *, struct got_object_idset_element
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_REMOVE(struct got_object_idset_tree
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_INSERT(struct got_object_idset_tree
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_FIND(struct got_object_idset_tree *
, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_NFIND(struct got_object_idset_tree
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_NEXT(struct got_object_idset_element
*); struct got_object_idset_element *got_object_idset_tree_RB_PREV
(struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_MINMAX(struct got_object_idset_tree
*, int);
52 cmp_elements)void got_object_idset_tree_RB_INSERT_COLOR(struct got_object_idset_tree
*, struct got_object_idset_element *); void got_object_idset_tree_RB_REMOVE_COLOR
(struct got_object_idset_tree *, struct got_object_idset_element
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_REMOVE(struct got_object_idset_tree
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_INSERT(struct got_object_idset_tree
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_FIND(struct got_object_idset_tree *
, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_NFIND(struct got_object_idset_tree
*, struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_NEXT(struct got_object_idset_element
*); struct got_object_idset_element *got_object_idset_tree_RB_PREV
(struct got_object_idset_element *); struct got_object_idset_element
*got_object_idset_tree_RB_MINMAX(struct got_object_idset_tree
*, int);;
53
54struct got_object_idset {
55 struct got_object_idset_tree entries;
56 int totelem;
57#define GOT_OBJECT_IDSET_MAX_ELEM2147483647 INT_MAX2147483647
58};
59
60struct got_object_idset *
61got_object_idset_alloc(void)
62{
63 struct got_object_idset *set;
64
65 set = malloc(sizeof(*set));
66 if (set == NULL((void *)0))
67 return NULL((void *)0);
68
69 RB_INIT(&set->entries)do { (&set->entries)->rbh_root = ((void *)0); } while
(0);
70 set->totelem = 0;
71
72 return set;
73}
74
75void
76got_object_idset_free(struct got_object_idset *set)
77{
78 struct got_object_idset_element *entry;
79
80 while ((entry = RB_MIN(got_object_idset_tree, &set->entries)got_object_idset_tree_RB_MINMAX(&set->entries, -1))) {
81 RB_REMOVE(got_object_idset_tree, &set->entries, entry)got_object_idset_tree_RB_REMOVE(&set->entries, entry);
82 /* User data should be freed by caller. */
83 free(entry);
84 }
85
86 free(set);
87}
88
89const struct got_error *
90got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
91 void *data)
92{
93 struct got_object_idset_element *new;
94
95 if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM2147483647)
1
Assuming field 'totelem' is < GOT_OBJECT_IDSET_MAX_ELEM
→
2
←
Taking false branch
→
96 return got_error(GOT_ERR_NO_SPACE9);
97
98 new = malloc(sizeof(*new));
3
←
Memory is allocated
→
99 if (new == NULL((void *)0))
4
←
Assuming 'new' is not equal to NULL
→
5
←
Taking false branch
→
100 return got_error_from_errno("malloc");
101
102 memcpy(&new->id, id, sizeof(new->id));
103 new->data = data;
104
105 RB_INSERT(got_object_idset_tree, &set->entries, new)got_object_idset_tree_RB_INSERT(&set->entries, new);
106 set->totelem++;
6
←
Potential leak of memory pointed to by 'new'
107 return NULL((void *)0);
108}
109
110static struct got_object_idset_element *
111find_element(struct got_object_idset *set, struct got_object_id *id)
112{
113 struct got_object_idset_element *entry;
114
115 entry = RB_ROOT(&set->entries)(&set->entries)->rbh_root;
116 while (entry) {
117 int cmp = got_object_id_cmp(id, &entry->id);
118 if (cmp < 0)
119 entry = RB_LEFT(entry, entry)(entry)->entry.rbe_left;
120 else if (cmp > 0)
121 entry = RB_RIGHT(entry, entry)(entry)->entry.rbe_right;
122 else
123 break;
124 }
125
126 return entry;
127}
128
129void *
130got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
131{
132 struct got_object_idset_element *entry = find_element(set, id);
133 return entry ? entry->data : NULL((void *)0);
134}
135
136const struct got_error *
137got_object_idset_remove(void **data, struct got_object_idset *set,
138 struct got_object_id *id)
139{
140 struct got_object_idset_element *entry;
141
142 if (data)
143 *data = NULL((void *)0);
144
145 if (set->totelem == 0)
146 return got_error(GOT_ERR_NO_OBJ17);
147
148 if (id == NULL((void *)0))
149 entry = RB_ROOT(&set->entries)(&set->entries)->rbh_root;
150 else
151 entry = find_element(set, id);
152 if (entry == NULL((void *)0))
153 return got_error_no_obj(id);
154
155 RB_REMOVE(got_object_idset_tree, &set->entries, entry)got_object_idset_tree_RB_REMOVE(&set->entries, entry);
156 if (data)
157 *data = entry->data;
158 free(entry);
159 set->totelem--;
160 return NULL((void *)0);
161}
162
163int
164got_object_idset_contains(struct got_object_idset *set,
165 struct got_object_id *id)
166{
167 struct got_object_idset_element *entry = find_element(set, id);
168 return entry ? 1 : 0;
169}
170
171void *
172got_object_idset_lookup_data(struct got_object_idset *set,
173 struct got_object_id *id)
174{
175 struct got_object_idset_element *entry = find_element(set, id);
176 return entry ? entry->data : NULL((void *)0);
177}
178
179const struct got_error *
180got_object_idset_for_each(struct got_object_idset *set,
181 const struct got_error *(*cb)(struct got_object_id *, void *, void *),
182 void *arg)
183{
184 const struct got_error *err;
185 struct got_object_idset_element *entry, *tmp;
186
187 RB_FOREACH_SAFE(entry, got_object_idset_tree, &set->entries, tmp)for ((entry) = got_object_idset_tree_RB_MINMAX(&set->entries
, -1); ((entry) != ((void *)0)) && ((tmp) = got_object_idset_tree_RB_NEXT
(entry), 1); (entry) = (tmp)) {
188 err = (*cb)(&entry->id, entry->data, arg);
189 if (err)
190 return err;
191 }
192 return NULL((void *)0);
193}
194
195int
196got_object_idset_num_elements(struct got_object_idset *set)
197{
198 return set->totelem;
199}
200
201RB_GENERATE(got_object_idset_tree, got_object_idset_element, entry,void got_object_idset_tree_RB_INSERT_COLOR(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*parent, *gparent, *tmp; while ((parent = (elm)->entry.rbe_parent
) && (parent)->entry.rbe_color == 1) { gparent = (
parent)->entry.rbe_parent; if (parent == (gparent)->entry
.rbe_left) { tmp = (gparent)->entry.rbe_right; if (tmp &&
(tmp)->entry.rbe_color == 1) { (tmp)->entry.rbe_color =
0; do { (parent)->entry.rbe_color = 0; (gparent)->entry
.rbe_color = 1; } while (0); elm = gparent; continue; } if ((
parent)->entry.rbe_right == elm) { do { (tmp) = (parent)->
entry.rbe_right; if (((parent)->entry.rbe_right = (tmp)->
entry.rbe_left)) { ((tmp)->entry.rbe_left)->entry.rbe_parent
= (parent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (parent)->entry.rbe_parent)) { if ((parent) == ((parent
)->entry.rbe_parent)->entry.rbe_left) ((parent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry
.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = parent; parent = elm; elm
= tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->
entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->
entry.rbe_left; if (((gparent)->entry.rbe_left = (tmp)->
entry.rbe_right)) { ((tmp)->entry.rbe_right)->entry.rbe_parent
= (gparent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (gparent)->entry.rbe_parent)) { if ((gparent) == ((gparent
)->entry.rbe_parent)->entry.rbe_left) ((gparent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((gparent)->
entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.rbe_right = (gparent); (gparent
)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->
entry.rbe_parent)) do {} while (0); } while (0); } else { tmp
= (gparent)->entry.rbe_left; if (tmp && (tmp)->
entry.rbe_color == 1) { (tmp)->entry.rbe_color = 0; do { (
parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color
= 1; } while (0); elm = gparent; continue; } if ((parent)->
entry.rbe_left == elm) { do { (tmp) = (parent)->entry.rbe_left
; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = parent; parent = elm; elm
= tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->
entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->
entry.rbe_right; if (((gparent)->entry.rbe_right = (tmp)->
entry.rbe_left)) { ((tmp)->entry.rbe_left)->entry.rbe_parent
= (gparent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (gparent)->entry.rbe_parent)) { if ((gparent) == ((gparent
)->entry.rbe_parent)->entry.rbe_left) ((gparent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((gparent)->
entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.rbe_left = (gparent); (gparent
)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->
entry.rbe_parent)) do {} while (0); } while (0); } } (head->
rbh_root)->entry.rbe_color = 0; } void got_object_idset_tree_RB_REMOVE_COLOR
(struct got_object_idset_tree *head, struct got_object_idset_element
*parent, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp; while ((elm == ((void *)0) || (elm)->entry.rbe_color
== 0) && elm != (head)->rbh_root) { if ((parent)->
entry.rbe_left == elm) { tmp = (parent)->entry.rbe_right; if
((tmp)->entry.rbe_color == 1) { do { (tmp)->entry.rbe_color
= 0; (parent)->entry.rbe_color = 1; } while (0); do { (tmp
) = (parent)->entry.rbe_right; if (((parent)->entry.rbe_right
= (tmp)->entry.rbe_left)) { ((tmp)->entry.rbe_left)->
entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->
entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent
) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent
)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent
)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (
head)->rbh_root = (tmp); (tmp)->entry.rbe_left = (parent
); (parent)->entry.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.rbe_parent)) do {} while (0); } while (0);
tmp = (parent)->entry.rbe_right; } if (((tmp)->entry.rbe_left
== ((void *)0) || ((tmp)->entry.rbe_left)->entry.rbe_color
== 0) && ((tmp)->entry.rbe_right == ((void *)0) ||
((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp
)->entry.rbe_color = 1; elm = parent; parent = (elm)->entry
.rbe_parent; } else { if ((tmp)->entry.rbe_right == ((void
*)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0
) { struct got_object_idset_element *oleft; if ((oleft = (tmp
)->entry.rbe_left)) (oleft)->entry.rbe_color = 0; (tmp)
->entry.rbe_color = 1; do { (oleft) = (tmp)->entry.rbe_left
; if (((tmp)->entry.rbe_left = (oleft)->entry.rbe_right
)) { ((oleft)->entry.rbe_right)->entry.rbe_parent = (tmp
); } do {} while (0); if (((oleft)->entry.rbe_parent = (tmp
)->entry.rbe_parent)) { if ((tmp) == ((tmp)->entry.rbe_parent
)->entry.rbe_left) ((tmp)->entry.rbe_parent)->entry.
rbe_left = (oleft); else ((tmp)->entry.rbe_parent)->entry
.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (
oleft)->entry.rbe_right = (tmp); (tmp)->entry.rbe_parent
= (oleft); do {} while (0); if (((oleft)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_right
; } (tmp)->entry.rbe_color = (parent)->entry.rbe_color;
(parent)->entry.rbe_color = 0; if ((tmp)->entry.rbe_right
) ((tmp)->entry.rbe_right)->entry.rbe_color = 0; do { (
tmp) = (parent)->entry.rbe_right; if (((parent)->entry.
rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->entry.rbe_left
)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp
)->entry.rbe_parent = (parent)->entry.rbe_parent)) { if
((parent) == ((parent)->entry.rbe_parent)->entry.rbe_left
) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp);
else ((parent)->entry.rbe_parent)->entry.rbe_right = (
tmp); } else (head)->rbh_root = (tmp); (tmp)->entry.rbe_left
= (parent); (parent)->entry.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while
(0); elm = (head)->rbh_root; break; } } else { tmp = (parent
)->entry.rbe_left; if ((tmp)->entry.rbe_color == 1) { do
{ (tmp)->entry.rbe_color = 0; (parent)->entry.rbe_color
= 1; } while (0); do { (tmp) = (parent)->entry.rbe_left; if
(((parent)->entry.rbe_left = (tmp)->entry.rbe_right)) {
((tmp)->entry.rbe_right)->entry.rbe_parent = (parent);
} do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left
; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->
entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->
entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)
->entry.rbe_color == 0)) { (tmp)->entry.rbe_color = 1; elm
= parent; parent = (elm)->entry.rbe_parent; } else { if (
(tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left
)->entry.rbe_color == 0) { struct got_object_idset_element
*oright; if ((oright = (tmp)->entry.rbe_right)) (oright)->
entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oright
) = (tmp)->entry.rbe_right; if (((tmp)->entry.rbe_right
= (oright)->entry.rbe_left)) { ((oright)->entry.rbe_left
)->entry.rbe_parent = (tmp); } do {} while (0); if (((oright
)->entry.rbe_parent = (tmp)->entry.rbe_parent)) { if ((
tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left) ((tmp
)->entry.rbe_parent)->entry.rbe_left = (oright); else (
(tmp)->entry.rbe_parent)->entry.rbe_right = (oright); }
else (head)->rbh_root = (oright); (oright)->entry.rbe_left
= (tmp); (tmp)->entry.rbe_parent = (oright); do {} while (
0); if (((oright)->entry.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->entry.rbe_left; } (tmp)->entry.rbe_color
= (parent)->entry.rbe_color; (parent)->entry.rbe_color
= 0; if ((tmp)->entry.rbe_left) ((tmp)->entry.rbe_left
)->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_left
; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); elm = (head)->rbh_root; break
; } } } if (elm) (elm)->entry.rbe_color = 0; } struct got_object_idset_element
* got_object_idset_tree_RB_REMOVE(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*child, *parent, *old = elm; int color; if ((elm)->entry.
rbe_left == ((void *)0)) child = (elm)->entry.rbe_right; else
if ((elm)->entry.rbe_right == ((void *)0)) child = (elm)->
entry.rbe_left; else { struct got_object_idset_element *left;
elm = (elm)->entry.rbe_right; while ((left = (elm)->entry
.rbe_left)) elm = left; child = (elm)->entry.rbe_right; parent
= (elm)->entry.rbe_parent; color = (elm)->entry.rbe_color
; if (child) (child)->entry.rbe_parent = parent; if (parent
) { if ((parent)->entry.rbe_left == elm) (parent)->entry
.rbe_left = child; else (parent)->entry.rbe_right = child;
do {} while (0); } else (head)->rbh_root = child; if ((elm
)->entry.rbe_parent == old) parent = elm; (elm)->entry =
(old)->entry; if ((old)->entry.rbe_parent) { if (((old
)->entry.rbe_parent)->entry.rbe_left == old) ((old)->
entry.rbe_parent)->entry.rbe_left = elm; else ((old)->entry
.rbe_parent)->entry.rbe_right = elm; do {} while (0); } else
(head)->rbh_root = elm; ((old)->entry.rbe_left)->entry
.rbe_parent = elm; if ((old)->entry.rbe_right) ((old)->
entry.rbe_right)->entry.rbe_parent = elm; if (parent) { left
= parent; do { do {} while (0); } while ((left = (left)->
entry.rbe_parent)); } goto color; } parent = (elm)->entry.
rbe_parent; color = (elm)->entry.rbe_color; if (child) (child
)->entry.rbe_parent = parent; if (parent) { if ((parent)->
entry.rbe_left == elm) (parent)->entry.rbe_left = child; else
(parent)->entry.rbe_right = child; do {} while (0); } else
(head)->rbh_root = child; color: if (color == 0) got_object_idset_tree_RB_REMOVE_COLOR
(head, parent, child); return (old); } struct got_object_idset_element
* got_object_idset_tree_RB_INSERT(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp; struct got_object_idset_element *parent = ((void *)0);
int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent
= tmp; comp = (cmp_elements)(elm, parent); if (comp < 0) tmp
= (tmp)->entry.rbe_left; else if (comp > 0) tmp = (tmp
)->entry.rbe_right; else return (tmp); } do { (elm)->entry
.rbe_parent = parent; (elm)->entry.rbe_left = (elm)->entry
.rbe_right = ((void *)0); (elm)->entry.rbe_color = 1; } while
(0); if (parent != ((void *)0)) { if (comp < 0) (parent)->
entry.rbe_left = elm; else (parent)->entry.rbe_right = elm
; do {} while (0); } else (head)->rbh_root = elm; got_object_idset_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct got_object_idset_element
* got_object_idset_tree_RB_FIND(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = cmp_elements
(elm, tmp); if (comp < 0) tmp = (tmp)->entry.rbe_left; else
if (comp > 0) tmp = (tmp)->entry.rbe_right; else return
(tmp); } return (((void *)0)); } struct got_object_idset_element
* got_object_idset_tree_RB_NFIND(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp = (head)->rbh_root; struct got_object_idset_element *
res = ((void *)0); int comp; while (tmp) { comp = cmp_elements
(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->entry
.rbe_left; } else if (comp > 0) tmp = (tmp)->entry.rbe_right
; else return (tmp); } return (res); } struct got_object_idset_element
* got_object_idset_tree_RB_NEXT(struct got_object_idset_element
*elm) { if ((elm)->entry.rbe_right) { elm = (elm)->entry
.rbe_right; while ((elm)->entry.rbe_left) elm = (elm)->
entry.rbe_left; } else { if ((elm)->entry.rbe_parent &&
(elm == ((elm)->entry.rbe_parent)->entry.rbe_left)) elm
= (elm)->entry.rbe_parent; else { while ((elm)->entry.
rbe_parent && (elm == ((elm)->entry.rbe_parent)->
entry.rbe_right)) elm = (elm)->entry.rbe_parent; elm = (elm
)->entry.rbe_parent; } } return (elm); } struct got_object_idset_element
* got_object_idset_tree_RB_PREV(struct got_object_idset_element
*elm) { if ((elm)->entry.rbe_left) { elm = (elm)->entry
.rbe_left; while ((elm)->entry.rbe_right) elm = (elm)->
entry.rbe_right; } else { if ((elm)->entry.rbe_parent &&
(elm == ((elm)->entry.rbe_parent)->entry.rbe_right)) elm
= (elm)->entry.rbe_parent; else { while ((elm)->entry.
rbe_parent && (elm == ((elm)->entry.rbe_parent)->
entry.rbe_left)) elm = (elm)->entry.rbe_parent; elm = (elm
)->entry.rbe_parent; } } return (elm); } struct got_object_idset_element
* got_object_idset_tree_RB_MINMAX(struct got_object_idset_tree
*head, int val) { struct got_object_idset_element *tmp = (head
)->rbh_root; struct got_object_idset_element *parent = ((void
*)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp
)->entry.rbe_left; else tmp = (tmp)->entry.rbe_right; }
return (parent); }
202 cmp_elements)void got_object_idset_tree_RB_INSERT_COLOR(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*parent, *gparent, *tmp; while ((parent = (elm)->entry.rbe_parent
) && (parent)->entry.rbe_color == 1) { gparent = (
parent)->entry.rbe_parent; if (parent == (gparent)->entry
.rbe_left) { tmp = (gparent)->entry.rbe_right; if (tmp &&
(tmp)->entry.rbe_color == 1) { (tmp)->entry.rbe_color =
0; do { (parent)->entry.rbe_color = 0; (gparent)->entry
.rbe_color = 1; } while (0); elm = gparent; continue; } if ((
parent)->entry.rbe_right == elm) { do { (tmp) = (parent)->
entry.rbe_right; if (((parent)->entry.rbe_right = (tmp)->
entry.rbe_left)) { ((tmp)->entry.rbe_left)->entry.rbe_parent
= (parent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (parent)->entry.rbe_parent)) { if ((parent) == ((parent
)->entry.rbe_parent)->entry.rbe_left) ((parent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry
.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = parent; parent = elm; elm
= tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->
entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->
entry.rbe_left; if (((gparent)->entry.rbe_left = (tmp)->
entry.rbe_right)) { ((tmp)->entry.rbe_right)->entry.rbe_parent
= (gparent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (gparent)->entry.rbe_parent)) { if ((gparent) == ((gparent
)->entry.rbe_parent)->entry.rbe_left) ((gparent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((gparent)->
entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.rbe_right = (gparent); (gparent
)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->
entry.rbe_parent)) do {} while (0); } while (0); } else { tmp
= (gparent)->entry.rbe_left; if (tmp && (tmp)->
entry.rbe_color == 1) { (tmp)->entry.rbe_color = 0; do { (
parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color
= 1; } while (0); elm = gparent; continue; } if ((parent)->
entry.rbe_left == elm) { do { (tmp) = (parent)->entry.rbe_left
; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = parent; parent = elm; elm
= tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->
entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->
entry.rbe_right; if (((gparent)->entry.rbe_right = (tmp)->
entry.rbe_left)) { ((tmp)->entry.rbe_left)->entry.rbe_parent
= (gparent); } do {} while (0); if (((tmp)->entry.rbe_parent
= (gparent)->entry.rbe_parent)) { if ((gparent) == ((gparent
)->entry.rbe_parent)->entry.rbe_left) ((gparent)->entry
.rbe_parent)->entry.rbe_left = (tmp); else ((gparent)->
entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->
rbh_root = (tmp); (tmp)->entry.rbe_left = (gparent); (gparent
)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->
entry.rbe_parent)) do {} while (0); } while (0); } } (head->
rbh_root)->entry.rbe_color = 0; } void got_object_idset_tree_RB_REMOVE_COLOR
(struct got_object_idset_tree *head, struct got_object_idset_element
*parent, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp; while ((elm == ((void *)0) || (elm)->entry.rbe_color
== 0) && elm != (head)->rbh_root) { if ((parent)->
entry.rbe_left == elm) { tmp = (parent)->entry.rbe_right; if
((tmp)->entry.rbe_color == 1) { do { (tmp)->entry.rbe_color
= 0; (parent)->entry.rbe_color = 1; } while (0); do { (tmp
) = (parent)->entry.rbe_right; if (((parent)->entry.rbe_right
= (tmp)->entry.rbe_left)) { ((tmp)->entry.rbe_left)->
entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->
entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent
) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent
)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent
)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (
head)->rbh_root = (tmp); (tmp)->entry.rbe_left = (parent
); (parent)->entry.rbe_parent = (tmp); do {} while (0); if
(((tmp)->entry.rbe_parent)) do {} while (0); } while (0);
tmp = (parent)->entry.rbe_right; } if (((tmp)->entry.rbe_left
== ((void *)0) || ((tmp)->entry.rbe_left)->entry.rbe_color
== 0) && ((tmp)->entry.rbe_right == ((void *)0) ||
((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp
)->entry.rbe_color = 1; elm = parent; parent = (elm)->entry
.rbe_parent; } else { if ((tmp)->entry.rbe_right == ((void
*)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0
) { struct got_object_idset_element *oleft; if ((oleft = (tmp
)->entry.rbe_left)) (oleft)->entry.rbe_color = 0; (tmp)
->entry.rbe_color = 1; do { (oleft) = (tmp)->entry.rbe_left
; if (((tmp)->entry.rbe_left = (oleft)->entry.rbe_right
)) { ((oleft)->entry.rbe_right)->entry.rbe_parent = (tmp
); } do {} while (0); if (((oleft)->entry.rbe_parent = (tmp
)->entry.rbe_parent)) { if ((tmp) == ((tmp)->entry.rbe_parent
)->entry.rbe_left) ((tmp)->entry.rbe_parent)->entry.
rbe_left = (oleft); else ((tmp)->entry.rbe_parent)->entry
.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (
oleft)->entry.rbe_right = (tmp); (tmp)->entry.rbe_parent
= (oleft); do {} while (0); if (((oleft)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_right
; } (tmp)->entry.rbe_color = (parent)->entry.rbe_color;
(parent)->entry.rbe_color = 0; if ((tmp)->entry.rbe_right
) ((tmp)->entry.rbe_right)->entry.rbe_color = 0; do { (
tmp) = (parent)->entry.rbe_right; if (((parent)->entry.
rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->entry.rbe_left
)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp
)->entry.rbe_parent = (parent)->entry.rbe_parent)) { if
((parent) == ((parent)->entry.rbe_parent)->entry.rbe_left
) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp);
else ((parent)->entry.rbe_parent)->entry.rbe_right = (
tmp); } else (head)->rbh_root = (tmp); (tmp)->entry.rbe_left
= (parent); (parent)->entry.rbe_parent = (tmp); do {} while
(0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while
(0); elm = (head)->rbh_root; break; } } else { tmp = (parent
)->entry.rbe_left; if ((tmp)->entry.rbe_color == 1) { do
{ (tmp)->entry.rbe_color = 0; (parent)->entry.rbe_color
= 1; } while (0); do { (tmp) = (parent)->entry.rbe_left; if
(((parent)->entry.rbe_left = (tmp)->entry.rbe_right)) {
((tmp)->entry.rbe_right)->entry.rbe_parent = (parent);
} do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left
; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->
entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->
entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)
->entry.rbe_color == 0)) { (tmp)->entry.rbe_color = 1; elm
= parent; parent = (elm)->entry.rbe_parent; } else { if (
(tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left
)->entry.rbe_color == 0) { struct got_object_idset_element
*oright; if ((oright = (tmp)->entry.rbe_right)) (oright)->
entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oright
) = (tmp)->entry.rbe_right; if (((tmp)->entry.rbe_right
= (oright)->entry.rbe_left)) { ((oright)->entry.rbe_left
)->entry.rbe_parent = (tmp); } do {} while (0); if (((oright
)->entry.rbe_parent = (tmp)->entry.rbe_parent)) { if ((
tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left) ((tmp
)->entry.rbe_parent)->entry.rbe_left = (oright); else (
(tmp)->entry.rbe_parent)->entry.rbe_right = (oright); }
else (head)->rbh_root = (oright); (oright)->entry.rbe_left
= (tmp); (tmp)->entry.rbe_parent = (oright); do {} while (
0); if (((oright)->entry.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->entry.rbe_left; } (tmp)->entry.rbe_color
= (parent)->entry.rbe_color; (parent)->entry.rbe_color
= 0; if ((tmp)->entry.rbe_left) ((tmp)->entry.rbe_left
)->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_left
; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right
)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent
); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent
)->entry.rbe_parent)) { if ((parent) == ((parent)->entry
.rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent
)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent
)->entry.rbe_right = (tmp); } else (head)->rbh_root = (
tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry
.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent
)) do {} while (0); } while (0); elm = (head)->rbh_root; break
; } } } if (elm) (elm)->entry.rbe_color = 0; } struct got_object_idset_element
* got_object_idset_tree_RB_REMOVE(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*child, *parent, *old = elm; int color; if ((elm)->entry.
rbe_left == ((void *)0)) child = (elm)->entry.rbe_right; else
if ((elm)->entry.rbe_right == ((void *)0)) child = (elm)->
entry.rbe_left; else { struct got_object_idset_element *left;
elm = (elm)->entry.rbe_right; while ((left = (elm)->entry
.rbe_left)) elm = left; child = (elm)->entry.rbe_right; parent
= (elm)->entry.rbe_parent; color = (elm)->entry.rbe_color
; if (child) (child)->entry.rbe_parent = parent; if (parent
) { if ((parent)->entry.rbe_left == elm) (parent)->entry
.rbe_left = child; else (parent)->entry.rbe_right = child;
do {} while (0); } else (head)->rbh_root = child; if ((elm
)->entry.rbe_parent == old) parent = elm; (elm)->entry =
(old)->entry; if ((old)->entry.rbe_parent) { if (((old
)->entry.rbe_parent)->entry.rbe_left == old) ((old)->
entry.rbe_parent)->entry.rbe_left = elm; else ((old)->entry
.rbe_parent)->entry.rbe_right = elm; do {} while (0); } else
(head)->rbh_root = elm; ((old)->entry.rbe_left)->entry
.rbe_parent = elm; if ((old)->entry.rbe_right) ((old)->
entry.rbe_right)->entry.rbe_parent = elm; if (parent) { left
= parent; do { do {} while (0); } while ((left = (left)->
entry.rbe_parent)); } goto color; } parent = (elm)->entry.
rbe_parent; color = (elm)->entry.rbe_color; if (child) (child
)->entry.rbe_parent = parent; if (parent) { if ((parent)->
entry.rbe_left == elm) (parent)->entry.rbe_left = child; else
(parent)->entry.rbe_right = child; do {} while (0); } else
(head)->rbh_root = child; color: if (color == 0) got_object_idset_tree_RB_REMOVE_COLOR
(head, parent, child); return (old); } struct got_object_idset_element
* got_object_idset_tree_RB_INSERT(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp; struct got_object_idset_element *parent = ((void *)0);
int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent
= tmp; comp = (cmp_elements)(elm, parent); if (comp < 0) tmp
= (tmp)->entry.rbe_left; else if (comp > 0) tmp = (tmp
)->entry.rbe_right; else return (tmp); } do { (elm)->entry
.rbe_parent = parent; (elm)->entry.rbe_left = (elm)->entry
.rbe_right = ((void *)0); (elm)->entry.rbe_color = 1; } while
(0); if (parent != ((void *)0)) { if (comp < 0) (parent)->
entry.rbe_left = elm; else (parent)->entry.rbe_right = elm
; do {} while (0); } else (head)->rbh_root = elm; got_object_idset_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct got_object_idset_element
* got_object_idset_tree_RB_FIND(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp = (head)->rbh_root; int comp; while (tmp) { comp = cmp_elements
(elm, tmp); if (comp < 0) tmp = (tmp)->entry.rbe_left; else
if (comp > 0) tmp = (tmp)->entry.rbe_right; else return
(tmp); } return (((void *)0)); } struct got_object_idset_element
* got_object_idset_tree_RB_NFIND(struct got_object_idset_tree
*head, struct got_object_idset_element *elm) { struct got_object_idset_element
*tmp = (head)->rbh_root; struct got_object_idset_element *
res = ((void *)0); int comp; while (tmp) { comp = cmp_elements
(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->entry
.rbe_left; } else if (comp > 0) tmp = (tmp)->entry.rbe_right
; else return (tmp); } return (res); } struct got_object_idset_element
* got_object_idset_tree_RB_NEXT(struct got_object_idset_element
*elm) { if ((elm)->entry.rbe_right) { elm = (elm)->entry
.rbe_right; while ((elm)->entry.rbe_left) elm = (elm)->
entry.rbe_left; } else { if ((elm)->entry.rbe_parent &&
(elm == ((elm)->entry.rbe_parent)->entry.rbe_left)) elm
= (elm)->entry.rbe_parent; else { while ((elm)->entry.
rbe_parent && (elm == ((elm)->entry.rbe_parent)->
entry.rbe_right)) elm = (elm)->entry.rbe_parent; elm = (elm
)->entry.rbe_parent; } } return (elm); } struct got_object_idset_element
* got_object_idset_tree_RB_PREV(struct got_object_idset_element
*elm) { if ((elm)->entry.rbe_left) { elm = (elm)->entry
.rbe_left; while ((elm)->entry.rbe_right) elm = (elm)->
entry.rbe_right; } else { if ((elm)->entry.rbe_parent &&
(elm == ((elm)->entry.rbe_parent)->entry.rbe_right)) elm
= (elm)->entry.rbe_parent; else { while ((elm)->entry.
rbe_parent && (elm == ((elm)->entry.rbe_parent)->
entry.rbe_left)) elm = (elm)->entry.rbe_parent; elm = (elm
)->entry.rbe_parent; } } return (elm); } struct got_object_idset_element
* got_object_idset_tree_RB_MINMAX(struct got_object_idset_tree
*head, int val) { struct got_object_idset_element *tmp = (head
)->rbh_root; struct got_object_idset_element *parent = ((void
*)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp
)->entry.rbe_left; else tmp = (tmp)->entry.rbe_right; }
return (parent); };