varnish-cache/lib/libvarnish/vbh.c
1
/*-
2
 * Copyright (c) 2006 Verdens Gang AS
3
 * Copyright (c) 2006-2011 Varnish Software AS
4
 * All rights reserved.
5
 *
6
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
7
 *
8
 * SPDX-License-Identifier: BSD-2-Clause
9
 *
10
 * Redistribution and use in source and binary forms, with or without
11
 * modification, are permitted provided that the following conditions
12
 * are met:
13
 * 1. Redistributions of source code must retain the above copyright
14
 *    notice, this list of conditions and the following disclaimer.
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in the
17
 *    documentation and/or other materials provided with the distribution.
18
 *
19
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
23
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29
 * SUCH DAMAGE.
30
 *
31
 * Implementation of a binary heap API
32
 *
33
 * See also:
34
 *      http://dl.acm.org/citation.cfm?doid=1785414.1785434
35
 *      (or: http://queue.acm.org/detail.cfm?id=1814327)
36
 */
37
38
#include "config.h"
39
40
#include <limits.h>
41
#include <stdint.h>
42
#include <stdlib.h>
43
#include <unistd.h>
44
#include <string.h>
45
46
#include "miniobj.h"
47
#include "vdef.h"
48
#include "vas.h"
49
#include "vbh.h"
50
51
/* Parameters --------------------------------------------------------*/
52
53
/*
54
 * The number of elements in a row has to be a compromise between
55
 * wasted space and number of memory allocations.
56
 * With 64k objects per row, there will be at least 5...10 seconds
57
 * between row additions on a very busy server.
58
 * At the same time, the worst case amount of wasted memory is kept
59
 * at a reasonable 1 MB -- two rows on 64bit system.
60
 * Finally, but without practical significance: 16 bits should be
61
 * easier for the compiler to optimize.
62
 */
63
#define ROW_SHIFT               16
64
65
66
#undef PARANOIA
67
68
/* Private definitions -----------------------------------------------*/
69
70
#define ROOT_IDX                1
71
72
#define ROW_WIDTH               (1 << ROW_SHIFT)
73
74
/*lint -emacro(572, ROW) shift 0 >> by 16 */
75
/*lint -emacro(835, ROW) 0 left of >> */
76
/*lint -emacro(778, ROW) const >> evaluates to zero */
77
#define ROW(b, n)               ((b)->array[(n) >> ROW_SHIFT])
78
79
/*lint -emacro(835, A) 0 left of & */
80
#define A(b, n)                 ROW(b, n)[(n) & (ROW_WIDTH - 1)]
81
82
struct vbh {
83
        unsigned                magic;
84
#define VBH_MAGIC               0xf581581aU     /* from /dev/random */
85
        void                    *priv;
86
        vbh_cmp_t               *cmp;
87
        vbh_update_t            *update;
88
        void                    ***array;
89
        unsigned                rows;
90
        unsigned                length;
91
        unsigned                next;
92
        unsigned                page_size;
93
        unsigned                page_mask;
94
        unsigned                page_shift;
95
};
96
97
#define VM_AWARE
98
99
#ifdef VM_AWARE
100
101
static  unsigned
102 91559921
parent(const struct vbh *bh, unsigned u)
103
{
104
        unsigned po;
105
        unsigned v;
106
107 91559921
        assert(u != UINT_MAX);
108 91559921
        po = u & bh->page_mask;
109
110 91559921
        if (u < bh->page_size || po > 3) {
111 91166361
                v = (u & ~bh->page_mask) | (po >> 1);
112 91559921
        } else if (po < 2) {
113 194320
                v = (u - bh->page_size) >> bh->page_shift;
114 194320
                v += v & ~(bh->page_mask >> 1);
115 194320
                v |= bh->page_size / 2;
116 194320
        } else {
117 199240
                v = u - 2;
118
        }
119 91559921
        return (v);
120
}
121
122
static void
123 1425239121
child(const struct vbh *bh, unsigned u, unsigned *a, unsigned *b)
124
{
125
        uintmax_t uu;
126
127 1425239121
        if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
128
                /* First two elements are magical except on the first page */
129 90998240
                *a = *b = u + 2;
130 1425239121
        } else if (u & (bh->page_size >> 1)) {
131
                /* The bottom row is even more magical */
132 181285760
                *a = (u & ~bh->page_mask) >> 1;
133 181285760
                *a |= u & (bh->page_mask >> 1);
134 181285760
                *a += 1;
135 181285760
                uu = (uintmax_t)*a << bh->page_shift;
136 181285760
                *a = uu;
137 181285760
                if (*a == uu) {
138 181285440
                        *b = *a + 1;
139 181285440
                } else {
140
                        /*
141
                         * An unsigned is not big enough: clamp instead
142
                         * of truncating.  We do not support adding
143
                         * more than UINT_MAX elements anyway, so this
144
                         * is without consequence.
145
                         */
146 320
                        *a = UINT_MAX;
147 320
                        *b = UINT_MAX;
148
                }
149 181285760
        } else {
150
                /* The rest is as usual, only inside the page */
151 1152955121
                *a = u + (u & bh->page_mask);
152 1152955121
                *b = *a + 1;
153
        }
