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