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