154
#ifdef PARANOIA
155
        assert(*a > 0);
156
        assert(*b > 0);
157
        if (*a != UINT_MAX) {
158
                assert(parent(bh, *a) == u);
159
                assert(parent(bh, *b) == u);
160
        }
161
#endif
162 1425239121
}
163
164
165
#else
166
167
static unsigned
168
parent(const struct vbh *bh, unsigned u)
169
{
170
171
        (void)bh;
172
        return (u / 2);
173
}
174
175
static void
176
child(const struct vbh *bh, unsigned u, unsigned *a, unsigned *b)
177
{
178
179
        (void)bh;
180
        *a = u * 2;
181
        *b = *a + 1;
182
}
183
184
#endif
185
186
/* Implementation ----------------------------------------------------*/
187
188
static void
189 199760
vbh_addrow(struct vbh *bh)
190
{
191
        unsigned u;
192
193
        /* First make sure we have space for another row */
194 199760
        if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
195 80
                u = bh->rows * 2;
196 80
                bh->array = realloc(bh->array, sizeof(*bh->array) * u);
197 80
                assert(bh->array != NULL);
198
199
                /* NULL out new pointers */
200 200
                while (bh->rows < u)
201 120
                        bh->array[bh->rows++] = NULL;
202 80
        }
203 199760
        assert(ROW(bh, bh->length) == NULL);
204 199760
        ROW(bh, bh->length) = malloc(sizeof(**bh->array) * ROW_WIDTH);
205 199760
        assert(ROW(bh, bh->length));
206 199760
        bh->length += ROW_WIDTH;
