btree/bt_compress.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996-2009 Oracle.  All rights reserved.
   5  */
   6
   7 #include "db_config.h"
   8
   9 #include "db_int.h"
  10 #include "dbinc/db_page.h"
  11 #include "dbinc/btree.h"
  12
  13 #ifdef HAVE_COMPRESSION
  14
  15 static int __bam_compress_marshal_data __P((DB *, const DBT *, DBT *));
  16 static int __bam_compress_set_dbt __P((DB *, DBT *, const void *, u_int32_t));
  17 static int __bamc_compress_del_and_get_next __P((DBC *, DBT *, DBT *));
  18 static int __bamc_compress_get_bothc __P((DBC *, DBT *, u_int32_t));
  19 static int __bamc_compress_get_multiple_key __P((DBC *, DBT *, u_int32_t));
  20 static int __bamc_compress_get_multiple __P((DBC *, DBT *, DBT *,u_int32_t));
  21 static int __bamc_compress_get_next __P((DBC *, u_int32_t));
  22 static int __bamc_compress_get_next_dup __P((DBC *, DBT *, u_int32_t));
  23 static int __bamc_compress_get_next_nodup __P((DBC *, u_int32_t));
  24 static int __bamc_compress_get_prev __P((DBC *, u_int32_t));
  25 static int __bamc_compress_get_prev_dup __P((DBC *, u_int32_t));
  26 static int __bamc_compress_get_prev_nodup __P((DBC *, u_int32_t));
  27 static int __bamc_compress_get_set __P((DBC *,
  28         DBT *, DBT *, u_int32_t, u_int32_t));
  29 static int __bamc_compress_ibulk_del __P((DBC *, DBT *, u_int32_t));
  30 static int __bamc_compress_idel __P((DBC *, u_int32_t));
  31 static int __bamc_compress_iget __P((DBC *, DBT *, DBT *, u_int32_t));
  32 static int __bamc_compress_iput __P((DBC *, DBT *, DBT *, u_int32_t));
  33 static int __bamc_compress_relocate __P((DBC *));
  34 static void __bamc_compress_reset __P((DBC *));
  35 static int __bamc_compress_seek __P((DBC *,
  36         const DBT *, const DBT *, u_int32_t));
  37 static int __bamc_compress_store __P((DBC *,
  38         DBT *, DBT*, DBT **, DBT **, DBT *, DBT *));
  39 static int __bamc_next_decompress __P((DBC *));
  40 static int __bamc_start_decompress __P((DBC *));
  41
  42 /*
  43  * Call __dbc_iget(), resizing DBTs if DB_BUFFER_SMALL is returned.
  44  * We're always using a transient cursor when this macro is used, so
  45  * we have to replace the OP with DB_CURRENT when we retry.
  46  */
  47 #define CMP_IGET_RETRY(ret, dbc, dbt1, dbt2, flags) do {                \
  48         DB_ASSERT((dbc)->env, F_ISSET((dbt1), DB_DBT_USERMEM));         \
  49         DB_ASSERT((dbc)->env, F_ISSET((dbt2), DB_DBT_USERMEM));         \
  50         if (((ret) =__dbc_iget((dbc),                                   \
  51             (dbt1), (dbt2), (flags))) == DB_BUFFER_SMALL) {             \
  52                 if ((CMP_RESIZE_DBT((ret), (dbc)->env, (dbt1))) != 0)   \
  53                         break;                                          \
  54                 if ((CMP_RESIZE_DBT((ret), (dbc)->env, (dbt2))) != 0)   \
  55                         break;                                          \
  56                 (ret) = __dbc_iget((dbc), (dbt1), (dbt2),               \
  57                         ((flags) & ~DB_OPFLAGS_MASK) | DB_CURRENT);     \
  58         }                                                               \
  59 } while (0)
  60
  61 #define CMP_INIT_DBT(dbt) do {                                          \
  62         (dbt)->data = NULL;                                             \
  63         (dbt)->size = 0;                                                \
  64         (dbt)->ulen = 0;                                                \
  65         (dbt)->doff = 0;                                                \
  66         (dbt)->dlen = 0;                                                \
  67         (dbt)->flags = DB_DBT_USERMEM;                                  \
  68         (dbt)->app_data = NULL;                                         \
  69 } while (0)
  70
  71 #define CMP_FREE_DBT(env, dbt) do {                                     \
  72         DB_ASSERT((env), F_ISSET((dbt), DB_DBT_USERMEM));               \
  73         __os_free((env), (dbt)->data);                                  \
  74 } while (0)
  75
  76 #define CMP_RESIZE_DBT(ret, env, dbt)                                   \
  77         (((dbt)->size > (dbt)->ulen) ?                                  \
  78         ((((ret) = __os_realloc((env), (dbt)->size, &(dbt)->data))      \
  79                 != 0) ? (ret) : (((dbt)->ulen = (dbt)->size), 0)) : 0)
  80
  81 static int
  82 __bam_compress_set_dbt(dbp, dbt, data, size)
  83         DB *dbp;
  84         DBT *dbt;
  85         const void *data;
  86         u_int32_t size;
  87 {
  88         int ret;
  89
  90         ret = 0;
  91         DB_ASSERT(dbp->env, F_ISSET(dbt, DB_DBT_USERMEM));
  92
  93         dbt->size = size;
  94         if (CMP_RESIZE_DBT(ret, dbp->env, dbt) != 0)
  95                 return (ret);
  96
  97         memcpy(dbt->data, data, size);
  98         return (0);
  99 }
 100
 101 /******************************************************************************/
 102
 103 /*
 104  * Very simple key/data stream to give __bamc_compress_merge_insert()
 105  * a source of data to work on.
 106  */
 107 struct __bam_compress_stream;
 108 typedef struct __bam_compress_stream BTREE_COMPRESS_STREAM;
 109 struct __bam_compress_stream
 110 {
 111         int (*next)(BTREE_COMPRESS_STREAM *, DBT *, DBT *);
 112
 113         void *kptr, *dptr;
 114         DBT *key, *data;
 115 };
 116
 117 /*
 118  * These function prototypes can not go at the beginning because they rely on
 119  * on BTREE_COMPRESS_STREAM defined above.
 120  * The prototypes are required to avoid the Microsoft C++ compiler generating
 121  * warnings about mismatching parameter lists.
 122  */
 123 static int __bam_cs_next_done __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 124 static int __bam_cs_single_next __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 125 static void __bam_cs_create_single
 126                         __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 127 static int __bam_cs_single_keyonly_next
 128                         __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 129 static void __bam_cs_create_single_keyonly
 130                         __P((BTREE_COMPRESS_STREAM *, DBT *));
 131 static int __bam_cs_multiple_key_next
 132                         __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 133 static void __bam_cs_create_multiple_key __P((BTREE_COMPRESS_STREAM *, DBT *));
 134 static int __bam_cs_multiple_next __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 135 static void __bam_cs_create_multiple
 136                         __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 137 static int __bam_cs_multiple_keyonly_next
 138                         __P((BTREE_COMPRESS_STREAM *, DBT *, DBT *));
 139 static void __bam_cs_create_multiple_keyonly
 140                         __P((BTREE_COMPRESS_STREAM *, DBT *));
 141 static int __bamc_compress_merge_insert
 142                 __P((DBC *, BTREE_COMPRESS_STREAM *, u_int32_t *, u_int32_t));
 143 static int __bamc_compress_merge_delete
 144                 __P((DBC *, BTREE_COMPRESS_STREAM *, u_int32_t *));
 145 static int __bamc_compress_merge_delete_dups
 146                 __P((DBC *, BTREE_COMPRESS_STREAM *, u_int32_t *));
 147
 148 /* BTREE_COMPRESS_STREAM->next() for when the data has finished. */
 149 static int
 150 __bam_cs_next_done(stream, key, data)
 151         BTREE_COMPRESS_STREAM *stream;
 152         DBT *key, *data;
 153 {
 154         COMPQUIET(stream, NULL);
 155         COMPQUIET(key, NULL);
 156         COMPQUIET(data, NULL);
 157         return (0);
 158 }
 159
 160 /* BTREE_COMPRESS_STREAM->next() for a single key/data pair. */
 161 static int
 162 __bam_cs_single_next(stream, key, data)
 163         BTREE_COMPRESS_STREAM *stream;
 164         DBT *key, *data;
 165 {
 166         key->data = stream->key->data;
 167         key->size = stream->key->size;
 168         data->data = stream->data->data;
 169         data->size = stream->data->size;
 170         stream->next = __bam_cs_next_done;
 171         return (1);
 172 }
 173
 174 /* Create a BTREE_COMPRESS_STREAM for a single key/data pair */
 175 static void
 176 __bam_cs_create_single(stream, key, data)
 177         BTREE_COMPRESS_STREAM *stream;
 178         DBT *key, *data;
 179 {
 180         stream->next = __bam_cs_single_next;
 181         stream->key = key;
 182         stream->data = data;
 183 }
 184
 185 /* BTREE_COMPRESS_STREAM->next() for a single key. */
 186 static int
 187 __bam_cs_single_keyonly_next(stream, key, data)
 188         BTREE_COMPRESS_STREAM *stream;
 189         DBT *key, *data;
 190 {
 191         key->data = stream->key->data;
 192         key->size = stream->key->size;
 193         if (data != NULL) {
 194                 data->data = NULL;
 195                 data->size = 0;
 196         }
 197         stream->next = __bam_cs_next_done;
 198         return (1);
 199 }
 200
 201 /* Create a BTREE_COMPRESS_STREAM for a single key/data pair */
 202 static void
 203 __bam_cs_create_single_keyonly(stream, key)
 204         BTREE_COMPRESS_STREAM *stream;
 205         DBT *key;
 206 {
 207         stream->next = __bam_cs_single_keyonly_next;
 208         stream->key = key;
 209 }
 210
 211 /*
 212  * BTREE_COMPRESS_STREAM->next() for a single buffer in the DB_MULTIPLE_KEY
 213  * format.
 214  */
 215 static int
 216 __bam_cs_multiple_key_next(stream, key, data)
 217         BTREE_COMPRESS_STREAM *stream;
 218         DBT *key, *data;
 219 {
 220         DB_MULTIPLE_KEY_NEXT(stream->kptr, stream->key, key->data, key->size,
 221                 data->data, data->size);
 222         if (key->data == NULL) {
 223                 stream->next = __bam_cs_next_done;
 224                 return (0);
 225         }
 226         return (1);
 227 }
 228
 229 /*
 230  * Create a BTREE_COMPRESS_STREAM for a single buffer in the DB_MULTIPLE_KEY
 231  * format.
 232  */
 233 static void
 234 __bam_cs_create_multiple_key(stream, multiple)
 235         BTREE_COMPRESS_STREAM *stream;
 236         DBT *multiple;
 237 {
 238         stream->next = __bam_cs_multiple_key_next;
 239         stream->key = multiple;
 240         DB_MULTIPLE_INIT(stream->kptr, stream->key);
 241 }
 242
 243 /* BTREE_COMPRESS_STREAM->next() for two buffers in the DB_MULTIPLE format. */
 244 static int
 245 __bam_cs_multiple_next(stream, key, data)
 246         BTREE_COMPRESS_STREAM *stream;
 247         DBT *key, *data;
 248 {
 249         DB_MULTIPLE_NEXT(stream->kptr, stream->key, key->data, key->size);
 250         DB_MULTIPLE_NEXT(stream->dptr, stream->data, data->data, data->size);
 251         if (key->data == NULL || data->data == NULL) {
 252                 stream->next = __bam_cs_next_done;
 253                 return (0);
 254         }
 255         return (1);
 256 }
 257
 258 /* Create a BTREE_COMPRESS_STREAM for two buffers in the DB_MULTIPLE format. */
 259 static void
 260 __bam_cs_create_multiple(stream, key, data)
 261         BTREE_COMPRESS_STREAM *stream;
 262         DBT *key, *data;
 263 {
 264         stream->next = __bam_cs_multiple_next;
 265         stream->key = key;
 266         stream->data = data;
 267         DB_MULTIPLE_INIT(stream->kptr, stream->key);
 268         DB_MULTIPLE_INIT(stream->dptr, stream->data);
 269 }
 270
 271 /*
 272  * BTREE_COMPRESS_STREAM->next() for a single buffer in the DB_MULTIPLE
 273  * format.
 274  */
 275 static int
 276 __bam_cs_multiple_keyonly_next(stream, key, data)
 277         BTREE_COMPRESS_STREAM *stream;
 278         DBT *key, *data;
 279 {
 280         DB_MULTIPLE_NEXT(stream->kptr, stream->key, key->data, key->size);
 281         if (key->data == NULL) {
 282                 stream->next = __bam_cs_next_done;
 283                 return (0);
 284         }
 285         if (data != NULL) {
 286                 data->data = NULL;
 287                 data->size = 0;
 288         }
 289         return (1);
 290 }
 291
 292 /*
 293  * Create a BTREE_COMPRESS_STREAM for a single buffer in the DB_MULTIPLE
 294  * format.
 295  */
 296 static void
 297 __bam_cs_create_multiple_keyonly(stream, key)
 298         BTREE_COMPRESS_STREAM *stream;
 299         DBT *key;
 300 {
 301         stream->next = __bam_cs_multiple_keyonly_next;
 302         stream->key = key;
 303         DB_MULTIPLE_INIT(stream->kptr, stream->key);
 304 }
 305
 306 /******************************************************************************/
 307
 308 /*
 309  * Marshal data in initial data format into destbuf, resizing destbuf if
 310  * necessary.
 311  */
 312 static int
 313 __bam_compress_marshal_data(dbp, data, destbuf)
 314         DB *dbp;
 315         const DBT *data;
 316         DBT *destbuf;
 317 {
 318         int ret;
 319         u_int8_t *ptr;
 320
 321         ret = 0;
 322         DB_ASSERT(dbp->env, F_ISSET(destbuf, DB_DBT_USERMEM));
 323
 324         destbuf->size = __db_compress_count_int(data->size);
 325         destbuf->size += data->size;
 326         if (CMP_RESIZE_DBT(ret, dbp->env, destbuf) != 0)
 327                 return (ret);
 328
 329         ptr = (u_int8_t*)destbuf->data;
 330         ptr += __db_compress_int(ptr, data->size);
 331         memcpy(ptr, data->data, data->size);
 332
 333         return (0);
 334 }
 335
 336 /*
 337  * Unmarshal initial data from source into data - does not copy, points
 338  * into source.
 339  */
 340 #define CMP_UNMARSHAL_DATA(src, dest) do {                              \
 341         (dest)->data = ((u_int8_t*)(src)->data) +                       \
 342                 __db_decompress_int32((u_int8_t*)(src)->data,           \
 343                         &(dest)->size);                                 \
 344 } while (0)
 345
 346 /******************************************************************************/
 347
 348 /*
 349  * __bam_compress_dupcmp --
 350  *      Duplicate comparison function for compressed BTrees.
 351  *
 352  * PUBLIC: int __bam_compress_dupcmp __P((DB *, const DBT *, const DBT *));
 353  */
 354 int
 355 __bam_compress_dupcmp(db, a, b)
 356         DB *db;
 357         const DBT *a;
 358         const DBT *b;
 359 {
 360         DBT dcmp_a, dcmp_b;
 361
 362         /* Decompress the initial data in a */
 363         CMP_UNMARSHAL_DATA(a, &dcmp_a);
 364         dcmp_a.ulen = 0;
 365         dcmp_a.doff = 0;
 366         dcmp_a.dlen = 0;
 367         dcmp_a.flags = 0;
 368         dcmp_a.app_data = 0;
 369
 370         /* Decompress the initial data in b */
 371         CMP_UNMARSHAL_DATA(b, &dcmp_b);
 372         dcmp_b.ulen = 0;
 373         dcmp_b.doff = 0;
 374         dcmp_b.dlen = 0;
 375         dcmp_b.flags = 0;
 376         dcmp_b.app_data = 0;
 377
 378         /* Call the user's duplicate compare function */
 379         return ((BTREE *)db->bt_internal)->
 380                 compress_dup_compare(db, &dcmp_a, &dcmp_b);
 381 }
 382
 383 /*
 384  * __bam_defcompress --
 385  *      Default compression routine.
 386  *
 387  * PUBLIC: int __bam_defcompress __P((DB *, const DBT *, const DBT *,
 388  * PUBLIC:     const DBT *, const DBT *, DBT *));
 389  */
 390 int
 391 __bam_defcompress(dbp, prevKey, prevData, key, data, dest)
 392         DB *dbp;
 393         const DBT *prevKey, *prevData, *key, *data;
 394         DBT *dest;
 395 {
 396         u_int8_t *ptr;
 397         const u_int8_t *k, *p;
 398         size_t len, prefix, suffix;
 399
 400         COMPQUIET(dbp, NULL);
 401
 402         k = (const u_int8_t*)key->data;
 403         p = (const u_int8_t*)prevKey->data;
 404         len = key->size > prevKey->size ? prevKey->size : key->size;
 405         for (; len-- && *k == *p; ++k, ++p)
 406                 continue;
 407
 408         prefix = (size_t)(k - (u_int8_t*)key->data);
 409         suffix = key->size - prefix;
 410
 411         if (prefix == prevKey->size && suffix == 0) {
 412                 /* It's a duplicate - do prefix compression on the value */
 413                 k = (const u_int8_t*)data->data;
 414                 p = (const u_int8_t*)prevData->data;
 415                 len = data->size > prevData->size ? prevData->size : data->size;
 416                 for (; len-- && *k == *p; ++k, ++p)
 417                         continue;
 418
 419                 prefix = (size_t)(k - (u_int8_t*)data->data);
 420                 suffix = data->size - prefix;
 421
 422                 /* Check that we have enough space in dest */
 423                 dest->size = (u_int32_t)(1 + __db_compress_count_int(prefix) +
 424                         __db_compress_count_int(suffix) + suffix);
 425                 if (dest->size > dest->ulen)
 426                         return (DB_BUFFER_SMALL);
 427
 428                 /* Magic identifying byte */
 429                 ptr = (u_int8_t*)dest->data;
 430                 *ptr = CMP_INT_SPARE_VAL;
 431                 ++ptr;
 432
 433                 /* prefix length */
 434                 ptr += __db_compress_int(ptr, prefix);
 435
 436                 /* suffix length */
 437                 ptr += __db_compress_int(ptr, suffix);
 438
 439                 /* suffix */
 440                 memcpy(ptr, k, suffix);
 441
 442                 return (0);
 443         }
 444
 445         /* Check that we have enough space in dest */
 446         dest->size = (u_int32_t)(__db_compress_count_int(prefix) +
 447                 __db_compress_count_int(suffix) +
 448                 __db_compress_count_int(data->size) + suffix + data->size);
 449         if (dest->size > dest->ulen)
 450                 return (DB_BUFFER_SMALL);
 451
 452         /* prefix length */
 453         ptr = (u_int8_t*)dest->data;
 454         ptr += __db_compress_int(ptr, prefix);
 455
 456         /* suffix length */
 457         ptr += __db_compress_int(ptr, suffix);
 458
 459         /* data length */
 460         ptr += __db_compress_int(ptr, data->size);
 461
 462         /* suffix */
 463         memcpy(ptr, k, suffix);
 464         ptr += suffix;
 465
 466         /* data */
 467         memcpy(ptr, data->data, data->size);
 468
 469         return (0);
 470 }
 471
 472 /*
 473  * __bam_defdecompress --
 474  *      Default decompression routine.
 475  *
 476  * PUBLIC: int __bam_defdecompress __P((DB *, const DBT *, const DBT *, DBT *,
 477  * PUBLIC:     DBT *, DBT *));
 478  */
 479 int
 480 __bam_defdecompress(dbp, prevKey, prevData, compressed, destKey, destData)
 481         DB *dbp;
 482         const DBT *prevKey, *prevData;
 483         DBT *compressed, *destKey, *destData;
 484 {
 485         u_int8_t *s, *d;
 486         u_int32_t prefix, suffix, size;
 487
 488         COMPQUIET(dbp, NULL);
 489
 490         /*
 491          * Check for the magic identifying byte, that tells us that this is a
 492          * compressed duplicate value.
 493          */
 494         s = (u_int8_t*)compressed->data;
 495         if (*s == CMP_INT_SPARE_VAL) {
 496                 ++s;
 497                 size = 1;
 498
 499                 /* Unmarshal prefix and suffix */
 500                 size += __db_decompress_count_int(s);
 501                 if (size > compressed->size)
 502                         return (EINVAL);
 503                 s += __db_decompress_int32(s, &prefix);
 504
 505                 size += __db_decompress_count_int(s);
 506                 if (size > compressed->size)
 507                         return (EINVAL);
 508                 s += __db_decompress_int32(s, &suffix);
 509
 510                 /* Check destination lengths */
 511                 destKey->size = prevKey->size;
 512                 destData->size = prefix + suffix;
 513                 if (destKey->size > destKey->ulen ||
 514                         destData->size > destData->ulen)
 515                         return (DB_BUFFER_SMALL);
 516
 517                 /* Write the key */
 518                 memcpy(destKey->data, prevKey->data, destKey->size);
 519
 520                 /* Write the prefix */
 521                 if (prefix > prevData->size)
 522                         return (EINVAL);
 523                 d = (u_int8_t*)destData->data;
 524                 memcpy(d, prevData->data, prefix);
 525                 d += prefix;
 526
 527                 /* Write the suffix */
 528                 size += suffix;
 529                 if (size > compressed->size)
 530                         return (EINVAL);
 531                 memcpy(d, s, suffix);
 532                 s += suffix;
 533
 534                 /* Return bytes read */
 535                 compressed->size = (u_int32_t)(s - (u_int8_t*)compressed->data);
 536                 return (0);
 537         }
 538
 539         /* Unmarshal prefix, suffix and data length */
 540         size = __db_decompress_count_int(s);
 541         if (size > compressed->size)
 542                 return (EINVAL);
 543         s += __db_decompress_int32(s, &prefix);
 544
 545         size += __db_decompress_count_int(s);
 546         if (size > compressed->size)
 547                 return (EINVAL);
 548         s += __db_decompress_int32(s, &suffix);
 549
 550         size += __db_decompress_count_int(s);
 551         if (size > compressed->size)
 552                 return (EINVAL);
 553         s += __db_decompress_int32(s, &destData->size);
 554
 555         /* Check destination lengths */
 556         destKey->size = prefix + suffix;
 557         if (destKey->size > destKey->ulen || destData->size > destData->ulen)
 558                 return (DB_BUFFER_SMALL);
 559
 560         /* Write the prefix */
 561         if (prefix > prevKey->size)
 562                 return (EINVAL);
 563         d = (u_int8_t*)destKey->data;
 564         memcpy(d, prevKey->data, prefix);
 565         d += prefix;
 566
 567         /* Write the suffix */
 568         size += suffix;
 569         if (size > compressed->size)
 570                 return (EINVAL);
 571         memcpy(d, s, suffix);
 572         s += suffix;
 573
 574         /* Write the data */
 575         size += destData->size;
 576         if (size > compressed->size)
 577                 return (EINVAL);
 578         memcpy(destData->data, s, destData->size);
 579         s += destData->size;
 580
 581         /* Return bytes read */
 582         compressed->size = (u_int32_t)(s - (u_int8_t*)compressed->data);
 583         return (0);
 584 }
 585
 586 /******************************************************************************/
 587
 588 /*
 589  * Set dbc up to start decompressing the compressed key/data pair, dbc->key1
 590  * and dbc->compressed.
 591  */
 592 static int
 593 __bamc_start_decompress(dbc)
 594         DBC *dbc;
 595 {
 596         BTREE_CURSOR *cp;
 597         int ret;
 598         u_int32_t datasize;
 599
 600         cp = (BTREE_CURSOR *)dbc->internal;
 601
 602         cp->prevKey = NULL;
 603         cp->prevData = NULL;
 604         cp->currentKey = &cp->key1;
 605         cp->currentData = &cp->data1;
 606         cp->compcursor = (u_int8_t*)cp->compressed.data;
 607         cp->compend = cp->compcursor + cp->compressed.size;
 608         cp->prevcursor = NULL;
 609         cp->prev2cursor = NULL;
 610
 611         /* Unmarshal the first data */
 612         cp->compcursor += __db_decompress_int32(cp->compcursor, &datasize);
 613         ret = __bam_compress_set_dbt(dbc->dbp,
 614             cp->currentData, cp->compcursor, datasize);
 615
 616         if (ret == 0)
 617              cp->compcursor += datasize;
 618         return (ret);
 619 }
 620
 621 /* Decompress the next key/data pair from dbc->compressed. */
 622 static int
 623 __bamc_next_decompress(dbc)
 624         DBC *dbc;
 625 {
 626         DBT compressed;
 627         int ret;
 628         BTREE_CURSOR *cp;
 629         DB *db;
 630
 631         ret = 0;
 632         cp = (BTREE_CURSOR *)dbc->internal;
 633         db = dbc->dbp;
 634
 635         if (cp->compcursor >= cp->compend)
 636                 return (DB_NOTFOUND);
 637
 638         cp->prevKey = cp->currentKey;
 639         cp->prevData = cp->currentData;
 640         cp->prev2cursor = cp->prevcursor;
 641         cp->prevcursor = cp->compcursor;
 642
 643         if (cp->currentKey == &cp->key1) {
 644                 cp->currentKey = &cp->key2;
 645                 cp->currentData = &cp->data2;
 646         } else {
 647                 cp->currentKey = &cp->key1;
 648                 cp->currentData = &cp->data1;
 649         }
 650
 651         compressed.flags = DB_DBT_USERMEM;
 652         compressed.data = (void*)cp->compcursor;
 653         compressed.ulen = compressed.size =
 654             (u_int32_t)(cp->compend - cp->compcursor);
 655         compressed.app_data = NULL;
 656
 657         while ((ret = ((BTREE *)db->bt_internal)->bt_decompress(db,
 658              cp->prevKey, cp->prevData, &compressed,
 659              cp->currentKey, cp->currentData)) == DB_BUFFER_SMALL) {
 660                 if (CMP_RESIZE_DBT(ret, dbc->env, cp->currentKey) != 0)
 661                         break;
 662                 if (CMP_RESIZE_DBT(ret, dbc->env, cp->currentData) != 0)
 663                         break;
 664         }
 665
 666         if (ret == 0)
 667                 cp->compcursor += compressed.size;
 668         return (ret);
 669 }
 670
 671 /*
 672  * Store key and data into destkey and destbuf, using the compression
 673  * callback given.
 674  */
 675 static int
 676 __bamc_compress_store(dbc, key, data, prevKey, prevData, destkey, destbuf)
 677         DBC *dbc;
 678         DBT *key, *data;
 679         DBT **prevKey, **prevData;
 680         DBT *destkey, *destbuf;
 681 {
 682         int ret;
 683         DBT dest;
 684
 685         if (*prevKey == 0) {
 686                 if ((ret = __bam_compress_set_dbt(dbc->dbp,
 687                     destkey, key->data, key->size)) != 0)
 688                         return (ret);
 689
 690                 /* Marshal data - resize if it won't fit */
 691                 ret = __bam_compress_marshal_data(dbc->dbp, data, destbuf);
 692
 693         } else if (((BTREE_CURSOR *)dbc->internal)->ovflsize > destbuf->size) {
 694                 /*
 695                  * Don't write more than cp->ovflsize bytes to the destination
 696                  * buffer - destbuf must be at least cp->ovflsize in size.
 697                  */
 698                 dest.flags = DB_DBT_USERMEM;
 699                 dest.data = (u_int8_t*)destbuf->data + destbuf->size;
 700                 dest.ulen =
 701                     ((BTREE_CURSOR *)dbc->internal)->ovflsize - destbuf->size;
 702                 dest.size = 0;
 703                 dest.app_data = NULL;
 704
 705                 ret = ((BTREE *)dbc->dbp->bt_internal)->bt_compress(
 706                     dbc->dbp, *prevKey, *prevData, key, data, &dest);
 707
 708                 if (ret == 0)
 709                         destbuf->size += dest.size;
 710         } else
 711                 ret = DB_BUFFER_SMALL;
 712
 713         if (ret == 0) {
 714                 *prevKey = key;
 715                 *prevData = data;
 716         }
 717
 718         return (ret);
 719 }
 720
 721 /*
 722  * Move dbc->dbc to the correct position to start linear searching for
 723  * seek_key/seek_data - the biggest key smaller than or equal to
 724  * seek_key/seek_data.
 725  */
 726 static int
 727 __bamc_compress_seek(dbc, seek_key, seek_data, flags)
 728         DBC *dbc;
 729         const DBT *seek_key;
 730         const DBT *seek_data;
 731         u_int32_t flags;
 732 {
 733         int ret;
 734         u_int32_t method;
 735         DB *dbp;
 736         BTREE_CURSOR *cp;
 737
 738         dbp = dbc->dbp;
 739         cp = (BTREE_CURSOR *)dbc->internal;
 740
 741         if ((ret = __bam_compress_set_dbt(
 742             dbp, &cp->key1, seek_key->data, seek_key->size)) != 0)
 743                 return (ret);
 744
 745         /*
 746          * We allow seek_data to be 0 for __bamc_compress_get_set() with
 747          * DB_SET
 748          */
 749         if (F_ISSET(dbp, DB_AM_DUPSORT) && seek_data != NULL) {
 750                 if ((ret = __bam_compress_marshal_data(
 751                     dbp, seek_data, &cp->compressed)) != 0)
 752                         return (ret);
 753
 754                 method = DB_GET_BOTH_LTE;
 755         } else
 756                 method = DB_SET_LTE;
 757
 758         CMP_IGET_RETRY(ret, dbc, &cp->key1, &cp->compressed, method | flags);
 759
 760         if (ret == 0 &&
 761             F_ISSET(dbp, DB_AM_DUPSORT) && seek_data == NULL &&
 762             __db_compare_both(dbp, seek_key, 0, &cp->key1, 0) == 0) {
 763                 /*
 764                  * Some entries for seek_key might be in the previous chunk,
 765                  * so we need to start searching there.
 766                  */
 767                 CMP_IGET_RETRY(ret,
 768                     dbc, &cp->key1, &cp->compressed, DB_PREV | flags);
 769                 if (ret == DB_NOTFOUND) {
 770                         /* No previous, we must need the first entry */
 771                         CMP_IGET_RETRY(ret,
 772                             dbc, &cp->key1, &cp->compressed, DB_FIRST | flags);
 773                 }
 774         }
 775
 776         return (ret);
 777 }
 778
 779 /* Reset the cursor to an uninitialized state */
 780 static void
 781 __bamc_compress_reset(dbc)
 782         DBC *dbc;
 783 {
 784         BTREE_CURSOR *cp;
 785
 786         cp = (BTREE_CURSOR *)dbc->internal;
 787
 788         cp->prevKey = 0;
 789         cp->prevData = 0;
 790         cp->currentKey = 0;
 791         cp->currentData = 0;
 792         cp->compcursor = 0;
 793         cp->compend = 0;
 794         cp->prevcursor = 0;
 795         cp->prev2cursor = 0;
 796
 797         F_CLR(cp, C_COMPRESS_DELETED|C_COMPRESS_MODIFIED);
 798 }
 799
 800 /*
 801  * Duplicate the cursor and delete the current entry, move the original cursor
 802  * on and then close the cursor we used to delete. We do that to make sure that
 803  * the close method runs __bamc_physdel(), and actually gets rid of the deleted
 804  * entry!
 805  */
 806 static int
 807 __bamc_compress_del_and_get_next(dbc, nextk, nextc)
 808      DBC *dbc;
 809      DBT *nextk, *nextc;
 810 {
 811         int ret, ret_n;
 812         DBC *dbc_n;
 813
 814         if ((ret = __dbc_dup(dbc, &dbc_n, DB_POSITION | DB_SHALLOW_DUP)) != 0)
 815                 return (ret);
 816         F_SET(dbc_n, DBC_TRANSIENT);
 817
 818         if ((ret = __dbc_idel(dbc_n, 0)) != 0)
 819                 goto err;
 820
 821         /* Read the next position */
 822         CMP_IGET_RETRY(ret, dbc, nextk, nextc, DB_NEXT);
 823
 824  err:
 825         if ((ret_n = __dbc_close(dbc_n)) != 0 && ret == 0)
 826                 ret = ret_n;
 827
 828         /* No need to relocate this cursor */
 829         F_CLR((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED);
 830
 831         return (ret);
 832 }
 833
 834 /*
 835  * Duplicate the cursor, re-locate the position that this cursor pointed to
 836  * using the duplicate (it may have been deleted), and then swap
 837  * the cursors. We do that to make sure that the close method runs
 838  * __bamc_physdel(), and gets rid of the entry that may have been deleted.
 839  */
 840 static int
 841 __bamc_compress_relocate(dbc)
 842         DBC *dbc;
 843 {
 844         int ret, t_ret;
 845         BTREE_CURSOR *cp, *cp_n;
 846         DBC *dbc_n;
 847
 848         cp = (BTREE_CURSOR *)dbc->internal;
 849
 850         if ((ret = __dbc_dup(dbc, &dbc_n, 0)) != 0)
 851                 return (ret);
 852         F_SET(dbc_n, DBC_TRANSIENT);
 853
 854         cp_n = (BTREE_CURSOR *)dbc_n->internal;
 855
 856         if (F_ISSET(cp, C_COMPRESS_DELETED)) {
 857                 /* Find the position after the deleted entry again */
 858                 ret = __bamc_compress_get_set(
 859                     dbc_n, &cp->del_key, &cp->del_data, 0, 0);
 860                 if (ret == DB_NOTFOUND) {
 861                         __bamc_compress_reset(dbc_n);
 862                         ret = 0;
 863                 } else if (ret != 0)
 864                         goto err;
 865
 866                 F_SET(cp_n, C_COMPRESS_DELETED);
 867
 868         } else if (cp->currentKey != NULL) {
 869                 /* Find the current entry again */
 870                 ret = __bamc_compress_get_set(
 871                     dbc_n, cp->currentKey, cp->currentData,
 872                     F_ISSET(dbc->dbp, DB_AM_DUPSORT) ? DB_GET_BOTH : DB_SET, 0);
 873
 874                 if (ret == DB_NOTFOUND) {
 875                         /* The current entry has been deleted */
 876                         if ((ret = __bam_compress_set_dbt(dbc_n->dbp,
 877                              &cp_n->del_key,
 878                              cp->currentKey->data, cp->currentKey->size)) != 0)
 879                                 return (ret);
 880                         if ((ret = __bam_compress_set_dbt(dbc_n->dbp,
 881                              &cp_n->del_data, cp->currentData->data,
 882                              cp->currentData->size)) != 0)
 883                                 return (ret);
 884                         F_SET(cp_n, C_COMPRESS_DELETED);
 885                         ret = 0;
 886                 } else if (ret != 0)
 887                         goto err;
 888         }
 889
 890  err:
 891         /* Cleanup and cursor resolution. This also clears the
 892            C_COMPRESS_MODIFIED flag. */
 893         if ((t_ret = __dbc_cleanup(dbc, dbc_n, ret)) != 0 && ret == 0)
 894                 ret = t_ret;
 895
 896         return (ret);
 897 }
 898
 899 /******************************************************************************/
 900
 901 #define CMP_STORE(key, data) do {                                           \
 902         while ((ret = __bamc_compress_store(dbc, (key), (data),             \
 903             &prevDestKey, &prevDestData, &destkey, &destbuf))               \
 904             == DB_BUFFER_SMALL) {                                           \
 905                 if ((ret = __dbc_iput(dbc,                                  \
 906                     &destkey, &destbuf, DB_KEYLAST)) != 0)                  \
 907                         goto end;                                           \
 908                 prevDestKey = NULL;                                         \
 909                 prevDestData = NULL;                                        \
 910                 destbuf.size = 0;                                           \
 911         }                                                                   \
 912 } while (0)
 913
 914 /* Merge the sorted key/data pairs from stream into the compressed database. */
 915 static int
 916 __bamc_compress_merge_insert(dbc, stream, countp, flags)
 917         DBC *dbc;
 918         BTREE_COMPRESS_STREAM *stream;
 919         u_int32_t *countp;
 920         u_int32_t flags;
 921 {
 922         DBT ikey1, ikey2, idata1, idata2, nextk, nextc, nextd, destkey, destbuf;
 923         DBT *ikey, *idata, *prevIkey, *prevIdata, *prevDestKey, *prevDestData;
 924         int ret, bulk_ret, cmp, nextExists, moreCompressed, iSmallEnough;
 925         int moreStream;
 926         u_int32_t chunk_count;
 927         ENV *env;
 928         BTREE_CURSOR *cp;
 929         DB *dbp;
 930
 931         env = dbc->env;
 932         cp = (BTREE_CURSOR *)dbc->internal;
 933         dbp = dbc->dbp;
 934         bulk_ret = 0;
 935
 936         memset(&ikey1, 0, sizeof(DBT));
 937         memset(&ikey2, 0, sizeof(DBT));
 938         memset(&idata1, 0, sizeof(DBT));
 939         memset(&idata2, 0, sizeof(DBT));
 940
 941         CMP_INIT_DBT(&nextk);
 942         CMP_INIT_DBT(&nextc);
 943         memset(&nextd, 0, sizeof(DBT));
 944
 945         CMP_INIT_DBT(&destkey);
 946         CMP_INIT_DBT(&destbuf);
 947         if ((ret = __os_malloc(env, cp->ovflsize, &destbuf.data)) != 0)
 948                 goto end;
 949         destbuf.ulen = cp->ovflsize;
 950
 951         if (countp != NULL)
 952                 *countp = 0;
 953         chunk_count = 0;
 954
 955         /* Get the first input key and data */
 956         ret = 0;
 957         prevIkey = NULL;
 958         prevIdata = NULL;
 959         ikey = &ikey1;
 960         idata = &idata1;
 961         if (stream->next(stream, ikey, idata) == 0)
 962                 goto end;
 963
 964         prevDestKey = NULL;
 965         prevDestData = NULL;
 966
 967         moreStream = 1;
 968         while (moreStream != 0) {
 969                 nextExists = 1;
 970                 moreCompressed = 1;
 971
 972                 /* Seek the ikey/idata position */
 973                 ret = __bamc_compress_seek(dbc, ikey, idata, 0);
 974                 if (ret == 0) {
 975                         /*
 976                          * Delete the key - we might overwrite it below
 977                          * but it's safer to just always delete it, and it
 978                          * doesn't seem significantly slower to do so.
 979                          */
 980                         ret = __bamc_compress_del_and_get_next(dbc, &nextk,
 981                                 &nextc);
 982                         if (ret == DB_NOTFOUND) {
 983                                 ret = 0;
 984                                 nextExists = 0;
 985                         } else if (ret == 0) {
 986                                 CMP_UNMARSHAL_DATA(&nextc, &nextd);
 987                         } else
 988                                 goto end;
 989                         ret = __bamc_start_decompress(dbc);
 990                 } else if (ret == DB_NOTFOUND) {
 991                         moreCompressed = 0;
 992
 993                         /* Read the next position */
 994                         CMP_IGET_RETRY(ret, dbc, &nextk, &nextc, DB_FIRST);
 995                         if (ret == DB_NOTFOUND) {
 996                                 ret = 0;
 997                                 nextExists = 0;
 998                         } else if (ret == 0) {
 999                                 CMP_UNMARSHAL_DATA(&nextc, &nextd);
1000                         }
1001                 }
1002
1003                 if (ret != 0)
1004                         goto end;
1005
1006                 /* !nextExists || ikey/idata < nextk/nextd */
1007                 iSmallEnough = 1;
1008
1009                 while (moreCompressed != 0 || iSmallEnough != 0) {
1010                         if (moreCompressed == 0)
1011                                 cmp = 1;
1012                         else if (iSmallEnough == 0)
1013                                 cmp = -1;
1014                         else
1015                                 cmp = __db_compare_both(dbp, cp->currentKey,
1016                                         cp->currentData, ikey, idata);
1017
1018                         if (cmp < 0) {
1019 store_current:                  CMP_STORE(cp->currentKey, cp->currentData);
1020                                 if (ret != 0)
1021                                         goto end;
1022                         } else {
1023                                 switch (flags) {
1024                                 case DB_KEYLAST:
1025                                 case DB_KEYFIRST:
1026                                 case DB_NODUPDATA:
1027                                         if (cmp == 0 && bulk_ret == 0 &&
1028                                                 F_ISSET(dbp, DB_AM_DUPSORT)) {
1029                                                 bulk_ret = __db_duperr(dbp,
1030                                                         flags);
1031
1032                                                 /*
1033                                                  * Continue until we store
1034                                                  * the current chunk,
1035                                                  * but don't insert any
1036                                                  * more entries.
1037                                                  */
1038                                                 moreStream = 0;
1039                                                 iSmallEnough = 0;
1040
1041                                                 goto store_current;
1042                                         }
1043                                         break;
1044                                 default:
1045                                         break;
1046                                 }
1047
1048                                 CMP_STORE(ikey, idata);
1049                                 if (ret != 0)
1050                                         goto end;
1051                                 ++chunk_count;
1052
1053                                 /*
1054                                  * prevDestKey/prevDestData now point to
1055                                  * the same DBTs as ikey/idata. We don't
1056                                  * want to overwrite them, so swap them
1057                                  * to point to the other DBTs.
1058                                  */
1059                                 if (ikey == &ikey1) {
1060                                         ikey = &ikey2;
1061                                         idata = &idata2;
1062                                         prevIkey = &ikey1;
1063                                         prevIdata = &idata1;
1064                                 } else {
1065                                         ikey = &ikey1;
1066                                         idata = &idata1;
1067                                         prevIkey = &ikey2;
1068                                         prevIdata = &idata2;
1069                                 }
1070
1071                                 do {
1072                                         /* Get the next input key and data */
1073                                         if (stream->next(
1074                                             stream, ikey, idata) == 0) {
1075                                                 moreStream = 0;
1076                                                 iSmallEnough = 0;
1077                                                 break;
1078                                         }
1079
1080 #ifdef DIAGNOSTIC
1081                                         /* Check that the stream is sorted */
1082                                         DB_ASSERT(env, __db_compare_both(dbp,
1083                                                 ikey, idata, prevIkey,
1084                                                 prevIdata) >= 0);
1085 #endif
1086
1087                                         /* Check for duplicates in the stream */
1088                                 } while (__db_compare_both(dbp, ikey, idata,
1089                                                  prevIkey, prevIdata) == 0);
1090
1091                                 /*
1092                                  * Check that !nextExists ||
1093                                  * ikey/idata < nextk/nextd
1094                                  */
1095                                 if (moreStream != 0 && nextExists != 0 &&
1096                                         __db_compare_both(dbp, ikey,
1097                                                 idata, &nextk, &nextd) >= 0)
1098                                         iSmallEnough = 0;
1099                         }
1100
1101                         if (cmp <= 0) {
1102                                 ret = __bamc_next_decompress(dbc);
1103                                 if (ret == DB_NOTFOUND) {
1104                                         moreCompressed = 0;
1105                                         ret = 0;
1106                                 } else if (ret != 0)
1107                                         goto end;
1108
1109                         }
1110                 }
1111
1112                 if (prevDestKey != NULL) {
1113                         if ((ret = __dbc_iput(
1114                             dbc, &destkey, &destbuf, DB_KEYLAST)) != 0)
1115                                 goto end;
1116
1117                         if (countp != NULL)
1118                                 *countp += chunk_count;
1119                         chunk_count = 0;
1120
1121                         prevDestKey = NULL;
1122                         prevDestData = NULL;
1123                         destbuf.size = 0;
1124                 }
1125         }
1126
1127  end:
1128         CMP_FREE_DBT(env, &destkey);
1129         CMP_FREE_DBT(env, &destbuf);
1130         CMP_FREE_DBT(env, &nextk);
1131         CMP_FREE_DBT(env, &nextc);
1132
1133         return (ret != 0 ? ret : bulk_ret);
1134 }
1135
1136 /******************************************************************************/
1137
1138 /* Remove the sorted key/data pairs in stream from the compressed database. */
1139 static int
1140 __bamc_compress_merge_delete(dbc, stream, countp)
1141         DBC *dbc;
1142         BTREE_COMPRESS_STREAM *stream;
1143         u_int32_t *countp;
1144 {
1145         DBT ikey, idata, nextk, nextc, nextd, destkey, destbuf, pdestkey;
1146         DBT pdestdata;
1147 #ifdef DIAGNOSTIC
1148         DBT pikey, pidata;
1149 #endif
1150         DBT *prevDestKey, *prevDestData;
1151         int ret, bulk_ret, cmp, moreCompressed, moreStream, nextExists;
1152         int iSmallEnough;
1153         u_int32_t chunk_count;
1154         ENV *env;
1155         BTREE_CURSOR *cp;
1156         DB *dbp;
1157
1158         env = dbc->env;
1159         cp = (BTREE_CURSOR *)dbc->internal;
1160         dbp = dbc->dbp;
1161         bulk_ret = 0;
1162
1163         memset(&ikey, 0, sizeof(DBT));
1164         memset(&idata, 0, sizeof(DBT));
1165
1166         CMP_INIT_DBT(&nextk);
1167         CMP_INIT_DBT(&nextc);
1168         memset(&nextd, 0, sizeof(DBT));
1169
1170         CMP_INIT_DBT(&pdestkey);
1171         CMP_INIT_DBT(&pdestdata);
1172
1173         CMP_INIT_DBT(&destkey);
1174         CMP_INIT_DBT(&destbuf);
1175         if ((ret = __os_malloc(env, cp->ovflsize, &destbuf.data)) != 0)
1176                 goto end;
1177         destbuf.ulen = cp->ovflsize;
1178
1179         if (countp != NULL)
1180                 *countp = 0;
1181         chunk_count = 0;
1182
1183         /* Get the first input key and data */
1184         ret = 0;
1185         if (stream->next(stream, &ikey, &idata) == 0)
1186                 goto end;
1187
1188         prevDestKey = NULL;
1189         prevDestData = NULL;
1190
1191         moreStream = 1;
1192         while (moreStream != 0) {
1193                 nextExists = 1;
1194                 moreCompressed = 1;
1195
1196                 /* Seek the ikey/idata position */
1197                 if ((ret = __bamc_compress_seek(dbc, &ikey, &idata, 0)) != 0)
1198                         goto end;
1199
1200                 /*
1201                  * Delete the key - we might overwrite it below but it's safer
1202                  * to just always delete it, and it doesn't seem significantly
1203                  * slower to do so.
1204                   */
1205                 ret = __bamc_compress_del_and_get_next(dbc, &nextk, &nextc);
1206                 if (ret == DB_NOTFOUND) {
1207                         ret = 0;
1208                         nextExists = 0;
1209                 } else if (ret == 0) {
1210                         CMP_UNMARSHAL_DATA(&nextc, &nextd);
1211                 } else
1212                         goto end;
1213
1214                 if ((ret = __bamc_start_decompress(dbc)) != 0)
1215                         goto end;
1216
1217                 /* !nextExists || ikey/idata < nextk/nextd */
1218                 iSmallEnough = 1;
1219
1220                 while (moreCompressed != 0 || iSmallEnough != 0) {
1221                         if (moreCompressed == 0)
1222                                 cmp = 1;
1223                         else if (iSmallEnough == 0)
1224                                 cmp = -1;
1225                         else
1226                                 cmp = __db_compare_both(dbp, cp->currentKey,
1227                                         cp->currentData, &ikey, &idata);
1228
1229                         if (cmp < 0) {
1230                                 if ((ret = __bamc_compress_store(dbc,
1231                                     cp->currentKey, cp->currentData,
1232                                     &prevDestKey, &prevDestData,
1233                                     &destkey, &destbuf)) != 0)
1234                                         goto end;
1235
1236                                 if ((ret = __bam_compress_set_dbt(dbp,
1237                                     &pdestkey, cp->currentKey->data,
1238                                     cp->currentKey->size)) != 0)
1239                                         goto end;
1240                                 if ((ret = __bam_compress_set_dbt(dbp,
1241                                     &pdestdata, cp->currentData->data,
1242                                     cp->currentData->size)) != 0)
1243                                         goto end;
1244                                 prevDestKey = &pdestkey;
1245                                 prevDestData = &pdestdata;
1246                         } else {
1247                                 if (cmp != 0) {
1248                                         /*
1249                                          * Continue until we store the current
1250                                          * chunk, but don't delete any more
1251                                          * entries.
1252                                          */
1253                                         bulk_ret = DB_NOTFOUND;
1254                                         moreStream = 0;
1255                                         iSmallEnough = 0;
1256                                 } else
1257                                         ++chunk_count;
1258
1259 #ifdef DIAGNOSTIC
1260                                 pikey = ikey;
1261                                 pidata = idata;
1262 #endif
1263
1264                                 /* Get the next input key and data */
1265                                 if (stream->next(stream, &ikey, &idata) == 0) {
1266                                         moreStream = 0;
1267                                         iSmallEnough = 0;
1268                                 }
1269
1270 #ifdef DIAGNOSTIC
1271                                 /* Check that the stream is sorted */
1272                                 DB_ASSERT(env, moreStream == 0 ||
1273                                     __db_compare_both(dbp, &ikey, &idata,
1274                                     &pikey, &pidata) >= 0);
1275 #endif
1276
1277                                 /*
1278                                  * Check that !nextExists ||
1279                                  * ikey/idata < nextk/nextd
1280                                  */
1281                                 if (moreStream != 0 && nextExists != 0 &&
1282                                         __db_compare_both(dbp, &ikey,
1283                                             &idata, &nextk, &nextd) >= 0)
1284                                         iSmallEnough = 0;
1285                         }
1286
1287                         if (cmp <= 0) {
1288                                 ret = __bamc_next_decompress(dbc);
1289                                 if (ret == DB_NOTFOUND) {
1290                                         moreCompressed = 0;
1291                                         ret = 0;
1292                                 } else if (ret != 0)
1293                                         goto end;
1294                         }
1295                 }
1296
1297                 if (prevDestKey != NULL) {
1298                         if ((ret = __dbc_iput(
1299                             dbc, &destkey, &destbuf, DB_KEYLAST)) != 0)
1300                                 goto end;
1301
1302                         if (countp)
1303                                 *countp += chunk_count;
1304                         chunk_count = 0;
1305
1306                         prevDestKey = NULL;
1307                         prevDestData = NULL;
1308                         destbuf.size = 0;
1309                 }
1310         }
1311
1312  end:
1313         CMP_FREE_DBT(env, &destkey);
1314         CMP_FREE_DBT(env, &destbuf);
1315         CMP_FREE_DBT(env, &pdestkey);
1316         CMP_FREE_DBT(env, &pdestdata);
1317         CMP_FREE_DBT(env, &nextk);
1318         CMP_FREE_DBT(env, &nextc);
1319
1320         return (ret != 0 ? ret : bulk_ret);
1321 }
1322
1323 /*
1324  * Remove the sorted keys in stream along with all duplicate values from
1325  * the compressed database.
1326  */
1327 static int
1328 __bamc_compress_merge_delete_dups(dbc, stream, countp)
1329         DBC *dbc;
1330         BTREE_COMPRESS_STREAM *stream;
1331         u_int32_t *countp;
1332 {
1333         DBC *dbc_n;
1334         DBT ikey, nextk, noread, destkey, destbuf, pdestkey, pdestdata;
1335 #ifdef DIAGNOSTIC
1336         DBT pikey;
1337 #endif
1338         DBT *prevDestKey, *prevDestData;
1339         int ret, ret_n, bulk_ret, cmp, moreCompressed, moreStream, nextExists;
1340         int iSmallEnough, ifound;
1341         u_int32_t chunk_count;
1342         ENV *env;
1343         BTREE_CURSOR *cp;
1344         DB *dbp;
1345
1346         env = dbc->env;
1347         cp = (BTREE_CURSOR *)dbc->internal;
1348         dbp = dbc->dbp;
1349         bulk_ret = 0;
1350
1351         memset(&ikey, 0, sizeof(DBT));
1352
1353         CMP_INIT_DBT(&nextk);
1354
1355         memset(&noread, 0, sizeof(DBT));
1356         noread.flags = DB_DBT_PARTIAL | DB_DBT_USERMEM;
1357
1358         CMP_INIT_DBT(&pdestkey);
1359         CMP_INIT_DBT(&pdestdata);
1360
1361         CMP_INIT_DBT(&destkey);
1362         CMP_INIT_DBT(&destbuf);
1363         if ((ret = __os_malloc(env, cp->ovflsize, &destbuf.data)) != 0)
1364                 goto end;
1365         destbuf.ulen = cp->ovflsize;
1366
1367         if (countp != NULL)
1368                 *countp = 0;
1369         chunk_count = 0;
1370
1371         /* Get the first input key and data */
1372         ret = 0;
1373         if (stream->next(stream, &ikey, NULL) == 0)
1374                 goto end;
1375         ifound = 0;
1376
1377         prevDestKey = NULL;
1378         prevDestData = NULL;
1379
1380         moreStream = 1;
1381         iSmallEnough = 0;
1382         nextExists = 0;
1383         while (moreStream != 0) {
1384                 if (iSmallEnough != 0) {
1385                         if (nextExists == 0) {
1386                                 /*
1387                                  * We've finished deleting the last key
1388                                  * in the database
1389                                  */
1390                                 if (ifound == 0) {
1391                                         bulk_ret = DB_NOTFOUND;
1392                                 } else
1393                                         ++chunk_count;
1394                                 break;
1395                         }
1396
1397                         /* Move to the next chunk */
1398                         CMP_IGET_RETRY(
1399                             ret, dbc, &cp->key1, &cp->compressed, DB_CURRENT);
1400                         if (ret == DB_NOTFOUND) {
1401                                 ret = 0;
1402                                 break;
1403                         } else if (ret != 0)
1404                                 goto end;
1405                 } else
1406                         /* Seek the ikey position */
1407                         if ((ret =
1408                             __bamc_compress_seek(dbc, &ikey, NULL, 0)) != 0)
1409                                 goto end;
1410
1411                 nextExists = 1;
1412                 moreCompressed = 1;
1413
1414                 /*
1415                  * Delete the key - we might overwrite it below but it's
1416                  * safer to just always delete it, and it doesn't seem
1417                  * significantly slower to do so.
1418                  */
1419                 ret = __bamc_compress_del_and_get_next(dbc, &nextk, &noread);
1420                 if (ret == DB_NOTFOUND) {
1421                         ret = 0;
1422                         nextExists = 0;
1423                 } else if (ret != 0)
1424                         goto end;
1425
1426                 if ((ret = __bamc_start_decompress(dbc)) != 0)
1427                         goto end;
1428
1429                 /* !nextExists || ikey <= nextk */
1430                 iSmallEnough = 1;
1431
1432                 while (moreCompressed != 0) {
1433                         if (moreCompressed == 0)
1434                                 cmp = 1;
1435                         else if (iSmallEnough == 0)
1436                                 cmp = -1;
1437                         else
1438                                 cmp = __db_compare_both(
1439                                     dbp, cp->currentKey, NULL, &ikey, NULL);
1440
1441                         if (cmp < 0) {
1442                                 if ((ret = __bamc_compress_store(dbc,
1443                                     cp->currentKey, cp->currentData,
1444                                     &prevDestKey,
1445                                     &prevDestData, &destkey, &destbuf)) != 0)
1446                                         goto end;
1447
1448                                 if ((ret = __bam_compress_set_dbt(dbp,
1449                                     &pdestkey, cp->currentKey->data,
1450                                     cp->currentKey->size)) != 0)
1451                                         goto end;
1452                                 if ((ret = __bam_compress_set_dbt(dbp,
1453                                      &pdestdata, cp->currentData->data,
1454                                      cp->currentData->size)) != 0)
1455                                         goto end;
1456                                 prevDestKey = &pdestkey;
1457                                 prevDestData = &pdestdata;
1458                         } else if (cmp > 0) {
1459                                 if (ifound == 0) {
1460                                         /*
1461                                          * Continue until we store the
1462                                          * current chunk, but don't delete
1463                                          * any more entries.
1464                                          */
1465                                         bulk_ret = DB_NOTFOUND;
1466                                         moreStream = 0;
1467                                         iSmallEnough = 0;
1468                                 } else
1469                                         ++chunk_count;
1470
1471 #ifdef DIAGNOSTIC
1472                                 pikey = ikey;
1473 #endif
1474
1475                                 /* Get the next input key */
1476                                 if (stream->next(stream, &ikey, NULL) == 0) {
1477                                         moreStream = 0;
1478                                         iSmallEnough = 0;
1479                                 }
1480                                 ifound = 0;
1481
1482 #ifdef DIAGNOSTIC
1483                                 /* Check that the stream is sorted */
1484                                 DB_ASSERT(env, moreStream == 0 ||
1485                                     __db_compare_both(dbp, &ikey, NULL,
1486                                     &pikey, NULL) >= 0);
1487 #endif
1488
1489                                 /* Check that !nextExists || ikey <= nextk */
1490                                 if (moreStream != 0 && nextExists != 0 &&
1491                                      __db_compare_both(dbp,
1492                                      &ikey, NULL, &nextk, NULL) > 0)
1493                                         iSmallEnough = 0;
1494                         } else /* cmp == 0 */
1495                                 ifound = 1;
1496
1497                         if (cmp <= 0) {
1498                                 ret = __bamc_next_decompress(dbc);
1499                                 if (ret == DB_NOTFOUND) {
1500                                         moreCompressed = 0;
1501                                         ret = 0;
1502                                 } else if (ret != 0)
1503                                         goto end;
1504                         }
1505                 }
1506
1507                 if (prevDestKey != NULL) {
1508                         /*
1509                          * Do the DBC->put() with a duplicate cursor, so that
1510                          * the main cursor's position isn't changed - we might
1511                          * need it to be the same in order to use DB_CURRENT
1512                          * above.
1513                          */
1514                         if ((ret = __dbc_dup(dbc, &dbc_n, 0)) != 0)
1515                                 goto end;
1516                         F_SET(dbc_n, DBC_TRANSIENT);
1517
1518                         ret = __dbc_iput(dbc_n, &destkey, &destbuf, DB_KEYLAST);
1519
1520                         if ((ret_n = __dbc_close(dbc_n)) != 0 && ret == 0)
1521                                 ret = ret_n;
1522
1523                         if (ret != 0)
1524                                 goto end;
1525
1526                         if (countp)
1527                                 *countp += chunk_count;
1528                         chunk_count = 0;
1529
1530                         prevDestKey = NULL;
1531                         prevDestData = NULL;
1532                         destbuf.size = 0;
1533                 }
1534         }
1535
1536  end:
1537         CMP_FREE_DBT(env, &destkey);
1538         CMP_FREE_DBT(env, &destbuf);
1539         CMP_FREE_DBT(env, &pdestkey);
1540         CMP_FREE_DBT(env, &pdestdata);
1541         CMP_FREE_DBT(env, &nextk);
1542
1543         return (ret != 0 ? ret : bulk_ret);
1544 }
1545
1546 /******************************************************************************/
1547
1548 /* Implements DB_PREV and DB_LAST for __bamc_compress_get() */
1549 static int
1550 __bamc_compress_get_prev(dbc, flags)
1551         DBC *dbc;
1552         u_int32_t flags;
1553 {
1554         int ret;
1555         u_int32_t tofind;
1556         BTREE_CURSOR *cp;
1557
1558         ret = 0;
1559         cp = (BTREE_CURSOR *)dbc->internal;
1560
1561         F_CLR(cp, C_COMPRESS_DELETED);
1562
1563         if (cp->prevKey != NULL) {
1564                 /* Return the stored previous key */
1565                 cp->currentKey = cp->prevKey;
1566                 cp->currentData = cp->prevData;
1567                 cp->compcursor = cp->prevcursor;
1568                 cp->prevKey = 0;
1569                 cp->prevData = 0;
1570                 cp->prevcursor = cp->prev2cursor;
1571                 cp->prev2cursor = 0;
1572         } else {
1573                 if (cp->currentKey == NULL) {
1574                         /* No current key, so fetch the last key */
1575                         flags |= DB_LAST;
1576                         tofind = (u_int32_t)-1;
1577                 } else if (cp->prevcursor == 0) {
1578                         /*
1579                          * The current key is at the begining of the
1580                          * compressed block, so get the last key from the
1581                          * previous block
1582                          */
1583                         flags |= DB_PREV;
1584                         tofind = (u_int32_t)-1;
1585                 } else {
1586                         /*
1587                          * We have to search for the previous key in the
1588                          * current block
1589                          */
1590                         flags |= DB_CURRENT;
1591                         tofind = (u_int32_t)
1592                             (cp->prevcursor - (u_int8_t*)cp->compressed.data);
1593                 }
1594
1595                 CMP_IGET_RETRY(ret, dbc, &cp->key1, &cp->compressed, flags);
1596                 if (ret != 0)
1597                         return (ret);
1598
1599                 /* Decompress until we reach tofind */
1600                 ret = __bamc_start_decompress(dbc);
1601                 while (ret == 0 && tofind > (u_int32_t)
1602                         (cp->compcursor - (u_int8_t*)cp->compressed.data)) {
1603                         ret = __bamc_next_decompress(dbc);
1604                 }
1605
1606                 if (ret == DB_NOTFOUND)
1607                         ret = 0;
1608         }
1609
1610         return (ret);
1611 }
1612
1613 /* Implements DB_PREV_DUP for __bamc_compress_get() */
1614 static int
1615 __bamc_compress_get_prev_dup(dbc, flags)
1616         DBC *dbc;
1617         u_int32_t flags;
1618 {
1619         int ret;
1620         BTREE_CURSOR *cp;
1621         DB *dbp;
1622         BTREE *t;
1623
1624         ret = 0;
1625         cp = (BTREE_CURSOR *)dbc->internal;
1626         dbp = dbc->dbp;
1627         t = (BTREE *)dbp->bt_internal;
1628
1629         if (cp->currentKey == 0)
1630                 return (EINVAL);
1631
1632         /* If this is a deleted entry, del_key is already set, otherwise we
1633            have to set it now */
1634         if (!F_ISSET(cp, C_COMPRESS_DELETED)) {
1635                 if ((ret = __bam_compress_set_dbt(dbp, &cp->del_key,
1636                             cp->currentKey->data, cp->currentKey->size)) != 0)
1637                         return (ret);
1638         }
1639
1640         if ((ret = __bamc_compress_get_prev(dbc, flags)) != 0)
1641                 return (ret);
1642
1643         if (t->bt_compare(dbp, cp->currentKey, &cp->del_key) != 0)
1644                 return (DB_NOTFOUND);
1645
1646         return (0);
1647 }
1648
1649 /* Implements DB_PREV_NODUP for __bamc_compress_get() */
1650 static int
1651 __bamc_compress_get_prev_nodup(dbc, flags)
1652         DBC *dbc;
1653         u_int32_t flags;
1654 {
1655         int ret;
1656         BTREE_CURSOR *cp;
1657         DB *dbp;
1658         BTREE *t;
1659
1660         cp = (BTREE_CURSOR *)dbc->internal;
1661         dbp = dbc->dbp;
1662         t = (BTREE *)dbp->bt_internal;
1663
1664         if (cp->currentKey == 0)
1665                 return (__bamc_compress_get_prev(dbc, flags));
1666
1667         /*
1668          * If this is a deleted entry, del_key is already set, otherwise we
1669          * have to set it now.
1670          */
1671         if (!F_ISSET(cp, C_COMPRESS_DELETED))
1672                 if ((ret = __bam_compress_set_dbt(dbp, &cp->del_key,
1673                     cp->currentKey->data, cp->currentKey->size)) != 0)
1674                         return (ret);
1675
1676         /*
1677          * Linear search for the next non-duplicate key - this is
1678          * especially inefficient for DB_PREV_NODUP, since we have to
1679          * decompress from the begining of the chunk to find previous
1680          * key/data pairs. Instead we could check for key equality as we
1681          * decompress.
1682          */
1683         do
1684                 if ((ret = __bamc_compress_get_prev(dbc, flags)) != 0)
1685                         return (ret);
1686         while (t->bt_compare(dbp, cp->currentKey, &cp->del_key) == 0);
1687
1688         return (0);
1689 }
1690
1691 /* Implements DB_NEXT and DB_FIRST for __bamc_compress_get() */
1692 static int
1693 __bamc_compress_get_next(dbc, flags)
1694         DBC *dbc;
1695         u_int32_t flags;
1696 {
1697         int ret;
1698         BTREE_CURSOR *cp;
1699
1700         cp = (BTREE_CURSOR *)dbc->internal;
1701
1702         if (F_ISSET(cp, C_COMPRESS_DELETED)) {
1703                 if (cp->currentKey == 0)
1704                         return (DB_NOTFOUND);
1705                 F_CLR(cp, C_COMPRESS_DELETED);
1706                 return (0);
1707         } else if (cp->currentKey) {
1708                 ret = __bamc_next_decompress(dbc);
1709                 if (ret != DB_NOTFOUND)
1710                         return (ret);
1711
1712                 flags |= DB_NEXT;
1713         } else
1714                 flags |= DB_FIRST;
1715
1716         CMP_IGET_RETRY(ret, dbc, &cp->key1, &cp->compressed, flags);
1717         if (ret == DB_NOTFOUND) {
1718                 /*
1719                  * Reset the cursor, so that
1720                  * __bamc_compress_get_multiple_key will end up pointing
1721                  * to the right place
1722                  */
1723                 __bamc_compress_reset(dbc);
1724                 return (DB_NOTFOUND);
1725         } else if (ret != 0)
1726                 return (ret);
1727
1728         ret = __bamc_start_decompress(dbc);
1729
1730         return (ret);
1731 }
1732
1733 /* Implements DB_NEXT_DUP for __bamc_compress_get() */
1734 static int
1735 __bamc_compress_get_next_dup(dbc, key, flags)
1736         DBC *dbc;
1737         DBT *key;
1738         u_int32_t flags;
1739 {
1740         int ret;
1741         BTREE_CURSOR *cp;
1742         DB *dbp;
1743         BTREE *t;
1744
1745         cp = (BTREE_CURSOR *)dbc->internal;
1746         dbp = dbc->dbp;
1747         t = (BTREE *)dbp->bt_internal;
1748
1749         if (cp->currentKey == 0)
1750                 return (EINVAL);
1751
1752         if (F_ISSET(cp, C_COMPRESS_DELETED)) {
1753                 /*
1754                  * Check that the next entry has the same key as the
1755                  * deleted entry.
1756                  */
1757                 if (cp->currentKey == 0)
1758                         return (DB_NOTFOUND);
1759                 F_CLR(cp, C_COMPRESS_DELETED);
1760                 return (t->bt_compare(dbp,
1761                     cp->currentKey, &cp->del_key) == 0 ? 0 : DB_NOTFOUND);
1762         }
1763
1764         /* Check that the next entry has the same key as the previous entry */
1765         ret = __bamc_next_decompress(dbc);
1766         if (ret == 0 && t->bt_compare(dbp, cp->currentKey, cp->prevKey) != 0)
1767                 return (DB_NOTFOUND);
1768         if (ret != DB_NOTFOUND)
1769                 return (ret);
1770
1771         if (key == NULL) {
1772                 /* Copy the current key to del_key */
1773                 if ((ret = __bam_compress_set_dbt(dbp, &cp->del_key,
1774                     cp->currentKey->data, cp->currentKey->size)) != 0)
1775                         return (ret);
1776                 key = &cp->del_key;
1777         }
1778
1779         /* Fetch the next chunk */
1780         CMP_IGET_RETRY(ret, dbc, &cp->key1, &cp->compressed, DB_NEXT | flags);
1781         if (ret == DB_NOTFOUND) {
1782                 /*
1783                  * Reset the cursor, so that __bamc_compress_get_multiple
1784                  * will end up pointing to the right place
1785                  */
1786                 __bamc_compress_reset(dbc);
1787                 return (DB_NOTFOUND);
1788         } else if (ret != 0)
1789                 return (ret);
1790
1791         if ((ret = __bamc_start_decompress(dbc)) != 0)
1792                 return (ret);
1793
1794         /* Check the keys are the same */
1795         if (t->bt_compare(dbp, cp->currentKey, key) != 0)
1796                 return (DB_NOTFOUND);
1797
1798         return (0);
1799 }
1800
1801 /* Implements DB_NEXT_NODUP for __bamc_compress_get() */
1802 static int
1803 __bamc_compress_get_next_nodup(dbc, flags)
1804         DBC *dbc;
1805         u_int32_t flags;
1806 {
1807         int ret;
1808         BTREE_CURSOR *cp;
1809         DB *dbp;
1810         BTREE *t;
1811
1812         cp = (BTREE_CURSOR *)dbc->internal;
1813         dbp = dbc->dbp;
1814         t = (BTREE *)dbp->bt_internal;
1815
1816         if (cp->currentKey == 0)
1817                 return (__bamc_compress_get_next(dbc, flags));
1818
1819         /*
1820          * If this is a deleted entry, del_key is already set, otherwise
1821          * we have to set it now
1822          */
1823         if (!F_ISSET(cp, C_COMPRESS_DELETED))
1824                 if ((ret = __bam_compress_set_dbt(dbp, &cp->del_key,
1825                     cp->currentKey->data, cp->currentKey->size)) != 0)
1826                         return (ret);
1827
1828         /* Linear search for the next non-duplicate key */
1829         do
1830                 if ((ret = __bamc_compress_get_next(dbc, flags)) != 0)
1831                         return (ret);
1832         while (t->bt_compare(dbp, cp->currentKey, &cp->del_key) == 0);
1833
1834         return (ret);
1835 }
1836
1837 /*
1838  * Implements DB_SET, DB_SET_RANGE, DB_GET_BOTH, and DB_GET_BOTH_RANGE
1839  * for __bamc_compress_get()
1840  */
1841 static int
1842 __bamc_compress_get_set(dbc, key, data, method, flags)
1843         DBC *dbc;
1844         DBT *key;
1845         DBT *data;
1846         u_int32_t method;
1847         u_int32_t flags;
1848 {
1849         int ret, cmp;
1850         BTREE_CURSOR *cp;
1851         DB *dbp;
1852
1853         cp = (BTREE_CURSOR *)dbc->internal;
1854         dbp = dbc->dbp;
1855
1856         if (method == DB_SET || method == DB_SET_RANGE)
1857             data = NULL;
1858
1859         F_CLR(cp, C_COMPRESS_DELETED);
1860
1861         ret = __bamc_compress_seek(dbc, key, data, flags);
1862         if (ret == DB_NOTFOUND)
1863                 CMP_IGET_RETRY(ret, dbc,
1864                     &cp->key1, &cp->compressed, DB_FIRST | flags);
1865         if (ret != 0)
1866                 return (ret);
1867
1868         /* Decompress and perform a linear search for the key */
1869         cmp = 0;
1870         ret = __bamc_start_decompress(dbc);
1871         while (ret == 0 && (cmp = __db_compare_both(dbp,
1872            cp->currentKey, cp->currentData, key, data)) < 0) {
1873                 ret = __bamc_next_decompress(dbc);
1874                 if (ret == DB_NOTFOUND) {
1875                         CMP_IGET_RETRY(ret, dbc,
1876                             &cp->key1, &cp->compressed, DB_NEXT | flags);
1877                         if (ret == 0)
1878                             ret = __bamc_start_decompress(dbc);
1879                 }
1880         }
1881
1882         switch (method) {
1883         case DB_SET:
1884         case DB_GET_BOTH_RANGE:
1885                 /*
1886                  * We need to exactly match the key, and if cmp != 0 we
1887                  * might not have - so check again here.
1888                  */
1889                 if (ret == 0 &&
1890                     __db_compare_both(dbp, cp->currentKey, 0, key, 0) != 0) {
1891                         /* We didn't find the key */
1892                         ret = DB_NOTFOUND;
1893                 }
1894                 break;
1895         case DB_GET_BOTH:
1896                 if (ret == 0 && (cmp != 0 || (!F_ISSET(dbp, DB_AM_DUPSORT) &&
1897                     __bam_defcmp(dbp, cp->currentData, data) != 0))) {
1898                         /* We didn't find the key/data pair */
1899                         ret = DB_NOTFOUND;
1900                 }
1901                 break;
1902         default:
1903                 DB_ASSERT(dbp->env, method == 0 || method == DB_SET_RANGE);
1904         }
1905
1906         return (ret);
1907 }
1908
1909 /* Implements DB_GET_BOTHC for __bamc_compress_get() */
1910 static int
1911 __bamc_compress_get_bothc(dbc, data, flags)
1912         DBC *dbc;
1913         DBT *data;
1914         u_int32_t flags;
1915 {
1916         int ret, cmp;
1917         BTREE_CURSOR *cp;
1918         DB *dbp;
1919
1920         cp = (BTREE_CURSOR *)dbc->internal;
1921         dbp = dbc->dbp;
1922
1923         /* Check that the data we are looking for comes after the current
1924            position */
1925         if (__db_compare_both(dbp, cp->currentKey,
1926             cp->currentData, cp->currentKey, data) >= 0)
1927                 return (DB_NOTFOUND);
1928
1929         cmp = 0;
1930         /* Perform a linear search for the data in the current chunk */
1931         while ((ret = __bamc_next_decompress(dbc)) == 0 &&
1932             (cmp = __db_compare_both(
1933             dbp, cp->currentKey, cp->currentData, cp->prevKey, data)) < 0)
1934                 continue;
1935
1936         if (ret == 0)
1937                 return (cmp == 0 ? 0 : DB_NOTFOUND);
1938         if (ret != DB_NOTFOUND)
1939                 return (ret);
1940
1941         /* Copy the current key to del_key */
1942         if ((ret = __bam_compress_set_dbt(dbp, &cp->del_key,
1943                     cp->currentKey->data, cp->currentKey->size)) != 0)
1944                 return (ret);
1945
1946         /* Search for the data using DB_GET_BOTH */
1947         return __bamc_compress_get_set(
1948             dbc, &cp->del_key, data, DB_GET_BOTH, flags);
1949 }
1950
1951 /* Implements DB_MULTIPLE_KEY for __bamc_compress_get() */
1952 static int
1953 __bamc_compress_get_multiple_key(dbc, data, flags)
1954         DBC *dbc;
1955         DBT *data;
1956         u_int32_t flags;
1957 {
1958         int ret;
1959         u_int8_t *writekey, *writedata;
1960         void *mptr;
1961         BTREE_CURSOR *cp;
1962
1963         ret = 0;
1964         cp = (BTREE_CURSOR *)dbc->internal;
1965
1966         DB_MULTIPLE_WRITE_INIT(mptr, data);
1967         DB_MULTIPLE_KEY_RESERVE_NEXT(mptr, data, writekey, cp->currentKey->size,
1968                 writedata, cp->currentData->size);
1969         if (writekey == NULL) {
1970                 data->size = cp->currentKey->size + cp->currentData->size +
1971                         4 * sizeof(u_int32_t);
1972                 return DB_BUFFER_SMALL;
1973         }
1974         DB_ASSERT(dbc->dbp->env, writedata != NULL);
1975
1976         memcpy(writekey, cp->currentKey->data, cp->currentKey->size);
1977         memcpy(writedata, cp->currentData->data, cp->currentData->size);
1978
1979         while ((ret = __bamc_compress_get_next(dbc, flags)) == 0) {
1980                 DB_MULTIPLE_KEY_RESERVE_NEXT(mptr, data, writekey,
1981                     cp->currentKey->size, writedata, cp->currentData->size);
1982                 if (writekey == NULL)
1983                         break;
1984                 DB_ASSERT(dbc->dbp->env, writedata != NULL);
1985
1986                 /*
1987                  * We could choose to optimize this by just storing one
1988                  * copy of a key for each set of duplicate data.
1989                  */
1990                 memcpy(writekey, cp->currentKey->data, cp->currentKey->size);
1991                 memcpy(writedata, cp->currentData->data, cp->currentData->size);
1992         }
1993
1994         if (ret == DB_NOTFOUND)
1995                 ret = 0;
1996
1997         if (ret == 0)
1998                 /*
1999                  * Rewind to the previous key/data, since we can't fit
2000                  * this one in the buffer
2001                  */
2002                 ret = __bamc_compress_get_prev(dbc, flags);
2003
2004         return (ret);
2005 }
2006
2007 /* Implements DB_MULTIPLE for __bamc_compress_get() */
2008 static int
2009 __bamc_compress_get_multiple(dbc, key, data, flags)
2010         DBC *dbc;
2011         DBT *key, *data;
2012         u_int32_t flags;
2013 {
2014         int ret;
2015         u_int8_t *writedata;
2016         void *mptr;
2017         BTREE_CURSOR *cp;
2018
2019         ret = 0;
2020         cp = (BTREE_CURSOR *)dbc->internal;
2021
2022         data->size = 0;
2023
2024         DB_MULTIPLE_WRITE_INIT(mptr, data);
2025         DB_MULTIPLE_RESERVE_NEXT(mptr, data, writedata, cp->currentData->size);
2026         data->size += cp->currentData->size + 2 * sizeof(u_int32_t);
2027         if (writedata == NULL)
2028                 return DB_BUFFER_SMALL;
2029
2030         memcpy(writedata, cp->currentData->data, cp->currentData->size);
2031
2032         while ((ret = __bamc_compress_get_next_dup(dbc, key, flags)) == 0) {
2033                 DB_MULTIPLE_RESERVE_NEXT(
2034                     mptr, data, writedata, cp->currentData->size);
2035                 data->size += cp->currentData->size + 2 * sizeof(u_int32_t);
2036                 if (writedata == NULL) {
2037                         /* DBC_FROM_DB_GET indicates we need to fit all the
2038                          * duplicates into the buffer or return DB_BUFFER_SMALL.
2039                          * [#17039]
2040                          */
2041                         if (F_ISSET(dbc, DBC_FROM_DB_GET))
2042                                 return DB_BUFFER_SMALL;
2043                         break;
2044                 }
2045
2046                 memcpy(writedata, cp->currentData->data, cp->currentData->size);
2047         }
2048
2049         if (ret == DB_NOTFOUND)
2050                 ret = 0;
2051
2052         if (ret == 0)
2053                 /*
2054                  * Rewind to the previous key/data, as that's now our current
2055                  * entry.
2056                  */
2057                 ret = __bamc_compress_get_prev(dbc, flags);
2058
2059         return (ret);
2060 }
2061
2062 /*
2063  * __bamc_compress_iget --
2064  *      Get using a compressed cursor. (internal)
2065  */
2066 static int
2067 __bamc_compress_iget(dbc, key, data, flags)
2068         DBC *dbc;
2069         DBT *key, *data;
2070         u_int32_t flags;
2071 {
2072         int ret;
2073         u_int32_t multiple, method;
2074         BTREE_CURSOR *cp;
2075         DB *dbp;
2076
2077         cp = (BTREE_CURSOR *)dbc->internal;
2078         dbp = dbc->dbp;
2079         ret = 0;
2080
2081         multiple = flags & (DB_MULTIPLE|DB_MULTIPLE_KEY);
2082         method = flags & DB_OPFLAGS_MASK;
2083         flags = flags & ~(DB_OPFLAGS_MASK|DB_MULTIPLE|DB_MULTIPLE_KEY);
2084
2085         switch (method) {
2086         case DB_CURRENT:
2087                 if (F_ISSET(cp, C_COMPRESS_DELETED))
2088                         ret = DB_KEYEMPTY;
2089                 else if (cp->currentKey == NULL)
2090                         ret = EINVAL;
2091                 break;
2092         case DB_FIRST:
2093                 __bamc_compress_reset(dbc);
2094                 ret = __bamc_compress_get_next(dbc, flags);
2095                 break;
2096         case DB_NEXT:
2097                 ret = __bamc_compress_get_next(dbc, flags);
2098                 break;
2099         case DB_NEXT_DUP:
2100                 ret = __bamc_compress_get_next_dup(dbc, 0, flags);
2101                 break;
2102         case DB_NEXT_NODUP:
2103                 ret = __bamc_compress_get_next_nodup(dbc, flags);
2104                 break;
2105         case DB_LAST:
2106                 __bamc_compress_reset(dbc);
2107                 ret = __bamc_compress_get_prev(dbc, flags);
2108                 break;
2109         case DB_PREV:
2110                 ret = __bamc_compress_get_prev(dbc, flags);
2111                 break;
2112         case DB_PREV_DUP:
2113                 ret = __bamc_compress_get_prev_dup(dbc, flags);
2114                 break;
2115         case DB_PREV_NODUP:
2116                 ret = __bamc_compress_get_prev_nodup(dbc, flags);
2117                 break;
2118         case DB_SET:
2119                 if (((BTREE *)
2120                     dbc->dbp->bt_internal)->bt_compare == __bam_defcmp)
2121                         F_SET(key, DB_DBT_ISSET);
2122                 /* FALL THROUGH */
2123         case DB_SET_RANGE:
2124                 ret = __bamc_compress_get_set(dbc, key, 0, method, flags);
2125                 break;
2126         case DB_GET_BOTH:
2127                 if (!F_ISSET(dbc->dbp, DB_AM_DUPSORT) || ((BTREE *)dbc->dbp->
2128                    bt_internal)->compress_dup_compare == __bam_defcmp)
2129                         F_SET(data, DB_DBT_ISSET);
2130                 /* FALL THROUGH */
2131         case DB_GET_BOTH_RANGE:
2132                 if (((BTREE *)
2133                     dbc->dbp->bt_internal)->bt_compare == __bam_defcmp)
2134                         F_SET(key, DB_DBT_ISSET);
2135                 ret = __bamc_compress_get_set(dbc, key, data, method, flags);
2136                 break;
2137         case DB_GET_BOTHC:
2138                 ret = __bamc_compress_get_bothc(dbc, data, flags);
2139                 break;
2140         default:
2141                 ret = __db_unknown_flag(dbp->env, "__bamc_compress_iget",
2142                         method);
2143                 break;
2144         }
2145
2146         if (ret != 0)
2147                 goto err;
2148
2149         switch (multiple) {
2150         case 0:
2151                 if (!F_ISSET(key, DB_DBT_ISSET))
2152                         ret = __db_retcopy(dbc->env, key,
2153                                 cp->currentKey->data, cp->currentKey->size,
2154                                 &dbc->rkey->data, &dbc->rkey->ulen);
2155                 if (!F_ISSET(data, DB_DBT_ISSET) && ret == 0)
2156                         ret = __db_retcopy(dbc->env, data,
2157                                 cp->currentData->data, cp->currentData->size,
2158                                 &dbc->rdata->data, &dbc->rdata->ulen);
2159                 break;
2160         case DB_MULTIPLE:
2161                 if (!F_ISSET(key, DB_DBT_ISSET))
2162                         ret = __db_retcopy(dbc->env, key,
2163                                 cp->currentKey->data, cp->currentKey->size,
2164                                 &dbc->rkey->data, &dbc->rkey->ulen);
2165                 if (ret == 0)
2166                         ret =
2167                             __bamc_compress_get_multiple(dbc, key, data, flags);
2168                 break;
2169         case DB_MULTIPLE_KEY:
2170                 ret = __bamc_compress_get_multiple_key(dbc, data, flags);
2171                 break;
2172         default:
2173                 ret = __db_unknown_flag(dbp->env, "__bamc_compress_iget",
2174                         multiple);
2175                 break;
2176         }
2177
2178  err:
2179         F_CLR(key, DB_DBT_ISSET);
2180         F_CLR(data, DB_DBT_ISSET);
2181
2182         return (ret);
2183 }
2184
2185 /*
2186  * __bamc_compress_get --
2187  *      Get using a compressed cursor.
2188  *
2189  * PUBLIC: int __bamc_compress_get __P((DBC *, DBT *, DBT *, u_int32_t));
2190  */
2191 int
2192 __bamc_compress_get(dbc, key, data, flags)
2193         DBC *dbc;
2194         DBT *key, *data;
2195         u_int32_t flags;
2196 {
2197         DBC *dbc_n;
2198         int ret, t_ret;
2199         u_int32_t tmp_flags;
2200
2201         switch (flags & DB_OPFLAGS_MASK) {
2202         case DB_CURRENT:
2203         case DB_GET_BOTHC:
2204         case DB_NEXT:
2205         case DB_NEXT_DUP:
2206         case DB_NEXT_NODUP:
2207         case DB_PREV:
2208         case DB_PREV_DUP:
2209         case DB_PREV_NODUP:
2210                 if (F_ISSET((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED)
2211                     && (ret = __bamc_compress_relocate(dbc)) != 0)
2212                         return (ret);
2213                 tmp_flags = DB_POSITION;
2214                 break;
2215         default:
2216                 F_CLR((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED);
2217                 tmp_flags = 0;
2218                 break;
2219         }
2220
2221         if (F_ISSET(dbc, DBC_TRANSIENT))
2222                 dbc_n = dbc;
2223         else {
2224                 if ((ret = __dbc_dup(dbc, &dbc_n, tmp_flags)) != 0)
2225                         goto err;
2226
2227                 /*
2228                  * We don't care about preserving the cursor's position on
2229                  * error.
2230                  */
2231                 F_SET(dbc_n, DBC_TRANSIENT);
2232
2233                 COPY_RET_MEM(dbc, dbc_n);
2234         }
2235
2236         if ((ret = __bamc_compress_iget(dbc_n, key, data, flags)) != 0)
2237                 goto err;
2238
2239 err:
2240         /* Cleanup and cursor resolution. */
2241         if ((t_ret = __dbc_cleanup(dbc, dbc_n, ret)) != 0 &&
2242                 (ret == 0 || ret == DB_BUFFER_SMALL))
2243                 ret = t_ret;
2244         return (ret);
2245 }
2246
2247 /*
2248  * __bamc_compress_iput --
2249  *      Put using a compressed cursor (internal)
2250  */
2251 static int
2252 __bamc_compress_iput(dbc, key, data, flags)
2253         DBC *dbc;
2254         DBT *key, *data;
2255         u_int32_t flags;
2256 {
2257         int ret;
2258         u_int32_t multi;
2259         DBT kcpy, pdata, empty;
2260         BTREE_COMPRESS_STREAM stream;
2261         BTREE_CURSOR *cp;
2262         DB *dbp;
2263         ENV *env;
2264
2265         cp = (BTREE_CURSOR *)dbc->internal;
2266         dbp = dbc->dbp;
2267         env = dbc->env;
2268
2269         memset(&pdata, 0, sizeof(DBT));
2270         memset(&empty, 0, sizeof(DBT));
2271
2272         multi = LF_ISSET(DB_MULTIPLE|DB_MULTIPLE_KEY);
2273         LF_CLR(DB_MULTIPLE|DB_MULTIPLE_KEY);
2274
2275         switch (flags) {
2276         case DB_CURRENT:
2277                 if (cp->currentKey == 0 || F_ISSET(cp, C_COMPRESS_DELETED)) {
2278                         ret = DB_NOTFOUND;
2279                         goto end;
2280                 }
2281
2282                 if (F_ISSET(data, DB_DBT_PARTIAL)) {
2283                         if ((ret = __db_buildpartial(
2284                             dbp, cp->currentData, data, &pdata)) != 0)
2285                                 goto end;
2286                         data = &pdata;
2287                 }
2288
2289                 if (F_ISSET(dbp, DB_AM_DUPSORT) &&
2290                     ((BTREE *)dbp->bt_internal)->compress_dup_compare(
2291                     dbp, cp->currentData, data) != 0) {
2292                         __db_errx(env,
2293                             "Existing data sorts differently from put data");
2294                         ret = EINVAL;
2295                         goto end;
2296                 }
2297                 CMP_INIT_DBT(&kcpy);
2298                 if ((ret = __bam_compress_set_dbt(dbp,
2299                     &kcpy, cp->currentKey->data, cp->currentKey->size)) != 0)
2300                         goto end;
2301
2302                 __bam_cs_create_single(&stream, &kcpy, data);
2303                 ret = __bamc_compress_merge_insert(dbc, &stream, NULL, flags);
2304
2305                 if (ret == 0)
2306                         /* Position the cursor on the entry written */
2307                         ret = __bamc_compress_get_set(
2308                             dbc, &kcpy, data, DB_GET_BOTH_RANGE, 0);
2309
2310                 CMP_FREE_DBT(env, &kcpy);
2311                 break;
2312         case DB_KEYFIRST:
2313         case DB_KEYLAST:
2314         case DB_NODUPDATA:
2315         case DB_OVERWRITE_DUP:
2316                 switch (multi) {
2317                 case 0:
2318                         if (F_ISSET(data, DB_DBT_PARTIAL)) {
2319                                 if ((ret = __bamc_compress_get_set(dbc, key,
2320                                     data, DB_SET, 0)) != 0 &&
2321                                     ret != DB_NOTFOUND)
2322                                         goto end;
2323                                 if ((ret = __db_buildpartial(dbp,
2324                                     ret == DB_NOTFOUND ? &empty :
2325                                     cp->currentData, data, &pdata)) != 0)
2326                                         goto end;
2327                                 data = &pdata;
2328                         }
2329
2330                         __bam_cs_create_single(&stream, key, data);
2331                         ret = __bamc_compress_merge_insert(
2332                             dbc, &stream, NULL, flags);
2333
2334                         if (ret == 0)
2335                                 /* Position the cursor on the entry written */
2336                                 ret = __bamc_compress_get_set(
2337                                     dbc, key, data, DB_GET_BOTH_RANGE, 0);
2338                         break;
2339                 case DB_MULTIPLE:
2340                         __bam_cs_create_multiple(&stream, key, data);
2341                         ret = __bamc_compress_merge_insert(
2342                             dbc, &stream, &key->doff, flags);
2343                         break;
2344                 case DB_MULTIPLE_KEY:
2345                         __bam_cs_create_multiple_key(&stream, key);
2346                         ret = __bamc_compress_merge_insert(
2347                             dbc, &stream, &key->doff, flags);
2348                         break;
2349                 default:
2350                         return (__db_unknown_flag(
2351                             dbp->env, "__bamc_compress_iput", multi));
2352                 }
2353                 break;
2354         case DB_NOOVERWRITE:
2355                 /* Check key doesn't already exist */
2356                 ret = __bamc_compress_get_set(dbc, key, 0, DB_SET, 0);
2357                 if (ret != DB_NOTFOUND) {
2358                         if (ret == 0)
2359                                 ret = DB_KEYEXIST;
2360                         goto end;
2361                 }
2362
2363                 if (F_ISSET(data, DB_DBT_PARTIAL)) {
2364                         if ((ret = __db_buildpartial(
2365                             dbp, &empty, data, &pdata)) != 0)
2366                                 goto end;
2367                         data = &pdata;
2368                 }
2369
2370                 __bam_cs_create_single(&stream, key, data);
2371                 ret = __bamc_compress_merge_insert(dbc, &stream, NULL, flags);
2372
2373                 if (ret == 0)
2374                         /* Position the cursor on the entry written */
2375                         ret = __bamc_compress_get_set(
2376                             dbc, key, data, DB_GET_BOTH_RANGE, 0);
2377                 break;
2378         default:
2379                 return (__db_unknown_flag(
2380                     dbp->env, "__bamc_compress_iput", flags));
2381         }
2382
2383  end:
2384         if (pdata.data != NULL)
2385                 __os_free(env, pdata.data);
2386         return (ret);
2387 }
2388
2389 /*
2390  * __bamc_compress_put --
2391  *      Put using a compressed cursor.
2392  *
2393  * PUBLIC: int __bamc_compress_put __P((DBC *, DBT *, DBT *, u_int32_t));
2394  */
2395 int
2396 __bamc_compress_put(dbc, key, data, flags)
2397         DBC *dbc;
2398         DBT *key, *data;
2399         u_int32_t flags;
2400 {
2401         DBC *dbc_n;
2402         int ret, t_ret;
2403
2404         if (F_ISSET((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED)) {
2405                 if ((flags & DB_OPFLAGS_MASK) == DB_CURRENT &&
2406                     (ret = __bamc_compress_relocate(dbc)) != 0)
2407                         return (ret);
2408                 F_CLR((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED);
2409         }
2410
2411         if (F_ISSET(dbc, DBC_TRANSIENT))
2412                 dbc_n = dbc;
2413         else {
2414                 if ((ret = __dbc_dup(dbc, &dbc_n,
2415                     (flags & DB_OPFLAGS_MASK) == DB_CURRENT ?
2416                     DB_POSITION : 0)) != 0)
2417                         goto err;
2418
2419                 /*
2420                  * We don't care about preserving the cursor's position on
2421                  * error.
2422                  */
2423                 F_SET(dbc_n, DBC_TRANSIENT);
2424         }
2425
2426         if ((ret = __bamc_compress_iput(dbc_n, key, data, flags)) != 0)
2427                 goto err;
2428
2429 err:
2430         /* Cleanup and cursor resolution. */
2431         if ((t_ret = __dbc_cleanup(dbc, dbc_n, ret)) != 0 &&
2432                 (ret == 0 || ret == DB_BUFFER_SMALL))
2433                 ret = t_ret;
2434         return (ret);
2435 }
2436
2437 /*
2438  * __bamc_compress_idel --
2439  *      Del using a compressed cursor. (internal)
2440  */
2441 static int
2442 __bamc_compress_idel(dbc, flags)
2443         DBC *dbc;
2444         u_int32_t flags;
2445 {
2446         int ret;
2447         BTREE_COMPRESS_STREAM stream;
2448         DB *dbp;
2449         BTREE_CURSOR *cp;
2450
2451         COMPQUIET(flags, 0);
2452
2453         dbp = dbc->dbp;
2454         cp = (BTREE_CURSOR *)dbc->internal;
2455
2456         if (F_ISSET(cp, C_COMPRESS_DELETED))
2457                 return DB_KEYEMPTY;
2458         if (cp->currentKey == 0)
2459                 return DB_NOTFOUND;
2460
2461         if ((ret = __bam_compress_set_dbt(dbp, &cp->del_key,
2462                      cp->currentKey->data, cp->currentKey->size)) != 0)
2463                 goto err;
2464         if ((ret = __bam_compress_set_dbt(dbp, &cp->del_data,
2465                      cp->currentData->data, cp->currentData->size)) != 0)
2466                 goto err;
2467
2468         __bam_cs_create_single(&stream, &cp->del_key, &cp->del_data);
2469         if ((ret = __bamc_compress_merge_delete(dbc, &stream, NULL)) != 0)
2470                 goto err;
2471
2472         /* Position the cursor on the entry after the key/data deleted */
2473         ret = __bamc_compress_get_set(dbc, &cp->del_key, &cp->del_data, 0, 0);
2474         if (ret == DB_NOTFOUND) {
2475                 __bamc_compress_reset(dbc);
2476                 ret = 0;
2477         } else if (ret != 0)
2478                 goto err;
2479
2480         /* Mark current as being deleted */
2481         F_SET(cp, C_COMPRESS_DELETED);
2482
2483  err:
2484         return (ret);
2485 }
2486
2487 /*
2488  * __bamc_compress_del --
2489  *      Del using a compressed cursor.
2490  *
2491  * PUBLIC: int __bamc_compress_del __P((DBC *, u_int32_t));
2492  */
2493 int
2494 __bamc_compress_del(dbc, flags)
2495         DBC *dbc;
2496         u_int32_t flags;
2497 {
2498         int ret, t_ret;
2499         DBC *dbc_n;
2500
2501         if (F_ISSET((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED) &&
2502             (ret = __bamc_compress_relocate(dbc)) != 0)
2503                 return (ret);
2504
2505         if (F_ISSET(dbc, DBC_TRANSIENT))
2506                 dbc_n = dbc;
2507         else {
2508                 if ((ret = __dbc_dup(dbc, &dbc_n, DB_POSITION)) != 0)
2509                         goto err;
2510
2511                 /*
2512                  * We don't care about preserving the cursor's position on
2513                  * error.
2514                  */
2515                 F_SET(dbc_n, DBC_TRANSIENT);
2516
2517                 COPY_RET_MEM(dbc, dbc_n);
2518         }
2519
2520         if ((ret = __bamc_compress_idel(dbc_n, flags)) != 0)
2521                 goto err;
2522
2523 err:
2524         /* Cleanup and cursor resolution. */
2525         if ((t_ret = __dbc_cleanup(dbc, dbc_n, ret)) != 0 &&
2526                 (ret == 0 || ret == DB_BUFFER_SMALL))
2527                 ret = t_ret;
2528         return (ret);
2529 }
2530
2531 /*
2532  * __bamc_compress_ibulk_del --
2533  *      Bulk del using a compressed cursor. (internal)
2534  */
2535 static int
2536 __bamc_compress_ibulk_del(dbc, key, flags)
2537         DBC *dbc;
2538         DBT *key;
2539         u_int32_t flags;
2540 {
2541         BTREE_COMPRESS_STREAM stream;
2542
2543         switch (flags) {
2544         case 0:
2545                 __bam_cs_create_single_keyonly(&stream, key);
2546                 return (__bamc_compress_merge_delete_dups(dbc, &stream, NULL));
2547         case DB_MULTIPLE:
2548                 __bam_cs_create_multiple_keyonly(&stream, key);
2549                 return (__bamc_compress_merge_delete_dups(
2550                     dbc, &stream, &key->doff));
2551         case DB_MULTIPLE_KEY:
2552                 __bam_cs_create_multiple_key(&stream, key);
2553                 return (__bamc_compress_merge_delete(dbc, &stream, &key->doff));
2554         default:
2555                 break;
2556         }
2557
2558         return (__db_unknown_flag(
2559             dbc->env, "__bamc_compress_ibulk_del", flags));
2560 }
2561
2562 /*
2563  * __bamc_compress_bulk_del --
2564  *      Bulk del using a compressed cursor.
2565  *
2566  * PUBLIC: int __bamc_compress_bulk_del __P((DBC *, DBT *, u_int32_t));
2567  */
2568 int
2569 __bamc_compress_bulk_del(dbc, key, flags)
2570         DBC *dbc;
2571         DBT *key;
2572         u_int32_t flags;
2573 {
2574         int ret, t_ret;
2575         DBC *dbc_n;
2576
2577         F_CLR((BTREE_CURSOR *)dbc->internal, C_COMPRESS_MODIFIED);
2578
2579         if (F_ISSET(dbc, DBC_TRANSIENT))
2580                 dbc_n = dbc;
2581         else {
2582                 if ((ret = __dbc_dup(dbc, &dbc_n, 0)) != 0)
2583                         goto err;
2584
2585                 /*
2586                  * We don't care about preserving the cursor's position on
2587                  * error.
2588                  */
2589                 F_SET(dbc_n, DBC_TRANSIENT);
2590         }
2591
2592         if ((ret = __bamc_compress_ibulk_del(dbc_n, key, flags)) != 0)
2593                 goto err;
2594
2595 err:
2596         /* Cleanup and cursor resolution. */
2597         if ((t_ret = __dbc_cleanup(dbc, dbc_n, ret)) != 0 &&
2598                 (ret == 0 || ret == DB_BUFFER_SMALL))
2599                 ret = t_ret;
2600         return (ret);
2601 }
2602
2603 /*
2604  * __bamc_compress_count --
2605  *      Count using a compressed cursor.
2606  *
2607  * PUBLIC: int __bamc_compress_count __P((DBC *, db_recno_t *));
2608  */
2609 int
2610 __bamc_compress_count(dbc, countp)
2611         DBC *dbc;
2612         db_recno_t *countp;
2613 {
2614         int ret, t_ret;
2615         db_recno_t count;
2616         DBT *key;
2617         DBC *dbc_n;
2618         BTREE_CURSOR *cp;
2619
2620         cp = (BTREE_CURSOR *)dbc->internal;
2621
2622         /*
2623          * If the current entry is deleted use del_key, otherwise use
2624          * currentKey.
2625          */
2626         if (F_ISSET(cp, C_COMPRESS_DELETED))
2627                 key = &cp->del_key;
2628         else
2629                 key = cp->currentKey;
2630
2631         /* Duplicate the cursor */
2632         if ((ret = __dbc_dup(dbc, &dbc_n, 0)) != 0)
2633                 return (ret);
2634
2635         /* We don't care about preserving the cursor's position on error */
2636         F_SET(dbc_n, DBC_TRANSIENT);
2637
2638         /* Find the first duplicate */
2639         if ((ret = __bamc_compress_get_set(dbc_n, key, 0, DB_SET, 0)) != 0)
2640                 goto err;
2641         count = 1;
2642
2643         /* Count subsequent duplicates */
2644         while ((ret = __bamc_compress_get_next_dup(dbc_n, key, 0)) == 0)
2645                 ++count;
2646
2647         if (ret == DB_NOTFOUND)
2648                 ret = 0;
2649         else if (ret != 0)
2650                 goto err;
2651
2652         *countp = count;
2653
2654  err:
2655         if ((t_ret = __dbc_close(dbc_n)) != 0 && ret == 0)
2656                 ret = t_ret;
2657
2658         return (ret);
2659 }
2660
2661 /*
2662  * __bamc_compress_cmp --
2663  *      Compare which compressed value is pointed to.
2664  *
2665  * PUBLIC: int __bamc_compress_cmp __P((DBC *, DBC *, int *));
2666  */
2667 int
2668 __bamc_compress_cmp(dbc, other_dbc, result)
2669         DBC *dbc, *other_dbc;
2670         int *result;
2671 {
2672         DB *dbp;
2673         BTREE_CURSOR *cp, *ocp;
2674
2675         /*
2676          * At this point, we already know that the cursors point to the same
2677          * DB.
2678          */
2679
2680         dbp = dbc->dbp;
2681         cp = (BTREE_CURSOR *)dbc->internal;
2682         ocp = (BTREE_CURSOR *)other_dbc->internal;
2683
2684         if (F_ISSET(cp, C_COMPRESS_DELETED))
2685                 if (F_ISSET(ocp, C_COMPRESS_DELETED))
2686                         *result = __db_compare_both(
2687                              dbp, &cp->del_key, &cp->del_data,
2688                              &ocp->del_key, &ocp->del_data) == 0 ? 0 : 1;
2689                 else {
2690                         if (ocp->currentKey == 0)
2691                                 goto err;
2692
2693                         *result = __db_compare_both(
2694                              dbp, &cp->del_key, &cp->del_data,
2695                              ocp->currentKey, ocp->currentData) == 0 ? 0 : 1;
2696                 }
2697         else {
2698                 if (cp->currentKey == 0)
2699                         goto err;
2700
2701                 if (F_ISSET(ocp, C_COMPRESS_DELETED))
2702                         *result = __db_compare_both(
2703                              dbp, cp->currentKey, cp->currentData,
2704                              &ocp->del_key, &ocp->del_data) == 0 ? 0 : 1;
2705                 else {
2706                         if (ocp->currentKey == 0)
2707                                 goto err;
2708
2709                         *result = __db_compare_both(
2710                              dbp, cp->currentKey, cp->currentData,
2711                              ocp->currentKey, ocp->currentData) == 0 ? 0 : 1;
2712                 }
2713         }
2714         return (0);
2715
2716  err:
2717         __db_errx(dbc->env,
2718                 "Both cursors must be initialized before calling DBC->cmp.");
2719         return (EINVAL);
2720 }
2721
2722 /*
2723  * __bamc_compress_dup --
2724  *      Duplicate the compression specific part of a btree cursor.
2725  *
2726  * PUBLIC: int __bamc_compress_dup __P((DBC *, DBC *, u_int32_t));
2727  */
2728 int
2729 __bamc_compress_dup(orig_dbc, new_dbc, flags)
2730         DBC *orig_dbc, *new_dbc;
2731         u_int32_t flags;
2732 {
2733         int ret;
2734         DB *dbp;
2735         BTREE_CURSOR *orig, *new;
2736
2737         dbp = new_dbc->dbp;
2738
2739         orig = (BTREE_CURSOR *)orig_dbc->internal;
2740         new = (BTREE_CURSOR *)new_dbc->internal;
2741
2742         if (orig->currentKey != NULL && !LF_ISSET(DB_SHALLOW_DUP)) {
2743                 new->currentKey = &new->key1;
2744                 new->currentData = &new->data1;
2745
2746                 if ((ret = __bam_compress_set_dbt(dbp, new->currentKey,
2747                     orig->currentKey->data, orig->currentKey->size)) != 0)
2748                         return (ret);
2749                 if ((ret = __bam_compress_set_dbt(dbp, new->currentData,
2750                     orig->currentData->data, orig->currentData->size)) != 0)
2751                         return (ret);
2752
2753                 if (orig->prevKey) {
2754                         new->prevKey = &new->key2;
2755                         new->prevData = &new->data2;
2756
2757                         if ((ret = __bam_compress_set_dbt(dbp, new->prevKey,
2758                             orig->prevKey->data, orig->prevKey->size)) != 0)
2759                                 return (ret);
2760                         if ((ret = __bam_compress_set_dbt(dbp, new->prevData,
2761                             orig->prevData->data, orig->prevData->size)) != 0)
2762                                 return (ret);
2763                 }
2764
2765                 if ((ret = __bam_compress_set_dbt(dbp, &new->compressed,
2766                     orig->compressed.data, orig->compressed.size)) != 0)
2767                         return (ret);
2768
2769                 new->compcursor = (u_int8_t*)new->compressed.data +
2770                         (orig->compcursor - (u_int8_t*)orig->compressed.data);
2771                 new->compend = (u_int8_t*)new->compressed.data +
2772                         (orig->compend - (u_int8_t*)orig->compressed.data);
2773                 new->prevcursor = orig->prevcursor == NULL ? NULL :
2774                         (u_int8_t*)new->compressed.data + (orig->prevcursor -
2775                                 (u_int8_t*)orig->compressed.data);
2776                 new->prev2cursor = orig->prev2cursor == NULL ? NULL :
2777                         (u_int8_t*)new->compressed.data + (orig->prev2cursor -
2778                                 (u_int8_t*)orig->compressed.data);
2779
2780                 if (F_ISSET(orig, C_COMPRESS_DELETED)) {
2781                         if ((ret = __bam_compress_set_dbt(dbp, &new->del_key,
2782                             orig->del_key.data, orig->del_key.size)) != 0)
2783                                 return (ret);
2784                         if ((ret = __bam_compress_set_dbt(dbp, &new->del_data,
2785                             orig->del_data.data, orig->del_data.size)) != 0)
2786                                 return (ret);
2787                 }
2788         }
2789
2790         return (0);
2791 }
2792
2793 /*
2794  * __bam_compress_salvage --
2795  *      Salvage the compressed data from the key/data pair
2796  *
2797  * PUBLIC: int __bam_compress_salvage __P((DB *, VRFY_DBINFO *,
2798  * PUBLIC:     void *, int (*)(void *, const void *), DBT *, DBT *));
2799  */
2800 int
2801 __bam_compress_salvage(dbp, vdp, handle, callback, key, data)
2802         DB *dbp;
2803         VRFY_DBINFO *vdp;
2804         void *handle;
2805         int (*callback) __P((void *, const void *));
2806         DBT *key, *data;
2807 {
2808         DBT key1, key2, data1, data2, compressed;
2809         DBT *currentKey, *currentData, *prevKey, *prevData;
2810         ENV *env;
2811         int ret, t_ret;
2812         u_int8_t *compcursor, *compend;
2813         u_int32_t datasize, size;
2814
2815         env = dbp->env;
2816
2817         memset(&key1, 0, sizeof(DBT));
2818         memset(&key2, 0, sizeof(DBT));
2819         memset(&data1, 0, sizeof(DBT));
2820         memset(&data2, 0, sizeof(DBT));
2821         memset(&compressed, 0, sizeof(DBT));
2822
2823         key1.flags = DB_DBT_USERMEM;
2824         key2.flags = DB_DBT_USERMEM;
2825         data1.flags = DB_DBT_USERMEM;
2826         data2.flags = DB_DBT_USERMEM;
2827         compressed.flags = DB_DBT_USERMEM;
2828
2829         prevKey = NULL;
2830         prevData = NULL;
2831         currentKey = key;
2832         currentData = &data2;
2833         compcursor = (u_int8_t*)data->data;
2834         compend = compcursor + data->size;
2835
2836         if (data->size == 0) {
2837                 ret = DB_VERIFY_FATAL;
2838                 goto unknown_data;
2839         }
2840
2841         /* Unmarshal the first data */
2842         size = __db_decompress_count_int(compcursor);
2843         if (size == 0xFF || compcursor + size > compend) {
2844                 ret = DB_VERIFY_FATAL;
2845                 goto unknown_data;
2846         }
2847         compcursor += __db_decompress_int32(compcursor, &datasize);
2848
2849         if (compcursor + datasize > compend) {
2850                 ret = DB_VERIFY_FATAL;
2851                 goto unknown_data;
2852         }
2853         if ((ret = __bam_compress_set_dbt(
2854             dbp, currentData, compcursor, datasize)) != 0)
2855                 goto err;
2856         compcursor += datasize;
2857
2858         /* Output first data (first key has already been output by our caller */
2859         if ((ret = __db_vrfy_prdbt(
2860             currentData, 0, " ", handle, callback, 0, vdp)) != 0)
2861                 goto err;
2862
2863         while (compcursor < compend) {
2864                 prevKey = currentKey;
2865                 prevData = currentData;
2866
2867                 if (currentKey == &key1) {
2868                         currentKey = &key2;
2869                         currentData = &data2;
2870                 } else {
2871                         currentKey = &key1;
2872                         currentData = &data1;
2873                 }
2874
2875                 compressed.data = (void*)compcursor;
2876                 compressed.ulen = compressed.size =
2877                     (u_int32_t)(compend - compcursor);
2878
2879                 /* Decompress the next key/data pair */
2880                 while ((ret = ((BTREE *)dbp->bt_internal)->bt_decompress(
2881                     dbp, prevKey, prevData,
2882                     &compressed, currentKey, currentData)) == DB_BUFFER_SMALL) {
2883                         if (CMP_RESIZE_DBT(ret, env, currentKey) != 0)
2884                                 break;
2885                         if (CMP_RESIZE_DBT(ret, env, currentData) != 0)
2886                                 break;
2887                 }
2888
2889                 if (ret == EINVAL) {
2890                         ret = DB_VERIFY_FATAL;
2891                         goto err;
2892                 }
2893                 if (ret != 0)
2894                         goto err;
2895
2896                 compcursor += compressed.size;
2897
2898                 if (compcursor > compend) {
2899                         ret = DB_VERIFY_FATAL;
2900                         goto err;
2901                 }
2902
2903                 /* Output the next key/data pair */
2904                 if ((ret = __db_vrfy_prdbt(
2905                     currentKey, 0, " ", handle, callback, 0, vdp)) != 0)
2906                         goto err;
2907                 if ((ret = __db_vrfy_prdbt(
2908                     currentData, 0, " ", handle, callback, 0, vdp)) != 0)
2909                         goto err;
2910         }
2911
2912         if (0) {
2913  unknown_data:
2914                 /*
2915                  * Make sure we output a data value for the key that's
2916                  * already been output
2917                  */
2918                 DB_INIT_DBT(
2919                     compressed, "UNKNOWN_DATA", sizeof("UNKNOWN_DATA") - 1);
2920                 if ((t_ret = __db_vrfy_prdbt(
2921                     &compressed, 0, " ", handle, callback, 0, vdp)) != 0)
2922                         ret = t_ret;
2923         }
2924
2925  err:
2926         __os_free(env, key1.data);
2927         __os_free(env, key2.data);
2928         __os_free(env, data1.data);
2929         __os_free(env, data2.data);
2930         return (ret);
2931 }
2932
2933 /*
2934  * __bam_compress_count --
2935  *      Calculate key and entry counts for the compressed BTree
2936  *
2937  * PUBLIC: int __bam_compress_count __P((DBC *, u_int32_t *, u_int32_t *));
2938  */
2939 int
2940 __bam_compress_count(dbc, nkeysp, ndatap)
2941         DBC *dbc;
2942         u_int32_t *nkeysp, *ndatap;
2943 {
2944         int ret, t_ret;
2945         u_int32_t nkeys, ndata;
2946         DB *dbp;
2947         BTREE *t;
2948         DBC *dbc_n;
2949         BTREE_CURSOR *cp_n;
2950
2951         dbp = dbc->dbp;
2952         t = (BTREE *)dbp->bt_internal;
2953
2954         /* Duplicate the cursor */
2955         if ((ret = __dbc_dup(dbc, &dbc_n, 0)) != 0)
2956                 return (ret);
2957
2958         /* We don't care about preserving the cursor's position on error */
2959         F_SET(dbc_n, DBC_TRANSIENT);
2960
2961         cp_n = (BTREE_CURSOR *)dbc_n->internal;
2962
2963         nkeys = 0;
2964         ndata = 0;
2965
2966         CMP_IGET_RETRY(ret, dbc_n, &cp_n->key1, &cp_n->compressed, DB_FIRST);
2967         if (ret != 0)
2968                 goto err;
2969
2970         if ((ret = __bamc_start_decompress(dbc_n)) != 0)
2971                 goto err;
2972         nkeys += 1;
2973
2974         for (;;) {
2975                 ndata += 1;
2976
2977                 ret = __bamc_next_decompress(dbc_n);
2978                 if (ret == DB_NOTFOUND) {
2979                         if (cp_n->currentKey == &cp_n->key1) {
2980                                 /*
2981                                  * Make sure that the previous key isn't
2982                                  * overwritten when we fetch the next chunk.
2983                                  */
2984                                 if ((ret = __bam_compress_set_dbt(dbp,
2985                                              &cp_n->key2, cp_n->key1.data,
2986                                              cp_n->key1.size)) != 0)
2987                                         goto err;
2988                         }
2989
2990                         CMP_IGET_RETRY(ret, dbc_n, &cp_n->key1,
2991                                 &cp_n->compressed, DB_NEXT);
2992                         if (ret != 0)
2993                                 goto err;
2994
2995                         ret = __bamc_start_decompress(dbc_n);
2996
2997                         cp_n->prevKey = &cp_n->key2;
2998                 }
2999
3000                 if (ret != 0)
3001                         goto err;
3002
3003                 if (t->bt_compare(dbp, cp_n->currentKey, cp_n->prevKey) != 0)
3004                         nkeys += 1;
3005         }
3006
3007 err:
3008         if (ret == DB_NOTFOUND)
3009                 ret = 0;
3010
3011         if ((t_ret = __dbc_close(dbc_n)) != 0 && ret == 0)
3012                 ret = t_ret;
3013
3014         if (ret == 0) {
3015                 if (nkeysp != NULL)
3016                         *nkeysp = nkeys;
3017                 if (ndatap != NULL)
3018                         *ndatap = ndata;
3019         }
3020
3021         return (ret);
3022 }
3023
3024 #endif