1 #pragma ident "%Z%%M% %I% %E% SMI" 2 3 /*- 4 * Copyright (c) 1990, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Margo Seltzer. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 #if defined(LIBC_SCCS) && !defined(lint) 40 static char sccsid[] = "@(#)hash_bigkey.c 8.5 (Berkeley) 11/2/95"; 41 #endif /* LIBC_SCCS and not lint */ 42 43 /* 44 * PACKAGE: hash 45 * DESCRIPTION: 46 * Big key/data handling for the hashing package. 47 * 48 * ROUTINES: 49 * External 50 * __big_keydata 51 * __big_split 52 * __big_insert 53 * __big_return 54 * __big_delete 55 * __find_last_page 56 * Internal 57 * collect_key 58 * collect_data 59 */ 60 #include <sys/types.h> 61 62 #include <stdlib.h> 63 #include <string.h> 64 65 #ifdef DEBUG 66 #include <assert.h> 67 #endif 68 69 #include "db-int.h" 70 #include "hash.h" 71 #include "page.h" 72 #include "extern.h" 73 74 static int32_t collect_key __P((HTAB *, PAGE16 *, int32_t, db_pgno_t *)); 75 static int32_t collect_data __P((HTAB *, PAGE16 *, int32_t)); 76 77 /* 78 * Big_insert 79 * 80 * You need to do an insert and the key/data pair is greater than 81 * MINFILL * the bucket size 82 * 83 * Returns: 84 * 0 ==> OK 85 * -1 ==> ERROR 86 */ 87 int32_t 88 __big_insert(hashp, pagep, key, val) 89 HTAB *hashp; 90 PAGE16 *pagep; 91 const DBT *key, *val; 92 { 93 size_t key_size, val_size; 94 indx_t key_move_bytes, val_move_bytes; 95 int8_t *key_data, *val_data, base_page; 96 97 key_data = (int8_t *)key->data; 98 key_size = key->size; 99 val_data = (int8_t *)val->data; 100 val_size = val->size; 101 102 NUM_ENT(pagep) = NUM_ENT(pagep) + 1; 103 104 for (base_page = 1; key_size + val_size;) { 105 /* Add a page! */ 106 pagep = 107 __add_bigpage(hashp, pagep, NUM_ENT(pagep) - 1, base_page); 108 if (!pagep) 109 return (-1); 110 111 /* There's just going to be one entry on this page. */ 112 NUM_ENT(pagep) = 1; 113 114 /* Move the key's data. */ 115 key_move_bytes = MIN(FREESPACE(pagep), key_size); 116 /* Mark the page as to how much key & data is on this page. */ 117 BIGKEYLEN(pagep) = key_move_bytes; 118 val_move_bytes = 119 MIN(FREESPACE(pagep) - key_move_bytes, val_size); 120 BIGDATALEN(pagep) = val_move_bytes; 121 122 /* Note big pages build beginning --> end, not vice versa. */ 123 if (key_move_bytes) 124 memmove(BIGKEY(pagep), key_data, key_move_bytes); 125 if (val_move_bytes) 126 memmove(BIGDATA(pagep), val_data, val_move_bytes); 127 128 key_size -= key_move_bytes; 129 key_data += key_move_bytes; 130 val_size -= val_move_bytes; 131 val_data += val_move_bytes; 132 133 base_page = 0; 134 } 135 __put_page(hashp, pagep, A_RAW, 1); 136 return (0); 137 } 138 139 /* 140 * Called when we need to delete a big pair. 141 * 142 * Returns: 143 * 0 => OK 144 * -1 => ERROR 145 */ 146 int32_t 147 #ifdef __STDC__ 148 __big_delete(HTAB *hashp, PAGE16 *pagep, indx_t ndx) 149 #else 150 __big_delete(hashp, pagep, ndx) 151 HTAB *hashp; 152 PAGE16 *pagep; 153 u_int32_t ndx; /* Index of big pair on base page. */ 154 #endif 155 { 156 PAGE16 *last_pagep; 157 158 /* Get first page with big key/data. */ 159 pagep = __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW); 160 if (!pagep) 161 return (-1); 162 163 /* 164 * Traverse through the pages, freeing the previous one (except 165 * the first) at each new page. 166 */ 167 while (NEXT_PGNO(pagep) != INVALID_PGNO) { 168 last_pagep = pagep; 169 pagep = __get_page(hashp, NEXT_PGNO(pagep), A_RAW); 170 if (!pagep) 171 return (-1); 172 __delete_page(hashp, last_pagep, A_OVFL); 173 } 174 175 /* Free the last page in the chain. */ 176 __delete_page(hashp, pagep, A_OVFL); 177 return (0); 178 } 179 180 /* 181 * Given a key, indicates whether the big key at cursorp matches the 182 * given key. 183 * 184 * Returns: 185 * 1 = Found! 186 * 0 = Key not found 187 * -1 error 188 */ 189 int32_t 190 __find_bigpair(hashp, cursorp, key, size) 191 HTAB *hashp; 192 CURSOR *cursorp; 193 int8_t *key; 194 int32_t size; 195 { 196 PAGE16 *pagep, *hold_pagep; 197 db_pgno_t next_pgno; 198 int32_t ksize; 199 u_int16_t bytes; 200 int8_t *kkey; 201 202 ksize = size; 203 kkey = key; 204 bytes = 0; 205 206 hold_pagep = NULL; 207 /* Chances are, hashp->cpage is the base page. */ 208 if (cursorp->pagep) 209 pagep = hold_pagep = cursorp->pagep; 210 else { 211 pagep = __get_page(hashp, cursorp->pgno, A_RAW); 212 if (!pagep) 213 return (-1); 214 } 215 216 /* 217 * Now, get the first page with the big stuff on it. 218 * 219 * XXX 220 * KLUDGE: we know that cursor is looking at the _next_ item, so 221 * we have to look at pgndx - 1. 222 */ 223 next_pgno = OADDR_TO_PAGE(DATA_OFF(pagep, (cursorp->pgndx - 1))); 224 if (!hold_pagep) 225 __put_page(hashp, pagep, A_RAW, 0); 226 pagep = __get_page(hashp, next_pgno, A_RAW); 227 if (!pagep) 228 return (-1); 229 230 /* While there are both keys to compare. */ 231 while ((ksize > 0) && (BIGKEYLEN(pagep))) { 232 if (ksize < KEY_OFF(pagep, 0) || 233 memcmp(BIGKEY(pagep), kkey, BIGKEYLEN(pagep))) { 234 __put_page(hashp, pagep, A_RAW, 0); 235 return (0); 236 } 237 kkey += BIGKEYLEN(pagep); 238 ksize -= BIGKEYLEN(pagep); 239 if (NEXT_PGNO(pagep) != INVALID_PGNO) { 240 next_pgno = NEXT_PGNO(pagep); 241 __put_page(hashp, pagep, A_RAW, 0); 242 pagep = __get_page(hashp, next_pgno, A_RAW); 243 if (!pagep) 244 return (-1); 245 } 246 } 247 __put_page(hashp, pagep, A_RAW, 0); 248 #ifdef DEBUG 249 assert(ksize >= 0); 250 #endif 251 if (ksize != 0) { 252 #ifdef HASH_STATISTICS 253 ++hash_collisions; 254 #endif 255 return (0); 256 } else 257 return (1); 258 } 259 260 /* 261 * Fill in the key and data for this big pair. 262 */ 263 int32_t 264 __big_keydata(hashp, pagep, key, val, ndx) 265 HTAB *hashp; 266 PAGE16 *pagep; 267 DBT *key, *val; 268 int32_t ndx; 269 { 270 ITEM_INFO ii; 271 PAGE16 *key_pagep; 272 db_pgno_t last_page; 273 274 key_pagep = 275 __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW); 276 if (!key_pagep) 277 return (-1); 278 key->size = collect_key(hashp, key_pagep, 0, &last_page); 279 key->data = hashp->bigkey_buf; 280 __put_page(hashp, key_pagep, A_RAW, 0); 281 282 if (key->size == -1) 283 return (-1); 284 285 /* Create an item_info to direct __big_return to the beginning pgno. */ 286 ii.pgno = last_page; 287 return (__big_return(hashp, &ii, val, 1)); 288 } 289 290 /* 291 * Return the big key on page, ndx. 292 */ 293 int32_t 294 #ifdef __STDC__ 295 __get_bigkey(HTAB *hashp, PAGE16 *pagep, indx_t ndx, DBT *key) 296 #else 297 __get_bigkey(hashp, pagep, ndx, key) 298 HTAB *hashp; 299 PAGE16 *pagep; 300 u_int32_t ndx; 301 DBT *key; 302 #endif 303 { 304 PAGE16 *key_pagep; 305 306 key_pagep = 307 __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW); 308 if (!pagep) 309 return (-1); 310 key->size = collect_key(hashp, key_pagep, 0, NULL); 311 key->data = hashp->bigkey_buf; 312 313 __put_page(hashp, key_pagep, A_RAW, 0); 314 315 return (0); 316 } 317 318 /* 319 * Return the big key and data indicated in item_info. 320 */ 321 int32_t 322 __big_return(hashp, item_info, val, on_bigkey_page) 323 HTAB *hashp; 324 ITEM_INFO *item_info; 325 DBT *val; 326 int32_t on_bigkey_page; 327 { 328 PAGE16 *pagep; 329 db_pgno_t next_pgno; 330 331 if (!on_bigkey_page) { 332 /* Get first page with big pair on it. */ 333 pagep = __get_page(hashp, 334 OADDR_TO_PAGE(item_info->data_off), A_RAW); 335 if (!pagep) 336 return (-1); 337 } else { 338 pagep = __get_page(hashp, item_info->pgno, A_RAW); 339 if (!pagep) 340 return (-1); 341 } 342 343 /* Traverse through the bigkey pages until a page with data is found. */ 344 while (!BIGDATALEN(pagep)) { 345 next_pgno = NEXT_PGNO(pagep); 346 __put_page(hashp, pagep, A_RAW, 0); 347 pagep = __get_page(hashp, next_pgno, A_RAW); 348 if (!pagep) 349 return (-1); 350 } 351 352 val->size = collect_data(hashp, pagep, 0); 353 if (val->size < 1) 354 return (-1); 355 val->data = (void *)hashp->bigdata_buf; 356 357 __put_page(hashp, pagep, A_RAW, 0); 358 return (0); 359 } 360 361 /* 362 * Given a page with a big key on it, traverse through the pages counting data 363 * length, and collect all of the data on the way up. Store the key in 364 * hashp->bigkey_buf. last_page indicates to the calling function what the 365 * last page with key on it is; this will help if you later want to retrieve 366 * the data portion. 367 * 368 * Does the work for __get_bigkey. 369 * 370 * Return total length of data; -1 if error. 371 */ 372 static int32_t 373 collect_key(hashp, pagep, len, last_page) 374 HTAB *hashp; 375 PAGE16 *pagep; 376 int32_t len; 377 db_pgno_t *last_page; 378 { 379 PAGE16 *next_pagep; 380 int32_t totlen, retval; 381 db_pgno_t next_pgno; 382 #ifdef DEBUG 383 db_pgno_t save_addr; 384 #endif 385 386 /* If this is the last page with key. */ 387 if (BIGDATALEN(pagep)) { 388 totlen = len + BIGKEYLEN(pagep); 389 if (hashp->bigkey_buf) 390 free(hashp->bigkey_buf); 391 hashp->bigkey_buf = (u_int8_t *)malloc(totlen); 392 if (!hashp->bigkey_buf) 393 return (-1); 394 memcpy(hashp->bigkey_buf + len, 395 BIGKEY(pagep), BIGKEYLEN(pagep)); 396 if (last_page) 397 *last_page = ADDR(pagep); 398 return (totlen); 399 } 400 401 /* Key filled up all of last key page, so we've gone 1 too far. */ 402 if (BIGKEYLEN(pagep) == 0) { 403 if (hashp->bigkey_buf) 404 free(hashp->bigkey_buf); 405 hashp->bigkey_buf = (u_int8_t *)malloc(len); 406 return (hashp->bigkey_buf ? len : -1); 407 } 408 totlen = len + BIGKEYLEN(pagep); 409 410 /* Set pagep to the next page in the chain. */ 411 if (last_page) 412 *last_page = ADDR(pagep); 413 next_pgno = NEXT_PGNO(pagep); 414 next_pagep = __get_page(hashp, next_pgno, A_RAW); 415 if (!next_pagep) 416 return (-1); 417 #ifdef DEBUG 418 save_addr = ADDR(pagep); 419 #endif 420 retval = collect_key(hashp, next_pagep, totlen, last_page); 421 422 #ifdef DEBUG 423 assert(save_addr == ADDR(pagep)); 424 #endif 425 memcpy(hashp->bigkey_buf + len, BIGKEY(pagep), BIGKEYLEN(pagep)); 426 __put_page(hashp, next_pagep, A_RAW, 0); 427 428 return (retval); 429 } 430 431 /* 432 * Given a page with big data on it, recur through the pages counting data 433 * length, and collect all of the data on the way up. Store the data in 434 * hashp->bigdata_buf. 435 * 436 * Does the work for __big_return. 437 * 438 * Return total length of data; -1 if error. 439 */ 440 static int32_t 441 collect_data(hashp, pagep, len) 442 HTAB *hashp; 443 PAGE16 *pagep; 444 int32_t len; 445 { 446 PAGE16 *next_pagep; 447 int32_t totlen, retval; 448 db_pgno_t next_pgno; 449 #ifdef DEBUG 450 db_pgno_t save_addr; 451 #endif 452 453 /* If there is no next page. */ 454 if (NEXT_PGNO(pagep) == INVALID_PGNO) { 455 if (hashp->bigdata_buf) 456 free(hashp->bigdata_buf); 457 totlen = len + BIGDATALEN(pagep); 458 hashp->bigdata_buf = (u_int8_t *)malloc(totlen); 459 if (!hashp->bigdata_buf) 460 return (-1); 461 memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep), 462 BIGDATA(pagep), BIGDATALEN(pagep)); 463 return (totlen); 464 } 465 totlen = len + BIGDATALEN(pagep); 466 467 /* Set pagep to the next page in the chain. */ 468 next_pgno = NEXT_PGNO(pagep); 469 next_pagep = __get_page(hashp, next_pgno, A_RAW); 470 if (!next_pagep) 471 return (-1); 472 473 #ifdef DEBUG 474 save_addr = ADDR(pagep); 475 #endif 476 retval = collect_data(hashp, next_pagep, totlen); 477 #ifdef DEBUG 478 assert(save_addr == ADDR(pagep)); 479 #endif 480 memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep), 481 BIGDATA(pagep), BIGDATALEN(pagep)); 482 __put_page(hashp, next_pagep, A_RAW, 0); 483 484 return (retval); 485 } 486