207 199760
}
208
209
struct vbh *
210 199560
VBH_new(void *priv, vbh_cmp_t *cmp_f, vbh_update_t *update_f)
211
{
212
        struct vbh *bh;
213
        unsigned u;
214
215 199560
        ALLOC_OBJ(bh, VBH_MAGIC);
216 199560
        if (bh == NULL)
217 0
                return (bh);
218 199560
        bh->priv = priv;
219
220 199560
        bh->page_size = (unsigned)getpagesize() / sizeof (void *);
221 199560
        bh->page_mask = bh->page_size - 1;
222 199560
        AZ(bh->page_size & bh->page_mask);      /* power of two */
223 1796040
        for (u = 1; (1U << u) != bh->page_size; u++)
224
                ;
225 199560
        bh->page_shift = u;
226 199560
        assert(bh->page_size <= (sizeof(**bh->array) * ROW_WIDTH));
227
228 199560
        bh->cmp = cmp_f;
229 199560
        bh->update = update_f;
230 199560
        bh->next = ROOT_IDX;
231
#ifdef TEST_DRIVER
232 40
        bh->rows = 1;           /* A tiny-ish number */
233
#else
234 199520
        bh->rows = 16;          /* A tiny-ish number */
235
#endif
236 199560
        bh->array = calloc(bh->rows, sizeof *bh->array);
237 199560
        assert(bh->array != NULL);
238 199560
        vbh_addrow(bh);
239 199560
        A(bh, ROOT_IDX) = NULL;
240 199560
        bh->magic = VBH_MAGIC;
241 199560
        return (bh);
242 199560
}
243
244
void
245 34440
VBH_destroy(struct vbh **bhp)
246
{
247
        struct vbh *bh;
248
        unsigned u;
249
250 34440
        TAKE_OBJ_NOTNULL(bh, bhp, VBH_MAGIC);
251 34440
        AZ(VBH_root(bh));
252
253 68920
        for (u = 0; u < bh->length; u += ROW_WIDTH)
254 34480
                free(ROW(bh, u));
255 34440
        free(bh->array);
256 34440
        FREE_OBJ(bh);
257 34440
}
258
259
static void
260 2792092148
vbh_update(const struct vbh *bh, unsigned u)
261
{
262 2792092148
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
263 2792092153
        assert(u < bh->next);
264 2792092174
        assert(A(bh, u) != NULL);
265 2792092223
        if (bh->update != NULL)
266 2792092225
                bh->update(bh->priv, A(bh, u), u);
267 2792092216
}
268
269
static void
270 1334644952
binhead_swap(const struct vbh *bh, unsigned u, unsigned v)
271
{
272
        void *p;
273
274 1334644952
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
275 1334644952
        assert(u < bh->next);
276 1334644953
        assert(A(bh, u) != NULL);
277 1334644953
        assert(v < bh->next);
278 1334644953
        assert(A(bh, v) != NULL);
279 1334644953
        p = A(bh, u);
280 1334644953
        A(bh, u) = A(bh, v);
281 1334644953
        A(bh, v) = p;
282 1334644953
        vbh_update(bh, u);
283 1334644953
        vbh_update(bh, v);
284 1334644953
}
285
286
static unsigned
287 152554187
vbh_trickleup(const struct vbh *bh, unsigned u)
288
{
289
        unsigned v;
290
291 152554187
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
292 152554185
        assert(u < bh->next);
293 152554185
        assert(A(bh, u) != NULL);
294
295 153001354
        while (u > ROOT_IDX) {
296 91559921
                assert(u < bh->next);
297 91559921
                assert(A(bh, u) != NULL);
298 91559921
                v = parent(bh, u);
299 91559921
                assert(v < u);
300 91559921
                assert(v < bh->next);
301 91559921
                assert(A(bh, v) != NULL);
302 91559920
                if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
303 91112761
                        break;
304 447161
                binhead_swap(bh, u, v);
305 447161
                u = v;
306
        }
307 152554216
        return (u);
308
}
309
310
static unsigned
311 91037609
vbh_trickledown(const struct vbh *bh, unsigned u)
312
{
313
        unsigned v1, v2;
314
315 91037609
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
316 91037609
        assert(u < bh->next);
317 91037609
        assert(A(bh, u) != NULL);
318
319 1425235401
        while (1) {
320 1425235401
                assert(u < bh->next);
321 1425235401
                assert(A(bh, u) != NULL);
322 1425235401
                child(bh, u, &v1, &v2);
323 1425235401
                assert(v1 > 0);
324 1425235401
                assert(v2 > 0);
325 1425235401
                assert(v1 <= v2);
326
327 1425235401
                if (v1 >= bh->next)
328 90968641
                        return (u);
329
330 1334266760
                assert(A(bh, v1) != NULL);
331 1334266760
                if (v1 != v2 && v2 < bh->next) {
332 1243070723
                        assert(A(bh, v2) != NULL);
333 1243070723
                        if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
334 112262
                                v1 = v2;
335 1243070723
                }
336 1334266760
                assert(v1 < bh->next);
337 1334266760
                assert(A(bh, v1) != NULL);
338 1334266760
                if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
339 68968
                        return (u);
340 1334197792
                binhead_swap(bh, u, v1);
341 1334197792
                u = v1;
342
        }
343 91037609
}
344
345
void
346 61516598
VBH_insert(struct vbh *bh, void *p)
347
{
348
        unsigned u;
349
350 61516598
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
351 61516589
        assert(bh->length >= bh->next);
352 61516585
        if (bh->length == bh->next)
353 200
                vbh_addrow(bh);
354 61516586
        assert(bh->length > bh->next);
355 61516589
        u = bh->next++;
356 61516589
        A(bh, u) = p;
357 61516589
        vbh_update(bh, u);
358 61516589
        (void)vbh_trickleup(bh, u);
359 61516589
        assert(u < bh->next);
360 61516551
        assert(A(bh, u) != NULL);
361 61516557
}
362
363
364
#ifdef PARANOIA
365
static void
366
chk(const struct vbh *bh)
367
{
368
        unsigned u, v;
369
370
        for (u = 2; u < bh->next; u++) {
371
                v = parent(bh, u);
372
                AZ(bh->cmp(bh->priv, A(bh, u), A(bh, v)));
373
        }
374
}
375
#endif
376
377
void *
378 73213111
VBH_root(const struct vbh *bh)
379
{
380
381 73213111
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
382
#ifdef PARANOIA
383
        chk(bh);
384
#endif
385 73213110
        return (A(bh, ROOT_IDX));
386
}
387
388
/*
389
 * It may seem counter-intuitive that we delete by replacement with
390
 * the tail object. "That's almost certain to not belong there, in
391
 * particular when we delete the root ?" is the typical reaction.
392
 *
393
 * If we tried to trickle up into the empty position, we would,
394
 * eventually, end up with a hole in the bottom row, at which point
395
 * we would move the tail object there.
396
 * But there is no guarantee that the tail object would not need to
397
 * trickle up from that position, in fact, it might be the new root
398
 * of this half of the subtree.
399
 * The total number of operations is guaranteed to be at least
400
 * N{height} downward selections, because we have to get the hole
401
 * all the way down, but in addition to that, we may get up to
402
 * N{height}-1 upward trickles.
403
 *
404
 * When we fill the hole with the tail object, the worst case is
405
 * that it trickles all the way up to of this half-tree, or down
406
 * to become the tail object again.
407
 *
408
 * In other words worst case is N{height} up or downward trickles.
409
 * But there is a decent chance that it does not make it all the way.
410
 */
