/usr/src/usr.bin/ctfconv/parse.c

Bug Summary

File:	src/usr.bin/ctfconv/parse.c
Warning:	line 674, column 5 Access to field 'it_type' results in a dereference of a null pointer (loaded from variable 'it')
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple amd64-unknown-openbsd7.4 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name parse.c -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -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.bin/ctfconv/obj -resource-dir /usr/local/llvm16/lib/clang/16 -D ZLIB -internal-isystem /usr/local/llvm16/lib/clang/16/include -internal-externc-isystem /usr/include -O2 -Wno-unused -Wno-unused-parameter -fdebug-compilation-dir=/usr/src/usr.bin/ctfconv/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fcf-protection=branch -fno-jump-tables -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/scan/2024-01-11-140451-98009-1 -x c /usr/src/usr.bin/ctfconv/parse.c
1/*	$OpenBSD: parse.c,v 1.15 2022/12/26 18:43:49 jmc Exp $ */
2 
3/*
4 * Copyright (c) 2016-2017 Martin Pieuchot
5 * Copyright (c) 2016 Jasper Lievisse Adriaanse <jasper@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19 
20/*
21 * DWARF to IT (internal type) representation parser.
22 */
23 
24#include <sys/queue.h>
25#include <sys/tree.h>
26#include <sys/types.h>
27#include <sys/ctf.h>
28 
29#include <assert.h>
30#include <limits.h>
31#include <err.h>
32#include <stdlib.h>
33#include <string.h>
34 
35#include "itype.h"
36#include "xmalloc.h"
37#include "dwarf.h"
38#include "dw.h"
39#include "pool.h"
40 
41#ifdef DEBUG
42#include <stdio.h>
43#endif
44 
45#ifndef NOPOOL
46struct pool it_pool, im_pool, ir_pool;
47#endif /* NOPOOL */
48 
49#ifndef nitems
50#define nitems(_a)(sizeof((_a)) / sizeof((_a)[0]))	(sizeof((_a)) / sizeof((_a)[0]))
51#endif
52 
53#define DPRINTF(x...)do { } while (0)	do { /*printf(x)*/ } while (0)
54 
55#define VOID_OFFSET1	1	/* Fake offset for generating "void" type. */
56 
57/*
58 * Tree used to resolve per-CU types based on their offset in
59 * the abbrev section.
60 */
61RB_HEAD(ioff_tree, itype)struct ioff_tree { struct itype *rbh_root; };
62 
63/*
64 * Per-type trees used to merge existing types with the ones of
65 * a newly parsed CU.
66 */
67RB_HEAD(itype_tree, itype)struct itype_tree { struct itype *rbh_root; }	 itypet[CTF_K_MAX31];
68 
69/*
70 * Tree of symbols used to build a list matching the order of
71 * the ELF symbol table.
72 */
73struct isymb_tree	 isymbt;
74 
75struct itype		*void_it;		/* no type is emited for void */
76uint16_t		 tidx, fidx, oidx;	/* type, func & object IDs */
77uint16_t		 long_tidx;		/* index of "long", for array */
78 
79 
80void		 cu_stat(void);
81void		 cu_parse(struct dwcu *, struct itype_queue *,
82		     struct ioff_tree *);
83void		 cu_resolve(struct dwcu *, struct itype_queue *,
84		     struct ioff_tree *);
85void		 cu_reference(struct dwcu *, struct itype_queue *);
86void		 cu_merge(struct dwcu *, struct itype_queue *);
87 
88struct itype	*parse_base(struct dwdie *, size_t);
89struct itype	*parse_refers(struct dwdie *, size_t, int);
90struct itype	*parse_array(struct dwdie *, size_t);
91struct itype	*parse_enum(struct dwdie *, size_t);
92struct itype	*parse_struct(struct dwdie *, size_t, int, size_t);
93struct itype	*parse_function(struct dwdie *, size_t);
94struct itype	*parse_funcptr(struct dwdie *, size_t);
95struct itype	*parse_variable(struct dwdie *, size_t);
96 
97void		 subparse_subrange(struct dwdie *, size_t, struct itype *);
98void		 subparse_enumerator(struct dwdie *, size_t, struct itype *);
99void		 subparse_member(struct dwdie *, size_t, struct itype *, size_t);
100void		 subparse_arguments(struct dwdie *, size_t, struct itype *);
101 
102size_t		 dav2val(struct dwaval *, size_t);
103const char	*dav2str(struct dwaval *);
104const char	*enc2name(unsigned short);
105 
106struct itype	*it_new(uint64_t, size_t, const char *, uint32_t, uint16_t,
107		     uint64_t, uint16_t, unsigned int);
108void		 it_merge(struct itype *, struct itype *);
109void		 it_reference(struct itype *);
110void		 it_free(struct itype *);
111int		 it_cmp(struct itype *, struct itype *);
112int		 it_name_cmp(struct itype *, struct itype *);
113int		 it_off_cmp(struct itype *, struct itype *);
114void		 ir_add(struct itype *, struct itype *);
115void		 ir_purge(struct itype *);
116struct imember	*im_new(const char *, size_t, size_t);
117 
118RB_GENERATE(itype_tree, itype, it_node, it_cmp)void itype_tree_RB_INSERT_COLOR(struct itype_tree *head, struct
 itype *elm) { struct itype *parent, *gparent, *tmp; while ((
parent = (elm)->it_node.rbe_parent) && (parent)->
it_node.rbe_color == 1) { gparent = (parent)->it_node.rbe_parent
; if (parent == (gparent)->it_node.rbe_left) { tmp = (gparent
)->it_node.rbe_right; if (tmp && (tmp)->it_node
.rbe_color == 1) { (tmp)->it_node.rbe_color = 0; do { (parent
)->it_node.rbe_color = 0; (gparent)->it_node.rbe_color =
 1; } while (0); elm = gparent; continue; } if ((parent)->
it_node.rbe_right == elm) { do { (tmp) = (parent)->it_node
.rbe_right; if (((parent)->it_node.rbe_right = (tmp)->it_node
.rbe_left)) { ((tmp)->it_node.rbe_left)->it_node.rbe_parent
 = (parent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (parent)->it_node.rbe_parent)) { if ((parent) == ((parent
)->it_node.rbe_parent)->it_node.rbe_left) ((parent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((parent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_left = (parent
); (parent)->it_node.rbe_parent = (tmp); do {} while (0); if
 (((tmp)->it_node.rbe_parent)) do {} while (0); } while (0
); tmp = parent; parent = elm; elm = tmp; } do { (parent)->
it_node.rbe_color = 0; (gparent)->it_node.rbe_color = 1; }
 while (0); do { (tmp) = (gparent)->it_node.rbe_left; if (
((gparent)->it_node.rbe_left = (tmp)->it_node.rbe_right
)) { ((tmp)->it_node.rbe_right)->it_node.rbe_parent = (
gparent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (gparent)->it_node.rbe_parent)) { if ((gparent) == ((gparent
)->it_node.rbe_parent)->it_node.rbe_left) ((gparent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((gparent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_right = (
gparent); (gparent)->it_node.rbe_parent = (tmp); do {} while
 (0); if (((tmp)->it_node.rbe_parent)) do {} while (0); } while
 (0); } else { tmp = (gparent)->it_node.rbe_left; if (tmp &&
 (tmp)->it_node.rbe_color == 1) { (tmp)->it_node.rbe_color
 = 0; do { (parent)->it_node.rbe_color = 0; (gparent)->
it_node.rbe_color = 1; } while (0); elm = gparent; continue; }
 if ((parent)->it_node.rbe_left == elm) { do { (tmp) = (parent
)->it_node.rbe_left; if (((parent)->it_node.rbe_left = (
tmp)->it_node.rbe_right)) { ((tmp)->it_node.rbe_right)->
it_node.rbe_parent = (parent); } do {} while (0); if (((tmp)->
it_node.rbe_parent = (parent)->it_node.rbe_parent)) { if (
(parent) == ((parent)->it_node.rbe_parent)->it_node.rbe_left
) ((parent)->it_node.rbe_parent)->it_node.rbe_left = (tmp
); else ((parent)->it_node.rbe_parent)->it_node.rbe_right
 = (tmp); } else (head)->rbh_root = (tmp); (tmp)->it_node
.rbe_right = (parent); (parent)->it_node.rbe_parent = (tmp
); do {} while (0); if (((tmp)->it_node.rbe_parent)) do {}
 while (0); } while (0); tmp = parent; parent = elm; elm = tmp
; } do { (parent)->it_node.rbe_color = 0; (gparent)->it_node
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->it_node
.rbe_right; if (((gparent)->it_node.rbe_right = (tmp)->
it_node.rbe_left)) { ((tmp)->it_node.rbe_left)->it_node
.rbe_parent = (gparent); } do {} while (0); if (((tmp)->it_node
.rbe_parent = (gparent)->it_node.rbe_parent)) { if ((gparent
) == ((gparent)->it_node.rbe_parent)->it_node.rbe_left)
 ((gparent)->it_node.rbe_parent)->it_node.rbe_left = (tmp
); else ((gparent)->it_node.rbe_parent)->it_node.rbe_right
 = (tmp); } else (head)->rbh_root = (tmp); (tmp)->it_node
.rbe_left = (gparent); (gparent)->it_node.rbe_parent = (tmp
); do {} while (0); if (((tmp)->it_node.rbe_parent)) do {}
 while (0); } while (0); } } (head->rbh_root)->it_node.
rbe_color = 0; } void itype_tree_RB_REMOVE_COLOR(struct itype_tree
 *head, struct itype *parent, struct itype *elm) { struct itype
 *tmp; while ((elm == ((void *)0) || (elm)->it_node.rbe_color
 == 0) && elm != (head)->rbh_root) { if ((parent)->
it_node.rbe_left == elm) { tmp = (parent)->it_node.rbe_right
; if ((tmp)->it_node.rbe_color == 1) { do { (tmp)->it_node
.rbe_color = 0; (parent)->it_node.rbe_color = 1; } while (
0); do { (tmp) = (parent)->it_node.rbe_right; if (((parent
)->it_node.rbe_right = (tmp)->it_node.rbe_left)) { ((tmp
)->it_node.rbe_left)->it_node.rbe_parent = (parent); } do
 {} while (0); if (((tmp)->it_node.rbe_parent = (parent)->
it_node.rbe_parent)) { if ((parent) == ((parent)->it_node.
rbe_parent)->it_node.rbe_left) ((parent)->it_node.rbe_parent
)->it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_left = (parent); (parent)->it_node
.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node.
rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
it_node.rbe_right; } if (((tmp)->it_node.rbe_left == ((void
 *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color ==
 0) && ((tmp)->it_node.rbe_right == ((void *)0) ||
 ((tmp)->it_node.rbe_right)->it_node.rbe_color == 0)) {
 (tmp)->it_node.rbe_color = 1; elm = parent; parent = (elm
)->it_node.rbe_parent; } else { if ((tmp)->it_node.rbe_right
 == ((void *)0) || ((tmp)->it_node.rbe_right)->it_node.
rbe_color == 0) { struct itype *oleft; if ((oleft = (tmp)->
it_node.rbe_left)) (oleft)->it_node.rbe_color = 0; (tmp)->
it_node.rbe_color = 1; do { (oleft) = (tmp)->it_node.rbe_left
; if (((tmp)->it_node.rbe_left = (oleft)->it_node.rbe_right
)) { ((oleft)->it_node.rbe_right)->it_node.rbe_parent =
 (tmp); } do {} while (0); if (((oleft)->it_node.rbe_parent
 = (tmp)->it_node.rbe_parent)) { if ((tmp) == ((tmp)->it_node
.rbe_parent)->it_node.rbe_left) ((tmp)->it_node.rbe_parent
)->it_node.rbe_left = (oleft); else ((tmp)->it_node.rbe_parent
)->it_node.rbe_right = (oleft); } else (head)->rbh_root
 = (oleft); (oleft)->it_node.rbe_right = (tmp); (tmp)->
it_node.rbe_parent = (oleft); do {} while (0); if (((oleft)->
it_node.rbe_parent)) do {} while (0); } while (0); tmp = (parent
)->it_node.rbe_right; } (tmp)->it_node.rbe_color = (parent
)->it_node.rbe_color; (parent)->it_node.rbe_color = 0; if
 ((tmp)->it_node.rbe_right) ((tmp)->it_node.rbe_right)->
it_node.rbe_color = 0; do { (tmp) = (parent)->it_node.rbe_right
; if (((parent)->it_node.rbe_right = (tmp)->it_node.rbe_left
)) { ((tmp)->it_node.rbe_left)->it_node.rbe_parent = (parent
); } do {} while (0); if (((tmp)->it_node.rbe_parent = (parent
)->it_node.rbe_parent)) { if ((parent) == ((parent)->it_node
.rbe_parent)->it_node.rbe_left) ((parent)->it_node.rbe_parent
)->it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_left = (parent); (parent)->it_node
.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node.
rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root
; break; } } else { tmp = (parent)->it_node.rbe_left; if (
(tmp)->it_node.rbe_color == 1) { do { (tmp)->it_node.rbe_color
 = 0; (parent)->it_node.rbe_color = 1; } while (0); do { (
tmp) = (parent)->it_node.rbe_left; if (((parent)->it_node
.rbe_left = (tmp)->it_node.rbe_right)) { ((tmp)->it_node
.rbe_right)->it_node.rbe_parent = (parent); } do {} while (
0); if (((tmp)->it_node.rbe_parent = (parent)->it_node.
rbe_parent)) { if ((parent) == ((parent)->it_node.rbe_parent
)->it_node.rbe_left) ((parent)->it_node.rbe_parent)->
it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_right = (parent); (parent)->
it_node.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
it_node.rbe_left; } if (((tmp)->it_node.rbe_left == ((void
 *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color ==
 0) && ((tmp)->it_node.rbe_right == ((void *)0) ||
 ((tmp)->it_node.rbe_right)->it_node.rbe_color == 0)) {
 (tmp)->it_node.rbe_color = 1; elm = parent; parent = (elm
)->it_node.rbe_parent; } else { if ((tmp)->it_node.rbe_left
 == ((void *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color
 == 0) { struct itype *oright; if ((oright = (tmp)->it_node
.rbe_right)) (oright)->it_node.rbe_color = 0; (tmp)->it_node
.rbe_color = 1; do { (oright) = (tmp)->it_node.rbe_right; if
 (((tmp)->it_node.rbe_right = (oright)->it_node.rbe_left
)) { ((oright)->it_node.rbe_left)->it_node.rbe_parent =
 (tmp); } do {} while (0); if (((oright)->it_node.rbe_parent
 = (tmp)->it_node.rbe_parent)) { if ((tmp) == ((tmp)->it_node
.rbe_parent)->it_node.rbe_left) ((tmp)->it_node.rbe_parent
)->it_node.rbe_left = (oright); else ((tmp)->it_node.rbe_parent
)->it_node.rbe_right = (oright); } else (head)->rbh_root
 = (oright); (oright)->it_node.rbe_left = (tmp); (tmp)->
it_node.rbe_parent = (oright); do {} while (0); if (((oright)
->it_node.rbe_parent)) do {} while (0); } while (0); tmp =
 (parent)->it_node.rbe_left; } (tmp)->it_node.rbe_color
 = (parent)->it_node.rbe_color; (parent)->it_node.rbe_color
 = 0; if ((tmp)->it_node.rbe_left) ((tmp)->it_node.rbe_left
)->it_node.rbe_color = 0; do { (tmp) = (parent)->it_node
.rbe_left; if (((parent)->it_node.rbe_left = (tmp)->it_node
.rbe_right)) { ((tmp)->it_node.rbe_right)->it_node.rbe_parent
 = (parent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (parent)->it_node.rbe_parent)) { if ((parent) == ((parent
)->it_node.rbe_parent)->it_node.rbe_left) ((parent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((parent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_right = (
parent); (parent)->it_node.rbe_parent = (tmp); do {} while
 (0); if (((tmp)->it_node.rbe_parent)) do {} while (0); } while
 (0); elm = (head)->rbh_root; break; } } } if (elm) (elm)->
it_node.rbe_color = 0; } struct itype * itype_tree_RB_REMOVE(
struct itype_tree *head, struct itype *elm) { struct itype *child
, *parent, *old = elm; int color; if ((elm)->it_node.rbe_left
 == ((void *)0)) child = (elm)->it_node.rbe_right; else if
 ((elm)->it_node.rbe_right == ((void *)0)) child = (elm)->
it_node.rbe_left; else { struct itype *left; elm = (elm)->
it_node.rbe_right; while ((left = (elm)->it_node.rbe_left)
) elm = left; child = (elm)->it_node.rbe_right; parent = (
elm)->it_node.rbe_parent; color = (elm)->it_node.rbe_color
; if (child) (child)->it_node.rbe_parent = parent; if (parent
) { if ((parent)->it_node.rbe_left == elm) (parent)->it_node
.rbe_left = child; else (parent)->it_node.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; if ((elm
)->it_node.rbe_parent == old) parent = elm; (elm)->it_node
 = (old)->it_node; if ((old)->it_node.rbe_parent) { if (
((old)->it_node.rbe_parent)->it_node.rbe_left == old) (
(old)->it_node.rbe_parent)->it_node.rbe_left = elm; else
 ((old)->it_node.rbe_parent)->it_node.rbe_right = elm; do
 {} while (0); } else (head)->rbh_root = elm; ((old)->it_node
.rbe_left)->it_node.rbe_parent = elm; if ((old)->it_node
.rbe_right) ((old)->it_node.rbe_right)->it_node.rbe_parent
 = elm; if (parent) { left = parent; do { do {} while (0); } while
 ((left = (left)->it_node.rbe_parent)); } goto color; } parent
 = (elm)->it_node.rbe_parent; color = (elm)->it_node.rbe_color
; if (child) (child)->it_node.rbe_parent = parent; if (parent
) { if ((parent)->it_node.rbe_left == elm) (parent)->it_node
.rbe_left = child; else (parent)->it_node.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; color:
 if (color == 0) itype_tree_RB_REMOVE_COLOR(head, parent, child
); return (old); } struct itype * itype_tree_RB_INSERT(struct
 itype_tree *head, struct itype *elm) { struct itype *tmp; struct
 itype *parent = ((void *)0); int comp = 0; tmp = (head)->
rbh_root; while (tmp) { parent = tmp; comp = (it_cmp)(elm, parent
); if (comp < 0) tmp = (tmp)->it_node.rbe_left; else if
 (comp > 0) tmp = (tmp)->it_node.rbe_right; else return
 (tmp); } do { (elm)->it_node.rbe_parent = parent; (elm)->
it_node.rbe_left = (elm)->it_node.rbe_right = ((void *)0);
 (elm)->it_node.rbe_color = 1; } while (0); if (parent != (
(void *)0)) { if (comp < 0) (parent)->it_node.rbe_left =
 elm; else (parent)->it_node.rbe_right = elm; do {} while (
0); } else (head)->rbh_root = elm; itype_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct itype * itype_tree_RB_FIND
(struct itype_tree *head, struct itype *elm) { struct itype *
tmp = (head)->rbh_root; int comp; while (tmp) { comp = it_cmp
(elm, tmp); if (comp < 0) tmp = (tmp)->it_node.rbe_left
; else if (comp > 0) tmp = (tmp)->it_node.rbe_right; else
 return (tmp); } return (((void *)0)); } struct itype * itype_tree_RB_NFIND
(struct itype_tree *head, struct itype *elm) { struct itype *
tmp = (head)->rbh_root; struct itype *res = ((void *)0); int
 comp; while (tmp) { comp = it_cmp(elm, tmp); if (comp < 0
) { res = tmp; tmp = (tmp)->it_node.rbe_left; } else if (comp
 > 0) tmp = (tmp)->it_node.rbe_right; else return (tmp)
; } return (res); } struct itype * itype_tree_RB_NEXT(struct itype
 *elm) { if ((elm)->it_node.rbe_right) { elm = (elm)->it_node
.rbe_right; while ((elm)->it_node.rbe_left) elm = (elm)->
it_node.rbe_left; } else { if ((elm)->it_node.rbe_parent &&
 (elm == ((elm)->it_node.rbe_parent)->it_node.rbe_left)
) elm = (elm)->it_node.rbe_parent; else { while ((elm)->
it_node.rbe_parent && (elm == ((elm)->it_node.rbe_parent
)->it_node.rbe_right)) elm = (elm)->it_node.rbe_parent;
 elm = (elm)->it_node.rbe_parent; } } return (elm); } struct
 itype * itype_tree_RB_PREV(struct itype *elm) { if ((elm)->
it_node.rbe_left) { elm = (elm)->it_node.rbe_left; while (
(elm)->it_node.rbe_right) elm = (elm)->it_node.rbe_right
; } else { if ((elm)->it_node.rbe_parent && (elm ==
 ((elm)->it_node.rbe_parent)->it_node.rbe_right)) elm =
 (elm)->it_node.rbe_parent; else { while ((elm)->it_node
.rbe_parent && (elm == ((elm)->it_node.rbe_parent)
->it_node.rbe_left)) elm = (elm)->it_node.rbe_parent; elm
 = (elm)->it_node.rbe_parent; } } return (elm); } struct itype
 * itype_tree_RB_MINMAX(struct itype_tree *head, int val) { struct
 itype *tmp = (head)->rbh_root; struct itype *parent = ((void
 *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp
)->it_node.rbe_left; else tmp = (tmp)->it_node.rbe_right
; } return (parent); };
119RB_GENERATE(isymb_tree, itype, it_node, it_name_cmp)void isymb_tree_RB_INSERT_COLOR(struct isymb_tree *head, struct
 itype *elm) { struct itype *parent, *gparent, *tmp; while ((
parent = (elm)->it_node.rbe_parent) && (parent)->
it_node.rbe_color == 1) { gparent = (parent)->it_node.rbe_parent
; if (parent == (gparent)->it_node.rbe_left) { tmp = (gparent
)->it_node.rbe_right; if (tmp && (tmp)->it_node
.rbe_color == 1) { (tmp)->it_node.rbe_color = 0; do { (parent
)->it_node.rbe_color = 0; (gparent)->it_node.rbe_color =
 1; } while (0); elm = gparent; continue; } if ((parent)->
it_node.rbe_right == elm) { do { (tmp) = (parent)->it_node
.rbe_right; if (((parent)->it_node.rbe_right = (tmp)->it_node
.rbe_left)) { ((tmp)->it_node.rbe_left)->it_node.rbe_parent
 = (parent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (parent)->it_node.rbe_parent)) { if ((parent) == ((parent
)->it_node.rbe_parent)->it_node.rbe_left) ((parent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((parent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_left = (parent
); (parent)->it_node.rbe_parent = (tmp); do {} while (0); if
 (((tmp)->it_node.rbe_parent)) do {} while (0); } while (0
); tmp = parent; parent = elm; elm = tmp; } do { (parent)->
it_node.rbe_color = 0; (gparent)->it_node.rbe_color = 1; }
 while (0); do { (tmp) = (gparent)->it_node.rbe_left; if (
((gparent)->it_node.rbe_left = (tmp)->it_node.rbe_right
)) { ((tmp)->it_node.rbe_right)->it_node.rbe_parent = (
gparent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (gparent)->it_node.rbe_parent)) { if ((gparent) == ((gparent
)->it_node.rbe_parent)->it_node.rbe_left) ((gparent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((gparent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_right = (
gparent); (gparent)->it_node.rbe_parent = (tmp); do {} while
 (0); if (((tmp)->it_node.rbe_parent)) do {} while (0); } while
 (0); } else { tmp = (gparent)->it_node.rbe_left; if (tmp &&
 (tmp)->it_node.rbe_color == 1) { (tmp)->it_node.rbe_color
 = 0; do { (parent)->it_node.rbe_color = 0; (gparent)->
it_node.rbe_color = 1; } while (0); elm = gparent; continue; }
 if ((parent)->it_node.rbe_left == elm) { do { (tmp) = (parent
)->it_node.rbe_left; if (((parent)->it_node.rbe_left = (
tmp)->it_node.rbe_right)) { ((tmp)->it_node.rbe_right)->
it_node.rbe_parent = (parent); } do {} while (0); if (((tmp)->
it_node.rbe_parent = (parent)->it_node.rbe_parent)) { if (
(parent) == ((parent)->it_node.rbe_parent)->it_node.rbe_left
) ((parent)->it_node.rbe_parent)->it_node.rbe_left = (tmp
); else ((parent)->it_node.rbe_parent)->it_node.rbe_right
 = (tmp); } else (head)->rbh_root = (tmp); (tmp)->it_node
.rbe_right = (parent); (parent)->it_node.rbe_parent = (tmp
); do {} while (0); if (((tmp)->it_node.rbe_parent)) do {}
 while (0); } while (0); tmp = parent; parent = elm; elm = tmp
; } do { (parent)->it_node.rbe_color = 0; (gparent)->it_node
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->it_node
.rbe_right; if (((gparent)->it_node.rbe_right = (tmp)->
it_node.rbe_left)) { ((tmp)->it_node.rbe_left)->it_node
.rbe_parent = (gparent); } do {} while (0); if (((tmp)->it_node
.rbe_parent = (gparent)->it_node.rbe_parent)) { if ((gparent
) == ((gparent)->it_node.rbe_parent)->it_node.rbe_left)
 ((gparent)->it_node.rbe_parent)->it_node.rbe_left = (tmp
); else ((gparent)->it_node.rbe_parent)->it_node.rbe_right
 = (tmp); } else (head)->rbh_root = (tmp); (tmp)->it_node
.rbe_left = (gparent); (gparent)->it_node.rbe_parent = (tmp
); do {} while (0); if (((tmp)->it_node.rbe_parent)) do {}
 while (0); } while (0); } } (head->rbh_root)->it_node.
rbe_color = 0; } void isymb_tree_RB_REMOVE_COLOR(struct isymb_tree
 *head, struct itype *parent, struct itype *elm) { struct itype
 *tmp; while ((elm == ((void *)0) || (elm)->it_node.rbe_color
 == 0) && elm != (head)->rbh_root) { if ((parent)->
it_node.rbe_left == elm) { tmp = (parent)->it_node.rbe_right
; if ((tmp)->it_node.rbe_color == 1) { do { (tmp)->it_node
.rbe_color = 0; (parent)->it_node.rbe_color = 1; } while (
0); do { (tmp) = (parent)->it_node.rbe_right; if (((parent
)->it_node.rbe_right = (tmp)->it_node.rbe_left)) { ((tmp
)->it_node.rbe_left)->it_node.rbe_parent = (parent); } do
 {} while (0); if (((tmp)->it_node.rbe_parent = (parent)->
it_node.rbe_parent)) { if ((parent) == ((parent)->it_node.
rbe_parent)->it_node.rbe_left) ((parent)->it_node.rbe_parent
)->it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_left = (parent); (parent)->it_node
.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node.
rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
it_node.rbe_right; } if (((tmp)->it_node.rbe_left == ((void
 *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color ==
 0) && ((tmp)->it_node.rbe_right == ((void *)0) ||
 ((tmp)->it_node.rbe_right)->it_node.rbe_color == 0)) {
 (tmp)->it_node.rbe_color = 1; elm = parent; parent = (elm
)->it_node.rbe_parent; } else { if ((tmp)->it_node.rbe_right
 == ((void *)0) || ((tmp)->it_node.rbe_right)->it_node.
rbe_color == 0) { struct itype *oleft; if ((oleft = (tmp)->
it_node.rbe_left)) (oleft)->it_node.rbe_color = 0; (tmp)->
it_node.rbe_color = 1; do { (oleft) = (tmp)->it_node.rbe_left
; if (((tmp)->it_node.rbe_left = (oleft)->it_node.rbe_right
)) { ((oleft)->it_node.rbe_right)->it_node.rbe_parent =
 (tmp); } do {} while (0); if (((oleft)->it_node.rbe_parent
 = (tmp)->it_node.rbe_parent)) { if ((tmp) == ((tmp)->it_node
.rbe_parent)->it_node.rbe_left) ((tmp)->it_node.rbe_parent
)->it_node.rbe_left = (oleft); else ((tmp)->it_node.rbe_parent
)->it_node.rbe_right = (oleft); } else (head)->rbh_root
 = (oleft); (oleft)->it_node.rbe_right = (tmp); (tmp)->
it_node.rbe_parent = (oleft); do {} while (0); if (((oleft)->
it_node.rbe_parent)) do {} while (0); } while (0); tmp = (parent
)->it_node.rbe_right; } (tmp)->it_node.rbe_color = (parent
)->it_node.rbe_color; (parent)->it_node.rbe_color = 0; if
 ((tmp)->it_node.rbe_right) ((tmp)->it_node.rbe_right)->
it_node.rbe_color = 0; do { (tmp) = (parent)->it_node.rbe_right
; if (((parent)->it_node.rbe_right = (tmp)->it_node.rbe_left
)) { ((tmp)->it_node.rbe_left)->it_node.rbe_parent = (parent
); } do {} while (0); if (((tmp)->it_node.rbe_parent = (parent
)->it_node.rbe_parent)) { if ((parent) == ((parent)->it_node
.rbe_parent)->it_node.rbe_left) ((parent)->it_node.rbe_parent
)->it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_left = (parent); (parent)->it_node
.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node.
rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root
; break; } } else { tmp = (parent)->it_node.rbe_left; if (
(tmp)->it_node.rbe_color == 1) { do { (tmp)->it_node.rbe_color
 = 0; (parent)->it_node.rbe_color = 1; } while (0); do { (
tmp) = (parent)->it_node.rbe_left; if (((parent)->it_node
.rbe_left = (tmp)->it_node.rbe_right)) { ((tmp)->it_node
.rbe_right)->it_node.rbe_parent = (parent); } do {} while (
0); if (((tmp)->it_node.rbe_parent = (parent)->it_node.
rbe_parent)) { if ((parent) == ((parent)->it_node.rbe_parent
)->it_node.rbe_left) ((parent)->it_node.rbe_parent)->
it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_right = (parent); (parent)->
it_node.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
it_node.rbe_left; } if (((tmp)->it_node.rbe_left == ((void
 *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color ==
 0) && ((tmp)->it_node.rbe_right == ((void *)0) ||
 ((tmp)->it_node.rbe_right)->it_node.rbe_color == 0)) {
 (tmp)->it_node.rbe_color = 1; elm = parent; parent = (elm
)->it_node.rbe_parent; } else { if ((tmp)->it_node.rbe_left
 == ((void *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color
 == 0) { struct itype *oright; if ((oright = (tmp)->it_node
.rbe_right)) (oright)->it_node.rbe_color = 0; (tmp)->it_node
.rbe_color = 1; do { (oright) = (tmp)->it_node.rbe_right; if
 (((tmp)->it_node.rbe_right = (oright)->it_node.rbe_left
)) { ((oright)->it_node.rbe_left)->it_node.rbe_parent =
 (tmp); } do {} while (0); if (((oright)->it_node.rbe_parent
 = (tmp)->it_node.rbe_parent)) { if ((tmp) == ((tmp)->it_node
.rbe_parent)->it_node.rbe_left) ((tmp)->it_node.rbe_parent
)->it_node.rbe_left = (oright); else ((tmp)->it_node.rbe_parent
)->it_node.rbe_right = (oright); } else (head)->rbh_root
 = (oright); (oright)->it_node.rbe_left = (tmp); (tmp)->
it_node.rbe_parent = (oright); do {} while (0); if (((oright)
->it_node.rbe_parent)) do {} while (0); } while (0); tmp =
 (parent)->it_node.rbe_left; } (tmp)->it_node.rbe_color
 = (parent)->it_node.rbe_color; (parent)->it_node.rbe_color
 = 0; if ((tmp)->it_node.rbe_left) ((tmp)->it_node.rbe_left
)->it_node.rbe_color = 0; do { (tmp) = (parent)->it_node
.rbe_left; if (((parent)->it_node.rbe_left = (tmp)->it_node
.rbe_right)) { ((tmp)->it_node.rbe_right)->it_node.rbe_parent
 = (parent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (parent)->it_node.rbe_parent)) { if ((parent) == ((parent
)->it_node.rbe_parent)->it_node.rbe_left) ((parent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((parent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_right = (
parent); (parent)->it_node.rbe_parent = (tmp); do {} while
 (0); if (((tmp)->it_node.rbe_parent)) do {} while (0); } while
 (0); elm = (head)->rbh_root; break; } } } if (elm) (elm)->
it_node.rbe_color = 0; } struct itype * isymb_tree_RB_REMOVE(
struct isymb_tree *head, struct itype *elm) { struct itype *child
, *parent, *old = elm; int color; if ((elm)->it_node.rbe_left
 == ((void *)0)) child = (elm)->it_node.rbe_right; else if
 ((elm)->it_node.rbe_right == ((void *)0)) child = (elm)->
it_node.rbe_left; else { struct itype *left; elm = (elm)->
it_node.rbe_right; while ((left = (elm)->it_node.rbe_left)
) elm = left; child = (elm)->it_node.rbe_right; parent = (
elm)->it_node.rbe_parent; color = (elm)->it_node.rbe_color
; if (child) (child)->it_node.rbe_parent = parent; if (parent
) { if ((parent)->it_node.rbe_left == elm) (parent)->it_node
.rbe_left = child; else (parent)->it_node.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; if ((elm
)->it_node.rbe_parent == old) parent = elm; (elm)->it_node
 = (old)->it_node; if ((old)->it_node.rbe_parent) { if (
((old)->it_node.rbe_parent)->it_node.rbe_left == old) (
(old)->it_node.rbe_parent)->it_node.rbe_left = elm; else
 ((old)->it_node.rbe_parent)->it_node.rbe_right = elm; do
 {} while (0); } else (head)->rbh_root = elm; ((old)->it_node
.rbe_left)->it_node.rbe_parent = elm; if ((old)->it_node
.rbe_right) ((old)->it_node.rbe_right)->it_node.rbe_parent
 = elm; if (parent) { left = parent; do { do {} while (0); } while
 ((left = (left)->it_node.rbe_parent)); } goto color; } parent
 = (elm)->it_node.rbe_parent; color = (elm)->it_node.rbe_color
; if (child) (child)->it_node.rbe_parent = parent; if (parent
) { if ((parent)->it_node.rbe_left == elm) (parent)->it_node
.rbe_left = child; else (parent)->it_node.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; color:
 if (color == 0) isymb_tree_RB_REMOVE_COLOR(head, parent, child
); return (old); } struct itype * isymb_tree_RB_INSERT(struct
 isymb_tree *head, struct itype *elm) { struct itype *tmp; struct
 itype *parent = ((void *)0); int comp = 0; tmp = (head)->
rbh_root; while (tmp) { parent = tmp; comp = (it_name_cmp)(elm
, parent); if (comp < 0) tmp = (tmp)->it_node.rbe_left;
 else if (comp > 0) tmp = (tmp)->it_node.rbe_right; else
 return (tmp); } do { (elm)->it_node.rbe_parent = parent; (
elm)->it_node.rbe_left = (elm)->it_node.rbe_right = ((void
 *)0); (elm)->it_node.rbe_color = 1; } while (0); if (parent
 != ((void *)0)) { if (comp < 0) (parent)->it_node.rbe_left
 = elm; else (parent)->it_node.rbe_right = elm; do {} while
 (0); } else (head)->rbh_root = elm; isymb_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct itype * isymb_tree_RB_FIND
(struct isymb_tree *head, struct itype *elm) { struct itype *
tmp = (head)->rbh_root; int comp; while (tmp) { comp = it_name_cmp
(elm, tmp); if (comp < 0) tmp = (tmp)->it_node.rbe_left
; else if (comp > 0) tmp = (tmp)->it_node.rbe_right; else
 return (tmp); } return (((void *)0)); } struct itype * isymb_tree_RB_NFIND
(struct isymb_tree *head, struct itype *elm) { struct itype *
tmp = (head)->rbh_root; struct itype *res = ((void *)0); int
 comp; while (tmp) { comp = it_name_cmp(elm, tmp); if (comp <
 0) { res = tmp; tmp = (tmp)->it_node.rbe_left; } else if (
comp > 0) tmp = (tmp)->it_node.rbe_right; else return (
tmp); } return (res); } struct itype * isymb_tree_RB_NEXT(struct
 itype *elm) { if ((elm)->it_node.rbe_right) { elm = (elm)
->it_node.rbe_right; while ((elm)->it_node.rbe_left) elm
 = (elm)->it_node.rbe_left; } else { if ((elm)->it_node
.rbe_parent && (elm == ((elm)->it_node.rbe_parent)
->it_node.rbe_left)) elm = (elm)->it_node.rbe_parent; else
 { while ((elm)->it_node.rbe_parent && (elm == ((elm
)->it_node.rbe_parent)->it_node.rbe_right)) elm = (elm)
->it_node.rbe_parent; elm = (elm)->it_node.rbe_parent; }
 } return (elm); } struct itype * isymb_tree_RB_PREV(struct itype
 *elm) { if ((elm)->it_node.rbe_left) { elm = (elm)->it_node
.rbe_left; while ((elm)->it_node.rbe_right) elm = (elm)->
it_node.rbe_right; } else { if ((elm)->it_node.rbe_parent &&
 (elm == ((elm)->it_node.rbe_parent)->it_node.rbe_right
)) elm = (elm)->it_node.rbe_parent; else { while ((elm)->
it_node.rbe_parent && (elm == ((elm)->it_node.rbe_parent
)->it_node.rbe_left)) elm = (elm)->it_node.rbe_parent; elm
 = (elm)->it_node.rbe_parent; } } return (elm); } struct itype
 * isymb_tree_RB_MINMAX(struct isymb_tree *head, int val) { struct
 itype *tmp = (head)->rbh_root; struct itype *parent = ((void
 *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp
)->it_node.rbe_left; else tmp = (tmp)->it_node.rbe_right
; } return (parent); };
120RB_GENERATE(ioff_tree, itype, it_node, it_off_cmp)void ioff_tree_RB_INSERT_COLOR(struct ioff_tree *head, struct
 itype *elm) { struct itype *parent, *gparent, *tmp; while ((
parent = (elm)->it_node.rbe_parent) && (parent)->
it_node.rbe_color == 1) { gparent = (parent)->it_node.rbe_parent
; if (parent == (gparent)->it_node.rbe_left) { tmp = (gparent
)->it_node.rbe_right; if (tmp && (tmp)->it_node
.rbe_color == 1) { (tmp)->it_node.rbe_color = 0; do { (parent
)->it_node.rbe_color = 0; (gparent)->it_node.rbe_color =
 1; } while (0); elm = gparent; continue; } if ((parent)->
it_node.rbe_right == elm) { do { (tmp) = (parent)->it_node
.rbe_right; if (((parent)->it_node.rbe_right = (tmp)->it_node
.rbe_left)) { ((tmp)->it_node.rbe_left)->it_node.rbe_parent
 = (parent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (parent)->it_node.rbe_parent)) { if ((parent) == ((parent
)->it_node.rbe_parent)->it_node.rbe_left) ((parent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((parent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_left = (parent
); (parent)->it_node.rbe_parent = (tmp); do {} while (0); if
 (((tmp)->it_node.rbe_parent)) do {} while (0); } while (0
); tmp = parent; parent = elm; elm = tmp; } do { (parent)->
it_node.rbe_color = 0; (gparent)->it_node.rbe_color = 1; }
 while (0); do { (tmp) = (gparent)->it_node.rbe_left; if (
((gparent)->it_node.rbe_left = (tmp)->it_node.rbe_right
)) { ((tmp)->it_node.rbe_right)->it_node.rbe_parent = (
gparent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (gparent)->it_node.rbe_parent)) { if ((gparent) == ((gparent
)->it_node.rbe_parent)->it_node.rbe_left) ((gparent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((gparent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_right = (
gparent); (gparent)->it_node.rbe_parent = (tmp); do {} while
 (0); if (((tmp)->it_node.rbe_parent)) do {} while (0); } while
 (0); } else { tmp = (gparent)->it_node.rbe_left; if (tmp &&
 (tmp)->it_node.rbe_color == 1) { (tmp)->it_node.rbe_color
 = 0; do { (parent)->it_node.rbe_color = 0; (gparent)->
it_node.rbe_color = 1; } while (0); elm = gparent; continue; }
 if ((parent)->it_node.rbe_left == elm) { do { (tmp) = (parent
)->it_node.rbe_left; if (((parent)->it_node.rbe_left = (
tmp)->it_node.rbe_right)) { ((tmp)->it_node.rbe_right)->
it_node.rbe_parent = (parent); } do {} while (0); if (((tmp)->
it_node.rbe_parent = (parent)->it_node.rbe_parent)) { if (
(parent) == ((parent)->it_node.rbe_parent)->it_node.rbe_left
) ((parent)->it_node.rbe_parent)->it_node.rbe_left = (tmp
); else ((parent)->it_node.rbe_parent)->it_node.rbe_right
 = (tmp); } else (head)->rbh_root = (tmp); (tmp)->it_node
.rbe_right = (parent); (parent)->it_node.rbe_parent = (tmp
); do {} while (0); if (((tmp)->it_node.rbe_parent)) do {}
 while (0); } while (0); tmp = parent; parent = elm; elm = tmp
; } do { (parent)->it_node.rbe_color = 0; (gparent)->it_node
.rbe_color = 1; } while (0); do { (tmp) = (gparent)->it_node
.rbe_right; if (((gparent)->it_node.rbe_right = (tmp)->
it_node.rbe_left)) { ((tmp)->it_node.rbe_left)->it_node
.rbe_parent = (gparent); } do {} while (0); if (((tmp)->it_node
.rbe_parent = (gparent)->it_node.rbe_parent)) { if ((gparent
) == ((gparent)->it_node.rbe_parent)->it_node.rbe_left)
 ((gparent)->it_node.rbe_parent)->it_node.rbe_left = (tmp
); else ((gparent)->it_node.rbe_parent)->it_node.rbe_right
 = (tmp); } else (head)->rbh_root = (tmp); (tmp)->it_node
.rbe_left = (gparent); (gparent)->it_node.rbe_parent = (tmp
); do {} while (0); if (((tmp)->it_node.rbe_parent)) do {}
 while (0); } while (0); } } (head->rbh_root)->it_node.
rbe_color = 0; } void ioff_tree_RB_REMOVE_COLOR(struct ioff_tree
 *head, struct itype *parent, struct itype *elm) { struct itype
 *tmp; while ((elm == ((void *)0) || (elm)->it_node.rbe_color
 == 0) && elm != (head)->rbh_root) { if ((parent)->
it_node.rbe_left == elm) { tmp = (parent)->it_node.rbe_right
; if ((tmp)->it_node.rbe_color == 1) { do { (tmp)->it_node
.rbe_color = 0; (parent)->it_node.rbe_color = 1; } while (
0); do { (tmp) = (parent)->it_node.rbe_right; if (((parent
)->it_node.rbe_right = (tmp)->it_node.rbe_left)) { ((tmp
)->it_node.rbe_left)->it_node.rbe_parent = (parent); } do
 {} while (0); if (((tmp)->it_node.rbe_parent = (parent)->
it_node.rbe_parent)) { if ((parent) == ((parent)->it_node.
rbe_parent)->it_node.rbe_left) ((parent)->it_node.rbe_parent
)->it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_left = (parent); (parent)->it_node
.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node.
rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
it_node.rbe_right; } if (((tmp)->it_node.rbe_left == ((void
 *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color ==
 0) && ((tmp)->it_node.rbe_right == ((void *)0) ||
 ((tmp)->it_node.rbe_right)->it_node.rbe_color == 0)) {
 (tmp)->it_node.rbe_color = 1; elm = parent; parent = (elm
)->it_node.rbe_parent; } else { if ((tmp)->it_node.rbe_right
 == ((void *)0) || ((tmp)->it_node.rbe_right)->it_node.
rbe_color == 0) { struct itype *oleft; if ((oleft = (tmp)->
it_node.rbe_left)) (oleft)->it_node.rbe_color = 0; (tmp)->
it_node.rbe_color = 1; do { (oleft) = (tmp)->it_node.rbe_left
; if (((tmp)->it_node.rbe_left = (oleft)->it_node.rbe_right
)) { ((oleft)->it_node.rbe_right)->it_node.rbe_parent =
 (tmp); } do {} while (0); if (((oleft)->it_node.rbe_parent
 = (tmp)->it_node.rbe_parent)) { if ((tmp) == ((tmp)->it_node
.rbe_parent)->it_node.rbe_left) ((tmp)->it_node.rbe_parent
)->it_node.rbe_left = (oleft); else ((tmp)->it_node.rbe_parent
)->it_node.rbe_right = (oleft); } else (head)->rbh_root
 = (oleft); (oleft)->it_node.rbe_right = (tmp); (tmp)->
it_node.rbe_parent = (oleft); do {} while (0); if (((oleft)->
it_node.rbe_parent)) do {} while (0); } while (0); tmp = (parent
)->it_node.rbe_right; } (tmp)->it_node.rbe_color = (parent
)->it_node.rbe_color; (parent)->it_node.rbe_color = 0; if
 ((tmp)->it_node.rbe_right) ((tmp)->it_node.rbe_right)->
it_node.rbe_color = 0; do { (tmp) = (parent)->it_node.rbe_right
; if (((parent)->it_node.rbe_right = (tmp)->it_node.rbe_left
)) { ((tmp)->it_node.rbe_left)->it_node.rbe_parent = (parent
); } do {} while (0); if (((tmp)->it_node.rbe_parent = (parent
)->it_node.rbe_parent)) { if ((parent) == ((parent)->it_node
.rbe_parent)->it_node.rbe_left) ((parent)->it_node.rbe_parent
)->it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_left = (parent); (parent)->it_node
.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node.
rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root
; break; } } else { tmp = (parent)->it_node.rbe_left; if (
(tmp)->it_node.rbe_color == 1) { do { (tmp)->it_node.rbe_color
 = 0; (parent)->it_node.rbe_color = 1; } while (0); do { (
tmp) = (parent)->it_node.rbe_left; if (((parent)->it_node
.rbe_left = (tmp)->it_node.rbe_right)) { ((tmp)->it_node
.rbe_right)->it_node.rbe_parent = (parent); } do {} while (
0); if (((tmp)->it_node.rbe_parent = (parent)->it_node.
rbe_parent)) { if ((parent) == ((parent)->it_node.rbe_parent
)->it_node.rbe_left) ((parent)->it_node.rbe_parent)->
it_node.rbe_left = (tmp); else ((parent)->it_node.rbe_parent
)->it_node.rbe_right = (tmp); } else (head)->rbh_root =
 (tmp); (tmp)->it_node.rbe_right = (parent); (parent)->
it_node.rbe_parent = (tmp); do {} while (0); if (((tmp)->it_node
.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->
it_node.rbe_left; } if (((tmp)->it_node.rbe_left == ((void
 *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color ==
 0) && ((tmp)->it_node.rbe_right == ((void *)0) ||
 ((tmp)->it_node.rbe_right)->it_node.rbe_color == 0)) {
 (tmp)->it_node.rbe_color = 1; elm = parent; parent = (elm
)->it_node.rbe_parent; } else { if ((tmp)->it_node.rbe_left
 == ((void *)0) || ((tmp)->it_node.rbe_left)->it_node.rbe_color
 == 0) { struct itype *oright; if ((oright = (tmp)->it_node
.rbe_right)) (oright)->it_node.rbe_color = 0; (tmp)->it_node
.rbe_color = 1; do { (oright) = (tmp)->it_node.rbe_right; if
 (((tmp)->it_node.rbe_right = (oright)->it_node.rbe_left
)) { ((oright)->it_node.rbe_left)->it_node.rbe_parent =
 (tmp); } do {} while (0); if (((oright)->it_node.rbe_parent
 = (tmp)->it_node.rbe_parent)) { if ((tmp) == ((tmp)->it_node
.rbe_parent)->it_node.rbe_left) ((tmp)->it_node.rbe_parent
)->it_node.rbe_left = (oright); else ((tmp)->it_node.rbe_parent
)->it_node.rbe_right = (oright); } else (head)->rbh_root
 = (oright); (oright)->it_node.rbe_left = (tmp); (tmp)->
it_node.rbe_parent = (oright); do {} while (0); if (((oright)
->it_node.rbe_parent)) do {} while (0); } while (0); tmp =
 (parent)->it_node.rbe_left; } (tmp)->it_node.rbe_color
 = (parent)->it_node.rbe_color; (parent)->it_node.rbe_color
 = 0; if ((tmp)->it_node.rbe_left) ((tmp)->it_node.rbe_left
)->it_node.rbe_color = 0; do { (tmp) = (parent)->it_node
.rbe_left; if (((parent)->it_node.rbe_left = (tmp)->it_node
.rbe_right)) { ((tmp)->it_node.rbe_right)->it_node.rbe_parent
 = (parent); } do {} while (0); if (((tmp)->it_node.rbe_parent
 = (parent)->it_node.rbe_parent)) { if ((parent) == ((parent
)->it_node.rbe_parent)->it_node.rbe_left) ((parent)->
it_node.rbe_parent)->it_node.rbe_left = (tmp); else ((parent
)->it_node.rbe_parent)->it_node.rbe_right = (tmp); } else
 (head)->rbh_root = (tmp); (tmp)->it_node.rbe_right = (
parent); (parent)->it_node.rbe_parent = (tmp); do {} while
 (0); if (((tmp)->it_node.rbe_parent)) do {} while (0); } while
 (0); elm = (head)->rbh_root; break; } } } if (elm) (elm)->
it_node.rbe_color = 0; } struct itype * ioff_tree_RB_REMOVE(struct
 ioff_tree *head, struct itype *elm) { struct itype *child, *
parent, *old = elm; int color; if ((elm)->it_node.rbe_left
 == ((void *)0)) child = (elm)->it_node.rbe_right; else if
 ((elm)->it_node.rbe_right == ((void *)0)) child = (elm)->
it_node.rbe_left; else { struct itype *left; elm = (elm)->
it_node.rbe_right; while ((left = (elm)->it_node.rbe_left)
) elm = left; child = (elm)->it_node.rbe_right; parent = (
elm)->it_node.rbe_parent; color = (elm)->it_node.rbe_color
; if (child) (child)->it_node.rbe_parent = parent; if (parent
) { if ((parent)->it_node.rbe_left == elm) (parent)->it_node
.rbe_left = child; else (parent)->it_node.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; if ((elm
)->it_node.rbe_parent == old) parent = elm; (elm)->it_node
 = (old)->it_node; if ((old)->it_node.rbe_parent) { if (
((old)->it_node.rbe_parent)->it_node.rbe_left == old) (
(old)->it_node.rbe_parent)->it_node.rbe_left = elm; else
 ((old)->it_node.rbe_parent)->it_node.rbe_right = elm; do
 {} while (0); } else (head)->rbh_root = elm; ((old)->it_node
.rbe_left)->it_node.rbe_parent = elm; if ((old)->it_node
.rbe_right) ((old)->it_node.rbe_right)->it_node.rbe_parent
 = elm; if (parent) { left = parent; do { do {} while (0); } while
 ((left = (left)->it_node.rbe_parent)); } goto color; } parent
 = (elm)->it_node.rbe_parent; color = (elm)->it_node.rbe_color
; if (child) (child)->it_node.rbe_parent = parent; if (parent
) { if ((parent)->it_node.rbe_left == elm) (parent)->it_node
.rbe_left = child; else (parent)->it_node.rbe_right = child
; do {} while (0); } else (head)->rbh_root = child; color:
 if (color == 0) ioff_tree_RB_REMOVE_COLOR(head, parent, child
); return (old); } struct itype * ioff_tree_RB_INSERT(struct ioff_tree
 *head, struct itype *elm) { struct itype *tmp; struct itype *
parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root
; while (tmp) { parent = tmp; comp = (it_off_cmp)(elm, parent
); if (comp < 0) tmp = (tmp)->it_node.rbe_left; else if
 (comp > 0) tmp = (tmp)->it_node.rbe_right; else return
 (tmp); } do { (elm)->it_node.rbe_parent = parent; (elm)->
it_node.rbe_left = (elm)->it_node.rbe_right = ((void *)0);
 (elm)->it_node.rbe_color = 1; } while (0); if (parent != (
(void *)0)) { if (comp < 0) (parent)->it_node.rbe_left =
 elm; else (parent)->it_node.rbe_right = elm; do {} while (
0); } else (head)->rbh_root = elm; ioff_tree_RB_INSERT_COLOR
(head, elm); return (((void *)0)); } struct itype * ioff_tree_RB_FIND
(struct ioff_tree *head, struct itype *elm) { struct itype *tmp
 = (head)->rbh_root; int comp; while (tmp) { comp = it_off_cmp
(elm, tmp); if (comp < 0) tmp = (tmp)->it_node.rbe_left
; else if (comp > 0) tmp = (tmp)->it_node.rbe_right; else
 return (tmp); } return (((void *)0)); } struct itype * ioff_tree_RB_NFIND
(struct ioff_tree *head, struct itype *elm) { struct itype *tmp
 = (head)->rbh_root; struct itype *res = ((void *)0); int comp
; while (tmp) { comp = it_off_cmp(elm, tmp); if (comp < 0)
 { res = tmp; tmp = (tmp)->it_node.rbe_left; } else if (comp
 > 0) tmp = (tmp)->it_node.rbe_right; else return (tmp)
; } return (res); } struct itype * ioff_tree_RB_NEXT(struct itype
 *elm) { if ((elm)->it_node.rbe_right) { elm = (elm)->it_node
.rbe_right; while ((elm)->it_node.rbe_left) elm = (elm)->
it_node.rbe_left; } else { if ((elm)->it_node.rbe_parent &&
 (elm == ((elm)->it_node.rbe_parent)->it_node.rbe_left)
) elm = (elm)->it_node.rbe_parent; else { while ((elm)->
it_node.rbe_parent && (elm == ((elm)->it_node.rbe_parent
)->it_node.rbe_right)) elm = (elm)->it_node.rbe_parent;
 elm = (elm)->it_node.rbe_parent; } } return (elm); } struct
 itype * ioff_tree_RB_PREV(struct itype *elm) { if ((elm)->
it_node.rbe_left) { elm = (elm)->it_node.rbe_left; while (
(elm)->it_node.rbe_right) elm = (elm)->it_node.rbe_right
; } else { if ((elm)->it_node.rbe_parent && (elm ==
 ((elm)->it_node.rbe_parent)->it_node.rbe_right)) elm =
 (elm)->it_node.rbe_parent; else { while ((elm)->it_node
.rbe_parent && (elm == ((elm)->it_node.rbe_parent)
->it_node.rbe_left)) elm = (elm)->it_node.rbe_parent; elm
 = (elm)->it_node.rbe_parent; } } return (elm); } struct itype
 * ioff_tree_RB_MINMAX(struct ioff_tree *head, int val) { struct
 itype *tmp = (head)->rbh_root; struct itype *parent = ((void
 *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp
)->it_node.rbe_left; else tmp = (tmp)->it_node.rbe_right
; } return (parent); };
121 
122/*
123 * Construct a list of internal type and functions based on DWARF
124 * INFO and ABBREV sections.
125 *
126 * Multiple CUs are supported.
127 */
128void
129dwarf_parse(const char *infobuf, size_t infolen, const char *abbuf,
130    size_t ablen)
131{
132	struct dwbuf		 info = { .buf = infobuf, .len = infolen };
133	struct dwbuf		 abbrev = { .buf = abbuf, .len = ablen };
134	struct dwcu		*dcu = NULL((void *)0);
135	struct ioff_tree	 cu_iofft;
136	struct itype_queue	 cu_itypeq;
137	struct itype		*it;
138	int			 i;
139 
140	for (i = 0; i < CTF_K_MAX31; i++)
141		RB_INIT(&itypet[i])do { (&itypet[i])->rbh_root = ((void *)0); } while (0);
142	RB_INIT(&isymbt)do { (&isymbt)->rbh_root = ((void *)0); } while (0);
143 
144	void_it = it_new(++tidx, VOID_OFFSET1, "void", 0,
145	    CTF_INT_SIGNED(1 << 0), 0, CTF_K_INTEGER1, 0);
146	TAILQ_INSERT_TAIL(&itypeq, void_it, it_next)do { (void_it)->it_next.tqe_next = ((void *)0); (void_it)->
it_next.tqe_prev = (&itypeq)->tqh_last; *(&itypeq)
->tqh_last = (void_it); (&itypeq)->tqh_last = &
(void_it)->it_next.tqe_next; } while (0);
147 
148	while (dw_cu_parse(&info, &abbrev, infolen, &dcu) == 0) {
149		TAILQ_INIT(&cu_itypeq)do { (&cu_itypeq)->tqh_first = ((void *)0); (&cu_itypeq
)->tqh_last = &(&cu_itypeq)->tqh_first; } while
 (0);
150 
151		/* We use a tree to speed-up type resolution. */
152		RB_INIT(&cu_iofft)do { (&cu_iofft)->rbh_root = ((void *)0); } while (0);
153 
154		/* Parse this CU */
155		cu_parse(dcu, &cu_itypeq, &cu_iofft);
156 
157		/* Resolve its types. */
158		cu_resolve(dcu, &cu_itypeq, &cu_iofft);
159		assert(RB_EMPTY(&cu_iofft))((((&cu_iofft)->rbh_root == ((void *)0))) ? (void)0 : __assert2
("/usr/src/usr.bin/ctfconv/parse.c", 159, __func__, "RB_EMPTY(&cu_iofft)"
));
160 
161		/* Mark used type as such. */
162		cu_reference(dcu, &cu_itypeq);
163 
164#ifdef DEBUG
165		/* Dump statistics for current CU. */
166		cu_stat();
167#endif
168 
169		/* Merge them with the common type list. */
170		cu_merge(dcu, &cu_itypeq);
171 
172		dw_dcu_free(dcu);
173	}
174 
175	/* We force array's index type to be 'long', for that we need its ID. */
176	RB_FOREACH(it, itype_tree, &itypet[CTF_K_INTEGER])for ((it) = itype_tree_RB_MINMAX(&itypet[1], -1); (it) !=
 ((void *)0); (it) = itype_tree_RB_NEXT(it)) {
177		if (it_name(it) == NULL((void *)0) || it->it_size != (8 * sizeof(long)))
178			continue;
179 
180		if (strcmp(it_name(it), "unsigned") == 0) {
181			long_tidx = it->it_idx;
182			break;
183		}
184	}
185}
186 
187struct itype *
188it_new(uint64_t index, size_t off, const char *name, uint32_t size,
189    uint16_t enc, uint64_t ref, uint16_t type, unsigned int flags)
190{
191	struct itype *it;
192#ifndef NOPOOL
193	static int it_pool_inited = 0;
194 
195	if (!it_pool_inited) {
196		pool_init(&it_pool, "it", 512, sizeof(struct itype));
197		pool_init(&im_pool, "im", 1024, sizeof(struct imember));
198		pool_init(&ir_pool, "ir", 1024, sizeof(struct itref));
199		it_pool_inited = 1;
200	}
201#endif
202 
203	assert((name != NULL) || !(flags & (ITF_FUNC|ITF_OBJ)))(((name != ((void *)0)) || !(flags & (0x04|0x08))) ? (void
)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c", 203, __func__
, "(name != NULL) || !(flags & (ITF_FUNC|ITF_OBJ))"));
204 
205	it = pmalloc(&it_pool, sizeof(*it));
206	SIMPLEQ_INIT(&it->it_refs)do { (&it->it_refs)->sqh_first = ((void *)0); (&
it->it_refs)->sqh_last = &(&it->it_refs)->
sqh_first; } while (0);
207	TAILQ_INIT(&it->it_members)do { (&it->it_members)->tqh_first = ((void *)0); (&
it->it_members)->tqh_last = &(&it->it_members
)->tqh_first; } while (0);
208	it->it_off = off;
209	it->it_ref = ref;
210	it->it_refp = NULL((void *)0);
211	it->it_size = size;
212	it->it_nelems = 0;
213	it->it_enc = enc;
214	it->it_idx = index;
215	it->it_type = type;
216	it->it_flags = flags;
217 
218	if (name == NULL((void *)0)) {
219		it->it_flags |= ITF_ANON0x80;
220	} else {
221		size_t n;
222 
223		if ((n = strlcpy(it->it_name, name, ITNAME_MAX128)) > ITNAME_MAX128)
224			warnx("name %s too long %zd > %d", name, n, ITNAME_MAX128);
225	}
226 
227	return it;
228}
229 
230struct itype *
231it_dup(struct itype *it)
232{
233	struct imember *copim, *im;
234	struct itype *copit;
235 
236	copit = it_new(it->it_idx, it->it_off, it_name(it), it->it_size,
237	    it->it_enc, it->it_ref, it->it_type, it->it_flags);
238 
239	copit->it_refp = it->it_refp;
240	copit->it_nelems = it->it_nelems;
241 
242	TAILQ_FOREACH(im, &it->it_members, im_next)for((im) = ((&it->it_members)->tqh_first); (im) != (
(void *)0); (im) = ((im)->im_next.tqe_next)) {
243		copim = im_new(im_name(im), im->im_ref, im->im_off);
244		copim->im_refp = im->im_refp;
245		TAILQ_INSERT_TAIL(&copit->it_members, copim, im_next)do { (copim)->im_next.tqe_next = ((void *)0); (copim)->
im_next.tqe_prev = (&copit->it_members)->tqh_last; *
(&copit->it_members)->tqh_last = (copim); (&copit
->it_members)->tqh_last = &(copim)->im_next.tqe_next
; } while (0);
246	}
247 
248	return copit;
249}
250 
251/*
252 * Merge the content of ``it'', the full type declaration into the
253 * forwarding representation ``fwd''.
254 */
255void
256it_merge(struct itype *fwd, struct itype *it)
257{
258	assert(fwd->it_flags & ITF_FORWARD)((fwd->it_flags & 0x10) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 258, __func__, "fwd->it_flags & ITF_FORWARD"));
259	assert(fwd->it_type == it->it_type)((fwd->it_type == it->it_type) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 259, __func__, "fwd->it_type == it->it_type"));
260	assert(TAILQ_EMPTY(&fwd->it_members))(((((&fwd->it_members)->tqh_first) == ((void *)0)))
 ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c", 260
, __func__, "TAILQ_EMPTY(&fwd->it_members)"));
261	assert(SIMPLEQ_EMPTY(&it->it_refs))(((((&it->it_refs)->sqh_first) == ((void *)0))) ? (
void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c", 261, __func__
, "SIMPLEQ_EMPTY(&it->it_refs)"));
262 
263	fwd->it_off = it->it_off;
264	fwd->it_ref = it->it_ref;
265	fwd->it_refp = it->it_refp;
266	fwd->it_size = it->it_size;
267	fwd->it_nelems = it->it_nelems;
268	fwd->it_enc = it->it_enc;
269	fwd->it_flags = it->it_flags;
270 
271	TAILQ_CONCAT(&fwd->it_members, &it->it_members, im_next)do { if (!(((&it->it_members)->tqh_first) == ((void
 *)0))) { *(&fwd->it_members)->tqh_last = (&it->
it_members)->tqh_first; (&it->it_members)->tqh_first
->im_next.tqe_prev = (&fwd->it_members)->tqh_last
; (&fwd->it_members)->tqh_last = (&it->it_members
)->tqh_last; do { ((&it->it_members))->tqh_first
 = ((void *)0); ((&it->it_members))->tqh_last = &
((&it->it_members))->tqh_first; } while (0); } } while
 (0);
272	assert(TAILQ_EMPTY(&it->it_members))(((((&it->it_members)->tqh_first) == ((void *)0))) ?
 (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c", 272,
 __func__, "TAILQ_EMPTY(&it->it_members)"));
273}
274 
275const char *
276it_name(struct itype *it)
277{
278	if (!(it->it_flags & ITF_ANON0x80))
279		return it->it_name;
280 
281	return NULL((void *)0);
282}
283 
284void
285it_reference(struct itype *it)
286{
287	struct imember *im;
288 
289	if (it == NULL((void *)0) || it->it_flags & ITF_USED0x40)
290		return;
291 
292	it->it_flags |= ITF_USED0x40;
293 
294	it_reference(it->it_refp);
295	TAILQ_FOREACH(im, &it->it_members, im_next)for((im) = ((&it->it_members)->tqh_first); (im) != (
(void *)0); (im) = ((im)->im_next.tqe_next))
296		it_reference(im->im_refp);
297}
298 
299void
300it_free(struct itype *it)
301{
302	struct imember *im;
303 
304	if (it == NULL((void *)0))
305		return;
306 
307	while ((im = TAILQ_FIRST(&it->it_members)((&it->it_members)->tqh_first)) != NULL((void *)0)) {
308		TAILQ_REMOVE(&it->it_members, im, im_next)do { if (((im)->im_next.tqe_next) != ((void *)0)) (im)->
im_next.tqe_next->im_next.tqe_prev = (im)->im_next.tqe_prev
; else (&it->it_members)->tqh_last = (im)->im_next
.tqe_prev; *(im)->im_next.tqe_prev = (im)->im_next.tqe_next
; ; ; } while (0);
309		pfree(&im_pool, im);
310	}
311 
312	ir_purge(it);
313	pfree(&it_pool, it);
314}
315 
316/*
317 * Return 0 if ``a'' matches ``b''.
318 */
319int
320it_cmp(struct itype *a, struct itype *b)
321{
322	int diff;
323 
324	if ((diff = (a->it_type - b->it_type)) != 0)
325		return diff;
326 
327	/* Basic types need to have the same size. */
328	if ((a->it_type == CTF_K_INTEGER1 || a->it_type == CTF_K_FLOAT2) &&
329	    (diff = (a->it_size - b->it_size) != 0))
330		return diff;
331 
332	/* Match by name */
333	if (!(a->it_flags & ITF_ANON0x80) && !(b->it_flags & ITF_ANON0x80))
334		return strcmp(it_name(a), it_name(b));
335 
336	/* Only one of them is anonym */
337	if ((a->it_flags & ITF_ANON0x80) != (b->it_flags & ITF_ANON0x80))
338		return (a->it_flags & ITF_ANON0x80) ? -1 : 1;
339 
340	/* Match by reference */
341	if ((a->it_refp != NULL((void *)0)) && (b->it_refp != NULL((void *)0)))
342		return it_cmp(a->it_refp, b->it_refp);
343 
344	return 1;
345}
346 
347int
348it_name_cmp(struct itype *a, struct itype *b)
349{
350	int diff;
351 
352	if ((diff = strcmp(it_name(a), it_name(b))) != 0)
353		return diff;
354 
355	return ((a->it_flags|ITF_MASK(0x20|0x40)) - (b->it_flags|ITF_MASK(0x20|0x40)));
356}
357 
358int
359it_off_cmp(struct itype *a, struct itype *b)
360{
361	return a->it_off - b->it_off;
362}
363 
364void
365ir_add(struct itype *it, struct itype *tmp)
366{
367	struct itref *ir;
368 
369	SIMPLEQ_FOREACH(ir, &tmp->it_refs, ir_next)for((ir) = ((&tmp->it_refs)->sqh_first); (ir) != ((
void *)0); (ir) = ((ir)->ir_next.sqe_next)) {
370		if (ir->ir_itp == it)
371			return;
372	}
373 
374	ir = pmalloc(&ir_pool, sizeof(*ir));
375	ir->ir_itp = it;
376	SIMPLEQ_INSERT_TAIL(&tmp->it_refs, ir, ir_next)do { (ir)->ir_next.sqe_next = ((void *)0); *(&tmp->
it_refs)->sqh_last = (ir); (&tmp->it_refs)->sqh_last
 = &(ir)->ir_next.sqe_next; } while (0);
377}
378 
379void
380ir_purge(struct itype *it)
381{
382	struct itref *ir;
383 
384	while ((ir = SIMPLEQ_FIRST(&it->it_refs)((&it->it_refs)->sqh_first)) != NULL((void *)0)) {
385		SIMPLEQ_REMOVE_HEAD(&it->it_refs, ir_next)do { if (((&it->it_refs)->sqh_first = (&it->
it_refs)->sqh_first->ir_next.sqe_next) == ((void *)0)) (
&it->it_refs)->sqh_last = &(&it->it_refs
)->sqh_first; } while (0);
386		pfree(&ir_pool, ir);
387	}
388}
389 
390struct imember *
391im_new(const char *name, size_t ref, size_t off)
392{
393	struct imember *im;
394 
395	im = pmalloc(&im_pool, sizeof(*im));
396	im->im_ref = ref;
397	im->im_off = off;
398	im->im_refp = NULL((void *)0);
399	if (name == NULL((void *)0)) {
400		im->im_flags = IMF_ANON0x01;
401	} else {
402		size_t n;
403 
404		n = strlcpy(im->im_name, name, ITNAME_MAX128);
405		if (n > ITNAME_MAX128)
406			warnx("name %s too long %zd > %d", name, n,
407			    ITNAME_MAX128);
408		im->im_flags = 0;
409	}
410 
411	return im;
412}
413 
414const char *
415im_name(struct imember *im)
416{
417	if (!(im->im_flags & IMF_ANON0x01))
418		return im->im_name;
419 
420	return NULL((void *)0);
421}
422 
423void
424cu_stat(void)
425{
426#ifndef NOPOOL
427	pool_dump();
428#endif
429}
430 
431/*
432 * Iterate over all types found in a given CU.  For all non-resolved types
433 * use their DWARF relative offset to find the relative type they are pointing
434 * to.  The CU offset tree, `cuot', is used to speedup relative type lookup.
435 */
436void
437cu_resolve(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
438{
439	struct itype	*it, *ref, tmp;
440	struct imember	*im;
441	unsigned int	 toresolve;
442	size_t		 off = dcu->dcu_offset;
443 
444	TAILQ_FOREACH(it, cutq, it_next)for((it) = ((cutq)->tqh_first); (it) != ((void *)0); (it) =
 ((it)->it_next.tqe_next)) {
445		if (!(it->it_flags & (ITF_UNRES0x01|ITF_UNRES_MEMB0x02)))
446			continue;
447 
448		/* If this type references another one, try to find it. */
449		if (it->it_flags & ITF_UNRES0x01) {
450			tmp.it_off = it->it_ref + off;
451			ref = RB_FIND(ioff_tree, cuot, &tmp)ioff_tree_RB_FIND(cuot, &tmp);
452			if (ref != NULL((void *)0)) {
453				it->it_refp = ref;
454				ir_add(it, ref);
455				it->it_flags &= ~ITF_UNRES0x01;
456			}
457		}
458 
459		/* If this type has members, resolve all of them. */
460		toresolve = it->it_nelems;
461		if ((it->it_flags & ITF_UNRES_MEMB0x02) && toresolve > 0) {
462			TAILQ_FOREACH(im, &it->it_members, im_next)for((im) = ((&it->it_members)->tqh_first); (im) != (
(void *)0); (im) = ((im)->im_next.tqe_next)) {
463				tmp.it_off = im->im_ref + off;
464				ref = RB_FIND(ioff_tree, cuot, &tmp)ioff_tree_RB_FIND(cuot, &tmp);
465				if (ref != NULL((void *)0)) {
466					im->im_refp = ref;
467					ir_add(it, ref);
468					toresolve--;
469				}
470			}
471			if (toresolve == 0)
472				it->it_flags &= ~ITF_UNRES_MEMB0x02;
473		}
474#if defined(DEBUG)
475		if (it->it_flags & (ITF_UNRES0x01|ITF_UNRES_MEMB0x02)) {
476			printf("0x%zx: %s type=%d unresolved 0x%llx",
477			    it->it_off, it_name(it), it->it_type, it->it_ref);
478			if (toresolve)
479				printf(": %d members", toresolve);
480			TAILQ_FOREACH(im, &it->it_members, im_next)for((im) = ((&it->it_members)->tqh_first); (im) != (
(void *)0); (im) = ((im)->im_next.tqe_next)) {
481				if (im->im_refp != NULL((void *)0))
482					continue;
483				printf("\n%zu: %s", im->im_ref, im_name(im));
484			}
485			printf("\n");
486		}
487#endif /* defined(DEBUG) */
488	}
489 
490	/* We'll reuse the tree for the next CU, so empty it. */
491	RB_FOREACH_SAFE(it, ioff_tree, cuot, ref)for ((it) = ioff_tree_RB_MINMAX(cuot, -1); ((it) != ((void *)
0)) && ((ref) = ioff_tree_RB_NEXT(it), 1); (it) = (ref
))
492		RB_REMOVE(ioff_tree, cuot, it)ioff_tree_RB_REMOVE(cuot, it);
493}
494 
495void
496cu_reference(struct dwcu *dcu, struct itype_queue *cutq)
497{
498	struct itype *it;
499 
500	TAILQ_FOREACH(it, cutq, it_next)for((it) = ((cutq)->tqh_first); (it) != ((void *)0); (it) =
 ((it)->it_next.tqe_next)) {
501		if (it->it_flags & (ITF_OBJ0x08|ITF_FUNC0x04))
502			it_reference(it);
503	}
504}
505 
506/*
507 * Merge type representation from a CU with already known types.
508 */
509void
510cu_merge(struct dwcu *dcu, struct itype_queue *cutq)
511{
512	struct itype *it, *nit, *prev, *first;
513	int diff;
514 
515	/* First ``it'' that needs a duplicate check. */
516	first = TAILQ_FIRST(cutq)((cutq)->tqh_first);
517	if (first == NULL((void *)0))
518		return;
519 
520	TAILQ_CONCAT(&itypeq, cutq, it_next)do { if (!(((cutq)->tqh_first) == ((void *)0))) { *(&itypeq
)->tqh_last = (cutq)->tqh_first; (cutq)->tqh_first->
it_next.tqe_prev = (&itypeq)->tqh_last; (&itypeq)->
tqh_last = (cutq)->tqh_last; do { ((cutq))->tqh_first =
 ((void *)0); ((cutq))->tqh_last = &((cutq))->tqh_first
; } while (0); } } while (0);
521 
522	/*
523	 * First pass: merge types
524	 */
525	for (it = first; it != NULL((void *)0); it = nit) {
526		nit = TAILQ_NEXT(it, it_next)((it)->it_next.tqe_next);
527 
528		/* Move functions & variable to their own list. */
529		if (it->it_flags & (ITF_FUNC0x04|ITF_OBJ0x08)) {
530			/*
531			 * FIXME: allow static variables with the same name
532			 * to be of different type.
533			 */
534			if (RB_FIND(isymb_tree, &isymbt, it)isymb_tree_RB_FIND(&isymbt, it) == NULL((void *)0))
535				RB_INSERT(isymb_tree, &isymbt, it)isymb_tree_RB_INSERT(&isymbt, it);
536			continue;
537		}
538 
539		/* Look if we already have this type. */
540		if (it->it_flags & ITF_USED0x40)
541			prev = RB_FIND(itype_tree, &itypet[it->it_type], it)itype_tree_RB_FIND(&itypet[it->it_type], it);
542		else
543			prev = NULL((void *)0);
544 
545		if (prev != NULL((void *)0)) {
546			struct itype *old = it;
547			struct itref *ir;
548			struct imember *im;
549 
550			/* Substitute references */
551			while ((ir = SIMPLEQ_FIRST(&old->it_refs)((&old->it_refs)->sqh_first)) != NULL((void *)0)) {
552				it = ir->ir_itp;
553 
554				SIMPLEQ_REMOVE_HEAD(&old->it_refs, ir_next)do { if (((&old->it_refs)->sqh_first = (&old->
it_refs)->sqh_first->ir_next.sqe_next) == ((void *)0)) (
&old->it_refs)->sqh_last = &(&old->it_refs
)->sqh_first; } while (0);
555				pfree(&ir_pool, ir);
556 
557				if (it->it_refp == old)
558					it->it_refp = prev;
559 
560				TAILQ_FOREACH(im, &it->it_members, im_next)for((im) = ((&it->it_members)->tqh_first); (im) != (
(void *)0); (im) = ((im)->im_next.tqe_next)) {
561					if (im->im_refp == old)
562						im->im_refp = prev;
563				}
564			}
565 
566			/* If we first got a forward reference, complete it. */
567			if ((prev->it_flags & ITF_FORWARD0x10) &&
568			    (old->it_flags & ITF_FORWARD0x10) == 0)
569			    	it_merge(prev, old);
570 
571			old->it_flags &= ~ITF_USED0x40;
572		} else if (it->it_flags & ITF_USED0x40) {
573			RB_INSERT(itype_tree, &itypet[it->it_type], it)itype_tree_RB_INSERT(&itypet[it->it_type], it);
574		}
575	}
576 
577	/*
578	 * Second pass: update indexes
579	 */
580	diff = 0;
581	for (it = first; it != NULL((void *)0); it = nit) {
582		nit = TAILQ_NEXT(it, it_next)((it)->it_next.tqe_next);
583 
584		if (it->it_flags & (ITF_FUNC0x04|ITF_OBJ0x08))
585			continue;
586 
587		/* Adjust indexes */
588		if (it->it_flags & ITF_USED0x40) {
589			it->it_idx -= diff;
590			continue;
591		}
592 
593		/* Remove unused */
594		TAILQ_REMOVE(&itypeq, it, it_next)do { if (((it)->it_next.tqe_next) != ((void *)0)) (it)->
it_next.tqe_next->it_next.tqe_prev = (it)->it_next.tqe_prev
; else (&itypeq)->tqh_last = (it)->it_next.tqe_prev
; *(it)->it_next.tqe_prev = (it)->it_next.tqe_next; ; ;
 } while (0);
595		it_free(it);
596		diff++;
597	}
598 
599	/* Update global index to match removed entries. */
600	it = TAILQ_LAST(&itypeq, itype_queue)(*(((struct itype_queue *)((&itypeq)->tqh_last))->tqh_last
));
601	while (it->it_flags & (ITF_FUNC0x04|ITF_OBJ0x08))
602		it = TAILQ_PREV(it, itype_queue, it_next)(*(((struct itype_queue *)((it)->it_next.tqe_prev))->tqh_last
));
603 
604	tidx = it->it_idx;
605}
606 
607/*
608 * Parse a CU.
609 */
610void
611cu_parse(struct dwcu *dcu, struct itype_queue *cutq, struct ioff_tree *cuot)
612{
613	struct itype *it = NULL((void *)0);
1
'it' initialized to a null pointer value→
614	struct dwdie *die;
615	size_t psz = dcu->dcu_psize;
616	size_t off = dcu->dcu_offset;
617 
618	assert(RB_EMPTY(cuot))((((cuot)->rbh_root == ((void *)0))) ? (void)0 : __assert2
("/usr/src/usr.bin/ctfconv/parse.c", 618, __func__, "RB_EMPTY(cuot)"
));
2
←
Assuming field 'rbh_root' is equal to null→
3
←
'?' condition is true→
619 
620	SIMPLEQ_FOREACH(die, &dcu->dcu_dies, die_next)for((die) = ((&dcu->dcu_dies)->sqh_first); (die) !=
 ((void *)0); (die) = ((die)->die_next.sqe_next)) {
4
←
Assuming 'die' is not equal to null→
5
←
Loop condition is true.  Entering loop body→
621		uint64_t tag = die->die_dab->dab_tag;
622 
623		switch (tag) {
6
←
Control jumps to 'case 13:'  at line 673→
624		case DW_TAG_array_type0x01:
625			it = parse_array(die, dcu->dcu_psize);
626			break;
627		case DW_TAG_enumeration_type0x04:
628			it = parse_enum(die, dcu->dcu_psize);
629			break;
630		case DW_TAG_pointer_type0x0f:
631			it = parse_refers(die, psz, CTF_K_POINTER3);
632			break;
633		case DW_TAG_structure_type0x13:
634			it = parse_struct(die, psz, CTF_K_STRUCT6, off);
635			if (it == NULL((void *)0))
636				continue;
637			break;
638		case DW_TAG_typedef0x16:
639			it = parse_refers(die, psz, CTF_K_TYPEDEF10);
640			break;
641		case DW_TAG_union_type0x17:
642			it = parse_struct(die, psz, CTF_K_UNION7, off);
643			if (it == NULL((void *)0))
644				continue;
645			break;
646		case DW_TAG_base_type0x24:
647			it = parse_base(die, psz);
648			if (it == NULL((void *)0))
649				continue;
650			break;
651		case DW_TAG_const_type0x26:
652			it = parse_refers(die, psz, CTF_K_CONST12);
653			break;
654		case DW_TAG_volatile_type0x35:
655			it = parse_refers(die, psz, CTF_K_VOLATILE11);
656			break;
657		case DW_TAG_restrict_type0x37:
658			it = parse_refers(die, psz, CTF_K_RESTRICT13);
659			break;
660		case DW_TAG_subprogram0x2e:
661			it = parse_function(die, psz);
662			if (it == NULL((void *)0))
663				continue;
664			break;
665		case DW_TAG_subroutine_type0x15:
666			it = parse_funcptr(die, psz);
667			break;
668		/*
669		 * Children are assumed to be right after their parent in
670		 * the list.  The parent parsing function takes care of
671		 * parsing them.
672		 */
673		 case DW_TAG_member0x0d:
674			 assert(it->it_type == CTF_K_STRUCT ||((it->it_type == 6 || it->it_type == 7 || it->it_type
 == 8) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 676, __func__, "it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION || it->it_type == CTF_K_ENUM"
))
7
←
Access to field 'it_type' results in a dereference of a null pointer (loaded from variable 'it')
675			    it->it_type == CTF_K_UNION ||((it->it_type == 6 || it->it_type == 7 || it->it_type
 == 8) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 676, __func__, "it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION || it->it_type == CTF_K_ENUM"
))
676			    it->it_type == CTF_K_ENUM)((it->it_type == 6 || it->it_type == 7 || it->it_type
 == 8) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 676, __func__, "it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION || it->it_type == CTF_K_ENUM"
));
677			continue;
678		 case DW_TAG_subrange_type0x21:
679			assert(it->it_type == CTF_K_ARRAY)((it->it_type == 4) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 679, __func__, "it->it_type == CTF_K_ARRAY"));
680			continue;
681		case DW_TAG_formal_parameter0x05:
682			/*
683			 * If we skipped the second inline definition,
684			 * skip its arguments.
685			 */
686			if (it == NULL((void *)0))
687				continue;
688 
689			/* See comment in subparse_arguments(). */
690			if (it->it_type == CTF_K_STRUCT6 ||
691			    it->it_type == CTF_K_UNION7 ||
692			    it->it_type == CTF_K_ENUM8 ||
693			    it->it_type == CTF_K_TYPEDEF10)
694				continue;
695 
696			if (it->it_flags & ITF_OBJ0x08)
697				continue;
698 
699			assert(it->it_type == CTF_K_FUNCTION)((it->it_type == 5) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 699, __func__, "it->it_type == CTF_K_FUNCTION"));
700			continue;
701		case DW_TAG_variable0x34:
702			it = parse_variable(die, psz);
703			/* Unnamed variables are discarded. */
704			if (it == NULL((void *)0))
705				continue;
706			break;
707#if 1
708		case DW_TAG_lexical_block0x0b:
709		case DW_TAG_inlined_subroutine0x1d:
710			continue;
711#endif
712		case DW_TAG_compile_unit0x11:
713		default:
714			DPRINTF("%s\n", dw_tag2name(tag))do { } while (0);
715			continue;
716		}
717 
718		TAILQ_INSERT_TAIL(cutq, it, it_next)do { (it)->it_next.tqe_next = ((void *)0); (it)->it_next
.tqe_prev = (cutq)->tqh_last; *(cutq)->tqh_last = (it);
 (cutq)->tqh_last = &(it)->it_next.tqe_next; } while
 (0);
719		RB_INSERT(ioff_tree, cuot, it)ioff_tree_RB_INSERT(cuot, it);
720	}
721}
722 
723struct itype *
724parse_base(struct dwdie *die, size_t psz)
725{
726	struct itype *it;
727	struct dwaval *dav;
728	uint16_t encoding, enc = 0, bits = 0;
729	int type;
730 
731	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
732		switch (dav->dav_dat->dat_attr) {
733		case DW_AT_encoding0x3e:
734			enc = dav2val(dav, psz);
735			break;
736		case DW_AT_byte_size0x0b:
737			bits = 8 * dav2val(dav, psz);
738			break;
739		default:
740			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
741			break;
742		}
743	}
744 
745	switch (enc) {
746	case DW_ATE_unsigned0x7:
747	case DW_ATE_address0x1:
748		encoding = 0;
749		type = CTF_K_INTEGER1;
750		break;
751	case DW_ATE_unsigned_char0x8:
752		encoding = CTF_INT_CHAR(1 << 1);
753		type = CTF_K_INTEGER1;
754		break;
755	case DW_ATE_signed0x5:
756		encoding = CTF_INT_SIGNED(1 << 0);
757		type = CTF_K_INTEGER1;
758		break;
759	case DW_ATE_signed_char0x6:
760		encoding = CTF_INT_SIGNED(1 << 0) | CTF_INT_CHAR(1 << 1);
761		type = CTF_K_INTEGER1;
762		break;
763	case DW_ATE_boolean0x2:
764		encoding = CTF_INT_SIGNED(1 << 0) | CTF_INT_BOOL(1 << 2);
765		type = CTF_K_INTEGER1;
766		break;
767	case DW_ATE_float0x4:
768		if (bits < psz)
769			encoding = CTF_FP_SINGLE1;
770		else if (bits == psz)
771			encoding = CTF_FP_DOUBLE2;
772		else
773			encoding = CTF_FP_LDOUBLE6;
774		type = CTF_K_FLOAT2;
775		break;
776	case DW_ATE_complex_float0x3:
777		if (bits < psz)
778			encoding = CTF_FP_CPLX3;
779		else if (bits == psz)
780			encoding = CTF_FP_DCPLX4;
781		else
782			encoding = CTF_FP_LDCPLX5;
783		type = CTF_K_FLOAT2;
784		break;
785	case DW_ATE_imaginary_float0x9:
786		if (bits < psz)
787			encoding = CTF_FP_IMAGRY10;
788		else if (bits == psz)
789			encoding = CTF_FP_DIMAGRY11;
790		else
791			encoding = CTF_FP_LDIMAGRY12;
792		type = CTF_K_FLOAT2;
793		break;
794	default:
795		DPRINTF("unknown encoding: %d\n", enc)do { } while (0);
796		return (NULL((void *)0));
797	}
798 
799	it = it_new(++tidx, die->die_offset, enc2name(enc), bits,
800	    encoding, 0, type, 0);
801 
802	return it;
803}
804 
805struct itype *
806parse_refers(struct dwdie *die, size_t psz, int type)
807{
808	struct itype *it;
809	struct dwaval *dav;
810	const char *name = NULL((void *)0);
811	size_t ref = 0, size = 0;
812 
813	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
814		switch (dav->dav_dat->dat_attr) {
815		case DW_AT_name0x03:
816			name = dav2str(dav);
817			break;
818		case DW_AT_type0x49:
819			ref = dav2val(dav, psz);
820			break;
821		case DW_AT_byte_size0x0b:
822			size = dav2val(dav, psz);
823			assert(size < UINT_MAX)((size < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 823, __func__, "size < UINT_MAX"));
824			break;
825		default:
826			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
827			break;
828		}
829	}
830 
831	it = it_new(++tidx, die->die_offset, name, size, 0, ref, type,
832	    ITF_UNRES0x01);
833 
834	if (it->it_ref == 0 && (it->it_size == sizeof(void *) ||
835	    type == CTF_K_CONST12 || type == CTF_K_VOLATILE11 ||
836	    type == CTF_K_POINTER3)) {
837		/* Work around GCC/clang not emiting a type for void */
838		it->it_flags &= ~ITF_UNRES0x01;
839		it->it_ref = VOID_OFFSET1;
840		it->it_refp = void_it;
841	}
842 
843	return it;
844}
845 
846struct itype *
847parse_array(struct dwdie *die, size_t psz)
848{
849	struct itype *it;
850	struct dwaval *dav;
851	const char *name = NULL((void *)0);
852	size_t ref = 0;
853 
854	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
855		switch (dav->dav_dat->dat_attr) {
856		case DW_AT_name0x03:
857			name = dav2str(dav);
858			break;
859		case DW_AT_type0x49:
860			ref = dav2val(dav, psz);
861			break;
862		default:
863			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
864			break;
865		}
866	}
867 
868	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_ARRAY4,
869	    ITF_UNRES0x01);
870 
871	subparse_subrange(die, psz, it);
872 
873	return it;
874}
875 
876struct itype *
877parse_enum(struct dwdie *die, size_t psz)
878{
879	struct itype *it;
880	struct dwaval *dav;
881	const char *name = NULL((void *)0);
882	size_t size = 0;
883 
884	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
885		switch (dav->dav_dat->dat_attr) {
886		case DW_AT_byte_size0x0b:
887			size = dav2val(dav, psz);
888			assert(size < UINT_MAX)((size < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 888, __func__, "size < UINT_MAX"));
889			break;
890		case DW_AT_name0x03:
891			name = dav2str(dav);
892			break;
893		default:
894			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
895			break;
896		}
897	}
898 
899	it = it_new(++tidx, die->die_offset, name, size, 0, 0, CTF_K_ENUM8, 0);
900 
901	subparse_enumerator(die, psz, it);
902 
903	return it;
904}
905 
906void
907subparse_subrange(struct dwdie *die, size_t psz, struct itype *it)
908{
909	struct dwaval *dav;
910 
911	assert(it->it_type == CTF_K_ARRAY)((it->it_type == 4) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 911, __func__, "it->it_type == CTF_K_ARRAY"));
912 
913	if (die->die_dab->dab_children == DW_CHILDREN_no0x00)
914		return;
915 
916	/*
917	 * This loop assumes that the children of a DIE are just
918	 * after it on the list.
919	 */
920	while ((die = SIMPLEQ_NEXT(die, die_next)((die)->die_next.sqe_next)) != NULL((void *)0)) {
921		uint64_t tag = die->die_dab->dab_tag;
922		size_t nelems = 0;
923 
924		if (tag != DW_TAG_subrange_type0x21)
925			break;
926 
927		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
928			switch (dav->dav_dat->dat_attr) {
929			case DW_AT_count0x37:
930				nelems = dav2val(dav, psz);
931				break;
932			case DW_AT_upper_bound0x2f:
933				nelems = dav2val(dav, psz) + 1;
934				break;
935			default:
936				DPRINTF("%s\n",do { } while (0)
937				    dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
938				break;
939			}
940		}
941 
942		assert(nelems < UINT_MAX)((nelems < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 942, __func__, "nelems < UINT_MAX"));
943		it->it_nelems = nelems;
944	}
945}
946 
947void
948subparse_enumerator(struct dwdie *die, size_t psz, struct itype *it)
949{
950	struct imember *im;
951	struct dwaval *dav;
952 
953	assert(it->it_type == CTF_K_ENUM)((it->it_type == 8) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 953, __func__, "it->it_type == CTF_K_ENUM"));
954 
955	if (die->die_dab->dab_children == DW_CHILDREN_no0x00)
956		return;
957 
958	/*
959	 * This loop assumes that the children of a DIE are just
960	 * after it on the list.
961	 */
962	while ((die = SIMPLEQ_NEXT(die, die_next)((die)->die_next.sqe_next)) != NULL((void *)0)) {
963		uint64_t tag = die->die_dab->dab_tag;
964		size_t val = 0;
965		const char *name = NULL((void *)0);
966 
967		if (tag != DW_TAG_enumerator0x28)
968			break;
969 
970		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
971			switch (dav->dav_dat->dat_attr) {
972			case DW_AT_name0x03:
973				name = dav2str(dav);
974				break;
975			case DW_AT_const_value0x1c:
976				val = dav2val(dav, psz);
977				break;
978			default:
979				DPRINTF("%s\n",do { } while (0)
980				    dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
981				break;
982			}
983		}
984 
985		if (name == NULL((void *)0)) {
986			warnx("%s with anon member", it_name(it));
987			continue;
988		}
989 
990		im = im_new(name, val, 0);
991		assert(it->it_nelems < UINT_MAX)((it->it_nelems < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 991, __func__, "it->it_nelems < UINT_MAX"));
992		it->it_nelems++;
993		TAILQ_INSERT_TAIL(&it->it_members, im, im_next)do { (im)->im_next.tqe_next = ((void *)0); (im)->im_next
.tqe_prev = (&it->it_members)->tqh_last; *(&it->
it_members)->tqh_last = (im); (&it->it_members)->
tqh_last = &(im)->im_next.tqe_next; } while (0);
994	}
995}
996 
997struct itype *
998parse_struct(struct dwdie *die, size_t psz, int type, size_t off)
999{
1000	struct itype *it = NULL((void *)0);
1001	struct dwaval *dav;
1002	const char *name = NULL((void *)0);
1003	unsigned int flags = 0;
1004	size_t size = 0;
1005	int forward = 0;
1006 
1007	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
1008		switch (dav->dav_dat->dat_attr) {
1009		case DW_AT_declaration0x3c:
1010			forward = dav2val(dav, psz);
1011			break;
1012		case DW_AT_byte_size0x0b:
1013			size = dav2val(dav, psz);
1014			assert(size < UINT_MAX)((size < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 1014, __func__, "size < UINT_MAX"));
1015			break;
1016		case DW_AT_name0x03:
1017			name = dav2str(dav);
1018			break;
1019		default:
1020			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
1021			break;
1022		}
1023	}
1024 
1025 
1026	if (forward)
1027		flags = ITF_FORWARD0x10;
1028	it = it_new(++tidx, die->die_offset, name, size, 0, 0, type, flags);
1029	subparse_member(die, psz, it, off);
1030 
1031	return it;
1032}
1033 
1034void
1035subparse_member(struct dwdie *die, size_t psz, struct itype *it, size_t offset)
1036{
1037	struct imember *im;
1038	struct dwaval *dav;
1039	const char *name;
1040	size_t off = 0, ref = 0, bits = 0;
1041	uint8_t lvl = die->die_lvl;
1042 
1043	assert(it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION)((it->it_type == 6 || it->it_type == 7) ? (void)0 : __assert2
("/usr/src/usr.bin/ctfconv/parse.c", 1043, __func__, "it->it_type == CTF_K_STRUCT || it->it_type == CTF_K_UNION"
));
1044 
1045	if (die->die_dab->dab_children == DW_CHILDREN_no0x00)
1046		return;
1047 
1048	/*
1049	 * This loop assumes that the children of a DIE are just
1050	 * after it on the list.
1051	 */
1052	while ((die = SIMPLEQ_NEXT(die, die_next)((die)->die_next.sqe_next)) != NULL((void *)0)) {
1053		int64_t tag = die->die_dab->dab_tag;
1054 
1055		name = NULL((void *)0);
1056		if (die->die_lvl <= lvl)
1057			break;
1058 
1059		/* Skip members of members */
1060		if (die->die_lvl > lvl + 1)
1061			continue;
1062		/*
1063		 * Nested declaration.
1064		 *
1065		 * This matches the case where a ``struct'', ``union'',
1066		 * ``enum'' or ``typedef'' is first declared "inside" a
1067		 * union or struct declaration.
1068		 */
1069		if (tag == DW_TAG_structure_type0x13 || tag == DW_TAG_union_type0x17 ||
1070		    tag == DW_TAG_enumeration_type0x04 || tag == DW_TAG_typedef0x16)
1071			continue;
1072 
1073		it->it_flags |= ITF_UNRES_MEMB0x02;
1074 
1075		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
1076			switch (dav->dav_dat->dat_attr) {
1077			case DW_AT_name0x03:
1078				name = dav2str(dav);
1079				break;
1080			case DW_AT_type0x49:
1081				ref = dav2val(dav, psz);
1082				break;
1083			case DW_AT_data_member_location0x38:
1084				off = 8 * dav2val(dav, psz);
1085				break;
1086			case DW_AT_bit_size0x0d:
1087				bits = dav2val(dav, psz);
1088				assert(bits < USHRT_MAX)((bits < 0xffff) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 1088, __func__, "bits < USHRT_MAX"));
1089				break;
1090			default:
1091				DPRINTF("%s\n",do { } while (0)
1092				    dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
1093				break;
1094			}
1095		}
1096 
1097		/*
1098		 * When a structure is declared inside an union, we
1099		 * have to generate a reference to make the resolver
1100		 * happy.
1101		 */
1102		if ((ref == 0) && (tag == DW_TAG_structure_type0x13))
1103			ref = die->die_offset - offset;
1104 
1105		im = im_new(name, ref, off);
1106		assert(it->it_nelems < UINT_MAX)((it->it_nelems < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 1106, __func__, "it->it_nelems < UINT_MAX"));
1107		it->it_nelems++;
1108		TAILQ_INSERT_TAIL(&it->it_members, im, im_next)do { (im)->im_next.tqe_next = ((void *)0); (im)->im_next
.tqe_prev = (&it->it_members)->tqh_last; *(&it->
it_members)->tqh_last = (im); (&it->it_members)->
tqh_last = &(im)->im_next.tqe_next; } while (0);
1109	}
1110}
1111 
1112 
1113void
1114subparse_arguments(struct dwdie *die, size_t psz, struct itype *it)
1115{
1116	struct imember *im;
1117	struct dwaval *dav;
1118	size_t ref = 0;
1119 
1120	assert(it->it_type == CTF_K_FUNCTION)((it->it_type == 5) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 1120, __func__, "it->it_type == CTF_K_FUNCTION"));
1121 
1122	if (die->die_dab->dab_children == DW_CHILDREN_no0x00)
1123		return;
1124 
1125	/*
1126	 * This loop assumes that the children of a DIE are after it
1127	 * on the list.
1128	 */
1129	while ((die = SIMPLEQ_NEXT(die, die_next)((die)->die_next.sqe_next)) != NULL((void *)0)) {
1130		uint64_t tag = die->die_dab->dab_tag;
1131 
1132		if (tag == DW_TAG_unspecified_parameters0x18) {
1133			/* TODO */
1134			continue;
1135		}
1136 
1137		/*
1138		 * Nested declaration.
1139		 *
1140		 * This matches the case where a ``struct'', ``union'',
1141		 * ``enum'', ``typedef'' or ``static'' variable is first
1142		 * declared inside a function declaration.
1143		 */
1144		switch (tag) {
1145		case DW_TAG_structure_type0x13:
1146		case DW_TAG_union_type0x17:
1147		case DW_TAG_enumeration_type0x04:
1148		case DW_TAG_typedef0x16:
1149		case DW_TAG_variable0x34:
1150			continue;
1151		default:
1152			break;
1153		}
1154 
1155		if (tag != DW_TAG_formal_parameter0x05)
1156			break;
1157 
1158		it->it_flags |= ITF_UNRES_MEMB0x02;
1159 
1160		SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
1161			switch (dav->dav_dat->dat_attr) {
1162			case DW_AT_type0x49:
1163				ref = dav2val(dav, psz);
1164				break;
1165			default:
1166				DPRINTF("%s\n",do { } while (0)
1167				    dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
1168				break;
1169			}
1170		}
1171 
1172		im = im_new(NULL((void *)0), ref, 0);
1173		assert(it->it_nelems < UINT_MAX)((it->it_nelems < 0xffffffffU) ? (void)0 : __assert2("/usr/src/usr.bin/ctfconv/parse.c"
, 1173, __func__, "it->it_nelems < UINT_MAX"));
1174		it->it_nelems++;
1175		TAILQ_INSERT_TAIL(&it->it_members, im, im_next)do { (im)->im_next.tqe_next = ((void *)0); (im)->im_next
.tqe_prev = (&it->it_members)->tqh_last; *(&it->
it_members)->tqh_last = (im); (&it->it_members)->
tqh_last = &(im)->im_next.tqe_next; } while (0);
1176	}
1177}
1178 
1179struct itype *
1180parse_function(struct dwdie *die, size_t psz)
1181{
1182	struct itype *it;
1183	struct dwaval *dav;
1184	const char *name = NULL((void *)0);
1185	size_t ref = 0;
1186 
1187	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
1188		switch (dav->dav_dat->dat_attr) {
1189		case DW_AT_name0x03:
1190			name = dav2str(dav);
1191			break;
1192		case DW_AT_type0x49:
1193			ref = dav2val(dav, psz);
1194			break;
1195		case DW_AT_abstract_origin0x31:
1196			/*
1197			 * Skip second empty definition for inline
1198			 * functions.
1199			 */
1200			return NULL((void *)0);
1201		default:
1202			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
1203			break;
1204		}
1205	}
1206 
1207	/*
1208	 * Work around for clang 4.0 generating DW_TAG_subprogram without
1209	 * any attribute.
1210	 */
1211	if (name == NULL((void *)0))
1212		return NULL((void *)0);
1213 
1214	it = it_new(++fidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION5,
1215	    ITF_UNRES0x01|ITF_FUNC0x04);
1216 
1217	subparse_arguments(die, psz, it);
1218 
1219	if (it->it_ref == 0) {
1220		/* Work around GCC not emiting a type for void */
1221		it->it_flags &= ~ITF_UNRES0x01;
1222		it->it_ref = VOID_OFFSET1;
1223		it->it_refp = void_it;
1224	}
1225 
1226	return it;
1227}
1228 
1229struct itype *
1230parse_funcptr(struct dwdie *die, size_t psz)
1231{
1232	struct itype *it;
1233	struct dwaval *dav;
1234	const char *name = NULL((void *)0);
1235	size_t ref = 0;
1236 
1237	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
1238		switch (dav->dav_dat->dat_attr) {
1239		case DW_AT_name0x03:
1240			name = dav2str(dav);
1241			break;
1242		case DW_AT_type0x49:
1243			ref = dav2val(dav, psz);
1244			break;
1245		default:
1246			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
1247			break;
1248		}
1249	}
1250 
1251	it = it_new(++tidx, die->die_offset, name, 0, 0, ref, CTF_K_FUNCTION5,
1252	    ITF_UNRES0x01);
1253 
1254	subparse_arguments(die, psz, it);
1255 
1256	if (it->it_ref == 0) {
1257		/* Work around GCC not emiting a type for void */
1258		it->it_flags &= ~ITF_UNRES0x01;
1259		it->it_ref = VOID_OFFSET1;
1260		it->it_refp = void_it;
1261	}
1262 
1263	return it;
1264}
1265 
1266struct itype *
1267parse_variable(struct dwdie *die, size_t psz)
1268{
1269	struct itype *it = NULL((void *)0);
1270	struct dwaval *dav;
1271	const char *name = NULL((void *)0);
1272	size_t ref = 0;
1273	int forward = 0, global = 0;
1274 
1275	SIMPLEQ_FOREACH(dav, &die->die_avals, dav_next)for((dav) = ((&die->die_avals)->sqh_first); (dav) !=
 ((void *)0); (dav) = ((dav)->dav_next.sqe_next)) {
1276		switch (dav->dav_dat->dat_attr) {
1277		case DW_AT_declaration0x3c:
1278			forward = dav2val(dav, psz);
1279			break;
1280		case DW_AT_name0x03:
1281			name = dav2str(dav);
1282			break;
1283		case DW_AT_type0x49:
1284			ref = dav2val(dav, psz);
1285			break;
1286		case DW_AT_location0x02:
1287			switch (dav->dav_dat->dat_form) {
1288			case DW_FORM_block0x09:
1289			case DW_FORM_block10x0a:
1290			case DW_FORM_block20x03:
1291			case DW_FORM_block40x04:
1292				global = 1;
1293				break;
1294			default:
1295				break;
1296			}
1297			break;
1298		default:
1299			DPRINTF("%s\n", dw_at2name(dav->dav_dat->dat_attr))do { } while (0);
1300			break;
1301		}
1302	}
1303 
1304 
1305	if (global && !forward && name != NULL((void *)0)) {
1306		it = it_new(++oidx, die->die_offset, name, 0, 0, ref, 0,
1307		    ITF_UNRES0x01|ITF_OBJ0x08);
1308	}
1309 
1310	return it;
1311}
1312 
1313size_t
1314dav2val(struct dwaval *dav, size_t psz)
1315{
1316	uint64_t val = (uint64_t)-1;
1317 
1318	switch (dav->dav_dat->dat_form) {
1319	case DW_FORM_addr0x01:
1320	case DW_FORM_ref_addr0x10:
1321		if (psz == sizeof(uint32_t))
1322			val = dav->dav_u32AV._V._T._u32;
1323		else
1324			val = dav->dav_u64AV._V._T._u64;
1325		break;
1326	case DW_FORM_block10x0a:
1327	case DW_FORM_block20x03:
1328	case DW_FORM_block40x04:
1329	case DW_FORM_block0x09:
1330		dw_loc_parse(&dav->dav_bufAV._buf, NULL((void *)0), &val, NULL((void *)0));
1331		break;
1332	case DW_FORM_flag0x0c:
1333	case DW_FORM_data10x0b:
1334	case DW_FORM_ref10x11:
1335		val = dav->dav_u8AV._V._T._u8;
1336		break;
1337	case DW_FORM_data20x05:
1338	case DW_FORM_ref20x12:
1339		val = dav->dav_u16AV._V._T._u16;
1340		break;
1341	case DW_FORM_data40x06:
1342	case DW_FORM_ref40x13:
1343		val = dav->dav_u32AV._V._T._u32;
1344		break;
1345	case DW_FORM_sdata0x0d:
1346	case DW_FORM_data80x07:
1347	case DW_FORM_ref80x14:
1348		val = dav->dav_u64AV._V._T._u64;
1349		break;
1350	case DW_FORM_strp0x0e:
1351		val = dav->dav_u32AV._V._T._u32;
1352		break;
1353	case DW_FORM_flag_present0x19:
1354		val = 1;
1355		break;
1356	default:
1357		break;
1358	}
1359 
1360	return val;
1361}
1362 
1363const char *
1364dav2str(struct dwaval *dav)
1365{
1366	const char *str = NULL((void *)0);
1367	extern const char *dstrbuf;
1368	extern size_t dstrlen;
1369 
1370	switch (dav->dav_dat->dat_form) {
1371	case DW_FORM_string0x08:
1372		str = dav->dav_strAV._V._str;
1373		break;
1374	case DW_FORM_strp0x0e:
1375		if (dav->dav_u32AV._V._T._u32 >= dstrlen)
1376			str = NULL((void *)0);
1377		else
1378			str = dstrbuf + dav->dav_u32AV._V._T._u32;
1379		break;
1380	default:
1381		break;
1382	}
1383 
1384	return str;
1385}
1386 
1387const char *
1388enc2name(unsigned short enc)
1389{
1390	static const char *enc_name[] = { "address", "boolean", "complex float",
1391	    "float", "signed", "char", "unsigned", "unsigned char",
1392	    "imaginary float", "packed decimal", "numeric string", "edited",
1393	    "signed fixed", "unsigned fixed", "decimal float" };
1394 
1395	if (enc > 0 && enc <= nitems(enc_name)(sizeof((enc_name)) / sizeof((enc_name)[0])))
1396		return enc_name[enc - 1];
1397 
1398	return "invalid";
1399}