1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 
3 /**
4  * @copyright 2013 Couchbase, Inc.
5  *
6  * @author Sarath Lakshman  <sarath@couchbase.com>
7  *
8  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
9  * use this file except in compliance with the License. You may obtain a copy of
10  * the License at
11  *
12  *  http://www.apache.org/licenses/LICENSE-2.0
13  *
14  * Unless required by applicable law or agreed to in writing, software
15  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
16  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
17  * License for the specific language governing permissions and limitations under
18  * the License.
19  **/
20 
21 #include "config.h"
22 #include <libcouchstore/couch_db.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include "../macros.h"
26 #include "purge_tests.h"
27 #include "../../src/couch_btree.h"
28 
29 char testpurgefile[1024] = "purge.couch";
30 typedef couchstore_error_t (*fetch_callback_fn)(couchfile_lookup_request *,
31                                                 const sized_buf *,
32                                                 const sized_buf *);
33 /* Compare helper function */
int_cmp(const sized_buf *a, const sized_buf *b)34 static int int_cmp(const sized_buf *a, const sized_buf *b)
35 {
36 
37     if (!a->size || !b->size) {
38         return 0;
39     }
40 
41     return *((int *) a->buf) - *((int *) b->buf);
42 }
43 
44 /* Read a field from reduce value */
red_intval(const node_pointer *ptr, int i)45 static int red_intval(const node_pointer *ptr, int i)
46 {
47     sized_buf red;
48     red.size = 0;
49 
50     if (ptr) {
51         red = ptr->reduce_value;
52     }
53 
54     if (red.size) {
55         return *((int *) red.buf + i);
56     }
57 
58     return 0;
59 }
60 
61 /* Reduction functions */
count_reduce(char *dst, size_t *size_r, const nodelist *leaflist, int count, void *ctx)62 static couchstore_error_t count_reduce(char *dst, size_t *size_r,
63                                                 const nodelist *leaflist,
64                                                 int count, void *ctx)
65 {
66     int *dst_count = (int *) dst;
67     (void) leaflist;
68     (void) size_r;
69     (void) ctx;
70 
71     *dst_count = count;
72     *size_r = sizeof(count);
73 
74     return COUCHSTORE_SUCCESS;
75 }
76 
count_rereduce(char *dst, size_t *size_r, const nodelist *ptrlist, int count, void *ctx)77 static couchstore_error_t count_rereduce(char *dst, size_t *size_r,
78                                                     const nodelist *ptrlist,
79                                                     int count,
80                                                     void *ctx)
81 {
82     int total = 0;
83     int *dst_count = (int *) dst;
84     const nodelist *i = ptrlist;
85     (void) size_r;
86     (void) ctx;
87 
88     while (i != NULL && count > 0) {
89         const int *reduce = (const int *) i->pointer->reduce_value.buf;
90         total += *reduce;
91         i = i->next;
92         count--;
93     }
94 
95     *dst_count = total;
96     *size_r = sizeof(total);
97 
98     return COUCHSTORE_SUCCESS;
99 }
100 
evenodd_reduce(char *dst, size_t *size_r, const nodelist *leaflist, int count, void *ctx)101 static couchstore_error_t evenodd_reduce(char *dst, size_t *size_r,
102                                                     const nodelist *leaflist,
103                                                     int count,
104                                                     void *ctx)
105 {
106     int *evenodd = (int *) dst;
107     int E = 0, O = 0;
108     int *val;
109 
110     (void) size_r;
111     (void) ctx;
112 
113     while (count--) {
114         val = (int *) leaflist->key.buf;
115         if (*val & 0x1) {
116             O++;
117         } else {
118             E++;
119         }
120         leaflist = leaflist->next;
121     }
122 
123 
124     evenodd[0] = E;
125     evenodd[1] = O;
126     *size_r = sizeof(int) * 2;
127 
128     return COUCHSTORE_SUCCESS;
129 }
130 
evenodd_rereduce(char *dst, size_t *size_r, const nodelist *leaflist, int count, void *ctx)131 static couchstore_error_t evenodd_rereduce(char *dst, size_t *size_r,
132                                                     const nodelist *leaflist,
133                                                     int count,
134                                                     void *ctx)
135 {
136     int *evenodd = (int *) dst;
137     int *node_evenodd;
138     int E = 0, O = 0;
139 
140     (void) size_r;
141     (void) ctx;
142 
143     while (count--) {
144         node_evenodd = (int *) leaflist->pointer->reduce_value.buf;
145         E += node_evenodd[0];
146         O += node_evenodd[1];
147         leaflist = leaflist->next;
148     }
149 
150     evenodd[0] = E;
151     evenodd[1] = O;
152     *size_r = sizeof(int) * 2;
153 
154     return COUCHSTORE_SUCCESS;
155 }
156 
uniq_reduce(char *dst, size_t *size_r, const nodelist *leaflist, int count, void *ctx)157 static couchstore_error_t uniq_reduce(char *dst, size_t *size_r,
158                                                     const nodelist *leaflist,
159                                                     int count,
160                                                     void *ctx)
161 {
162     int map[64];
163     int *val;
164     int total = 0;
165     int i, pos;
166     memset(map, 0, 64 * sizeof(int));
167     val = (int *) dst;
168     val[0] = count;
169 
170     (void) ctx;
171 
172     while (count--) {
173         val = (int *) leaflist->data.buf;
174         if (!map[*val]) {
175             map[*val] = 1;
176 
177             total++;
178         }
179         leaflist = leaflist->next;
180     }
181 
182     val = (int *) dst;
183     val[1] = total;
184     pos = 2;
185     for (i = 0; i < 64; i++) {
186         if (map[i] == 1) {
187             val[pos++] = i;
188         }
189     }
190 
191     *size_r = sizeof(int) * (total + 2);
192 
193     return COUCHSTORE_SUCCESS;
194 }
195 
uniq_rereduce(char *dst, size_t *size_r, const nodelist *leaflist, int count, void *ctx)196 static couchstore_error_t uniq_rereduce(char *dst, size_t *size_r,
197                                                     const nodelist *leaflist,
198                                                     int count,
199                                                     void *ctx)
200 {
201     int map[64];
202     int *val;
203     int i, pos, unique_count = 0, total_count = 0;
204     (void) ctx;
205 
206     memset(map, 0, 64 * sizeof(int));
207 
208     while (count--) {
209         val = (int *) leaflist->pointer->reduce_value.buf;
210         total_count += val[0];
211         for (i = 2; i < val[1] + 2; i++) {
212 
213             if (!map[val[i]]) {
214                 map[val[i]] = 1;
215 
216                 unique_count++;
217             }
218         }
219 
220         leaflist = leaflist->next;
221     }
222 
223     val = (int *) dst;
224     val[0] = total_count;
225     val[1] = unique_count;
226 
227     pos = 2;
228     for (i = 0; i < 64; i++) {
229         if (map[i] == 1) {
230             val[pos++] = i;
231 
232         }
233     }
234 
235 
236     *size_r = sizeof(int) * (unique_count + 2);
237 
238     return COUCHSTORE_SUCCESS;
239 }
240 
241 /* Purge functions */
keepall_purge_kp(const node_pointer *ptr, void *ctx)242 static int keepall_purge_kp(const node_pointer *ptr, void *ctx)
243 {
244     (void) ctx;
245     return PURGE_KEEP;
246 }
247 
keepall_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)248 static int keepall_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)
249 {
250     (void) key;
251     (void) val;
252     (void) ctx;
253 
254     return PURGE_KEEP;
255 }
256 
all_purge_kp(const node_pointer *ptr, void *ctx)257 static int all_purge_kp(const node_pointer *ptr, void *ctx)
258 {
259     int *count;
260     count = (int *) ctx;
261     count[1] += red_intval(ptr, 0);
262     return PURGE_ITEM;
263 }
264 
all_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)265 static int all_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)
266 {
267     int *count;
268     (void) key;
269     (void) val;
270 
271     count = (int *) ctx;
272     count[0]++;
273     return PURGE_ITEM;
274 }
275 
evenodd_purge_kp(const node_pointer *ptr, void *ctx)276 static int evenodd_purge_kp(const node_pointer *ptr, void *ctx)
277 {
278     int even_count, odd_count;
279     (void) ctx;
280 
281     even_count = red_intval(ptr, 0);
282     odd_count = red_intval(ptr, 1);
283 
284     if (!even_count) {
285         return PURGE_ITEM;
286     } else if (!odd_count) {
287         return PURGE_KEEP;
288     }
289 
290     return PURGE_PARTIAL;
291 }
292 
evenodd_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)293 static int evenodd_purge_kv(const sized_buf *key, const sized_buf *val,
294                                                             void *ctx)
295 {
296     int *count = (int *) ctx;
297     int *num = (int *) key->buf;
298     (void) val;
299     (void) ctx;
300 
301     if (*num % 2 == 0) {
302         return PURGE_KEEP;
303     }
304 
305     (*count)++;
306 
307     return PURGE_ITEM;
308 }
309 
evenodd_stop_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)310 static int evenodd_stop_purge_kv(const sized_buf *key, const sized_buf *val,
311                                                                 void *ctx)
312 {
313     int *count = (int *) ctx;
314     int *num = (int *) key->buf;
315     (void) val;
316 
317     if (*count >= 4) {
318         return PURGE_STOP;
319     }
320 
321     if (*num % 2 == 0) {
322         return PURGE_KEEP;
323     }
324 
325     (*count)++;
326 
327     return PURGE_ITEM;
328 }
329 
skip_purge_kp(const node_pointer *ptr, void *ctx)330 static int skip_purge_kp(const node_pointer *ptr, void *ctx)
331 {
332     int *count = (int *) ctx;
333     int len, range_start, range_end;
334     len = red_intval(ptr, 1);
335     range_start = red_intval(ptr, 2);
336     range_end = red_intval(ptr, len + 1);
337 
338     if (!len) {
339         return PURGE_KEEP;
340     } else if (range_start >= 32 && range_end <= 63) {
341         (*count)++;
342         return PURGE_ITEM;
343     }
344 
345     return PURGE_PARTIAL;
346 }
347 
skip_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)348 static int skip_purge_kv(const sized_buf *key, const sized_buf *val, void *ctx)
349 {
350     int *count = (int *) ctx;
351     int *num = (int *) val->buf;
352     (void) key;
353 
354     if (*num < 32) {
355         return PURGE_KEEP;
356     }
357 
358     (*count)++;
359 
360     return PURGE_ITEM;
361 }
362 
363 /* Btree iterator callbacks */
check_vals_callback(couchfile_lookup_request *rq, const sized_buf *k, const sized_buf *v)364 static couchstore_error_t check_vals_callback(couchfile_lookup_request *rq,
365                                                             const sized_buf *k,
366                                                             const sized_buf *v)
367 {
368 
369     int *ctx = rq->callback_ctx;
370     int *num = (int *) k->buf;
371     assert(*num == ctx[1] && *num <= ctx[0]);
372     ctx[1]++;
373 
374     return COUCHSTORE_SUCCESS;
375 }
376 
check_odd_callback(couchfile_lookup_request *rq, const sized_buf *k, const sized_buf *v)377 static couchstore_error_t check_odd_callback(couchfile_lookup_request *rq,
378                                                             const sized_buf *k,
379                                                             const sized_buf *v)
380 {
381     int *key = (int *) k->buf;
382     assert(*key % 2 == 0);
383 
384     return COUCHSTORE_SUCCESS;
385 }
386 
check_odd2_callback(couchfile_lookup_request *rq, const sized_buf *k, const sized_buf *v)387 static couchstore_error_t check_odd2_callback(couchfile_lookup_request *rq,
388                                                             const sized_buf *k,
389                                                             const sized_buf *v)
390 {
391     int *key = (int *) k->buf;
392     int *val = (int *) v->buf;
393     assert(*key % 2 == 0);
394 
395     switch ((*key)) {
396     case 2:
397     case 14006:
398     case 500000:
399         assert(*key == *val);
400         break;
401     case 4:
402     case 10:
403     case 200000:
404         assert(0);
405     default:
406         assert(*val == (*key % 64));
407     }
408 
409     return COUCHSTORE_SUCCESS;
410 }
411 
check_odd_stop_callback(couchfile_lookup_request *rq, const sized_buf *k, const sized_buf *v)412 static couchstore_error_t check_odd_stop_callback(couchfile_lookup_request *rq,
413                                                             const sized_buf *k,
414                                                             const sized_buf *v)
415 {
416     int *num = (int *) k->buf;
417     switch (*num) {
418     case 1:
419     case 3:
420     case 5:
421     case 7:
422         assert(0);
423     }
424 
425     return COUCHSTORE_SUCCESS;
426 }
427 
check_skiprange_callback(couchfile_lookup_request *rq, const sized_buf *k, const sized_buf *v)428 static couchstore_error_t  check_skiprange_callback(couchfile_lookup_request *rq,
429                                                             const sized_buf *k,
430                                                             const sized_buf *v)
431 {
432     int *key = (int *) k->buf;
433     int *val = (int *) v->buf;
434     int *last = (int *) rq->callback_ctx;
435     assert(*val >= 0 && *val <= 31);
436     assert(*key > *last);
437     *last = *key;
438 
439     return COUCHSTORE_SUCCESS;
440 }
441 
442 /* Helper function to populate a btree  with {1..N} sequence */
insert_items(tree_file *file, node_pointer *root, reduce_fn reduce, reduce_fn rereduce, int n)443 static node_pointer *insert_items(tree_file *file, node_pointer *root,
444                                   reduce_fn reduce,
445                                   reduce_fn rereduce,
446                                   int n)
447 {
448 
449     int errcode, i;
450     couchfile_modify_request rq;
451     couchfile_modify_action *acts;
452     node_pointer *nroot = NULL;
453     int *arr1, *arr2;
454     sized_buf *keys, *vals;
455 
456     arr1 = (int *) calloc(n, sizeof(int));
457     arr2 = (int *) calloc(n, sizeof(int));
458     keys = (sized_buf *) calloc(n, sizeof(sized_buf));
459     vals = (sized_buf *) calloc(n, sizeof(sized_buf));
460     acts = (couchfile_modify_action *) calloc(n, sizeof(couchfile_modify_action));
461 
462     for (i = 0; i < n; i++) {
463         arr1[i] = i + 1;
464         arr2[i] = (i + 1) % 64;
465 
466         keys[i].size = sizeof(int);
467         keys[i].buf = (void *) &arr1[i];
468 
469         vals[i].size = sizeof(int);
470         vals[i].buf = (void *) &arr2[i];
471 
472         acts[i].type = ACTION_INSERT;
473         acts[i].value.data = &vals[i];
474         acts[i].key = &keys[i];
475     }
476 
477     rq.cmp.compare = int_cmp;
478     rq.file = file;
479     rq.actions = acts;
480     rq.num_actions = n;
481     rq.reduce = reduce;
482     rq.rereduce = rereduce;
483     rq.compacting = 0;
484     rq.kv_chunk_threshold = 6 * 1024;
485     rq.kp_chunk_threshold = 6 * 1024;
486 
487     nroot = modify_btree(&rq, root, &errcode);
488     free(arr1);
489     free(arr2);
490     free(keys);
491     free(vals);
492     free(acts);
493 
494     assert(errcode == 0);
495 
496     return nroot;
497 }
498 
499 /* Helper function to create a purge btree modify request */
purge_request(tree_file *file, reduce_fn reduce, reduce_fn rereduce, purge_kp_fn purge_kp, purge_kv_fn purge_kv, void *purge_ctx)500 static couchfile_modify_request purge_request(tree_file *file, reduce_fn reduce,
501                                                           reduce_fn rereduce,
502                                                           purge_kp_fn purge_kp,
503                                                           purge_kv_fn purge_kv,
504                                                           void *purge_ctx)
505 {
506     couchfile_modify_request rq;
507 
508     rq.cmp.compare = int_cmp;
509     rq.file = file;
510     rq.actions = NULL;
511     rq.num_actions = 0;
512     rq.reduce = reduce;
513     rq.rereduce = rereduce;
514     rq.compacting = 0;
515     rq.kv_chunk_threshold = 6 * 1024;
516     rq.kp_chunk_threshold = 6 * 1024;
517     rq.purge_kp = purge_kp;
518     rq.purge_kv = purge_kv;
519     rq.enable_purging = 1;
520     rq.guided_purge_ctx = purge_ctx;
521 
522     return rq;
523 
524 }
525 
526 /* Btree iterator helper function */
iter_btree(tree_file *file, node_pointer *root, void *ctx, fetch_callback_fn callback)527 static couchstore_error_t iter_btree(tree_file *file, node_pointer *root,
528                                                     void *ctx,
529                                                     fetch_callback_fn callback)
530 {
531     couchfile_lookup_request rq;
532     sized_buf k = {NULL, 0};
533     sized_buf *keys = &k;
534 
535     rq.cmp.compare = int_cmp;
536     rq.file = file;
537     rq.num_keys = 1;
538     rq.keys = &keys;
539     rq.callback_ctx = ctx;
540     rq.fetch_callback = callback;
541     rq.node_callback = NULL;
542     rq.fold = 1;
543 
544     return btree_lookup(&rq, root->pointer);
545 }
546 
547 
548 /* Unit tests for guided_purge api */
549 
test_no_purge_itemsnull550 void test_no_purge_items()
551 {
552     int errcode, N;
553     int redval;
554     int ctx[2];
555     int purge_sum[2] = {0, 0};
556     Db *db = NULL;
557     node_pointer *root = NULL, *newroot = NULL;
558     couchfile_modify_request purge_rq;
559     fprintf(stderr, "\nExecuting test_no_purge_items...\n");
560 
561     N = 211341;
562     ctx[0] = N;
563     ctx[1] = 1;
564     remove(testpurgefile);
565     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
566     root = insert_items(&db->file, NULL, count_reduce, count_rereduce, N);
567     assert(root != NULL);
568 
569     redval = red_intval(root, 0);
570     assert(redval == N);
571     fprintf(stderr, "Initial reduce value equals N\n");
572 
573     purge_rq = purge_request(&db->file, count_reduce, count_rereduce,
574                     keepall_purge_kp, keepall_purge_kv, (void *) purge_sum);
575     newroot = guided_purge_btree(&purge_rq, root, &errcode);
576 
577     assert(purge_sum[0] == 0 && purge_sum[1] == 0);
578     fprintf(stderr, "guided_purge returned correct accumulator {0,0}\n");
579 
580     redval = red_intval(newroot, 0);
581     assert(redval == N);
582     fprintf(stderr, "Reduce value after guided purge equals N\n");
583 
584     try(iter_btree(&db->file, newroot, &ctx, check_vals_callback));
585     fprintf(stderr, "Btree has same values after guided purge\n");
586 
587 cleanup:
588     free(root);
589     if (root != newroot) {
590         free(newroot);
591     }
592     couchstore_close_db(db);
593     assert(errcode == 0);
594 }
595 
test_all_purge_itemsnull596 void test_all_purge_items()
597 {
598     int errcode, N;
599     int redval;
600     int purge_sum[2] = {0, 0};
601     Db *db = NULL;
602     node_pointer *root = NULL, *newroot = NULL;
603     couchfile_modify_request purge_rq;
604     fprintf(stderr, "\nExecuting test_all_purge_items...\n");
605 
606     N = 211341;
607     remove(testpurgefile);
608     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
609     root = insert_items(&db->file, NULL, count_reduce, count_rereduce, N);
610     assert(root != NULL);
611 
612     redval = red_intval(root, 0);
613     assert(redval == N);
614     fprintf(stderr, "Initial reduce value equals N\n");
615 
616     purge_rq = purge_request(&db->file, count_reduce, count_rereduce,
617                             all_purge_kp, all_purge_kv, (void *) &purge_sum);
618     newroot = guided_purge_btree(&purge_rq, root, &errcode);
619 
620     assert(purge_sum[0] == 0 && purge_sum[1] == N);
621     fprintf(stderr, "guided_purge returned correct accumulator {0,N}\n");
622 
623     redval = red_intval(newroot, 0);
624     assert(redval == 0);
625     fprintf(stderr, "Reduce value after guided purge equals 0\n");
626 
627     assert(newroot == NULL);
628     fprintf(stderr, "Btree is empty after guided purge\n");
629 
630 cleanup:
631     free(root);
632     free(newroot);
633     couchstore_close_db(db);
634     assert(errcode == 0);
635 }
636 
637 
test_partial_purge_itemsnull638 void test_partial_purge_items()
639 {
640     int errcode, N;
641     int exp_evenodd[2];
642     int purge_count = 0;
643     Db *db = NULL;
644     node_pointer *root = NULL, *newroot = NULL;
645     couchfile_modify_request purge_rq;
646     fprintf(stderr, "\nExecuting test_partial_purge_items...\n");
647 
648     N = 211341;
649     exp_evenodd[0] = N / 2;
650     exp_evenodd[1] = N / 2 + N % 2;
651 
652     remove(testpurgefile);
653     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
654     root = insert_items(&db->file, NULL, evenodd_reduce, evenodd_rereduce, N);
655     assert(root != NULL);
656 
657     assert(exp_evenodd[0] == red_intval(root, 0) && exp_evenodd[1] == red_intval(root, 1));
658     fprintf(stderr, "Initial reduce value equals {NumEven, NumOdd}\n");
659 
660     purge_rq = purge_request(&db->file, evenodd_reduce, evenodd_rereduce,
661                     evenodd_purge_kp, evenodd_purge_kv, (void *) &purge_count);
662     newroot = guided_purge_btree(&purge_rq, root, &errcode);
663 
664     assert(purge_count == exp_evenodd[1]);
665     fprintf(stderr, "guided_purge returned correct accumulator {0,NumOdd}\n");
666 
667     assert(red_intval(newroot, 0) == exp_evenodd[0] && red_intval(newroot, 1) == 0);
668     fprintf(stderr, "Reduce value after guided purge equals {NumEven, 0}\n");
669 
670     try(iter_btree(&db->file, newroot, NULL, check_odd_callback));
671     fprintf(stderr, "Btree has no odd values after guided purge\n");
672 
673 cleanup:
674     free(root);
675     free(newroot);
676     couchstore_close_db(db);
677     assert(errcode == 0);
678 }
679 
test_partial_purge_items2null680 void test_partial_purge_items2()
681 {
682     int errcode, N;
683     Db *db = NULL;
684     node_pointer *root = NULL, *newroot = NULL;
685     int range_start, range_end;
686     int count, purge_count = 0, iter_context = -1;
687     couchfile_modify_request purge_rq;
688     fprintf(stderr, "\nExecuting test_partial_purge_items2...\n");
689 
690     N = 320000;
691     remove(testpurgefile);
692     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
693     root = insert_items(&db->file, NULL, uniq_reduce, uniq_rereduce, N);
694     assert(root != NULL);
695 
696     count = red_intval(root, 1);
697     range_start = red_intval(root, 2);
698     range_end = red_intval(root, count + 1);
699     assert(range_start == 0 && range_end == 63);
700 
701     fprintf(stderr, "Initial reduce value equals seq{0, 63}\n");
702 
703     purge_rq = purge_request(&db->file, uniq_reduce, uniq_rereduce,
704                         skip_purge_kp, skip_purge_kv, (void *) &purge_count);
705     newroot = guided_purge_btree(&purge_rq, root, &errcode);
706 
707     assert(purge_count == N / 2);
708     fprintf(stderr, "guided_purge returned correct accumulator N/2\n");
709 
710     count = red_intval(newroot, 1);
711     range_start = red_intval(newroot, 2);
712     range_end = red_intval(newroot, count + 1);
713     assert(red_intval(newroot, 0) == N / 2 && range_start == 0 && range_end == 31);
714     fprintf(stderr, "Reduce value after guided purge equals {0, 31}\n");
715 
716     try(iter_btree(&db->file, newroot, &iter_context, check_skiprange_callback));
717     fprintf(stderr, "Btree has only values within the range {0, 31} and keys are sorted\n");
718 
719 cleanup:
720     free(root);
721     free(newroot);
722     couchstore_close_db(db);
723     assert(errcode == 0);
724 }
725 
test_partial_purge_with_stopnull726 void test_partial_purge_with_stop()
727 {
728     int errcode, N;
729     int exp_evenodd[2];
730     int purge_count = 0;
731     Db *db = NULL;
732     node_pointer *root = NULL, *newroot = NULL;
733     couchfile_modify_request purge_rq;
734     fprintf(stderr, "\nExecuting test_partial_purge_items...\n");
735 
736     N = 211341;
737     exp_evenodd[0] = N / 2;
738     exp_evenodd[1] = N / 2 + N % 2;
739 
740     remove(testpurgefile);
741     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
742     root = insert_items(&db->file, NULL, evenodd_reduce, evenodd_rereduce, N);
743     assert(root != NULL);
744 
745     assert(exp_evenodd[0] == red_intval(root, 0) && exp_evenodd[1] == red_intval(root, 1));
746     fprintf(stderr, "Initial reduce value equals {NumEven, NumOdd}\n");
747 
748     purge_rq = purge_request(&db->file, evenodd_reduce, evenodd_rereduce,
749             evenodd_purge_kp, evenodd_stop_purge_kv, (void *) &purge_count);
750     newroot = guided_purge_btree(&purge_rq, root, &errcode);
751 
752     assert(purge_count == 4);
753     fprintf(stderr, "guided_purge returned correct accumulator - 4\n");
754 
755     assert(red_intval(newroot, 0) == exp_evenodd[0]);
756     assert(red_intval(newroot, 1) == (exp_evenodd[1] - 4));
757     fprintf(stderr, "Reduce value after guided purge equals {NumEven, NumOdd-4}\n");
758 
759     try(iter_btree(&db->file, newroot, NULL, check_odd_stop_callback));
760     fprintf(stderr, "Btree does not contain first 4 odd values after guided purge\n");
761 
762 cleanup:
763     free(root);
764     free(newroot);
765     couchstore_close_db(db);
766     assert(errcode == 0);
767 }
768 
test_add_remove_purgenull769 void test_add_remove_purge()
770 {
771     int errcode, N, i;
772     int exp_evenodd[2];
773     int purge_count = 0;
774     Db *db = NULL;
775     node_pointer *root = NULL, *newroot = NULL;
776     couchfile_modify_request purge_rq;
777     int *arr = NULL;
778     couchfile_modify_action *acts = NULL;
779     sized_buf *keys = NULL;
780     fprintf(stderr, "\nExecuting test_add_remove_purge...\n");
781 
782     N = 211341;
783     exp_evenodd[0] = N / 2;
784     exp_evenodd[1] = N / 2 + N % 2;
785 
786     remove(testpurgefile);
787     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
788     root = insert_items(&db->file, NULL, evenodd_reduce, evenodd_rereduce, N);
789     assert(root != NULL);
790 
791     assert(exp_evenodd[0] == red_intval(root, 0) && exp_evenodd[1] == red_intval(root, 1));
792     fprintf(stderr, "Initial reduce value equals {NumEven, NumOdd}\n");
793 
794     purge_rq = purge_request(&db->file, evenodd_reduce, evenodd_rereduce,
795                     evenodd_purge_kp, evenodd_purge_kv, (void *) &purge_count);
796 
797     /* Add few add and remove actions in the modify request */
798     arr = (int *) calloc(6, sizeof(int));
799     keys = (sized_buf *) calloc(6, sizeof(sized_buf));
800     acts = (couchfile_modify_action *) calloc(6, sizeof(couchfile_modify_action));
801 
802     arr[0] = 2;
803     arr[1] = 4;
804     arr[2] = 10;
805     arr[3] = 14006;
806     arr[4] = 200000;
807     arr[5] = 500000;
808 
809     acts[0].type = ACTION_INSERT;
810     acts[1].type = ACTION_REMOVE;
811     acts[2].type = ACTION_REMOVE;
812     acts[3].type = ACTION_INSERT;
813     acts[4].type = ACTION_REMOVE;
814     acts[5].type = ACTION_INSERT;
815 
816 
817     for (i = 0; i < 6; i++) {
818         keys[i].size  = sizeof(int);
819         keys[i].buf = (void *) &arr[i];
820         acts[i].key = &keys[i];
821         acts[i].value.data = &keys[i];
822     }
823 
824     purge_rq.actions = acts;
825     purge_rq.num_actions = 6;
826     purge_rq.enable_purging = 1;
827     newroot = modify_btree(&purge_rq, root, &errcode);
828 
829 
830     assert(purge_count == exp_evenodd[1]);
831     fprintf(stderr, "Btree add_remove with purge returned correct purge_count - Numodds\n");
832 
833     assert(red_intval(newroot, 0) == (exp_evenodd[0] - 2) && red_intval(newroot, 1) == 0);
834     fprintf(stderr, "Btree reduce value equals - {NumEven-2, 0}\n");
835 
836     try(iter_btree(&db->file, newroot, NULL, check_odd2_callback));
837     fprintf(stderr, "Btree has no odd values after guided purge\n");
838     fprintf(stderr, "Keys 4,10,200000 are not in tree after guided purge\n");
839 
840 cleanup:
841     free(root);
842     free(newroot);
843     free(keys);
844     free(acts);
845     free(arr);
846     couchstore_close_db(db);
847     assert(errcode == 0);
848 }
849 
test_only_single_leafnodenull850 void test_only_single_leafnode()
851 {
852     int errcode, N;
853     int redval;
854     int purge_sum[2] = {0,0};
855     Db *db = NULL;
856     node_pointer *root = NULL, *newroot = NULL;
857     couchfile_modify_request purge_rq;
858 
859     fprintf(stderr, "\nExecuting test_only_single_leafnode...\n");
860     N = 2;
861     remove(testpurgefile);
862     try(couchstore_open_db(testpurgefile, COUCHSTORE_OPEN_FLAG_CREATE, &db));
863     root = insert_items(&db->file, NULL, count_reduce, count_rereduce, N);
864     assert(root != NULL);
865 
866     redval = red_intval(root, 0);
867     assert(redval == N);
868     fprintf(stderr, "Initial reduce value equals N\n");
869 
870     purge_rq = purge_request(&db->file, count_reduce, count_rereduce, keepall_purge_kp, all_purge_kv, (void *) &purge_sum);
871     newroot = guided_purge_btree(&purge_rq, root, &errcode);
872 
873     assert(purge_sum[0] == N && purge_sum[1] == 0);
874     fprintf(stderr, "guided_purge returned correct accumulator {N,0}\n");
875 
876     redval = red_intval(newroot, 0);
877     assert(redval == 0);
878     fprintf(stderr, "Reduce value after guided purge equals 0\n");
879 
880     assert(newroot == NULL);
881     fprintf(stderr, "Btree is empty after guided purge\n");
882 
883 cleanup:
884     free(root);
885     free(newroot);
886     couchstore_close_db(db);
887     assert(errcode == 0);
888 }
889