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