411
412
void
413 61475713
VBH_delete(struct vbh *bh, unsigned idx)
414
{
415
416 61475713
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
417 61475712
        assert(bh->next > ROOT_IDX);
418 61475711
        assert(idx < bh->next);
419 61475711
        assert(idx > 0);
420 61475711
        assert(A(bh, idx) != NULL);
421 61475713
        bh->update(bh->priv, A(bh, idx), VBH_NOIDX);
422 61475713
        if (idx == --bh->next) {
423 189982
                A(bh, bh->next) = NULL;
424 189982
                return;
425
        }
426 61285729
        A(bh, idx) = A(bh, bh->next);
427 61285729
        A(bh, bh->next) = NULL;
428 61285729
        vbh_update(bh, idx);
429 61285729
        idx = vbh_trickleup(bh, idx);
430 61285729
        assert(idx < bh->next);
431 61285729
        assert(idx > 0);
432 61285729
        assert(A(bh, idx) != NULL);
433 61285729
        idx = vbh_trickledown(bh, idx);
434 61285729
        assert(idx < bh->next);
435 61285729
        assert(idx > 0);
436 61285729
        assert(A(bh, idx) != NULL);
437
438
        /*
439
         * We keep a hysteresis of one full row before we start to
440
         * return space to the OS to avoid silly behaviour around
441
         * row boundaries.
442
         */
443 61285729
        if (bh->next + 2 * ROW_WIDTH <= bh->length) {
444 160
                free(ROW(bh, bh->length - 1));
445 160
                ROW(bh, bh->length - 1) = NULL;
446 160
                bh->length -= ROW_WIDTH;
447 160
        }
448 61475711
}
449
450
/*
451
 * Move an item up/down after changing its key value
452
 */
