Bug Summary

File:src/usr.sbin/ldapctl/../ldapd/schema.c
Warning:line 936, column 7
Null pointer passed as 1st argument to string comparison function

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name schema.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 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/ldapctl/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/usr.sbin/ldapctl/../ldapd -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/ldapctl/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -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 -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/ldapctl/../ldapd/schema.c
1/* $OpenBSD: schema.c,v 1.19 2019/10/24 12:39:26 tb Exp $ */
2
3/*
4 * Copyright (c) 2010 Martin Hedenfalk <martinh@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19#include <sys/types.h>
20
21#include <ctype.h>
22#include <stdlib.h>
23#include <string.h>
24#include <syslog.h>
25
26#include "ldapd.h"
27#include "log.h"
28
29#define ERROR-1 -1
30#define STRING1 1
31
32static int
33attr_oid_cmp(struct attr_type *a, struct attr_type *b)
34{
35 return strcasecmp(a->oid, b->oid);
36}
37
38static int
39obj_oid_cmp(struct object *a, struct object *b)
40{
41 return strcasecmp(a->oid, b->oid);
42}
43
44static int
45oidname_cmp(struct oidname *a, struct oidname *b)
46{
47 return strcasecmp(a->on_name, b->on_name);
48}
49
50static int
51symoid_cmp(struct symoid *a, struct symoid *b)
52{
53 return strcasecmp(a->name, b->name);
54}
55
56RB_GENERATE(attr_type_tree, attr_type, link, attr_oid_cmp)void attr_type_tree_RB_INSERT_COLOR(struct attr_type_tree *head
, struct attr_type *elm) { struct attr_type *parent, *gparent
, *tmp; while ((parent = (elm)->link.rbe_parent) &&
(parent)->link.rbe_color == 1) { gparent = (parent)->link
.rbe_parent; if (parent == (gparent)->link.rbe_left) { tmp
= (gparent)->link.rbe_right; if (tmp && (tmp)->
link.rbe_color == 1) { (tmp)->link.rbe_color = 0; do { (parent
)->link.rbe_color = 0; (gparent)->link.rbe_color = 1; }
while (0); elm = gparent; continue; } if ((parent)->link.
rbe_right == elm) { do { (tmp) = (parent)->link.rbe_right;
if (((parent)->link.rbe_right = (tmp)->link.rbe_left))
{ ((tmp)->link.rbe_left)->link.rbe_parent = (parent); }
do {} while (0); if (((tmp)->link.rbe_parent = (parent)->
link.rbe_parent)) { if ((parent) == ((parent)->link.rbe_parent
)->link.rbe_left) ((parent)->link.rbe_parent)->link.
rbe_left = (tmp); else ((parent)->link.rbe_parent)->link
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->link.rbe_left = (parent); (parent)->link.rbe_parent =
(tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do {
} while (0); } while (0); tmp = parent; parent = elm; elm = tmp
; } do { (parent)->link.rbe_color = 0; (gparent)->link.
rbe_color = 1; } while (0); do { (tmp) = (gparent)->link.rbe_left
; if (((gparent)->link.rbe_left = (tmp)->link.rbe_right
)) { ((tmp)->link.rbe_right)->link.rbe_parent = (gparent
); } do {} while (0); if (((tmp)->link.rbe_parent = (gparent
)->link.rbe_parent)) { if ((gparent) == ((gparent)->link
.rbe_parent)->link.rbe_left) ((gparent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((gparent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (gparent); (gparent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); } else { tmp = (gparent)->link
.rbe_left; if (tmp && (tmp)->link.rbe_color == 1) {
(tmp)->link.rbe_color = 0; do { (parent)->link.rbe_color
= 0; (gparent)->link.rbe_color = 1; } while (0); elm = gparent
; continue; } if ((parent)->link.rbe_left == elm) { do { (
tmp) = (parent)->link.rbe_left; if (((parent)->link.rbe_left
= (tmp)->link.rbe_right)) { ((tmp)->link.rbe_right)->
link.rbe_parent = (parent); } do {} while (0); if (((tmp)->
link.rbe_parent = (parent)->link.rbe_parent)) { if ((parent
) == ((parent)->link.rbe_parent)->link.rbe_left) ((parent
)->link.rbe_parent)->link.rbe_left = (tmp); else ((parent
)->link.rbe_parent)->link.rbe_right = (tmp); } else (head
)->rbh_root = (tmp); (tmp)->link.rbe_right = (parent); (
parent)->link.rbe_parent = (tmp); do {} while (0); if (((tmp
)->link.rbe_parent)) do {} while (0); } while (0); tmp = parent
; parent = elm; elm = tmp; } do { (parent)->link.rbe_color
= 0; (gparent)->link.rbe_color = 1; } while (0); do { (tmp
) = (gparent)->link.rbe_right; if (((gparent)->link.rbe_right
= (tmp)->link.rbe_left)) { ((tmp)->link.rbe_left)->
link.rbe_parent = (gparent); } do {} while (0); if (((tmp)->
link.rbe_parent = (gparent)->link.rbe_parent)) { if ((gparent
) == ((gparent)->link.rbe_parent)->link.rbe_left) ((gparent
)->link.rbe_parent)->link.rbe_left = (tmp); else ((gparent
)->link.rbe_parent)->link.rbe_right = (tmp); } else (head
)->rbh_root = (tmp); (tmp)->link.rbe_left = (gparent); (
gparent)->link.rbe_parent = (tmp); do {} while (0); if (((
tmp)->link.rbe_parent)) do {} while (0); } while (0); } } (
head->rbh_root)->link.rbe_color = 0; } void attr_type_tree_RB_REMOVE_COLOR
(struct attr_type_tree *head, struct attr_type *parent, struct
attr_type *elm) { struct attr_type *tmp; while ((elm == ((void
*)0) || (elm)->link.rbe_color == 0) && elm != (head
)->rbh_root) { if ((parent)->link.rbe_left == elm) { tmp
= (parent)->link.rbe_right; if ((tmp)->link.rbe_color ==
1) { do { (tmp)->link.rbe_color = 0; (parent)->link.rbe_color
= 1; } while (0); do { (tmp) = (parent)->link.rbe_right; if
(((parent)->link.rbe_right = (tmp)->link.rbe_left)) { (
(tmp)->link.rbe_left)->link.rbe_parent = (parent); } do
{} while (0); if (((tmp)->link.rbe_parent = (parent)->
link.rbe_parent)) { if ((parent) == ((parent)->link.rbe_parent
)->link.rbe_left) ((parent)->link.rbe_parent)->link.
rbe_left = (tmp); else ((parent)->link.rbe_parent)->link
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->link.rbe_left = (parent); (parent)->link.rbe_parent =
(tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do {
} while (0); } while (0); tmp = (parent)->link.rbe_right; }
if (((tmp)->link.rbe_left == ((void*)0) || ((tmp)->link
.rbe_left)->link.rbe_color == 0) && ((tmp)->link
.rbe_right == ((void*)0) || ((tmp)->link.rbe_right)->link
.rbe_color == 0)) { (tmp)->link.rbe_color = 1; elm = parent
; parent = (elm)->link.rbe_parent; } else { if ((tmp)->
link.rbe_right == ((void*)0) || ((tmp)->link.rbe_right)->
link.rbe_color == 0) { struct attr_type *oleft; if ((oleft = (
tmp)->link.rbe_left)) (oleft)->link.rbe_color = 0; (tmp
)->link.rbe_color = 1; do { (oleft) = (tmp)->link.rbe_left
; if (((tmp)->link.rbe_left = (oleft)->link.rbe_right))
{ ((oleft)->link.rbe_right)->link.rbe_parent = (tmp); }
do {} while (0); if (((oleft)->link.rbe_parent = (tmp)->
link.rbe_parent)) { if ((tmp) == ((tmp)->link.rbe_parent)->
link.rbe_left) ((tmp)->link.rbe_parent)->link.rbe_left =
(oleft); else ((tmp)->link.rbe_parent)->link.rbe_right
= (oleft); } else (head)->rbh_root = (oleft); (oleft)->
link.rbe_right = (tmp); (tmp)->link.rbe_parent = (oleft); do
{} while (0); if (((oleft)->link.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->link.rbe_right; } (tmp)
->link.rbe_color = (parent)->link.rbe_color; (parent)->
link.rbe_color = 0; if ((tmp)->link.rbe_right) ((tmp)->
link.rbe_right)->link.rbe_color = 0; do { (tmp) = (parent)
->link.rbe_right; if (((parent)->link.rbe_right = (tmp)
->link.rbe_left)) { ((tmp)->link.rbe_left)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_left = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); elm = (head)->rbh_root; break;
} } else { tmp = (parent)->link.rbe_left; if ((tmp)->link
.rbe_color == 1) { do { (tmp)->link.rbe_color = 0; (parent
)->link.rbe_color = 1; } while (0); do { (tmp) = (parent)->
link.rbe_left; if (((parent)->link.rbe_left = (tmp)->link
.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = (parent)->link.rbe_left;
} if (((tmp)->link.rbe_left == ((void*)0) || ((tmp)->link
.rbe_left)->link.rbe_color == 0) && ((tmp)->link
.rbe_right == ((void*)0) || ((tmp)->link.rbe_right)->link
.rbe_color == 0)) { (tmp)->link.rbe_color = 1; elm = parent
; parent = (elm)->link.rbe_parent; } else { if ((tmp)->
link.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->
link.rbe_color == 0) { struct attr_type *oright; if ((oright =
(tmp)->link.rbe_right)) (oright)->link.rbe_color = 0; (
tmp)->link.rbe_color = 1; do { (oright) = (tmp)->link.rbe_right
; if (((tmp)->link.rbe_right = (oright)->link.rbe_left)
) { ((oright)->link.rbe_left)->link.rbe_parent = (tmp);
} do {} while (0); if (((oright)->link.rbe_parent = (tmp)
->link.rbe_parent)) { if ((tmp) == ((tmp)->link.rbe_parent
)->link.rbe_left) ((tmp)->link.rbe_parent)->link.rbe_left
= (oright); else ((tmp)->link.rbe_parent)->link.rbe_right
= (oright); } else (head)->rbh_root = (oright); (oright)->
link.rbe_left = (tmp); (tmp)->link.rbe_parent = (oright); do
{} while (0); if (((oright)->link.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->link.rbe_left; } (tmp)->
link.rbe_color = (parent)->link.rbe_color; (parent)->link
.rbe_color = 0; if ((tmp)->link.rbe_left) ((tmp)->link.
rbe_left)->link.rbe_color = 0; do { (tmp) = (parent)->link
.rbe_left; if (((parent)->link.rbe_left = (tmp)->link.rbe_right
)) { ((tmp)->link.rbe_right)->link.rbe_parent = (parent
); } do {} while (0); if (((tmp)->link.rbe_parent = (parent
)->link.rbe_parent)) { if ((parent) == ((parent)->link.
rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent)
->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); elm = (head)->rbh_root; break;
} } } if (elm) (elm)->link.rbe_color = 0; } struct attr_type
* attr_type_tree_RB_REMOVE(struct attr_type_tree *head, struct
attr_type *elm) { struct attr_type *child, *parent, *old = elm
; int color; if ((elm)->link.rbe_left == ((void*)0)) child
= (elm)->link.rbe_right; else if ((elm)->link.rbe_right
== ((void*)0)) child = (elm)->link.rbe_left; else { struct
attr_type *left; elm = (elm)->link.rbe_right; while ((left
= (elm)->link.rbe_left)) elm = left; child = (elm)->link
.rbe_right; parent = (elm)->link.rbe_parent; color = (elm)
->link.rbe_color; if (child) (child)->link.rbe_parent =
parent; if (parent) { if ((parent)->link.rbe_left == elm)
(parent)->link.rbe_left = child; else (parent)->link.rbe_right
= child; do {} while (0); } else (head)->rbh_root = child
; if ((elm)->link.rbe_parent == old) parent = elm; (elm)->
link = (old)->link; if ((old)->link.rbe_parent) { if ((
(old)->link.rbe_parent)->link.rbe_left == old) ((old)->
link.rbe_parent)->link.rbe_left = elm; else ((old)->link
.rbe_parent)->link.rbe_right = elm; do {} while (0); } else
(head)->rbh_root = elm; ((old)->link.rbe_left)->link
.rbe_parent = elm; if ((old)->link.rbe_right) ((old)->link
.rbe_right)->link.rbe_parent = elm; if (parent) { left = parent
; do { do {} while (0); } while ((left = (left)->link.rbe_parent
)); } goto color; } parent = (elm)->link.rbe_parent; color
= (elm)->link.rbe_color; if (child) (child)->link.rbe_parent
= parent; if (parent) { if ((parent)->link.rbe_left == elm
) (parent)->link.rbe_left = child; else (parent)->link.
rbe_right = child; do {} while (0); } else (head)->rbh_root
= child; color: if (color == 0) attr_type_tree_RB_REMOVE_COLOR
(head, parent, child); return (old); } struct attr_type * attr_type_tree_RB_INSERT
(struct attr_type_tree *head, struct attr_type *elm) { struct
attr_type *tmp; struct attr_type *parent = ((void*)0); int comp
= 0; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp
= (attr_oid_cmp)(elm, parent); if (comp < 0) tmp = (tmp)->
link.rbe_left; else if (comp > 0) tmp = (tmp)->link.rbe_right
; else return (tmp); } do { (elm)->link.rbe_parent = parent
; (elm)->link.rbe_left = (elm)->link.rbe_right = ((void
*)0); (elm)->link.rbe_color = 1; } while (0); if (parent !=
((void*)0)) { if (comp < 0) (parent)->link.rbe_left = elm
; else (parent)->link.rbe_right = elm; do {} while (0); } else
(head)->rbh_root = elm; attr_type_tree_RB_INSERT_COLOR(head
, elm); return (((void*)0)); } struct attr_type * attr_type_tree_RB_FIND
(struct attr_type_tree *head, struct attr_type *elm) { struct
attr_type *tmp = (head)->rbh_root; int comp; while (tmp) {
comp = attr_oid_cmp(elm, tmp); if (comp < 0) tmp = (tmp)->
link.rbe_left; else if (comp > 0) tmp = (tmp)->link.rbe_right
; else return (tmp); } return (((void*)0)); } struct attr_type
* attr_type_tree_RB_NFIND(struct attr_type_tree *head, struct
attr_type *elm) { struct attr_type *tmp = (head)->rbh_root
; struct attr_type *res = ((void*)0); int comp; while (tmp) {
comp = attr_oid_cmp(elm, tmp); if (comp < 0) { res = tmp;
tmp = (tmp)->link.rbe_left; } else if (comp > 0) tmp =
(tmp)->link.rbe_right; else return (tmp); } return (res);
} struct attr_type * attr_type_tree_RB_NEXT(struct attr_type
*elm) { if ((elm)->link.rbe_right) { elm = (elm)->link
.rbe_right; while ((elm)->link.rbe_left) elm = (elm)->link
.rbe_left; } else { if ((elm)->link.rbe_parent && (
elm == ((elm)->link.rbe_parent)->link.rbe_left)) elm = (
elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_right
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct attr_type * attr_type_tree_RB_PREV
(struct attr_type *elm) { if ((elm)->link.rbe_left) { elm =
(elm)->link.rbe_left; while ((elm)->link.rbe_right) elm
= (elm)->link.rbe_right; } else { if ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_right
)) elm = (elm)->link.rbe_parent; else { while ((elm)->link
.rbe_parent && (elm == ((elm)->link.rbe_parent)->
link.rbe_left)) elm = (elm)->link.rbe_parent; elm = (elm)->
link.rbe_parent; } } return (elm); } struct attr_type * attr_type_tree_RB_MINMAX
(struct attr_type_tree *head, int val) { struct attr_type *tmp
= (head)->rbh_root; struct attr_type *parent = ((void*)0)
; while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->
link.rbe_left; else tmp = (tmp)->link.rbe_right; } return (
parent); };
57RB_GENERATE(object_tree, object, link, obj_oid_cmp)void object_tree_RB_INSERT_COLOR(struct object_tree *head, struct
object *elm) { struct object *parent, *gparent, *tmp; while (
(parent = (elm)->link.rbe_parent) && (parent)->
link.rbe_color == 1) { gparent = (parent)->link.rbe_parent
; if (parent == (gparent)->link.rbe_left) { tmp = (gparent
)->link.rbe_right; if (tmp && (tmp)->link.rbe_color
== 1) { (tmp)->link.rbe_color = 0; do { (parent)->link
.rbe_color = 0; (gparent)->link.rbe_color = 1; } while (0)
; elm = gparent; continue; } if ((parent)->link.rbe_right ==
elm) { do { (tmp) = (parent)->link.rbe_right; if (((parent
)->link.rbe_right = (tmp)->link.rbe_left)) { ((tmp)->
link.rbe_left)->link.rbe_parent = (parent); } do {} while (
0); if (((tmp)->link.rbe_parent = (parent)->link.rbe_parent
)) { if ((parent) == ((parent)->link.rbe_parent)->link.
rbe_left) ((parent)->link.rbe_parent)->link.rbe_left = (
tmp); else ((parent)->link.rbe_parent)->link.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->link.rbe_left
= (parent); (parent)->link.rbe_parent = (tmp); do {} while
(0); if (((tmp)->link.rbe_parent)) do {} while (0); } while
(0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->
link.rbe_color = 0; (gparent)->link.rbe_color = 1; } while
(0); do { (tmp) = (gparent)->link.rbe_left; if (((gparent
)->link.rbe_left = (tmp)->link.rbe_right)) { ((tmp)->
link.rbe_right)->link.rbe_parent = (gparent); } do {} while
(0); if (((tmp)->link.rbe_parent = (gparent)->link.rbe_parent
)) { if ((gparent) == ((gparent)->link.rbe_parent)->link
.rbe_left) ((gparent)->link.rbe_parent)->link.rbe_left =
(tmp); else ((gparent)->link.rbe_parent)->link.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->link.
rbe_right = (gparent); (gparent)->link.rbe_parent = (tmp);
do {} while (0); if (((tmp)->link.rbe_parent)) do {} while
(0); } while (0); } else { tmp = (gparent)->link.rbe_left
; if (tmp && (tmp)->link.rbe_color == 1) { (tmp)->
link.rbe_color = 0; do { (parent)->link.rbe_color = 0; (gparent
)->link.rbe_color = 1; } while (0); elm = gparent; continue
; } if ((parent)->link.rbe_left == elm) { do { (tmp) = (parent
)->link.rbe_left; if (((parent)->link.rbe_left = (tmp)->
link.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = parent; parent = elm; elm =
tmp; } do { (parent)->link.rbe_color = 0; (gparent)->link
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->link.
rbe_right; if (((gparent)->link.rbe_right = (tmp)->link
.rbe_left)) { ((tmp)->link.rbe_left)->link.rbe_parent =
(gparent); } do {} while (0); if (((tmp)->link.rbe_parent
= (gparent)->link.rbe_parent)) { if ((gparent) == ((gparent
)->link.rbe_parent)->link.rbe_left) ((gparent)->link
.rbe_parent)->link.rbe_left = (tmp); else ((gparent)->link
.rbe_parent)->link.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->link.rbe_left = (gparent); (gparent)->
link.rbe_parent = (tmp); do {} while (0); if (((tmp)->link
.rbe_parent)) do {} while (0); } while (0); } } (head->rbh_root
)->link.rbe_color = 0; } void object_tree_RB_REMOVE_COLOR(
struct object_tree *head, struct object *parent, struct object
*elm) { struct object *tmp; while ((elm == ((void*)0) || (elm
)->link.rbe_color == 0) && elm != (head)->rbh_root
) { if ((parent)->link.rbe_left == elm) { tmp = (parent)->
link.rbe_right; if ((tmp)->link.rbe_color == 1) { do { (tmp
)->link.rbe_color = 0; (parent)->link.rbe_color = 1; } while
(0); do { (tmp) = (parent)->link.rbe_right; if (((parent)
->link.rbe_right = (tmp)->link.rbe_left)) { ((tmp)->
link.rbe_left)->link.rbe_parent = (parent); } do {} while (
0); if (((tmp)->link.rbe_parent = (parent)->link.rbe_parent
)) { if ((parent) == ((parent)->link.rbe_parent)->link.
rbe_left) ((parent)->link.rbe_parent)->link.rbe_left = (
tmp); else ((parent)->link.rbe_parent)->link.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->link.rbe_left
= (parent); (parent)->link.rbe_parent = (tmp); do {} while
(0); if (((tmp)->link.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->link.rbe_right; } if (((tmp)->link
.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->link
.rbe_color == 0) && ((tmp)->link.rbe_right == ((void
*)0) || ((tmp)->link.rbe_right)->link.rbe_color == 0)) {
(tmp)->link.rbe_color = 1; elm = parent; parent = (elm)->
link.rbe_parent; } else { if ((tmp)->link.rbe_right == ((void
*)0) || ((tmp)->link.rbe_right)->link.rbe_color == 0) {
struct object *oleft; if ((oleft = (tmp)->link.rbe_left))
(oleft)->link.rbe_color = 0; (tmp)->link.rbe_color = 1
; do { (oleft) = (tmp)->link.rbe_left; if (((tmp)->link
.rbe_left = (oleft)->link.rbe_right)) { ((oleft)->link.
rbe_right)->link.rbe_parent = (tmp); } do {} while (0); if
(((oleft)->link.rbe_parent = (tmp)->link.rbe_parent)) {
if ((tmp) == ((tmp)->link.rbe_parent)->link.rbe_left) (
(tmp)->link.rbe_parent)->link.rbe_left = (oleft); else (
(tmp)->link.rbe_parent)->link.rbe_right = (oleft); } else
(head)->rbh_root = (oleft); (oleft)->link.rbe_right = (
tmp); (tmp)->link.rbe_parent = (oleft); do {} while (0); if
(((oleft)->link.rbe_parent)) do {} while (0); } while (0)
; tmp = (parent)->link.rbe_right; } (tmp)->link.rbe_color
= (parent)->link.rbe_color; (parent)->link.rbe_color =
0; if ((tmp)->link.rbe_right) ((tmp)->link.rbe_right)->
link.rbe_color = 0; do { (tmp) = (parent)->link.rbe_right;
if (((parent)->link.rbe_right = (tmp)->link.rbe_left))
{ ((tmp)->link.rbe_left)->link.rbe_parent = (parent); }
do {} while (0); if (((tmp)->link.rbe_parent = (parent)->
link.rbe_parent)) { if ((parent) == ((parent)->link.rbe_parent
)->link.rbe_left) ((parent)->link.rbe_parent)->link.
rbe_left = (tmp); else ((parent)->link.rbe_parent)->link
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->link.rbe_left = (parent); (parent)->link.rbe_parent =
(tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do {
} while (0); } while (0); elm = (head)->rbh_root; break; }
} else { tmp = (parent)->link.rbe_left; if ((tmp)->link
.rbe_color == 1) { do { (tmp)->link.rbe_color = 0; (parent
)->link.rbe_color = 1; } while (0); do { (tmp) = (parent)->
link.rbe_left; if (((parent)->link.rbe_left = (tmp)->link
.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = (parent)->link.rbe_left;
} if (((tmp)->link.rbe_left == ((void*)0) || ((tmp)->link
.rbe_left)->link.rbe_color == 0) && ((tmp)->link
.rbe_right == ((void*)0) || ((tmp)->link.rbe_right)->link
.rbe_color == 0)) { (tmp)->link.rbe_color = 1; elm = parent
; parent = (elm)->link.rbe_parent; } else { if ((tmp)->
link.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->
link.rbe_color == 0) { struct object *oright; if ((oright = (
tmp)->link.rbe_right)) (oright)->link.rbe_color = 0; (tmp
)->link.rbe_color = 1; do { (oright) = (tmp)->link.rbe_right
; if (((tmp)->link.rbe_right = (oright)->link.rbe_left)
) { ((oright)->link.rbe_left)->link.rbe_parent = (tmp);
} do {} while (0); if (((oright)->link.rbe_parent = (tmp)
->link.rbe_parent)) { if ((tmp) == ((tmp)->link.rbe_parent
)->link.rbe_left) ((tmp)->link.rbe_parent)->link.rbe_left
= (oright); else ((tmp)->link.rbe_parent)->link.rbe_right
= (oright); } else (head)->rbh_root = (oright); (oright)->
link.rbe_left = (tmp); (tmp)->link.rbe_parent = (oright); do
{} while (0); if (((oright)->link.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->link.rbe_left; } (tmp)->
link.rbe_color = (parent)->link.rbe_color; (parent)->link
.rbe_color = 0; if ((tmp)->link.rbe_left) ((tmp)->link.
rbe_left)->link.rbe_color = 0; do { (tmp) = (parent)->link
.rbe_left; if (((parent)->link.rbe_left = (tmp)->link.rbe_right
)) { ((tmp)->link.rbe_right)->link.rbe_parent = (parent
); } do {} while (0); if (((tmp)->link.rbe_parent = (parent
)->link.rbe_parent)) { if ((parent) == ((parent)->link.
rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent)
->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); elm = (head)->rbh_root; break;
} } } if (elm) (elm)->link.rbe_color = 0; } struct object
* object_tree_RB_REMOVE(struct object_tree *head, struct object
*elm) { struct object *child, *parent, *old = elm; int color
; if ((elm)->link.rbe_left == ((void*)0)) child = (elm)->
link.rbe_right; else if ((elm)->link.rbe_right == ((void*)
0)) child = (elm)->link.rbe_left; else { struct object *left
; elm = (elm)->link.rbe_right; while ((left = (elm)->link
.rbe_left)) elm = left; child = (elm)->link.rbe_right; parent
= (elm)->link.rbe_parent; color = (elm)->link.rbe_color
; if (child) (child)->link.rbe_parent = parent; if (parent
) { if ((parent)->link.rbe_left == elm) (parent)->link.
rbe_left = child; else (parent)->link.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; if ((elm)->
link.rbe_parent == old) parent = elm; (elm)->link = (old)->
link; if ((old)->link.rbe_parent) { if (((old)->link.rbe_parent
)->link.rbe_left == old) ((old)->link.rbe_parent)->link
.rbe_left = elm; else ((old)->link.rbe_parent)->link.rbe_right
= elm; do {} while (0); } else (head)->rbh_root = elm; ((
old)->link.rbe_left)->link.rbe_parent = elm; if ((old)->
link.rbe_right) ((old)->link.rbe_right)->link.rbe_parent
= elm; if (parent) { left = parent; do { do {} while (0); } while
((left = (left)->link.rbe_parent)); } goto color; } parent
= (elm)->link.rbe_parent; color = (elm)->link.rbe_color
; if (child) (child)->link.rbe_parent = parent; if (parent
) { if ((parent)->link.rbe_left == elm) (parent)->link.
rbe_left = child; else (parent)->link.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; color: if (
color == 0) object_tree_RB_REMOVE_COLOR(head, parent, child);
return (old); } struct object * object_tree_RB_INSERT(struct
object_tree *head, struct object *elm) { struct object *tmp;
struct object *parent = ((void*)0); int comp = 0; tmp = (head
)->rbh_root; while (tmp) { parent = tmp; comp = (obj_oid_cmp
)(elm, parent); if (comp < 0) tmp = (tmp)->link.rbe_left
; else if (comp > 0) tmp = (tmp)->link.rbe_right; else return
(tmp); } do { (elm)->link.rbe_parent = parent; (elm)->
link.rbe_left = (elm)->link.rbe_right = ((void*)0); (elm)->
link.rbe_color = 1; } while (0); if (parent != ((void*)0)) { if
(comp < 0) (parent)->link.rbe_left = elm; else (parent
)->link.rbe_right = elm; do {} while (0); } else (head)->
rbh_root = elm; object_tree_RB_INSERT_COLOR(head, elm); return
(((void*)0)); } struct object * object_tree_RB_FIND(struct object_tree
*head, struct object *elm) { struct object *tmp = (head)->
rbh_root; int comp; while (tmp) { comp = obj_oid_cmp(elm, tmp
); if (comp < 0) tmp = (tmp)->link.rbe_left; else if (comp
> 0) tmp = (tmp)->link.rbe_right; else return (tmp); }
return (((void*)0)); } struct object * object_tree_RB_NFIND(
struct object_tree *head, struct object *elm) { struct object
*tmp = (head)->rbh_root; struct object *res = ((void*)0);
int comp; while (tmp) { comp = obj_oid_cmp(elm, tmp); if (comp
< 0) { res = tmp; tmp = (tmp)->link.rbe_left; } else if
(comp > 0) tmp = (tmp)->link.rbe_right; else return (tmp
); } return (res); } struct object * object_tree_RB_NEXT(struct
object *elm) { if ((elm)->link.rbe_right) { elm = (elm)->
link.rbe_right; while ((elm)->link.rbe_left) elm = (elm)->
link.rbe_left; } else { if ((elm)->link.rbe_parent &&
(elm == ((elm)->link.rbe_parent)->link.rbe_left)) elm =
(elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_right
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct object * object_tree_RB_PREV(struct
object *elm) { if ((elm)->link.rbe_left) { elm = (elm)->
link.rbe_left; while ((elm)->link.rbe_right) elm = (elm)->
link.rbe_right; } else { if ((elm)->link.rbe_parent &&
(elm == ((elm)->link.rbe_parent)->link.rbe_right)) elm
= (elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_left
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct object * object_tree_RB_MINMAX(struct
object_tree *head, int val) { struct object *tmp = (head)->
rbh_root; struct object *parent = ((void*)0); while (tmp) { parent
= tmp; if (val < 0) tmp = (tmp)->link.rbe_left; else tmp
= (tmp)->link.rbe_right; } return (parent); };
58RB_GENERATE(oidname_tree, oidname, link, oidname_cmp)void oidname_tree_RB_INSERT_COLOR(struct oidname_tree *head, struct
oidname *elm) { struct oidname *parent, *gparent, *tmp; while
((parent = (elm)->link.rbe_parent) && (parent)->
link.rbe_color == 1) { gparent = (parent)->link.rbe_parent
; if (parent == (gparent)->link.rbe_left) { tmp = (gparent
)->link.rbe_right; if (tmp && (tmp)->link.rbe_color
== 1) { (tmp)->link.rbe_color = 0; do { (parent)->link
.rbe_color = 0; (gparent)->link.rbe_color = 1; } while (0)
; elm = gparent; continue; } if ((parent)->link.rbe_right ==
elm) { do { (tmp) = (parent)->link.rbe_right; if (((parent
)->link.rbe_right = (tmp)->link.rbe_left)) { ((tmp)->
link.rbe_left)->link.rbe_parent = (parent); } do {} while (
0); if (((tmp)->link.rbe_parent = (parent)->link.rbe_parent
)) { if ((parent) == ((parent)->link.rbe_parent)->link.
rbe_left) ((parent)->link.rbe_parent)->link.rbe_left = (
tmp); else ((parent)->link.rbe_parent)->link.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->link.rbe_left
= (parent); (parent)->link.rbe_parent = (tmp); do {} while
(0); if (((tmp)->link.rbe_parent)) do {} while (0); } while
(0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->
link.rbe_color = 0; (gparent)->link.rbe_color = 1; } while
(0); do { (tmp) = (gparent)->link.rbe_left; if (((gparent
)->link.rbe_left = (tmp)->link.rbe_right)) { ((tmp)->
link.rbe_right)->link.rbe_parent = (gparent); } do {} while
(0); if (((tmp)->link.rbe_parent = (gparent)->link.rbe_parent
)) { if ((gparent) == ((gparent)->link.rbe_parent)->link
.rbe_left) ((gparent)->link.rbe_parent)->link.rbe_left =
(tmp); else ((gparent)->link.rbe_parent)->link.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->link.
rbe_right = (gparent); (gparent)->link.rbe_parent = (tmp);
do {} while (0); if (((tmp)->link.rbe_parent)) do {} while
(0); } while (0); } else { tmp = (gparent)->link.rbe_left
; if (tmp && (tmp)->link.rbe_color == 1) { (tmp)->
link.rbe_color = 0; do { (parent)->link.rbe_color = 0; (gparent
)->link.rbe_color = 1; } while (0); elm = gparent; continue
; } if ((parent)->link.rbe_left == elm) { do { (tmp) = (parent
)->link.rbe_left; if (((parent)->link.rbe_left = (tmp)->
link.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = parent; parent = elm; elm =
tmp; } do { (parent)->link.rbe_color = 0; (gparent)->link
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->link.
rbe_right; if (((gparent)->link.rbe_right = (tmp)->link
.rbe_left)) { ((tmp)->link.rbe_left)->link.rbe_parent =
(gparent); } do {} while (0); if (((tmp)->link.rbe_parent
= (gparent)->link.rbe_parent)) { if ((gparent) == ((gparent
)->link.rbe_parent)->link.rbe_left) ((gparent)->link
.rbe_parent)->link.rbe_left = (tmp); else ((gparent)->link
.rbe_parent)->link.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->link.rbe_left = (gparent); (gparent)->
link.rbe_parent = (tmp); do {} while (0); if (((tmp)->link
.rbe_parent)) do {} while (0); } while (0); } } (head->rbh_root
)->link.rbe_color = 0; } void oidname_tree_RB_REMOVE_COLOR
(struct oidname_tree *head, struct oidname *parent, struct oidname
*elm) { struct oidname *tmp; while ((elm == ((void*)0) || (elm
)->link.rbe_color == 0) && elm != (head)->rbh_root
) { if ((parent)->link.rbe_left == elm) { tmp = (parent)->
link.rbe_right; if ((tmp)->link.rbe_color == 1) { do { (tmp
)->link.rbe_color = 0; (parent)->link.rbe_color = 1; } while
(0); do { (tmp) = (parent)->link.rbe_right; if (((parent)
->link.rbe_right = (tmp)->link.rbe_left)) { ((tmp)->
link.rbe_left)->link.rbe_parent = (parent); } do {} while (
0); if (((tmp)->link.rbe_parent = (parent)->link.rbe_parent
)) { if ((parent) == ((parent)->link.rbe_parent)->link.
rbe_left) ((parent)->link.rbe_parent)->link.rbe_left = (
tmp); else ((parent)->link.rbe_parent)->link.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->link.rbe_left
= (parent); (parent)->link.rbe_parent = (tmp); do {} while
(0); if (((tmp)->link.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->link.rbe_right; } if (((tmp)->link
.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->link
.rbe_color == 0) && ((tmp)->link.rbe_right == ((void
*)0) || ((tmp)->link.rbe_right)->link.rbe_color == 0)) {
(tmp)->link.rbe_color = 1; elm = parent; parent = (elm)->
link.rbe_parent; } else { if ((tmp)->link.rbe_right == ((void
*)0) || ((tmp)->link.rbe_right)->link.rbe_color == 0) {
struct oidname *oleft; if ((oleft = (tmp)->link.rbe_left)
) (oleft)->link.rbe_color = 0; (tmp)->link.rbe_color = 1
; do { (oleft) = (tmp)->link.rbe_left; if (((tmp)->link
.rbe_left = (oleft)->link.rbe_right)) { ((oleft)->link.
rbe_right)->link.rbe_parent = (tmp); } do {} while (0); if
(((oleft)->link.rbe_parent = (tmp)->link.rbe_parent)) {
if ((tmp) == ((tmp)->link.rbe_parent)->link.rbe_left) (
(tmp)->link.rbe_parent)->link.rbe_left = (oleft); else (
(tmp)->link.rbe_parent)->link.rbe_right = (oleft); } else
(head)->rbh_root = (oleft); (oleft)->link.rbe_right = (
tmp); (tmp)->link.rbe_parent = (oleft); do {} while (0); if
(((oleft)->link.rbe_parent)) do {} while (0); } while (0)
; tmp = (parent)->link.rbe_right; } (tmp)->link.rbe_color
= (parent)->link.rbe_color; (parent)->link.rbe_color =
0; if ((tmp)->link.rbe_right) ((tmp)->link.rbe_right)->
link.rbe_color = 0; do { (tmp) = (parent)->link.rbe_right;
if (((parent)->link.rbe_right = (tmp)->link.rbe_left))
{ ((tmp)->link.rbe_left)->link.rbe_parent = (parent); }
do {} while (0); if (((tmp)->link.rbe_parent = (parent)->
link.rbe_parent)) { if ((parent) == ((parent)->link.rbe_parent
)->link.rbe_left) ((parent)->link.rbe_parent)->link.
rbe_left = (tmp); else ((parent)->link.rbe_parent)->link
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->link.rbe_left = (parent); (parent)->link.rbe_parent =
(tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do {
} while (0); } while (0); elm = (head)->rbh_root; break; }
} else { tmp = (parent)->link.rbe_left; if ((tmp)->link
.rbe_color == 1) { do { (tmp)->link.rbe_color = 0; (parent
)->link.rbe_color = 1; } while (0); do { (tmp) = (parent)->
link.rbe_left; if (((parent)->link.rbe_left = (tmp)->link
.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = (parent)->link.rbe_left;
} if (((tmp)->link.rbe_left == ((void*)0) || ((tmp)->link
.rbe_left)->link.rbe_color == 0) && ((tmp)->link
.rbe_right == ((void*)0) || ((tmp)->link.rbe_right)->link
.rbe_color == 0)) { (tmp)->link.rbe_color = 1; elm = parent
; parent = (elm)->link.rbe_parent; } else { if ((tmp)->
link.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->
link.rbe_color == 0) { struct oidname *oright; if ((oright = (
tmp)->link.rbe_right)) (oright)->link.rbe_color = 0; (tmp
)->link.rbe_color = 1; do { (oright) = (tmp)->link.rbe_right
; if (((tmp)->link.rbe_right = (oright)->link.rbe_left)
) { ((oright)->link.rbe_left)->link.rbe_parent = (tmp);
} do {} while (0); if (((oright)->link.rbe_parent = (tmp)
->link.rbe_parent)) { if ((tmp) == ((tmp)->link.rbe_parent
)->link.rbe_left) ((tmp)->link.rbe_parent)->link.rbe_left
= (oright); else ((tmp)->link.rbe_parent)->link.rbe_right
= (oright); } else (head)->rbh_root = (oright); (oright)->
link.rbe_left = (tmp); (tmp)->link.rbe_parent = (oright); do
{} while (0); if (((oright)->link.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->link.rbe_left; } (tmp)->
link.rbe_color = (parent)->link.rbe_color; (parent)->link
.rbe_color = 0; if ((tmp)->link.rbe_left) ((tmp)->link.
rbe_left)->link.rbe_color = 0; do { (tmp) = (parent)->link
.rbe_left; if (((parent)->link.rbe_left = (tmp)->link.rbe_right
)) { ((tmp)->link.rbe_right)->link.rbe_parent = (parent
); } do {} while (0); if (((tmp)->link.rbe_parent = (parent
)->link.rbe_parent)) { if ((parent) == ((parent)->link.
rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent)
->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); elm = (head)->rbh_root; break;
} } } if (elm) (elm)->link.rbe_color = 0; } struct oidname
* oidname_tree_RB_REMOVE(struct oidname_tree *head, struct oidname
*elm) { struct oidname *child, *parent, *old = elm; int color
; if ((elm)->link.rbe_left == ((void*)0)) child = (elm)->
link.rbe_right; else if ((elm)->link.rbe_right == ((void*)
0)) child = (elm)->link.rbe_left; else { struct oidname *left
; elm = (elm)->link.rbe_right; while ((left = (elm)->link
.rbe_left)) elm = left; child = (elm)->link.rbe_right; parent
= (elm)->link.rbe_parent; color = (elm)->link.rbe_color
; if (child) (child)->link.rbe_parent = parent; if (parent
) { if ((parent)->link.rbe_left == elm) (parent)->link.
rbe_left = child; else (parent)->link.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; if ((elm)->
link.rbe_parent == old) parent = elm; (elm)->link = (old)->
link; if ((old)->link.rbe_parent) { if (((old)->link.rbe_parent
)->link.rbe_left == old) ((old)->link.rbe_parent)->link
.rbe_left = elm; else ((old)->link.rbe_parent)->link.rbe_right
= elm; do {} while (0); } else (head)->rbh_root = elm; ((
old)->link.rbe_left)->link.rbe_parent = elm; if ((old)->
link.rbe_right) ((old)->link.rbe_right)->link.rbe_parent
= elm; if (parent) { left = parent; do { do {} while (0); } while
((left = (left)->link.rbe_parent)); } goto color; } parent
= (elm)->link.rbe_parent; color = (elm)->link.rbe_color
; if (child) (child)->link.rbe_parent = parent; if (parent
) { if ((parent)->link.rbe_left == elm) (parent)->link.
rbe_left = child; else (parent)->link.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; color: if (
color == 0) oidname_tree_RB_REMOVE_COLOR(head, parent, child)
; return (old); } struct oidname * oidname_tree_RB_INSERT(struct
oidname_tree *head, struct oidname *elm) { struct oidname *tmp
; struct oidname *parent = ((void*)0); int comp = 0; tmp = (head
)->rbh_root; while (tmp) { parent = tmp; comp = (oidname_cmp
)(elm, parent); if (comp < 0) tmp = (tmp)->link.rbe_left
; else if (comp > 0) tmp = (tmp)->link.rbe_right; else return
(tmp); } do { (elm)->link.rbe_parent = parent; (elm)->
link.rbe_left = (elm)->link.rbe_right = ((void*)0); (elm)->
link.rbe_color = 1; } while (0); if (parent != ((void*)0)) { if
(comp < 0) (parent)->link.rbe_left = elm; else (parent
)->link.rbe_right = elm; do {} while (0); } else (head)->
rbh_root = elm; oidname_tree_RB_INSERT_COLOR(head, elm); return
(((void*)0)); } struct oidname * oidname_tree_RB_FIND(struct
oidname_tree *head, struct oidname *elm) { struct oidname *tmp
= (head)->rbh_root; int comp; while (tmp) { comp = oidname_cmp
(elm, tmp); if (comp < 0) tmp = (tmp)->link.rbe_left; else
if (comp > 0) tmp = (tmp)->link.rbe_right; else return
(tmp); } return (((void*)0)); } struct oidname * oidname_tree_RB_NFIND
(struct oidname_tree *head, struct oidname *elm) { struct oidname
*tmp = (head)->rbh_root; struct oidname *res = ((void*)0)
; int comp; while (tmp) { comp = oidname_cmp(elm, tmp); if (comp
< 0) { res = tmp; tmp = (tmp)->link.rbe_left; } else if
(comp > 0) tmp = (tmp)->link.rbe_right; else return (tmp
); } return (res); } struct oidname * oidname_tree_RB_NEXT(struct
oidname *elm) { if ((elm)->link.rbe_right) { elm = (elm)->
link.rbe_right; while ((elm)->link.rbe_left) elm = (elm)->
link.rbe_left; } else { if ((elm)->link.rbe_parent &&
(elm == ((elm)->link.rbe_parent)->link.rbe_left)) elm =
(elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_right
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct oidname * oidname_tree_RB_PREV(struct
oidname *elm) { if ((elm)->link.rbe_left) { elm = (elm)->
link.rbe_left; while ((elm)->link.rbe_right) elm = (elm)->
link.rbe_right; } else { if ((elm)->link.rbe_parent &&
(elm == ((elm)->link.rbe_parent)->link.rbe_right)) elm
= (elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_left
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct oidname * oidname_tree_RB_MINMAX
(struct oidname_tree *head, int val) { struct oidname *tmp = (
head)->rbh_root; struct oidname *parent = ((void*)0); while
(tmp) { parent = tmp; if (val < 0) tmp = (tmp)->link.rbe_left
; else tmp = (tmp)->link.rbe_right; } return (parent); };
59RB_GENERATE(symoid_tree, symoid, link, symoid_cmp)void symoid_tree_RB_INSERT_COLOR(struct symoid_tree *head, struct
symoid *elm) { struct symoid *parent, *gparent, *tmp; while (
(parent = (elm)->link.rbe_parent) && (parent)->
link.rbe_color == 1) { gparent = (parent)->link.rbe_parent
; if (parent == (gparent)->link.rbe_left) { tmp = (gparent
)->link.rbe_right; if (tmp && (tmp)->link.rbe_color
== 1) { (tmp)->link.rbe_color = 0; do { (parent)->link
.rbe_color = 0; (gparent)->link.rbe_color = 1; } while (0)
; elm = gparent; continue; } if ((parent)->link.rbe_right ==
elm) { do { (tmp) = (parent)->link.rbe_right; if (((parent
)->link.rbe_right = (tmp)->link.rbe_left)) { ((tmp)->
link.rbe_left)->link.rbe_parent = (parent); } do {} while (
0); if (((tmp)->link.rbe_parent = (parent)->link.rbe_parent
)) { if ((parent) == ((parent)->link.rbe_parent)->link.
rbe_left) ((parent)->link.rbe_parent)->link.rbe_left = (
tmp); else ((parent)->link.rbe_parent)->link.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->link.rbe_left
= (parent); (parent)->link.rbe_parent = (tmp); do {} while
(0); if (((tmp)->link.rbe_parent)) do {} while (0); } while
(0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->
link.rbe_color = 0; (gparent)->link.rbe_color = 1; } while
(0); do { (tmp) = (gparent)->link.rbe_left; if (((gparent
)->link.rbe_left = (tmp)->link.rbe_right)) { ((tmp)->
link.rbe_right)->link.rbe_parent = (gparent); } do {} while
(0); if (((tmp)->link.rbe_parent = (gparent)->link.rbe_parent
)) { if ((gparent) == ((gparent)->link.rbe_parent)->link
.rbe_left) ((gparent)->link.rbe_parent)->link.rbe_left =
(tmp); else ((gparent)->link.rbe_parent)->link.rbe_right
= (tmp); } else (head)->rbh_root = (tmp); (tmp)->link.
rbe_right = (gparent); (gparent)->link.rbe_parent = (tmp);
do {} while (0); if (((tmp)->link.rbe_parent)) do {} while
(0); } while (0); } else { tmp = (gparent)->link.rbe_left
; if (tmp && (tmp)->link.rbe_color == 1) { (tmp)->
link.rbe_color = 0; do { (parent)->link.rbe_color = 0; (gparent
)->link.rbe_color = 1; } while (0); elm = gparent; continue
; } if ((parent)->link.rbe_left == elm) { do { (tmp) = (parent
)->link.rbe_left; if (((parent)->link.rbe_left = (tmp)->
link.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = parent; parent = elm; elm =
tmp; } do { (parent)->link.rbe_color = 0; (gparent)->link
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->link.
rbe_right; if (((gparent)->link.rbe_right = (tmp)->link
.rbe_left)) { ((tmp)->link.rbe_left)->link.rbe_parent =
(gparent); } do {} while (0); if (((tmp)->link.rbe_parent
= (gparent)->link.rbe_parent)) { if ((gparent) == ((gparent
)->link.rbe_parent)->link.rbe_left) ((gparent)->link
.rbe_parent)->link.rbe_left = (tmp); else ((gparent)->link
.rbe_parent)->link.rbe_right = (tmp); } else (head)->rbh_root
= (tmp); (tmp)->link.rbe_left = (gparent); (gparent)->
link.rbe_parent = (tmp); do {} while (0); if (((tmp)->link
.rbe_parent)) do {} while (0); } while (0); } } (head->rbh_root
)->link.rbe_color = 0; } void symoid_tree_RB_REMOVE_COLOR(
struct symoid_tree *head, struct symoid *parent, struct symoid
*elm) { struct symoid *tmp; while ((elm == ((void*)0) || (elm
)->link.rbe_color == 0) && elm != (head)->rbh_root
) { if ((parent)->link.rbe_left == elm) { tmp = (parent)->
link.rbe_right; if ((tmp)->link.rbe_color == 1) { do { (tmp
)->link.rbe_color = 0; (parent)->link.rbe_color = 1; } while
(0); do { (tmp) = (parent)->link.rbe_right; if (((parent)
->link.rbe_right = (tmp)->link.rbe_left)) { ((tmp)->
link.rbe_left)->link.rbe_parent = (parent); } do {} while (
0); if (((tmp)->link.rbe_parent = (parent)->link.rbe_parent
)) { if ((parent) == ((parent)->link.rbe_parent)->link.
rbe_left) ((parent)->link.rbe_parent)->link.rbe_left = (
tmp); else ((parent)->link.rbe_parent)->link.rbe_right =
(tmp); } else (head)->rbh_root = (tmp); (tmp)->link.rbe_left
= (parent); (parent)->link.rbe_parent = (tmp); do {} while
(0); if (((tmp)->link.rbe_parent)) do {} while (0); } while
(0); tmp = (parent)->link.rbe_right; } if (((tmp)->link
.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->link
.rbe_color == 0) && ((tmp)->link.rbe_right == ((void
*)0) || ((tmp)->link.rbe_right)->link.rbe_color == 0)) {
(tmp)->link.rbe_color = 1; elm = parent; parent = (elm)->
link.rbe_parent; } else { if ((tmp)->link.rbe_right == ((void
*)0) || ((tmp)->link.rbe_right)->link.rbe_color == 0) {
struct symoid *oleft; if ((oleft = (tmp)->link.rbe_left))
(oleft)->link.rbe_color = 0; (tmp)->link.rbe_color = 1
; do { (oleft) = (tmp)->link.rbe_left; if (((tmp)->link
.rbe_left = (oleft)->link.rbe_right)) { ((oleft)->link.
rbe_right)->link.rbe_parent = (tmp); } do {} while (0); if
(((oleft)->link.rbe_parent = (tmp)->link.rbe_parent)) {
if ((tmp) == ((tmp)->link.rbe_parent)->link.rbe_left) (
(tmp)->link.rbe_parent)->link.rbe_left = (oleft); else (
(tmp)->link.rbe_parent)->link.rbe_right = (oleft); } else
(head)->rbh_root = (oleft); (oleft)->link.rbe_right = (
tmp); (tmp)->link.rbe_parent = (oleft); do {} while (0); if
(((oleft)->link.rbe_parent)) do {} while (0); } while (0)
; tmp = (parent)->link.rbe_right; } (tmp)->link.rbe_color
= (parent)->link.rbe_color; (parent)->link.rbe_color =
0; if ((tmp)->link.rbe_right) ((tmp)->link.rbe_right)->
link.rbe_color = 0; do { (tmp) = (parent)->link.rbe_right;
if (((parent)->link.rbe_right = (tmp)->link.rbe_left))
{ ((tmp)->link.rbe_left)->link.rbe_parent = (parent); }
do {} while (0); if (((tmp)->link.rbe_parent = (parent)->
link.rbe_parent)) { if ((parent) == ((parent)->link.rbe_parent
)->link.rbe_left) ((parent)->link.rbe_parent)->link.
rbe_left = (tmp); else ((parent)->link.rbe_parent)->link
.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)
->link.rbe_left = (parent); (parent)->link.rbe_parent =
(tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do {
} while (0); } while (0); elm = (head)->rbh_root; break; }
} else { tmp = (parent)->link.rbe_left; if ((tmp)->link
.rbe_color == 1) { do { (tmp)->link.rbe_color = 0; (parent
)->link.rbe_color = 1; } while (0); do { (tmp) = (parent)->
link.rbe_left; if (((parent)->link.rbe_left = (tmp)->link
.rbe_right)) { ((tmp)->link.rbe_right)->link.rbe_parent
= (parent); } do {} while (0); if (((tmp)->link.rbe_parent
= (parent)->link.rbe_parent)) { if ((parent) == ((parent)
->link.rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent
)->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); tmp = (parent)->link.rbe_left;
} if (((tmp)->link.rbe_left == ((void*)0) || ((tmp)->link
.rbe_left)->link.rbe_color == 0) && ((tmp)->link
.rbe_right == ((void*)0) || ((tmp)->link.rbe_right)->link
.rbe_color == 0)) { (tmp)->link.rbe_color = 1; elm = parent
; parent = (elm)->link.rbe_parent; } else { if ((tmp)->
link.rbe_left == ((void*)0) || ((tmp)->link.rbe_left)->
link.rbe_color == 0) { struct symoid *oright; if ((oright = (
tmp)->link.rbe_right)) (oright)->link.rbe_color = 0; (tmp
)->link.rbe_color = 1; do { (oright) = (tmp)->link.rbe_right
; if (((tmp)->link.rbe_right = (oright)->link.rbe_left)
) { ((oright)->link.rbe_left)->link.rbe_parent = (tmp);
} do {} while (0); if (((oright)->link.rbe_parent = (tmp)
->link.rbe_parent)) { if ((tmp) == ((tmp)->link.rbe_parent
)->link.rbe_left) ((tmp)->link.rbe_parent)->link.rbe_left
= (oright); else ((tmp)->link.rbe_parent)->link.rbe_right
= (oright); } else (head)->rbh_root = (oright); (oright)->
link.rbe_left = (tmp); (tmp)->link.rbe_parent = (oright); do
{} while (0); if (((oright)->link.rbe_parent)) do {} while
(0); } while (0); tmp = (parent)->link.rbe_left; } (tmp)->
link.rbe_color = (parent)->link.rbe_color; (parent)->link
.rbe_color = 0; if ((tmp)->link.rbe_left) ((tmp)->link.
rbe_left)->link.rbe_color = 0; do { (tmp) = (parent)->link
.rbe_left; if (((parent)->link.rbe_left = (tmp)->link.rbe_right
)) { ((tmp)->link.rbe_right)->link.rbe_parent = (parent
); } do {} while (0); if (((tmp)->link.rbe_parent = (parent
)->link.rbe_parent)) { if ((parent) == ((parent)->link.
rbe_parent)->link.rbe_left) ((parent)->link.rbe_parent)
->link.rbe_left = (tmp); else ((parent)->link.rbe_parent
)->link.rbe_right = (tmp); } else (head)->rbh_root = (tmp
); (tmp)->link.rbe_right = (parent); (parent)->link.rbe_parent
= (tmp); do {} while (0); if (((tmp)->link.rbe_parent)) do
{} while (0); } while (0); elm = (head)->rbh_root; break;
} } } if (elm) (elm)->link.rbe_color = 0; } struct symoid
* symoid_tree_RB_REMOVE(struct symoid_tree *head, struct symoid
*elm) { struct symoid *child, *parent, *old = elm; int color
; if ((elm)->link.rbe_left == ((void*)0)) child = (elm)->
link.rbe_right; else if ((elm)->link.rbe_right == ((void*)
0)) child = (elm)->link.rbe_left; else { struct symoid *left
; elm = (elm)->link.rbe_right; while ((left = (elm)->link
.rbe_left)) elm = left; child = (elm)->link.rbe_right; parent
= (elm)->link.rbe_parent; color = (elm)->link.rbe_color
; if (child) (child)->link.rbe_parent = parent; if (parent
) { if ((parent)->link.rbe_left == elm) (parent)->link.
rbe_left = child; else (parent)->link.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; if ((elm)->
link.rbe_parent == old) parent = elm; (elm)->link = (old)->
link; if ((old)->link.rbe_parent) { if (((old)->link.rbe_parent
)->link.rbe_left == old) ((old)->link.rbe_parent)->link
.rbe_left = elm; else ((old)->link.rbe_parent)->link.rbe_right
= elm; do {} while (0); } else (head)->rbh_root = elm; ((
old)->link.rbe_left)->link.rbe_parent = elm; if ((old)->
link.rbe_right) ((old)->link.rbe_right)->link.rbe_parent
= elm; if (parent) { left = parent; do { do {} while (0); } while
((left = (left)->link.rbe_parent)); } goto color; } parent
= (elm)->link.rbe_parent; color = (elm)->link.rbe_color
; if (child) (child)->link.rbe_parent = parent; if (parent
) { if ((parent)->link.rbe_left == elm) (parent)->link.
rbe_left = child; else (parent)->link.rbe_right = child; do
{} while (0); } else (head)->rbh_root = child; color: if (
color == 0) symoid_tree_RB_REMOVE_COLOR(head, parent, child);
return (old); } struct symoid * symoid_tree_RB_INSERT(struct
symoid_tree *head, struct symoid *elm) { struct symoid *tmp;
struct symoid *parent = ((void*)0); int comp = 0; tmp = (head
)->rbh_root; while (tmp) { parent = tmp; comp = (symoid_cmp
)(elm, parent); if (comp < 0) tmp = (tmp)->link.rbe_left
; else if (comp > 0) tmp = (tmp)->link.rbe_right; else return
(tmp); } do { (elm)->link.rbe_parent = parent; (elm)->
link.rbe_left = (elm)->link.rbe_right = ((void*)0); (elm)->
link.rbe_color = 1; } while (0); if (parent != ((void*)0)) { if
(comp < 0) (parent)->link.rbe_left = elm; else (parent
)->link.rbe_right = elm; do {} while (0); } else (head)->
rbh_root = elm; symoid_tree_RB_INSERT_COLOR(head, elm); return
(((void*)0)); } struct symoid * symoid_tree_RB_FIND(struct symoid_tree
*head, struct symoid *elm) { struct symoid *tmp = (head)->
rbh_root; int comp; while (tmp) { comp = symoid_cmp(elm, tmp)
; if (comp < 0) tmp = (tmp)->link.rbe_left; else if (comp
> 0) tmp = (tmp)->link.rbe_right; else return (tmp); }
return (((void*)0)); } struct symoid * symoid_tree_RB_NFIND(
struct symoid_tree *head, struct symoid *elm) { struct symoid
*tmp = (head)->rbh_root; struct symoid *res = ((void*)0);
int comp; while (tmp) { comp = symoid_cmp(elm, tmp); if (comp
< 0) { res = tmp; tmp = (tmp)->link.rbe_left; } else if
(comp > 0) tmp = (tmp)->link.rbe_right; else return (tmp
); } return (res); } struct symoid * symoid_tree_RB_NEXT(struct
symoid *elm) { if ((elm)->link.rbe_right) { elm = (elm)->
link.rbe_right; while ((elm)->link.rbe_left) elm = (elm)->
link.rbe_left; } else { if ((elm)->link.rbe_parent &&
(elm == ((elm)->link.rbe_parent)->link.rbe_left)) elm =
(elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_right
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct symoid * symoid_tree_RB_PREV(struct
symoid *elm) { if ((elm)->link.rbe_left) { elm = (elm)->
link.rbe_left; while ((elm)->link.rbe_right) elm = (elm)->
link.rbe_right; } else { if ((elm)->link.rbe_parent &&
(elm == ((elm)->link.rbe_parent)->link.rbe_right)) elm
= (elm)->link.rbe_parent; else { while ((elm)->link.rbe_parent
&& (elm == ((elm)->link.rbe_parent)->link.rbe_left
)) elm = (elm)->link.rbe_parent; elm = (elm)->link.rbe_parent
; } } return (elm); } struct symoid * symoid_tree_RB_MINMAX(struct
symoid_tree *head, int val) { struct symoid *tmp = (head)->
rbh_root; struct symoid *parent = ((void*)0); while (tmp) { parent
= tmp; if (val < 0) tmp = (tmp)->link.rbe_left; else tmp
= (tmp)->link.rbe_right; } return (parent); };
60
61static struct attr_list *push_attr(struct attr_list *alist, struct attr_type *a);
62static struct obj_list *push_obj(struct obj_list *olist, struct object *obj);
63static struct name_list *push_name(struct name_list *nl, char *name);
64int is_oidstr(const char *oidstr);
65
66struct attr_type *
67lookup_attribute_by_name(struct schema *schema, char *name)
68{
69 struct oidname *on, find;
70
71 find.on_name = name;
72 on = RB_FIND(oidname_tree, &schema->attr_names, &find)oidname_tree_RB_FIND(&schema->attr_names, &find);
73
74 if (on)
75 return on->on_attr_typeon_ptr.ou_attr_type;
76 return NULL((void*)0);
77}
78
79struct attr_type *
80lookup_attribute_by_oid(struct schema *schema, char *oid)
81{
82 struct attr_type find;
83
84 find.oid = oid;
85 return RB_FIND(attr_type_tree, &schema->attr_types, &find)attr_type_tree_RB_FIND(&schema->attr_types, &find);
86}
87
88struct attr_type *
89lookup_attribute(struct schema *schema, char *oid_or_name)
90{
91 if (is_oidstr(oid_or_name))
92 return lookup_attribute_by_oid(schema, oid_or_name);
93 return lookup_attribute_by_name(schema, oid_or_name);
94}
95
96struct object *
97lookup_object_by_oid(struct schema *schema, char *oid)
98{
99 struct object find;
100
101 find.oid = oid;
102 return RB_FIND(object_tree, &schema->objects, &find)object_tree_RB_FIND(&schema->objects, &find);
103}
104
105struct object *
106lookup_object_by_name(struct schema *schema, char *name)
107{
108 struct oidname *on, find;
109
110 find.on_name = name;
111 on = RB_FIND(oidname_tree, &schema->object_names, &find)oidname_tree_RB_FIND(&schema->object_names, &find);
112
113 if (on)
114 return on->on_objecton_ptr.ou_object;
115 return NULL((void*)0);
116}
117
118struct object *
119lookup_object(struct schema *schema, char *oid_or_name)
120{
121 if (is_oidstr(oid_or_name))
122 return lookup_object_by_oid(schema, oid_or_name);
123 return lookup_object_by_name(schema, oid_or_name);
124}
125
126/*
127 * Looks up a symbolic OID, optionally with a suffix OID, so if
128 * SYMBOL = 1.2.3.4
129 * then
130 * SYMBOL:5.6 = 1.2.3.4.5.6
131 *
132 * Returned string must be freed by the caller.
133 * Modifies the name argument.
134 */
135char *
136lookup_symbolic_oid(struct schema *schema, char *name)
137{
138 struct symoid *symoid, find;
139 char *colon, *oid;
140 size_t sz;
141
142 colon = strchr(name, ':');
143 if (colon != NULL((void*)0)) {
144 if (!is_oidstr(colon + 1)) {
145 log_warnx("invalid OID after colon: %s", colon + 1);
146 return NULL((void*)0);
147 }
148 *colon = '\0';
149 }
150
151 find.name = name;
152 symoid = RB_FIND(symoid_tree, &schema->symbolic_oids, &find)symoid_tree_RB_FIND(&schema->symbolic_oids, &find);
153 if (symoid == NULL((void*)0))
154 return NULL((void*)0);
155
156 if (colon == NULL((void*)0))
157 return strdup(symoid->oid);
158
159 /* Expand SYMBOL:OID. */
160 sz = strlen(symoid->oid) + 1 + strlen(colon + 1) + 1;
161 if ((oid = malloc(sz)) == NULL((void*)0)) {
162 log_warnx("malloc");
163 return NULL((void*)0);
164 }
165
166 strlcpy(oid, symoid->oid, sz);
167 strlcat(oid, ".", sz);
168 strlcat(oid, colon + 1, sz);
169
170 return oid;
171}
172
173/*
174 * Push a symbol-OID pair on the tree. Name and OID must be valid pointers
175 * during the lifetime of the tree.
176 */
177static struct symoid *
178push_symbolic_oid(struct schema *schema, char *name, char *oid)
179{
180 struct symoid *symoid, find;
181
182 find.name = name;
183 symoid = RB_FIND(symoid_tree, &schema->symbolic_oids, &find)symoid_tree_RB_FIND(&schema->symbolic_oids, &find);
184
185 if (symoid == NULL((void*)0)) {
186 symoid = calloc(1, sizeof(*symoid));
187 if (symoid == NULL((void*)0)) {
188 log_warnx("calloc");
189 return NULL((void*)0);
190 }
191
192 symoid->name = name;
193 RB_INSERT(symoid_tree, &schema->symbolic_oids, symoid)symoid_tree_RB_INSERT(&schema->symbolic_oids, symoid);
194 }
195
196 free(symoid->oid);
197 symoid->oid = oid;
198
199 return symoid;
200}
201
202static struct attr_list *
203push_attr(struct attr_list *alist, struct attr_type *a)
204{
205 struct attr_ptr *aptr;
206
207 if (alist == NULL((void*)0)) {
208 if ((alist = calloc(1, sizeof(*alist))) == NULL((void*)0)) {
209 log_warn("calloc");
210 return NULL((void*)0);
211 }
212 SLIST_INIT(alist){ ((alist)->slh_first) = ((void*)0); };
213 }
214
215 if ((aptr = calloc(1, sizeof(*aptr))) == NULL((void*)0)) {
216 log_warn("calloc");
217 free(alist);
218 return NULL((void*)0);
219 }
220 aptr->attr_type = a;
221 SLIST_INSERT_HEAD(alist, aptr, next)do { (aptr)->next.sle_next = (alist)->slh_first; (alist
)->slh_first = (aptr); } while (0);
222
223 return alist;
224}
225
226static struct obj_list *
227push_obj(struct obj_list *olist, struct object *obj)
228{
229 struct obj_ptr *optr;
230
231 if (olist == NULL((void*)0)) {
232 if ((olist = calloc(1, sizeof(*olist))) == NULL((void*)0)) {
233 log_warn("calloc");
234 return NULL((void*)0);
235 }
236 SLIST_INIT(olist){ ((olist)->slh_first) = ((void*)0); };
237 }
238
239 if ((optr = calloc(1, sizeof(*optr))) == NULL((void*)0)) {
240 log_warn("calloc");
241 free(olist);
242 return NULL((void*)0);
243 }
244 optr->object = obj;
245 SLIST_INSERT_HEAD(olist, optr, next)do { (optr)->next.sle_next = (olist)->slh_first; (olist
)->slh_first = (optr); } while (0);
246
247 return olist;
248}
249
250int
251is_oidstr(const char *oidstr)
252{
253 struct ber_oid oid;
254 return (ober_string2oid(oidstr, &oid) == 0);
33
←
Assuming the condition is true
→
34
←
Returning the value 1, which participates in a condition later
→
255}
256
257static struct name_list *
258push_name(struct name_list *nl, char *name)
259{
260 struct name *n;
261
262 if (nl == NULL((void*)0)) {
263 if ((nl = calloc(1, sizeof(*nl))) == NULL((void*)0)) {
264 log_warn("calloc");
265 return NULL((void*)0);
266 }
267 SLIST_INIT(nl){ ((nl)->slh_first) = ((void*)0); };
268 }
269 if ((n = calloc(1, sizeof(*n))) == NULL((void*)0)) {
270 log_warn("calloc");
271 free(nl);
272 return NULL((void*)0);
273 }
274 n->name = name;
275 SLIST_INSERT_HEAD(nl, n, next)do { (n)->next.sle_next = (nl)->slh_first; (nl)->slh_first
= (n); } while (0);
276
277 return nl;
278}
279
280static int
281schema_getc(struct schema *schema, int quotec)
282{
283 int c, next;
284
285 if (schema->pushback_index)
286 return (schema->pushback_buffer[--schema->pushback_index]);
287
288 if (quotec) {
289 if ((c = getc(schema->fp)(!__isthreaded ? (--(schema->fp)->_r < 0 ? __srget(schema
->fp) : (int)(*(schema->fp)->_p++)) : (getc)(schema->
fp))) == EOF(-1)) {
290 log_warnx("reached end of file while parsing "
291 "quoted string");
292 return EOF(-1);
293 }
294 return (c);
295 }
296
297 while ((c = getc(schema->fp)(!__isthreaded ? (--(schema->fp)->_r < 0 ? __srget(schema
->fp) : (int)(*(schema->fp)->_p++)) : (getc)(schema->
fp))) == '\\') {
298 next = getc(schema->fp)(!__isthreaded ? (--(schema->fp)->_r < 0 ? __srget(schema
->fp) : (int)(*(schema->fp)->_p++)) : (getc)(schema->
fp));
299 if (next != '\n') {
300 c = next;
301 break;
302 }
303 schema->lineno++;
304 }
305
306 return (c);
307}
308
309static int
310schema_ungetc(struct schema *schema, int c)
311{
312 if (c == EOF(-1))
313 return EOF(-1);
314
315 if (schema->pushback_index < SCHEMA_MAXPUSHBACK128-1)
316 return (schema->pushback_buffer[schema->pushback_index++] = c);
317 else
318 return (EOF(-1));
319}
320
321static int
322findeol(struct schema *schema)
323{
324 int c;
325
326 /* skip to either EOF or the first real EOL */
327 while (1) {
328 if (schema->pushback_index)
329 c = schema->pushback_buffer[--schema->pushback_index];
330 else
331 c = schema_getc(schema, 0);
332 if (c == '\n') {
333 schema->lineno++;
334 break;
335 }
336 if (c == EOF(-1))
337 break;
338 }
339 return (ERROR-1);
340}
341
342static int
343schema_lex(struct schema *schema, char **kw)
344{
345 char buf[8096];
346 char *p;
347 int quotec, next, c;
348
349 if (kw
11.1
'kw' is non-null, which participates in a condition later
39.1
'kw' is non-null
)
12
←
Taking true branch
→
40
←
Taking true branch
→
350 *kw = NULL((void*)0);
41
←
Null pointer value stored to 'kw'
→
351
352top:
353 p = buf;
354 while ((c = schema_getc(schema, 0)) == ' ' || c == '\t')
13
←
Assuming the condition is false
→
14
←
Assuming the condition is false
→
15
←
Loop condition is false. Execution continues on line 357
→
42
←
Assuming the condition is false
→
43
←
Assuming the condition is false
→
44
←
Loop condition is false. Execution continues on line 357
→
355 ; /* nothing */
356
357 if (c == '#')
16
←
Assuming the condition is false
→
17
←
Taking false branch
→
45
←
Assuming the condition is false
→
46
←
Taking false branch
→
358 while ((c = schema_getc(schema, 0)) != '\n' && c != EOF(-1))
359 ; /* nothing */
360
361 switch (c) {
18
←
'Default' branch taken. Execution continues on line 401
→
47
←
'Default' branch taken. Execution continues on line 401
→
362 case '\'':
363 case '"':
364 quotec = c;
365 while (1) {
366 if ((c = schema_getc(schema, quotec)) == EOF(-1))
367 return (0);
368 if (c == '\n') {
369 schema->lineno++;
370 continue;
371 } else if (c == '\\') {
372 if ((next = schema_getc(schema, quotec)) == EOF(-1))
373 return (0);
374 if (next == quotec || c == ' ' || c == '\t')
375 c = next;
376 else if (next == '\n')
377 continue;
378 else
379 schema_ungetc(schema, next);
380 } else if (c == quotec) {
381 *p = '\0';
382 break;
383 }
384 if (p + 1 >= buf + sizeof(buf) - 1) {
385 log_warnx("string too long");
386 return (findeol(schema));
387 }
388 *p++ = (char)c;
389 }
390 if (kw != NULL((void*)0) && (*kw = strdup(buf)) == NULL((void*)0))
391 fatal("schema_lex: strdup");
392 return (STRING1);
393 }
394
395#define allowed_in_string(x)(isalnum(x) || (ispunct(x) && x != '(' && x !=
')' && x != '{' && x != '}' && x != '<'
&& x != '>' && x != '!' && x != '='
&& x != '/' && x != '#' && x != ',')
) \
396 (isalnum(x) || (ispunct(x) && x != '(' && x != ')' && \
397 x != '{' && x != '}' && x != '<' && x != '>' && \
398 x != '!' && x != '=' && x != '/' && x != '#' && \
399 x != ','))
400
401 if (isalnum(c) || c == ':' || c == '_' || c == '*') {
19
←
Assuming the condition is false
→
20
←
Assuming the condition is false
→
21
←
Assuming the condition is false
→
22
←
Taking false branch
→
48
←
Assuming the condition is false
→
49
←
Assuming the condition is false
→
50
←
Assuming the condition is false
→
51
←
Taking false branch
→
402 do {
403 *p++ = c;
404 if ((size_t)(p-buf) >= sizeof(buf)) {
405 log_warnx("string too long");
406 return (findeol(schema));
407 }
408 } while ((c = schema_getc(schema, 0)) != EOF(-1) && (allowed_in_string(c)(isalnum(c) || (ispunct(c) && c != '(' && c !=
')' && c != '{' && c != '}' && c != '<'
&& c != '>' && c != '!' && c != '='
&& c != '/' && c != '#' && c != ',')
)));
409 schema_ungetc(schema, c);
410 *p = '\0';
411 if (kw != NULL((void*)0) && (*kw = strdup(buf)) == NULL((void*)0))
412 fatal("schema_lex: strdup");
413 return STRING1;
414 }
415 if (c == '\n') {
23
←
Assuming the condition is false
→
24
←
Taking false branch
→
52
←
Assuming the condition is false
→
53
←
Taking false branch
→
416 schema->lineno++;
417 goto top;
418 }
419 if (c == EOF(-1))
25
←
Assuming the condition is false
→
26
←
Taking false branch
→
54
←
Assuming the condition is false
→
55
←
Taking false branch
→
420 return (0);
421 return (c);
422}
423
424struct schema *
425schema_new(void)
426{
427 struct schema *schema;
428
429 if ((schema = calloc(1, sizeof(*schema))) == NULL((void*)0))
430 return NULL((void*)0);
431
432 RB_INIT(&schema->attr_types)do { (&schema->attr_types)->rbh_root = ((void*)0); }
while (0);
433 RB_INIT(&schema->attr_names)do { (&schema->attr_names)->rbh_root = ((void*)0); }
while (0);
434 RB_INIT(&schema->objects)do { (&schema->objects)->rbh_root = ((void*)0); } while
(0);
435 RB_INIT(&schema->object_names)do { (&schema->object_names)->rbh_root = ((void*)0)
; } while (0);
436 RB_INIT(&schema->symbolic_oids)do { (&schema->symbolic_oids)->rbh_root = ((void*)0
); } while (0);
437
438 return schema;
439}
440
441static void
442schema_err(struct schema *schema, const char *fmt, ...)
443{
444 va_list ap;
445 char *msg;
446
447 va_start(ap, fmt)__builtin_va_start(ap, fmt);
448 if (vasprintf(&msg, fmt, ap) == -1)
449 fatal("vasprintf");
450 va_end(ap)__builtin_va_end(ap);
451 logit(LOG_CRIT2, "%s:%d: %s", schema->filename, schema->lineno, msg);
452 free(msg);
453
454 schema->error++;
455}
456
457static int
458schema_link_attr_name(struct schema *schema, const char *name, struct attr_type *attr)
459{
460 struct oidname *oidname, *prev;
461
462 if ((oidname = calloc(1, sizeof(*oidname))) == NULL((void*)0)) {
463 log_warn("calloc");
464 return -1;
465 }
466
467 oidname->on_name = name;
468 oidname->on_attr_typeon_ptr.ou_attr_type = attr;
469 prev = RB_INSERT(oidname_tree, &schema->attr_names, oidname)oidname_tree_RB_INSERT(&schema->attr_names, oidname);
470 if (prev != NULL((void*)0)) {
471 schema_err(schema, "attribute type name '%s'"
472 " already defined for oid %s",
473 name, prev->on_attr_typeon_ptr.ou_attr_type->oid);
474 free(oidname);
475 return -1;
476 }
477
478 return 0;
479}
480
481static int
482schema_link_attr_names(struct schema *schema, struct attr_type *attr)
483{
484 struct name *name;
485
486 SLIST_FOREACH(name, attr->names, next)for((name) = ((attr->names)->slh_first); (name) != ((void
*)0); (name) = ((name)->next.sle_next)) {
487 if (schema_link_attr_name(schema, name->name, attr) != 0)
488 return -1;
489 }
490 return 0;
491}
492
493static int
494schema_link_obj_name(struct schema *schema, const char *name, struct object *obj)
495{
496 struct oidname *oidname, *prev;
497
498 if ((oidname = calloc(1, sizeof(*oidname))) == NULL((void*)0)) {
499 log_warn("calloc");
500 return -1;
501 }
502
503 oidname->on_name = name;
504 oidname->on_objecton_ptr.ou_object = obj;
505 prev = RB_INSERT(oidname_tree, &schema->object_names, oidname)oidname_tree_RB_INSERT(&schema->object_names, oidname);
506 if (prev != NULL((void*)0)) {
507 schema_err(schema, "object class name '%s'"
508 " already defined for oid %s",
509 name, prev->on_objecton_ptr.ou_object->oid);
510 free(oidname);
511 return -1;
512 }
513
514 return 0;
515}
516
517static int
518schema_link_obj_names(struct schema *schema, struct object *obj)
519{
520 struct name *name;
521
522 SLIST_FOREACH(name, obj->names, next)for((name) = ((obj->names)->slh_first); (name) != ((void
*)0); (name) = ((name)->next.sle_next)) {
523 if (schema_link_obj_name(schema, name->name, obj) != 0)
524 return -1;
525 }
526 return 0;
527}
528
529static struct name_list *
530schema_parse_names(struct schema *schema)
531{
532 struct name_list *nlist = NULL((void*)0);
533 char *kw;
534 int token;
535
536 token = schema_lex(schema, &kw);
537 if (token == STRING1)
538 return push_name(NULL((void*)0), kw);
539
540 if (token != '(')
541 goto fail;
542
543 for (;;) {
544 token = schema_lex(schema, &kw);
545 if (token == ')')
546 break;
547 if (token != STRING1)
548 goto fail;
549 nlist = push_name(nlist, kw);
550 }
551
552 return nlist;
553
554fail:
555 free(kw);
556 /* FIXME: leaks nlist here */
557 return NULL((void*)0);
558}
559
560static void
561schema_free_name_list(struct name_list *nlist)
562{
563 struct name *name;
564
565 while ((name = SLIST_FIRST(nlist)((nlist)->slh_first)) != NULL((void*)0)) {
566 SLIST_REMOVE_HEAD(nlist, next)do { (nlist)->slh_first = (nlist)->slh_first->next.sle_next
; } while (0);
567 free(name->name);
568 free(name);
569 }
570 free(nlist);
571}
572
573static struct attr_list *
574schema_parse_attrlist(struct schema *schema)
575{
576 struct attr_list *alist = NULL((void*)0);
577 struct attr_type *attr;
578 char *kw;
579 int token, want_dollar = 0;
580
581 token = schema_lex(schema, &kw);
582 if (token == STRING1) {
583 if ((attr = lookup_attribute(schema, kw)) == NULL((void*)0)) {
584 schema_err(schema, "undeclared attribute type '%s'", kw);
585 goto fail;
586 }
587 free(kw);
588 return push_attr(NULL((void*)0), attr);
589 }
590
591 if (token != '(')
592 goto fail;
593
594 for (;;) {
595 token = schema_lex(schema, &kw);
596 if (token == ')')
597 break;
598 if (token == '$') {
599 if (!want_dollar)
600 goto fail;
601 want_dollar = 0;
602 continue;
603 }
604 if (token != STRING1)
605 goto fail;
606 if ((attr = lookup_attribute(schema, kw)) == NULL((void*)0)) {
607 schema_err(schema, "%s: no such attribute", kw);
608 goto fail;
609 }
610 alist = push_attr(alist, attr);
611 free(kw);
612 want_dollar = 1;
613 }
614
615 return alist;
616
617fail:
618 free(kw);
619 /* FIXME: leaks alist here */
620 return NULL((void*)0);
621}
622
623static struct obj_list *
624schema_parse_objlist(struct schema *schema)
625{
626 struct obj_list *olist = NULL((void*)0);
627 struct object *obj;
628 char *kw;
629 int token, want_dollar = 0;
630
631 token = schema_lex(schema, &kw);
632 if (token == STRING1) {
633 if ((obj = lookup_object(schema, kw)) == NULL((void*)0)) {
634 schema_err(schema, "undeclared object class '%s'", kw);
635 goto fail;
636 }
637 free(kw);
638 return push_obj(NULL((void*)0), obj);
639 }
640
641 if (token != '(')
642 goto fail;
643
644 for (;;) {
645 token = schema_lex(schema, &kw);
646 if (token == ')')
647 break;
648 if (token == '$') {
649 if (!want_dollar)
650 goto fail;
651 want_dollar = 0;
652 continue;
653 }
654 if (token != STRING1)
655 goto fail;
656 if ((obj = lookup_object(schema, kw)) == NULL((void*)0))
657 goto fail;
658 olist = push_obj(olist, obj);
659 want_dollar = 1;
660 }
661
662 return olist;
663
664fail:
665 free(kw);
666 /* FIXME: leaks olist here */
667 return NULL((void*)0);
668}
669
670static int
671schema_validate_match_rule(struct schema *schema, struct attr_type *at,
672 const struct match_rule *mrule, enum match_rule_type type)
673{
674 int i;
675
676 if (mrule == NULL((void*)0))
677 return 0;
678
679 if ((mrule->type & type) != type) {
680 schema_err(schema, "%s: bad matching rule '%s'",
681 ATTR_NAME(at)((at)->names ? (((at)->names)->slh_first)->name :
(at)->oid), mrule->name);
682 return -1;
683 }
684
685 /* Is this matching rule compatible with the attribute syntax? */
686 if (strcmp(mrule->syntax_oid, at->syntax->oid) == 0)
687 return 0;
688
689 /* Check any alternative syntaxes for compatibility. */
690 for (i = 0; mrule->alt_syntax_oids && mrule->alt_syntax_oids[i]; i++)
691 if (strcmp(mrule->alt_syntax_oids[i], at->syntax->oid) == 0)
692 return 0;
693
694 schema_err(schema, "%s: inappropriate matching rule '%s' for syntax [%s]",
695 ATTR_NAME(at)((at)->names ? (((at)->names)->slh_first)->name :
(at)->oid), mrule->name, at->syntax->oid);
696 return -1;
697}
698
699static int
700schema_parse_attributetype(struct schema *schema)
701{
702 struct attr_type *attr = NULL((void*)0), *prev, *sup;
703 struct name_list *xnames;
704 char *kw = NULL((void*)0), *arg = NULL((void*)0);
705 int token, ret = 0, c;
706
707 if (schema_lex(schema, NULL((void*)0)) != '(')
708 goto fail;
709
710 if (schema_lex(schema, &kw) != STRING1)
711 goto fail;
712
713 if ((attr = calloc(1, sizeof(*attr))) == NULL((void*)0)) {
714 log_warn("calloc");
715 goto fail;
716 }
717 attr->usage = USAGE_USER_APP;
718
719 if (is_oidstr(kw))
720 attr->oid = kw;
721 else {
722 attr->oid = lookup_symbolic_oid(schema, kw);
723 if (attr->oid == NULL((void*)0))
724 goto fail;
725 free(kw);
726 }
727 kw = NULL((void*)0);
728
729 prev = RB_INSERT(attr_type_tree, &schema->attr_types, attr)attr_type_tree_RB_INSERT(&schema->attr_types, attr);
730 if (prev != NULL((void*)0)) {
731 schema_err(schema, "attribute type %s already defined", attr->oid);
732 goto fail;
733 }
734
735 while (ret == 0) {
736 token = schema_lex(schema, &kw);
737 if (token == ')')
738 break;
739 else if (token != STRING1)
740 goto fail;
741 if (strcasecmp(kw, "NAME") == 0) {
742 attr->names = schema_parse_names(schema);
743 if (attr->names == NULL((void*)0))
744 goto fail;
745 schema_link_attr_names(schema, attr);
746 } else if (strcasecmp(kw, "DESC") == 0) {
747 if (schema_lex(schema, &attr->desc) != STRING1)
748 goto fail;
749 } else if (strcasecmp(kw, "OBSOLETE") == 0) {
750 attr->obsolete = 1;
751 } else if (strcasecmp(kw, "SUP") == 0) {
752 if (schema_lex(schema, &arg) != STRING1)
753 goto fail;
754 if ((attr->sup = lookup_attribute(schema, arg)) == NULL((void*)0)) {
755 schema_err(schema, "%s: no such attribute", arg);
756 goto fail;
757 }
758 free(arg);
759 } else if (strcasecmp(kw, "EQUALITY") == 0) {
760 if (schema_lex(schema, &arg) != STRING1)
761 goto fail;
762 if ((attr->equality = match_rule_lookup(arg)) == NULL((void*)0)) {
763 schema_err(schema, "%s: unknown matching rule",
764 arg);
765 goto fail;
766 }
767 free(arg);
768 } else if (strcasecmp(kw, "ORDERING") == 0) {
769 if (schema_lex(schema, &arg) != STRING1)
770 goto fail;
771 if ((attr->ordering = match_rule_lookup(arg)) == NULL((void*)0)) {
772 schema_err(schema, "%s: unknown matching rule",
773 arg);
774 goto fail;
775 }
776 free(arg);
777 } else if (strcasecmp(kw, "SUBSTR") == 0) {
778 if (schema_lex(schema, &arg) != STRING1)
779 goto fail;
780 if ((attr->substr = match_rule_lookup(arg)) == NULL((void*)0)) {
781 schema_err(schema, "%s: unknown matching rule",
782 arg);
783 goto fail;
784 }
785 free(arg);
786 } else if (strcasecmp(kw, "SYNTAX") == 0) {
787 if (schema_lex(schema, &arg) != STRING1 ||
788 !is_oidstr(arg))
789 goto fail;
790
791 if ((attr->syntax = syntax_lookup(arg)) == NULL((void*)0)) {
792 schema_err(schema, "syntax not supported: %s",
793 arg);
794 goto fail;
795 }
796
797 if ((c = schema_getc(schema, 0)) == '{') {
798 if (schema_lex(schema, NULL((void*)0)) != STRING1 ||
799 schema_lex(schema, NULL((void*)0)) != '}')
800 goto fail;
801 } else
802 schema_ungetc(schema, c);
803 free(arg);
804 } else if (strcasecmp(kw, "SINGLE-VALUE") == 0) {
805 attr->single = 1;
806 } else if (strcasecmp(kw, "COLLECTIVE") == 0) {
807 attr->collective = 1;
808 } else if (strcasecmp(kw, "NO-USER-MODIFICATION") == 0) {
809 attr->immutable = 1;
810 } else if (strcasecmp(kw, "USAGE") == 0) {
811 if (schema_lex(schema, &arg) != STRING1)
812 goto fail;
813 if (strcasecmp(arg, "dSAOperation") == 0)
814 attr->usage = USAGE_DSA_OP;
815 else if (strcasecmp(arg, "directoryOperation") == 0)
816 attr->usage = USAGE_DIR_OP;
817 else if (strcasecmp(arg, "distributedOperation") == 0)
818 attr->usage = USAGE_DIST_OP;
819 else if (strcasecmp(arg, "userApplications") == 0)
820 attr->usage = USAGE_USER_APP;
821 else {
822 schema_err(schema, "invalid usage '%s'", arg);
823 goto fail;
824 }
825 free(arg);
826 } else if (strncmp(kw, "X-", 2) == 0) {
827 /* unknown extension, eat argument(s) */
828 xnames = schema_parse_names(schema);
829 if (xnames == NULL((void*)0))
830 goto fail;
831 schema_free_name_list(xnames);
832 } else {
833 schema_err(schema, "syntax error at token '%s'", kw);
834 goto fail;
835 }
836 free(kw);
837 }
838
839 /* Check that a syntax is defined, either directly or
840 * indirectly via a superior attribute type.
841 */
842 sup = attr->sup;
843 while (attr->syntax == NULL((void*)0) && sup != NULL((void*)0)) {
844 attr->syntax = sup->syntax;
845 sup = sup->sup;
846 }
847 if (attr->syntax == NULL((void*)0)) {
848 schema_err(schema, "%s: no syntax defined", ATTR_NAME(attr)((attr)->names ? (((attr)->names)->slh_first)->name
: (attr)->oid));
849 goto fail;
850 }
851
852 /* If the attribute type doesn't explicitly define equality, check
853 * if any superior attribute type does.
854 */
855 sup = attr->sup;
856 while (attr->equality == NULL((void*)0) && sup != NULL((void*)0)) {
857 attr->equality = sup->equality;
858 sup = sup->sup;
859 }
860 /* Same thing with ordering matching rule. */
861 sup = attr->sup;
862 while (attr->ordering == NULL((void*)0) && sup != NULL((void*)0)) {
863 attr->ordering = sup->ordering;
864 sup = sup->sup;
865 }
866 /* ...and substring matching rule. */
867 sup = attr->sup;
868 while (attr->substr == NULL((void*)0) && sup != NULL((void*)0)) {
869 attr->substr = sup->substr;
870 sup = sup->sup;
871 }
872
873 if (schema_validate_match_rule(schema, attr, attr->equality, MATCH_EQUALITY) != 0 ||
874 schema_validate_match_rule(schema, attr, attr->ordering, MATCH_ORDERING) != 0 ||
875 schema_validate_match_rule(schema, attr, attr->substr, MATCH_SUBSTR) != 0)
876 goto fail;
877
878 return 0;
879
880fail:
881 free(kw);
882 if (attr != NULL((void*)0)) {
883 if (attr->oid != NULL((void*)0)) {
884 RB_REMOVE(attr_type_tree, &schema->attr_types, attr)attr_type_tree_RB_REMOVE(&schema->attr_types, attr);
885 free(attr->oid);
886 }
887 free(attr->desc);
888 free(attr);
889 }
890 return -1;
891}
892
893static int
894schema_parse_objectclass(struct schema *schema)
895{
896 struct object *obj = NULL((void*)0), *prev;
897 struct obj_ptr *optr;
898 struct name_list *xnames;
899 char *kw = NULL((void*)0);
900 int token, ret = 0;
901
902 if (schema_lex(schema, NULL((void*)0)) != '(')
9
←
Assuming the condition is false
→
10
←
Taking false branch
→
903 goto fail;
904
905 if (schema_lex(schema, &kw) != STRING1)
11
←
Calling 'schema_lex'
→
27
←
Returning from 'schema_lex'
→
28
←
Assuming the condition is false
→
29
←
Taking false branch
→
906 goto fail;
907
908 if ((obj = calloc(1, sizeof(*obj))) == NULL((void*)0)) {
30
←
Assuming the condition is false
→
31
←
Taking false branch
→
909 log_warn("calloc");
910 goto fail;
911 }
912 obj->kind = KIND_STRUCTURAL;
913
914 if (is_oidstr(kw))
32
←
Calling 'is_oidstr'
→
35
←
Returning from 'is_oidstr'
→
36
←
Taking true branch
→
915 obj->oid = kw;
916 else {
917 obj->oid = lookup_symbolic_oid(schema, kw);
918 if (obj->oid == NULL((void*)0))
919 goto fail;
920 free(kw);
921 }
922 kw = NULL((void*)0);
923
924 prev = RB_INSERT(object_tree, &schema->objects, obj)object_tree_RB_INSERT(&schema->objects, obj);
925 if (prev
36.1
'prev' is equal to NULL
 != NULL((void*)0)) {
37
←
Taking false branch
→
926 schema_err(schema, "object class %s already defined", obj->oid);
927 goto fail;
928 }
929
930 while (ret == 0) {
38
←
Loop condition is true. Entering loop body
→
931 token = schema_lex(schema, &kw);
39
←
Calling 'schema_lex'
→
56
←
Returning from 'schema_lex'
→
932 if (token == ')')
57
←
Assuming the condition is false
→
58
←
Taking false branch
→
933 break;
934 else if (token != STRING1)
59
←
Assuming 'token' is equal to STRING
→
60
←
Taking false branch
→
935 goto fail;
936 if (strcasecmp(kw, "NAME") == 0) {
61
←
Null pointer passed as 1st argument to string comparison function
937 obj->names = schema_parse_names(schema);
938 if (obj->names == NULL((void*)0))
939 goto fail;
940 schema_link_obj_names(schema, obj);
941 } else if (strcasecmp(kw, "DESC") == 0) {
942 if (schema_lex(schema, &obj->desc) != STRING1)
943 goto fail;
944 } else if (strcasecmp(kw, "OBSOLETE") == 0) {
945 obj->obsolete = 1;
946 } else if (strcasecmp(kw, "SUP") == 0) {
947 obj->sup = schema_parse_objlist(schema);
948 if (obj->sup == NULL((void*)0))
949 goto fail;
950 } else if (strcasecmp(kw, "ABSTRACT") == 0) {
951 obj->kind = KIND_ABSTRACT;
952 } else if (strcasecmp(kw, "STRUCTURAL") == 0) {
953 obj->kind = KIND_STRUCTURAL;
954 } else if (strcasecmp(kw, "AUXILIARY") == 0) {
955 obj->kind = KIND_AUXILIARY;
956 } else if (strcasecmp(kw, "MUST") == 0) {
957 obj->must = schema_parse_attrlist(schema);
958 if (obj->must == NULL((void*)0))
959 goto fail;
960 } else if (strcasecmp(kw, "MAY") == 0) {
961 obj->may = schema_parse_attrlist(schema);
962 if (obj->may == NULL((void*)0))
963 goto fail;
964 } else if (strncasecmp(kw, "X-", 2) == 0) {
965 /* unknown extension, eat argument(s) */
966 xnames = schema_parse_names(schema);
967 if (xnames == NULL((void*)0))
968 goto fail;
969 schema_free_name_list(xnames);
970 } else {
971 schema_err(schema, "syntax error at token '%s'", kw);
972 goto fail;
973 }
974 free(kw);
975 }
976
977 /* Verify the subclassing is allowed.
978 *
979 * Structural object classes cannot subclass auxiliary object classes.
980 * Auxiliary object classes cannot subclass structural object classes.
981 * Abstract object classes cannot derive from structural or auxiliary
982 * object classes.
983 */
984 if (obj->sup != NULL((void*)0)) {
985 SLIST_FOREACH(optr, obj->sup, next)for((optr) = ((obj->sup)->slh_first); (optr) != ((void*
)0); (optr) = ((optr)->next.sle_next)) {
986 if (obj->kind == KIND_STRUCTURAL &&
987 optr->object->kind == KIND_AUXILIARY) {
988 log_warnx("structural object class '%s' cannot"
989 " subclass auxiliary object class '%s'",
990 OBJ_NAME(obj)((obj)->names ? (((obj)->names)->slh_first)->name
: (obj)->oid), OBJ_NAME(optr->object)((optr->object)->names ? (((optr->object)->names)
->slh_first)->name : (optr->object)->oid));
991 goto fail;
992 }
993
994 if (obj->kind == KIND_AUXILIARY &&
995 optr->object->kind == KIND_STRUCTURAL) {
996 log_warnx("auxiliary object class '%s' cannot"
997 " subclass structural object class '%s'",
998 OBJ_NAME(obj)((obj)->names ? (((obj)->names)->slh_first)->name
: (obj)->oid), OBJ_NAME(optr->object)((optr->object)->names ? (((optr->object)->names)
->slh_first)->name : (optr->object)->oid));
999 goto fail;
1000 }
1001
1002 if (obj->kind == KIND_ABSTRACT &&
1003 optr->object->kind != KIND_ABSTRACT) {
1004 log_warnx("abstract object class '%s' cannot"
1005 " subclass non-abstract object class '%s'",
1006 OBJ_NAME(obj)((obj)->names ? (((obj)->names)->slh_first)->name
: (obj)->oid), OBJ_NAME(optr->object)((optr->object)->names ? (((optr->object)->names)
->slh_first)->name : (optr->object)->oid));
1007 goto fail;
1008 }
1009 }
1010 }
1011
1012 return 0;
1013
1014fail:
1015 free(kw);
1016 if (obj != NULL((void*)0)) {
1017 if (obj->oid != NULL((void*)0)) {
1018 RB_REMOVE(object_tree, &schema->objects, obj)object_tree_RB_REMOVE(&schema->objects, obj);
1019 free(obj->oid);
1020 }
1021 free(obj->desc);
1022 free(obj);
1023 }
1024 return -1;
1025}
1026
1027static int
1028schema_parse_objectidentifier(struct schema *schema)
1029{
1030 char *symname = NULL((void*)0), *symoid = NULL((void*)0);
1031 char *oid = NULL((void*)0);
1032
1033 if (schema_lex(schema, &symname) != STRING1)
1034 goto fail;
1035 if (schema_lex(schema, &symoid) != STRING1)
1036 goto fail;
1037
1038 if (is_oidstr(symoid)) {
1039 oid = symoid;
1040 symoid = NULL((void*)0);
1041 } else if ((oid = lookup_symbolic_oid(schema, symoid)) == NULL((void*)0))
1042 goto fail;
1043
1044 if (push_symbolic_oid(schema, symname, oid) == NULL((void*)0))
1045 goto fail;
1046
1047 free(symoid);
1048 return 0;
1049
1050fail:
1051 free(symname);
1052 free(symoid);
1053 free(oid);
1054 return -1;
1055}
1056
1057int
1058schema_parse(struct schema *schema, const char *filename)
1059{
1060 char *kw;
1061 int token, ret = 0;
1062
1063 log_debug("parsing schema file '%s'", filename);
1064
1065 if ((schema->fp = fopen(filename, "r")) == NULL((void*)0)) {
1
Assuming the condition is false
→
2
←
Taking false branch
→
1066 log_warn("%s", filename);
1067 return -1;
1068 }
1069 schema->filename = filename;
1070 schema->lineno = 1;
1071
1072 while (ret == 0) {
3
←
Loop condition is true. Entering loop body
→
1073 token = schema_lex(schema, &kw);
1074 if (token
3.1
'token' is equal to STRING
 == STRING1) {
4
←
Taking true branch
→
1075 if (strcasecmp(kw, "attributetype") == 0)
5
←
Assuming the condition is false
→
6
←
Taking false branch
→
1076 ret = schema_parse_attributetype(schema);
1077 else if (strcasecmp(kw, "objectclass") == 0)
7
←
Taking true branch
→
1078 ret = schema_parse_objectclass(schema);
8
←
Calling 'schema_parse_objectclass'
→
1079 else if (strcasecmp(kw, "objectidentifier") == 0)
1080 ret = schema_parse_objectidentifier(schema);
1081 else {
1082 schema_err(schema, "syntax error at '%s'", kw);
1083 ret = -1;
1084 }
1085 if (ret == -1 && schema->error == 0)
1086 schema_err(schema, "syntax error");
1087 free(kw);
1088 } else if (token == 0) { /* EOF */
1089 break;
1090 } else {
1091 schema_err(schema, "syntax error");
1092 ret = -1;
1093 }
1094 }
1095
1096 fclose(schema->fp);
1097 schema->fp = NULL((void*)0);
1098 schema->filename = NULL((void*)0);
1099
1100 return ret;
1101}
1102
1103static int
1104schema_dump_names(const char *desc, struct name_list *nlist,
1105 char *buf, size_t size)
1106{
1107 struct name *name;
1108
1109 if (nlist == NULL((void*)0) || SLIST_EMPTY(nlist)(((nlist)->slh_first) == ((void*)0)))
1110 return 0;
1111
1112 if (strlcat(buf, " ", size) >= size ||
1113 strlcat(buf, desc, size) >= size)
1114 return -1;
1115
1116 name = SLIST_FIRST(nlist)((nlist)->slh_first);
1117 if (SLIST_NEXT(name, next)((name)->next.sle_next) == NULL((void*)0)) {
1118 /* single name, no parenthesis */
1119 if (strlcat(buf, " '", size) >= size ||
1120 strlcat(buf, name->name, size) >= size ||
1121 strlcat(buf, "'", size) >= size)
1122 return -1;
1123 } else {
1124 if (strlcat(buf, " ( ", size) >= size)
1125 return -1;
1126 SLIST_FOREACH(name, nlist, next)for((name) = ((nlist)->slh_first); (name) != ((void*)0); (
name) = ((name)->next.sle_next))
1127 if (strlcat(buf, "'", size) >= size ||
1128 strlcat(buf, name->name, size) >= size ||
1129 strlcat(buf, "' ", size) >= size)
1130 return -1;
1131 if (strlcat(buf, ")", size) >= size)
1132 return -1;
1133 }
1134
1135 return 0;
1136}
1137
1138static int
1139schema_dump_attrlist(const char *desc, struct attr_list *alist,
1140 char *buf, size_t size)
1141{
1142 struct attr_ptr *aptr;
1143
1144 if (alist == NULL((void*)0) || SLIST_EMPTY(alist)(((alist)->slh_first) == ((void*)0)))
1145 return 0;
1146
1147 if (strlcat(buf, " ", size) >= size ||
1148 strlcat(buf, desc, size) >= size)
1149 return -1;
1150
1151 aptr = SLIST_FIRST(alist)((alist)->slh_first);
1152 if (SLIST_NEXT(aptr, next)((aptr)->next.sle_next) == NULL((void*)0)) {
1153 /* single attribute, no parenthesis */
1154 if (strlcat(buf, " ", size) >= size ||
1155 strlcat(buf, ATTR_NAME(aptr->attr_type)((aptr->attr_type)->names ? (((aptr->attr_type)->
names)->slh_first)->name : (aptr->attr_type)->oid
), size) >= size)
1156 return -1;
1157 } else {
1158 if (strlcat(buf, " ( ", size) >= size)
1159 return -1;
1160 SLIST_FOREACH(aptr, alist, next)for((aptr) = ((alist)->slh_first); (aptr) != ((void*)0); (
aptr) = ((aptr)->next.sle_next)) {
1161 if (strlcat(buf, ATTR_NAME(aptr->attr_type)((aptr->attr_type)->names ? (((aptr->attr_type)->
names)->slh_first)->name : (aptr->attr_type)->oid
),
1162 size) >= size ||
1163 strlcat(buf, " ", size) >= size)
1164 return -1;
1165 if (SLIST_NEXT(aptr, next)((aptr)->next.sle_next) != NULL((void*)0) &&
1166 strlcat(buf, "$ ", size) >= size)
1167 return -1;
1168 }
1169 if (strlcat(buf, ")", size) >= size)
1170 return -1;
1171 }
1172
1173 return 0;
1174}
1175
1176static int
1177schema_dump_objlist(const char *desc, struct obj_list *olist,
1178 char *buf, size_t size)
1179{
1180 struct obj_ptr *optr;
1181
1182 if (olist == NULL((void*)0) || SLIST_EMPTY(olist)(((olist)->slh_first) == ((void*)0)))
1183 return 0;
1184
1185 if (strlcat(buf, " ", size) >= size ||
1186 strlcat(buf, desc, size) >= size)
1187 return -1;
1188
1189 optr = SLIST_FIRST(olist)((olist)->slh_first);
1190 if (SLIST_NEXT(optr, next)((optr)->next.sle_next) == NULL((void*)0)) {
1191 /* single attribute, no parenthesis */
1192 if (strlcat(buf, " ", size) >= size ||
1193 strlcat(buf, OBJ_NAME(optr->object)((optr->object)->names ? (((optr->object)->names)
->slh_first)->name : (optr->object)->oid), size) >= size)
1194 return -1;
1195 } else {
1196 if (strlcat(buf, " ( ", size) >= size)
1197 return -1;
1198 SLIST_FOREACH(optr, olist, next)for((optr) = ((olist)->slh_first); (optr) != ((void*)0); (
optr) = ((optr)->next.sle_next)) {
1199 if (strlcat(buf, OBJ_NAME(optr->object)((optr->object)->names ? (((optr->object)->names)
->slh_first)->name : (optr->object)->oid), size) >= size ||
1200 strlcat(buf, " ", size) >= size)
1201 return -1;
1202 if (SLIST_NEXT(optr, next)((optr)->next.sle_next) != NULL((void*)0) &&
1203 strlcat(buf, "$ ", size) >= size)
1204 return -1;
1205 }
1206 if (strlcat(buf, ")", size) >= size)
1207 return -1;
1208 }
1209
1210 return 0;
1211}
1212
1213int
1214schema_dump_object(struct object *obj, char *buf, size_t size)
1215{
1216 if (strlcpy(buf, "( ", size) >= size ||
1217 strlcat(buf, obj->oid, size) >= size)
1218 return -1;
1219
1220 if (schema_dump_names("NAME", obj->names, buf, size) != 0)
1221 return -1;
1222
1223 if (obj->desc != NULL((void*)0))
1224 if (strlcat(buf, " DESC '", size) >= size ||
1225 strlcat(buf, obj->desc, size) >= size ||
1226 strlcat(buf, "'", size) >= size)
1227 return -1;
1228
1229 switch (obj->kind) {
1230 case KIND_STRUCTURAL:
1231 if (strlcat(buf, " STRUCTURAL", size) >= size)
1232 return -1;
1233 break;
1234 case KIND_ABSTRACT:
1235 if (strlcat(buf, " ABSTRACT", size) >= size)
1236 return -1;
1237 break;
1238 case KIND_AUXILIARY:
1239 if (strlcat(buf, " AUXILIARY", size) >= size)
1240 return -1;
1241 break;
1242 }
1243
1244 if (schema_dump_objlist("SUP", obj->sup, buf, size) != 0)
1245 return -1;
1246
1247 if (obj->obsolete && strlcat(buf, " OBSOLETE", size) >= size)
1248 return -1;
1249
1250 if (schema_dump_attrlist("MUST", obj->must, buf, size) != 0)
1251 return -1;
1252
1253 if (schema_dump_attrlist("MAY", obj->may, buf, size) != 0)
1254 return -1;
1255
1256 if (strlcat(buf, " )", size) >= size)
1257 return -1;
1258
1259 return 0;
1260}
1261
1262int
1263schema_dump_attribute(struct attr_type *at, char *buf, size_t size)
1264{
1265 if (strlcpy(buf, "( ", size) >= size ||
1266 strlcat(buf, at->oid, size) >= size)
1267 return -1;
1268
1269 if (schema_dump_names("NAME", at->names, buf, size) != 0)
1270 return -1;
1271
1272 if (at->desc != NULL((void*)0))
1273 if (strlcat(buf, " DESC '", size) >= size ||
1274 strlcat(buf, at->desc, size) >= size ||
1275 strlcat(buf, "'", size) >= size)
1276 return -1;
1277
1278 if (at->obsolete && strlcat(buf, " OBSOLETE", size) >= size)
1279 return -1;
1280
1281 if (at->sup != NULL((void*)0))
1282 if (strlcat(buf, " SUP ", size) >= size ||
1283 strlcat(buf, ATTR_NAME(at->sup)((at->sup)->names ? (((at->sup)->names)->slh_first
)->name : (at->sup)->oid), size) >= size)
1284 return -1;
1285
1286 if (at->equality != NULL((void*)0))
1287 if (strlcat(buf, " EQUALITY ", size) >= size ||
1288 strlcat(buf, at->equality->name, size) >= size)
1289 return -1;
1290
1291 if (at->ordering != NULL((void*)0))
1292 if (strlcat(buf, " ORDERING ", size) >= size ||
1293 strlcat(buf, at->ordering->name, size) >= size)
1294 return -1;
1295
1296 if (at->substr != NULL((void*)0))
1297 if (strlcat(buf, " SUBSTR ", size) >= size ||
1298 strlcat(buf, at->substr->name, size) >= size)
1299 return -1;
1300
1301 if (at->syntax != NULL((void*)0))
1302 if (strlcat(buf, " SYNTAX ", size) >= size ||
1303 strlcat(buf, at->syntax->oid, size) >= size)
1304 return -1;
1305
1306 if (at->single && strlcat(buf, " SINGLE-VALUE", size) >= size)
1307 return -1;
1308
1309 if (at->collective && strlcat(buf, " COLLECTIVE", size) >= size)
1310 return -1;
1311
1312 if (at->immutable && strlcat(buf, " NO-USER-MODIFICATION", size) >= size)
1313 return -1;
1314
1315 switch (at->usage) {
1316 case USAGE_USER_APP:
1317 /* User application usage is the default. */
1318 break;
1319 case USAGE_DIR_OP:
1320 if (strlcat(buf, " USAGE directoryOperation", size) >= size)
1321 return -1;
1322 break;
1323 case USAGE_DIST_OP:
1324 if (strlcat(buf, " USAGE distributedOperation", size) >= size)
1325 return -1;
1326 break;
1327 case USAGE_DSA_OP:
1328 if (strlcat(buf, " USAGE dSAOperation", size) >= size)
1329 return -1;
1330 break;
1331 }
1332
1333 if (strlcat(buf, " )", size) >= size)
1334 return -1;
1335
1336 return 0;
1337}
1338
1339int
1340schema_dump_match_rule(struct match_rule *mr, char *buf, size_t size)
1341{
1342 if (strlcpy(buf, "( ", size) >= size ||
1343 strlcat(buf, mr->oid, size) >= size ||
1344 strlcat(buf, " NAME '", size) >= size ||
1345 strlcat(buf, mr->name, size) >= size ||
1346 strlcat(buf, "' SYNTAX ", size) >= size ||
1347 strlcat(buf, mr->syntax_oid, size) >= size ||
1348 strlcat(buf, " )", size) >= size)
1349 return -1;
1350
1351 return 0;
1352}
1353