1/*
2 * Copyright 1997-1998, 2001 John-Mark Gurney.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 */
14
15#include <limits.h>
16#include <stdlib.h>
17#include <string.h>
18#include <strings.h>
19
20#include "bt_output.h"
21#include "bt_iterator.h"
22#include "stream.h"
23
24#define PRINT_EVICTED_KEYS
25
26#define DEBUG_BT_TYPE(fp, btr) \
27 fprintf(fp, "btr: %p NBT: %d NONE: %d " \
28 "LL: %d YL: %d " \
29 "BIG: %d ksize: %d\n", \
30 btr, NBT(btr), NONE_BT(btr), \
31 LL(btr), YL(btr), \
32 BIG_BT(btr), btr->s.ksize);
33
34static int treeheight(bt *btr)
35{
36 bt_n *x = btr->root;
37 if (!x) {
38 return 0;
39 }
40
41 int ret = 0;
42 while (x && !x->leaf) {
43 x = NODES(btr, x)[0];
44 ret++;
45 }
46
47 return ++ret;
48}
49
50void bt_dump_info(FILE *fp, bt *btr)
51{
52 fprintf(fp, "BT: %p t: %d nbits: %d nbyte: %d kbyte: %d "
53 "ksize: %d koff: %d noff: %d numkeys: %d numnodes: %d "
54 "height: %d btr: %p btype: %d ktype: %d bflag: %d "
55 "num: %d root: %p dirty_left: %u msize: %ld dsize: %ld "
56 "dirty: %u\n",
57 btr, btr->t, btr->nbits, btr->nbyte, btr->kbyte, btr->s.ksize,
58 btr->keyofst, btr->nodeofst, btr->numkeys, btr->numnodes,
59 treeheight(btr), (void *)btr, btr->s.btype, btr->s.ktype,
60 btr->s.bflag, btr->s.num, btr->root,
61 btr->dirty_left, btr->msize, btr->dsize, btr->dirty);
62 DEBUG_BT_TYPE(fp, btr);
63}
64
65static void bt_dump_array(FILE *fp, ai_arr *arr, bool verbose)
66{
67 fprintf(fp, "Array: capacity: %d used: %d\n", arr->capacity, arr->used);
68 if (verbose) {
69 for (int i = 0; i < arr->used; i++) {
70 const int len = 20;
71 char digest_str[2 + (len * 2) + 1];
72 digest_str[0] = '\0';
73 generate_packed_hex_string((uint8_t *) &arr->data[i * CF_DIGEST_KEY_SZ], len, digest_str);
74 fprintf(fp, "\tData[%d]: %s\n", i, digest_str);
75 }
76 }
77}
78
79static void bt_dump_nbtr(FILE *fp, ai_nbtr *nbtr, bool is_index, bool verbose)
80{
81 if (nbtr->is_btree) {
82 bt_dumptree(fp, nbtr->u.nbtr, is_index, verbose);
83 } else {
84 bt_dump_array(fp, nbtr->u.arr, verbose);
85 }
86}
87
88static void dump_tree_node(FILE *fp, bt *btr, bt_n *x, int depth, bool is_index, int slot, bool verbose)
89{
90 if (!x->leaf) {
91 fprintf(fp, "%d: NODE: ", depth);
92 if (x->dirty > 0) {
93 GET_BTN_SIZE(x->leaf);
94 void *ds = GET_DS(x, nsize);
95 fprintf(fp, "slot: %d n: %d scion: %d -> (%p) ds: %p dirty: %u\n",
96 slot, x->n, x->scion, (void *)x, ds, x->dirty);
97 } else {
98 fprintf(fp, "slot: %d n: %d scion: %d -> (%p)\n",
99 slot, x->n, x->scion, (void *) x);
100 }
101 } else if (verbose) {
102 if (x->dirty > 0) {
103 GET_BTN_SIZE(x->leaf) void *ds = GET_DS(x, nsize);
104 fprintf(fp, "%d: LEAF: slot: %d n: %d scion: %d -> (%p) ds: %p dirty: %u\n",
105 depth, slot, x->n, x->scion, (void *)x, ds, x->dirty);
106 } else {
107 fprintf(fp, "%d: LEAF: slot: %d n: %d scion: %d -> (%p)\n",
108 depth, slot, x->n, x->scion, (void *)x);
109 }
110 if (btr->dirty_left) {
111 if (findminnode(btr, btr->root) == x) {
112#ifdef PRINT_EVICTED_KEYS
113 for (uint32 i = 1; i <= btr->dirty_left; i++) {
114 fprintf(fp, "\t\t\t\t\tEVICTED KEY:\t\t\t%u\n", i);
115 }
116#else
117 fprintf(fp, "\t\tDL: %u\n", btr->dirty_left);
118#endif
119 }
120 }
121 }
122
123 for (int i = 0; i < x->n; i++) {
124 void *be = KEYS(btr, x, i);
125 ai_obj akey;
126 convertStream2Key(be, &akey, btr);
127 void *rrow = parseStream(be, btr);
128 if (is_index) {
129 fprintf(fp, "\tINDEX-KEY: ");
130 dump_ai_obj_as_digest(fp, &akey);
131 if (!rrow) { fprintf(fp, "\t\tTOTAL EVICTION\n"); }
132 else { bt_dump_nbtr(fp, (ai_nbtr *) rrow, 0, verbose); }
133 } else if (verbose) {
134 bool key_printed = 0;
135 if (LL(btr)) {
136 fprintf(fp, "\t\tLL: PTR: %p\t", rrow);
137 } else {
138 bool gost = IS_GHOST(btr, rrow);
139 if (gost) { fprintf(fp, "\t\tROW [%d]: %p \tGHOST-", i, rrow); }
140 else { fprintf(fp, "\t\tROW [%d]: %p\t", i, rrow); }
141 }
142 if (!key_printed) {
143 fprintf(fp, "KEY: ");
144 dump_ai_obj_as_digest(fp, &akey);
145 }
146 if (x->dirty > 0) {
147#ifdef PRINT_EVICTED_KEYS
148 uint32 dr = getDR(btr, x, i);
149 if (dr) { fprintf(fp, "\t\t\t\tDR: %d\n", dr); }
150 else {
151 ulong beg = akey.l;
152 for (ulong j = 1; j <= (ulong)dr; j++) {
153 fprintf(fp, "\t\t\t\t\tEVICTED KEY:\t\t\t%lu\n", beg + j);
154 }
155 }
156#else
157 fprintf(fp, "\t\t\t\tDR: %d\n", getDR(btr, x, i));
158#endif
159 }
160 }
161 }
162 if (!x->leaf && verbose) {
163 depth++;
164 for (int i = 0; i <= x->n; i++) {
165 fprintf(fp, "\t\tNPTR[%d]: %p\n", i, NODES(btr, x)[i]);
166 dump_tree_node(fp, btr, NODES(btr, x)[i], depth, is_index, i, verbose);
167 }
168 }
169}
170
171void bt_dumptree(FILE *fp, bt *btr, bool is_index, bool verbose)
172{
173 bt_dump_info(fp, btr);
174 if (btr->root && btr->numkeys > 0) {
175 dump_tree_node(fp, btr, btr->root, 0, is_index, 0, verbose);
176 }
177 fprintf(fp, "\n");
178}
179