453
454
void
455 29751880
VBH_reorder(const struct vbh *bh, unsigned idx)
456
{
457
458 29751880
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
459 29751880
        assert(bh->next > ROOT_IDX);
460 29751880
        assert(idx < bh->next);
461 29751880
        assert(idx > 0);
462 29751880
        assert(A(bh, idx) != NULL);
463 29751880
        idx = vbh_trickleup(bh, idx);
464 29751880
        assert(idx < bh->next);
465 29751880
        assert(idx > 0);
466 29751880
        assert(A(bh, idx) != NULL);
467 29751880
        idx = vbh_trickledown(bh, idx);
468 29751880
        assert(idx < bh->next);
469 29751880
        assert(idx > 0);
470 29751880
        assert(A(bh, idx) != NULL);
471 29751880
}
472
473
#ifdef TEST_DRIVER
474
475
#include <stdio.h>
476
#include <string.h>
477
478
#include "vrnd.h"
479
480
/* Test driver -------------------------------------------------------*/
481
482
struct foo {
483
        unsigned        magic;
484
#define FOO_MAGIC       0x23239823
485
        unsigned        idx;
486
        unsigned        key;
487
        unsigned        n;
488
};
489
490
#define M 500083        /* Number of operations */
491
#define N 131101        /* Number of items */
492
#define R -1            /* Random modulus */
493
494
static struct foo *ff[N];
495
496
static int v_matchproto_(vbh_cmp_t)
497 2666543560
cmp(void *priv, const void *a, const void *b)
498
{
499
        const struct foo *fa, *fb;
500
501 2666543560
        (void)priv;
502 2666543560
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
503 2666543560
        CAST_OBJ_NOTNULL(fb, b, FOO_MAGIC);
504 2666543560
        return (fa->key < fb->key);
505
}
506
507
static void v_matchproto_(vbh_update_t)
508 2849299000
update(void *priv, void *a, unsigned u)
509
{
510
        struct foo *fa;
511
512 2849299000
        (void)priv;
513 2849299000
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
514 2849299000
        fa->idx = u;
515 2849299000
}
516
517
#ifdef CHECK2
518
static void
519
chk2(struct vbh *bh)
520
{
521
        unsigned u, v;
522
        struct foo *fa, *fb;
523
524
        for (u = 2; u < bh->next; u++) {
525
                v = parent(bh, u);
526
                fa = A(bh, u);
527
                fb = A(bh, v);
528
                assert(fa->key >= fb->key);
529
        }
530
}
531
#endif
532
533
static void
534 261016000
vrnd_lock(void)
535
{
536 261016000
}
537
538
int
539 40
main(void)
540
{
541
        struct vbh *bh;
542
        unsigned j, u, v, lr, n;
543
        struct foo *fp;
544
545 40
        VRND_SeedAll();
546 40
        VRND_SeedTestable(1);
547 40
        VRND_Lock = vrnd_lock;
548 40
        VRND_Unlock = vrnd_lock;
549
550 40
        bh = VBH_new(NULL, cmp, update);
551 1280
        for (n = 2; n; n += n) {
552 1240
                child(bh, n - 1, &u, &v);
553 1240
                child(bh, n, &u, &v);
554 1240
                child(bh, n + 1, &u, &v);
555 1240
        }
556
557 40
        lr = 0; /* unconfuse some compilers... */
558
559 120
        for (j = 0; j < 2; j++) {
560
                /* First insert our N elements */
561 10488160
                for (u = 0; u < N; u++) {
562 10488080
                        lr = VRND_RandomTestable() % R;
563 10488080
                        ALLOC_OBJ(ff[u], FOO_MAGIC);
564 10488080
                        assert(ff[u] != NULL);
565 10488080
                        ff[u]->key = lr;
566 10488080
                        ff[u]->n = u;
567 10488080
                        VBH_insert(bh, ff[u]);
568
569 10488080
                        fp = VBH_root(bh);
570 10488080
                        assert(fp->idx == 1);
571 10488080
                        assert(fp->key <= lr);
572 10488080
                }
573 80
                fprintf(stderr, "%d inserts OK\n", N);
574
                /* For M cycles, pick the root, insert new */
575 40006720
                for (u = 0; u < M; u++) {
576 40006640
                        fp = VBH_root(bh);
577 40006640
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
578 40006640
                        assert(fp->idx == 1);
579
580
                        /*
581
                         * It cannot possibly be larger than the last
582
                         * value we added
583
                         */
584 40006640
                        assert(fp->key <= lr);
585 40006640
                        VBH_delete(bh, fp->idx);
586
587 40006640
                        n = fp->n;
588 40006640
                        ALLOC_OBJ(ff[n], FOO_MAGIC);
589 40006640
                        assert(ff[n] != NULL);
590 40006640
                        FREE_OBJ(fp);
591 40006640
                        fp = ff[n];
592 40006640
                        fp->n = n;
593
594 40006640
                        lr = VRND_RandomTestable() % R;
595 40006640
                        fp->key = lr;
596 40006640
                        VBH_insert(bh, fp);
597 40006640
                }
598 80
                fprintf(stderr, "%d replacements OK\n", M);
599
                /* The remove everything */
600 80
                lr = 0;
601 10488160
                for (u = 0; u < N; u++) {
602 10488080
                        fp = VBH_root(bh);
603 10488080
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
604 10488080
                        assert(fp->idx == 1);
605 10488080
                        assert(fp->key >= lr);
606 10488080
                        lr = fp->key;
607 10488080
                        VBH_delete(bh, fp->idx);
608 10488080
                        ff[fp->n] = NULL;
609 10488080
                        FREE_OBJ(fp);
610 10488080
                }
611 80
                fprintf(stderr, "%d removes OK\n", N);
612
613 40006720
                for (u = 0; u < M; u++) {
614 40006640
                        v = VRND_RandomTestable() % N;
615 40006640
                        if (ff[v] != NULL) {
616 29748600
                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
617 29748600
                                AN(ff[v]->idx);
618 29748600
                                if (ff[v]->key & 1) {
619 0
                                        VBH_delete(bh, ff[v]->idx);
620 0
                                        assert(ff[v]->idx == VBH_NOIDX);
621 0
                                        FREE_OBJ(ff[v]);
622 0
                                        ff[v] = NULL;
623 0
                                } else {
624 29748600
                                        ff[v]->key = VRND_RandomTestable() % R;
625 29748600
                                        VBH_reorder(bh, ff[v]->idx);
626
                                }
627 29748600
                        } else {
628 10258040
                                ALLOC_OBJ(ff[v], FOO_MAGIC);
629 10258040
                                assert(ff[v] != NULL);
630 10258040
                                ff[v]->key = VRND_RandomTestable() % R;
631 10258040
                                VBH_insert(bh, ff[v]);
632 10258040
                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
633 10258040
                                AN(ff[v]->idx);
634
                        }
635
#ifdef CHECK2
636
                        chk2(bh);
637
#endif
638 40006640
                }
639 80
                fprintf(stderr, "%d updates OK\n", M);
640 80
        }
641 10258080
        while ((fp = VBH_root(bh)) != NULL) {
642 10258040
                VBH_delete(bh, fp->idx);
643 10258040
                FREE_OBJ(fp);
644
        }
645 40
        VBH_destroy(&bh);
646 40
        AZ(bh);
647 40
        return (0);
648
}
649
#endif