1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Mike Olson. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)bt_utils.c 5.1 (Berkeley) 01/23/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <db.h> 17 #include "btree.h" 18 19 /* 20 * _BT_BUILDRET -- Build return key/data pair as a result of search or scan. 21 * 22 * This routine manages the statically allocated buffers in which we 23 * return data to the user. 24 * 25 * Parameters: 26 * t -- btree from which to return datum 27 * d -- DATUM to be returned to the user. 28 * data -- data argument supplied by user for return 29 * key -- key argument supplied by user for return 30 * 31 * Returns: 32 * RET_SUCCESS, RET_ERROR. 33 * 34 * Side Effects: 35 * May free and reallocate static buffers, if the data 36 * we want to return is bigger than the space we have to 37 * do so. 38 */ 39 40 int 41 _bt_buildret(t, d, data, key) 42 BTREE_P t; 43 DATUM *d; 44 DBT *data; 45 DBT *key; 46 { 47 static int _data_s = 0; 48 static int _key_s = 0; 49 static char *_data = (char *) NULL; 50 static char *_key = (char *) NULL; 51 pgno_t chain; 52 53 if (d->d_flags & D_BIGKEY) { 54 if (_key != (char *) NULL) 55 (void) free(_key); 56 (void) bcopy((char *) &(d->d_bytes[0]), 57 (char *) &chain, 58 sizeof(chain)); 59 if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR) 60 return (RET_ERROR); 61 key->data = _key; 62 key->size = _key_s; 63 } else { 64 /* need more space for key? */ 65 if (d->d_ksize > _key_s) { 66 if (_key != (char *) NULL) 67 (void) free (_key); 68 if ((_key = (char *) malloc((unsigned) d->d_ksize)) 69 == (char *) NULL) 70 return (RET_ERROR); 71 _key_s = d->d_ksize; 72 } 73 74 key->data = _key; 75 if ((key->size = d->d_ksize) > 0) 76 (void) bcopy(&(d->d_bytes[0]), 77 _key, 78 (int) d->d_ksize); 79 } 80 81 if (d->d_flags & D_BIGDATA) { 82 if (_data != (char *) NULL) 83 (void) free(_data); 84 (void) bcopy(&(d->d_bytes[d->d_ksize]), 85 (char *) &chain, 86 sizeof(chain)); 87 if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR) 88 return (RET_ERROR); 89 data->data = _data; 90 data->size = _data_s; 91 } else { 92 /* need more space for data? */ 93 if (d->d_dsize > _data_s) { 94 if (_data != (char *) NULL) 95 (void) free (_data); 96 if ((_data = (char *) malloc((unsigned) d->d_dsize)) 97 == (char *) NULL) 98 return (RET_ERROR); 99 _data_s = d->d_dsize; 100 } 101 102 data->data = _data; 103 104 if ((data->size = d->d_dsize) > 0) 105 (void) bcopy(&(d->d_bytes[d->d_ksize]), 106 _data, 107 (size_t) (d->d_dsize)); 108 } 109 110 return (RET_SUCCESS); 111 } 112 113 /* 114 * _BT_CMP -- Compare a key to a given item on the current page. 115 * 116 * This routine is a wrapper for the user's comparison function. 117 * 118 * Parameters: 119 * t -- tree in which to do comparison 120 * p -- pointer to one argument for the comparison function 121 * n -- index of item to supply second arg to comparison function 122 * 123 * Returns: 124 * < 0 if p is < item at n 125 * = 0 if p is = item at n 126 * > 0 if p is > item at n 127 */ 128 129 int 130 _bt_cmp(t, p, n) 131 BTREE_P t; 132 char *p; 133 index_t n; 134 { 135 BTHEADER *h; 136 IDATUM *id; 137 DATUM *d; 138 char *arg; 139 int ignore; 140 int free_arg; 141 pgno_t chain; 142 int r; 143 144 h = t->bt_curpage; 145 146 /* 147 * The left-most key at any level of the tree on internal pages 148 * is guaranteed (artificially, by the code here) to be less than 149 * any user key. This saves us from having to update the leftmost 150 * key when the user inserts a new key in the tree smaller than 151 * anything we've seen yet. 152 */ 153 154 if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0) 155 return (1); 156 157 if (h->h_flags & F_LEAF) { 158 d = (DATUM *) GETDATUM(h,n); 159 if (d->d_flags & D_BIGKEY) { 160 free_arg = TRUE; 161 bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain)); 162 if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR) 163 return (RET_ERROR); 164 } else { 165 free_arg = FALSE; 166 arg = &(d->d_bytes[0]); 167 } 168 } else { 169 id = (IDATUM *) GETDATUM(h,n); 170 if (id->i_flags & D_BIGKEY) { 171 free_arg = TRUE; 172 bcopy(&(id->i_bytes[0]), 173 (char *) &chain, 174 sizeof(chain)); 175 if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR) 176 return (RET_ERROR); 177 } else { 178 free_arg = FALSE; 179 arg = &(id->i_bytes[0]); 180 } 181 } 182 r = (*(t->bt_compare))(p, arg); 183 184 if (free_arg) 185 (void) free(arg); 186 187 return (r); 188 } 189 190 /* 191 * _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack. 192 * 193 * When we descend the tree, we keep track of parent pages in order 194 * to handle splits on insertions. 195 * 196 * Parameters: 197 * t -- tree for which to push parent 198 * pgno -- page number to push (_bt_push only) 199 * 200 * Returns: 201 * RET_SUCCESS, RET_ERROR. 202 */ 203 204 int 205 _bt_push(t, pgno) 206 BTREE_P t; 207 pgno_t pgno; 208 { 209 BTSTACK *new; 210 211 if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK))) 212 == (BTSTACK *) NULL) 213 return (RET_ERROR); 214 new->bts_pgno = pgno; 215 new->bts_next = t->bt_stack; 216 t->bt_stack = new; 217 218 return (RET_SUCCESS); 219 } 220 221 pgno_t 222 _bt_pop(t) 223 BTREE_P t; 224 { 225 BTSTACK *s; 226 pgno_t p = P_NONE; 227 228 if ((s = t->bt_stack) != (BTSTACK *) NULL) { 229 p = s->bts_pgno; 230 t->bt_stack = s->bts_next; 231 (void) free ((char *) s); 232 } 233 return (p); 234 } 235 236 #ifdef DEBUG 237 void 238 _btdump(tree) 239 BTREE tree; 240 { 241 BTREE_P t = (BTREE_P) tree; 242 DATUM *d; 243 IDATUM *id; 244 BTHEADER *h; 245 pgno_t npages; 246 pgno_t i; 247 index_t cur, top; 248 249 npages = t->bt_npages; 250 (void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx", 251 t->bt_fname, t->bt_s.bt_d.d_fd, 252 t->bt_psize, t->bt_curpage); 253 (void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare); 254 if (t->bt_flags & BTF_SEQINIT) 255 (void) printf("BTF_SEQINIT"); 256 (void) printf(")\n"); 257 258 for (i = P_ROOT; i <= npages; i++) { 259 if (_bt_getpage(t, i) == RET_ERROR) 260 _punt(); 261 h = t->bt_curpage; 262 top = NEXTINDEX(h); 263 (void) printf(" page %d:\n", i); 264 (void) printf("\tpgno %d prev %d next %d\n", 265 h->h_pgno, h->h_prevpg, h->h_nextpg); 266 (void) printf("\tlower %d upper %d nextind %d flags (", 267 h->h_lower, h->h_upper, top); 268 if (h->h_flags & F_LEAF) 269 (void) printf("F_LEAF"); 270 else 271 (void) printf("<internal>"); 272 if (h->h_flags & F_DIRTY) 273 (void) printf("|F_DIRTY"); 274 if (h->h_flags & F_PRESERVE) 275 (void) printf("|F_PRESERVE"); 276 if (h->h_flags & F_CONT) { 277 (void) printf("|F_CONT)"); 278 if (h->h_prevpg == P_NONE) { 279 size_t longsz; 280 (void) bcopy((char *) &(h->h_linp[0]), 281 (char *) &longsz, 282 sizeof(longsz)); 283 printf("\n\t\t(chain start, data length %ld)", 284 longsz); 285 } 286 printf("\n"); 287 continue; 288 } 289 (void) printf(")\n"); 290 for (cur = 0; cur < top; cur++) { 291 (void) printf("\t [%d] off %d ", cur, h->h_linp[cur]); 292 if (h->h_flags & F_LEAF) { 293 d = (DATUM *) GETDATUM(h,cur); 294 (void) printf("ksize %d", d->d_ksize); 295 if (d->d_flags & D_BIGKEY) 296 (void) printf(" (indirect)"); 297 (void) printf("; dsize %d", d->d_dsize); 298 if (d->d_flags & D_BIGDATA) 299 (void) printf(" (indirect)"); 300 } else { 301 id = (IDATUM *) GETDATUM(h,cur); 302 (void) printf("size %d pgno %d", 303 id->i_size, id->i_pgno); 304 if (id->i_flags & D_BIGKEY) 305 (void) printf(" (indirect)"); 306 } 307 (void) printf("\n"); 308 } 309 (void) printf("\n"); 310 } 311 } 312 #endif /* DEBUG */ 313 314 #ifdef DEBUG 315 _punt() 316 { 317 int pid; 318 319 pid = getpid(); 320 (void) kill(pid, SIGILL); 321 } 322 #endif /* DEBUG */ 323