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