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 64148190
parent(const struct vbh *bh, unsigned u)
102
{
103
        unsigned po;
104
        unsigned v;
105
106 64148190
        assert(u != UINT_MAX);
107 64148190
        po = u & bh->page_mask;
108
109 64148190
        if (u < bh->page_size || po > 3) {
110 63872698
                v = (u & ~bh->page_mask) | (po >> 1);
111 64148190
        } else if (po < 2) {
112 136024
                v = (u - bh->page_size) >> bh->page_shift;
113 136024
                v += v & ~(bh->page_mask >> 1);
114 136024
                v |= bh->page_size / 2;
115 136024
        } else {
116 139468
                v = u - 2;
117
        }
118 64148190
        return (v);
119
}
120
121
static void
122 997732686
child(const struct vbh *bh, unsigned u, unsigned *a, unsigned *b)
123
{
124
        uintmax_t uu;
125
126 997732686
        if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
127
                /* First two elements are magical except on the first page */
128 63698768
                *a = *b = u + 2;
129 997732686
        } else if (u & (bh->page_size >> 1)) {
130
                /* The bottom row is even more magical */
131 126900032
                *a = (u & ~bh->page_mask) >> 1;
132 126900032
                *a |= u & (bh->page_mask >> 1);
133 126900032
                *a += 1;
134 126900032
                uu = (uintmax_t)*a << bh->page_shift;
135 126900032
                *a = uu;
136 126900032
                if (*a == uu) {
137 126899808
                        *b = *a + 1;
138 126899808
                } 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 224
                        *a = UINT_MAX;
146 224
                        *b = UINT_MAX;
147
                }
148 126900032
        } else {
149
                /* The rest is as usual, only inside the page */
150 807133886
                *a = u + (u & bh->page_mask);
151 807133886
                *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 997732686
}
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 148164
vbh_addrow(struct vbh *bh)
189
{
190
        unsigned u;
191
192
        /* First make sure we have space for another row */
193 148164
        if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
194 56
                u = bh->rows * 2;
195 56
                bh->array = realloc(bh->array, sizeof(*bh->array) * u);
196 56
                assert(bh->array != NULL);
197
198
                /* NULL out new pointers */
199 140
                while (bh->rows < u)
200 84
                        bh->array[bh->rows++] = NULL;
201 56
        }
202 148164
        assert(ROW(bh, bh->length) == NULL);
203 148164
        ROW(bh, bh->length) = malloc(sizeof(**bh->array) * ROW_WIDTH);
204 148164
        assert(ROW(bh, bh->length));
205 148164
        bh->length += ROW_WIDTH;
206 148164
}
207
208
struct vbh *
209 148024
VBH_new(void *priv, vbh_cmp_t *cmp_f, vbh_update_t *update_f)
210
{
211
        struct vbh *bh;
212
        unsigned u;
213
214 148024
        ALLOC_OBJ(bh, VBH_MAGIC);
215 148024
        if (bh == NULL)
216 0
                return (bh);
217 148024
        bh->priv = priv;
218
219 148024
        bh->page_size = (unsigned)getpagesize() / sizeof (void *);
220 148024
        bh->page_mask = bh->page_size - 1;
221 148024
        AZ(bh->page_size & bh->page_mask);      /* power of two */
222 1332216
        for (u = 1; (1U << u) != bh->page_size; u++)
223
                ;
224 148024
        bh->page_shift = u;
225 148024
        assert(bh->page_size <= (sizeof(**bh->array) * ROW_WIDTH));
226
227 148024
        bh->cmp = cmp_f;
228 148024
        bh->update = update_f;
229 148024
        bh->next = ROOT_IDX;
230
#ifdef TEST_DRIVER
231 28
        bh->rows = 1;           /* A tiny-ish number */
232
#else
233 147996
        bh->rows = 16;          /* A tiny-ish number */
234
#endif
235 148024
        bh->array = calloc(bh->rows, sizeof *bh->array);
236 148024
        assert(bh->array != NULL);
237 148024
        vbh_addrow(bh);
238 148024
        A(bh, ROOT_IDX) = NULL;
239 148024
        bh->magic = VBH_MAGIC;
240 148024
        return (bh);
241 148024
}
242
243
void
244 26208
VBH_destroy(struct vbh **bhp)
245
{
246
        struct vbh *bh;
247
        unsigned u;
248
249 26208
        TAKE_OBJ_NOTNULL(bh, bhp, VBH_MAGIC);
250 26208
        AZ(VBH_root(bh));
251
252 52444
        for (u = 0; u < bh->length; u += ROW_WIDTH)
253 26236
                free(ROW(bh, u));
254 26208
        free(bh->array);
255 26208
        FREE_OBJ(bh);
256 26208
}
257
258
static void
259 1954652229
vbh_update(const struct vbh *bh, unsigned u)
260
{
261 1954652229
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
262 1954652229
        assert(u < bh->next);
263 1954652229
        assert(A(bh, u) != NULL);
264 1954652229
        if (bh->update != NULL)
265 1954652229
                bh->update(bh->priv, A(bh, u), u);
266 1954652229
}
267
268
static void
269 934312322
binhead_swap(const struct vbh *bh, unsigned u, unsigned v)
270
{
271
        void *p;
272
273 934312322
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
274 934312322
        assert(u < bh->next);
275 934312322
        assert(A(bh, u) != NULL);
276 934312322
        assert(v < bh->next);
277 934312322
        assert(A(bh, v) != NULL);
278 934312322
        p = A(bh, u);
279 934312322
        A(bh, u) = A(bh, v);
280 934312322
        A(bh, v) = p;
281 934312322
        vbh_update(bh, u);
282 934312322
        vbh_update(bh, v);
283 934312322
}
284
285
static unsigned
286 106853892
vbh_trickleup(const struct vbh *bh, unsigned u)
287
{
288
        unsigned v;
289
290 106853892
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
291 106853892
        assert(u < bh->next);
292 106853892
        assert(A(bh, u) != NULL);
293
294 107191111
        while (u > ROOT_IDX) {
295 64148190
                assert(u < bh->next);
296 64148190
                assert(A(bh, u) != NULL);
297 64148190
                v = parent(bh, u);
298 64148190
                assert(v < u);
299 64148190
                assert(v < bh->next);
300 64148190
                assert(A(bh, v) != NULL);
301 64148190
                if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
302 63810971
                        break;
303 337219
                binhead_swap(bh, u, v);
304 337219
                u = v;
305
        }
306 106853892
        return (u);
307
}
308
309
static unsigned
310 63754979
vbh_trickledown(const struct vbh *bh, unsigned u)
311
{
312
        unsigned v1, v2;
313
314 63754979
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
315 63754979
        assert(u < bh->next);
316 63754979
        assert(A(bh, u) != NULL);
317
318 997730082
        while (1) {
319 997730082
                assert(u < bh->next);
320 997730082
                assert(A(bh, u) != NULL);
321 997730082
                child(bh, u, &v1, &v2);
322 997730082
                assert(v1 > 0);
323 997730082
                assert(v2 > 0);
324 997730082
                assert(v1 <= v2);
325
326 997730082
                if (v1 >= bh->next)
327 63703786
                        return (u);
328
329 934026296
                assert(A(bh, v1) != NULL);
330 934026296
                if (v1 != v2 && v2 < bh->next) {
331 870178191
                        assert(A(bh, v2) != NULL);
332 870178191
                        if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
333 83304
                                v1 = v2;
334 870178191
                }
335 934026296
                assert(v1 < bh->next);
336 934026296
                assert(A(bh, v1) != NULL);
337 934026296
                if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
338 51193
                        return (u);
339 933975103
                binhead_swap(bh, u, v1);
340 933975103
                u = v1;
341
        }
342 63754979
}
343
344
void
345 43098986
VBH_insert(struct vbh *bh, void *p)
346
{
347
        unsigned u;
348
349 43098986
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
350 43098986
        assert(bh->length >= bh->next);
351 43098986
        if (bh->length == bh->next)
352 140
                vbh_addrow(bh);
353 43098986
        assert(bh->length > bh->next);
354 43098986
        u = bh->next++;
355 43098986
        A(bh, u) = p;
356 43098986
        vbh_update(bh, u);
357 43098986
        (void)vbh_trickleup(bh, u);
358 43098986
        assert(u < bh->next);
359 43098986
        assert(A(bh, u) != NULL);
360 43098986
}
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 51361358
VBH_root(const struct vbh *bh)
378
{
379
380 51361358
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
381
#ifdef PARANOIA
382
        chk(bh);
383
#endif
384 51361358
        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 43069315
VBH_delete(struct vbh *bh, unsigned idx)
413
{
414
415 43069315
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
416 43069315
        assert(bh->next > ROOT_IDX);
417 43069315
        assert(idx < bh->next);
418 43069315
        assert(idx > 0);
419 43069315
        assert(A(bh, idx) != NULL);
420 43069315
        bh->update(bh->priv, A(bh, idx), VBH_NOIDX);
421 43069315
        if (idx == --bh->next) {
422 140652
                A(bh, bh->next) = NULL;
423 140652
                return;
424
        }
425 42928663
        A(bh, idx) = A(bh, bh->next);
426 42928663
        A(bh, bh->next) = NULL;
427 42928663
        vbh_update(bh, idx);
428 42928663
        idx = vbh_trickleup(bh, idx);
429 42928663
        assert(idx < bh->next);
430 42928663
        assert(idx > 0);
431 42928663
        assert(A(bh, idx) != NULL);
432 42928663
        idx = vbh_trickledown(bh, idx);
433 42928663
        assert(idx < bh->next);
434 42928663
        assert(idx > 0);
435 42928663
        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 42928663
        if (bh->next + 2 * ROW_WIDTH <= bh->length) {
443 112
                free(ROW(bh, bh->length - 1));
444 112
                ROW(bh, bh->length - 1) = NULL;
445 112
                bh->length -= ROW_WIDTH;
446 112
        }
447 43069315
}
448
449
/*
450
 * Move an item up/down after changing its key value
451
 */
452
453
void
454 20826316
VBH_reorder(const struct vbh *bh, unsigned idx)
455
{
456
457 20826316
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
458 20826316
        assert(bh->next > ROOT_IDX);
459 20826316
        assert(idx < bh->next);
460 20826316
        assert(idx > 0);
461 20826316
        assert(A(bh, idx) != NULL);
462 20826316
        idx = vbh_trickleup(bh, idx);
463 20826316
        assert(idx < bh->next);
464 20826316
        assert(idx > 0);
465 20826316
        assert(A(bh, idx) != NULL);
466 20826316
        idx = vbh_trickledown(bh, idx);
467 20826316
        assert(idx < bh->next);
468 20826316
        assert(idx > 0);
469 20826316
        assert(A(bh, idx) != NULL);
470 20826316
}
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 1866580492
cmp(void *priv, const void *a, const void *b)
497
{
498
        const struct foo *fa, *fb;
499
500 1866580492
        (void)priv;
501 1866580492
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
502 1866580492
        CAST_OBJ_NOTNULL(fb, b, FOO_MAGIC);
503 1866580492
        return (fa->key < fb->key);
504
}
505
506
static void v_matchproto_(vbh_update_t)
507 1994509300
update(void *priv, void *a, unsigned u)
508
{
509
        struct foo *fa;
510
511 1994509300
        (void)priv;
512 1994509300
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
513 1994509300
        fa->idx = u;
514 1994509300
}
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 182711200
vrnd_lock(void)
534
{
535 182711200
}
536
537
int
538 28
main(void)
539
{
540
        struct vbh *bh;
541
        unsigned j, u, v, lr, n;
542
        struct foo *fp;
543
544 28
        VRND_SeedAll();
545 28
        VRND_SeedTestable(1);
546 28
        VRND_Lock = vrnd_lock;
547 28
        VRND_Unlock = vrnd_lock;
548
549 28
        bh = VBH_new(NULL, cmp, update);
550 896
        for (n = 2; n; n += n) {
551 868
                child(bh, n - 1, &u, &v);
552 868
                child(bh, n, &u, &v);
553 868
                child(bh, n + 1, &u, &v);
554 868
        }
555
556 28
        lr = 0; /* unconfuse some compilers... */
557
558 84
        for (j = 0; j < 2; j++) {
559
                /* First insert our N elements */
560 7341712
                for (u = 0; u < N; u++) {
561 7341656
                        lr = VRND_RandomTestable() % R;
562 7341656
                        ALLOC_OBJ(ff[u], FOO_MAGIC);
563 7341656
                        assert(ff[u] != NULL);
564 7341656
                        ff[u]->key = lr;
565 7341656
                        ff[u]->n = u;
566 7341656
                        VBH_insert(bh, ff[u]);
567
568 7341656
                        fp = VBH_root(bh);
569 7341656
                        assert(fp->idx == 1);
570 7341656
                        assert(fp->key <= lr);
571 7341656
                }
572 56
                fprintf(stderr, "%d inserts OK\n", N);
573
                /* For M cycles, pick the root, insert new */
574 28004704
                for (u = 0; u < M; u++) {
575 28004648
                        fp = VBH_root(bh);
576 28004648
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
577 28004648
                        assert(fp->idx == 1);
578
579
                        /*
580
                         * It cannot possibly be larger than the last
581
                         * value we added
582
                         */
583 28004648
                        assert(fp->key <= lr);
584 28004648
                        VBH_delete(bh, fp->idx);
585
586 28004648
                        n = fp->n;
587 28004648
                        ALLOC_OBJ(ff[n], FOO_MAGIC);
588 28004648
                        assert(ff[n] != NULL);
589 28004648
                        FREE_OBJ(fp);
590 28004648
                        fp = ff[n];
591 28004648
                        fp->n = n;
592
593 28004648
                        lr = VRND_RandomTestable() % R;
594 28004648
                        fp->key = lr;
595 28004648
                        VBH_insert(bh, fp);
596 28004648
                }
597 56
                fprintf(stderr, "%d replacements OK\n", M);
598
                /* The remove everything */
599 56
                lr = 0;
600 7341712
                for (u = 0; u < N; u++) {
601 7341656
                        fp = VBH_root(bh);
602 7341656
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
603 7341656
                        assert(fp->idx == 1);
604 7341656
                        assert(fp->key >= lr);
605 7341656
                        lr = fp->key;
606 7341656
                        VBH_delete(bh, fp->idx);
607 7341656
                        ff[fp->n] = NULL;
608 7341656
                        FREE_OBJ(fp);
609 7341656
                }
610 56
                fprintf(stderr, "%d removes OK\n", N);
611
612 28004704
                for (u = 0; u < M; u++) {
613 28004648
                        v = VRND_RandomTestable() % N;
614 28004648
                        if (ff[v] != NULL) {
615 20824020
                                CHECK_OBJ(ff[v], FOO_MAGIC);
616 20824020
                                AN(ff[v]->idx);
617 20824020
                                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 20824020
                                        ff[v]->key = VRND_RandomTestable() % R;
624 20824020
                                        VBH_reorder(bh, ff[v]->idx);
625
                                }
626 20824020
                        } else {
627 7180628
                                ALLOC_OBJ(ff[v], FOO_MAGIC);
628 7180628
                                assert(ff[v] != NULL);
629 7180628
                                ff[v]->key = VRND_RandomTestable() % R;
630 7180628
                                VBH_insert(bh, ff[v]);
631 7180628
                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
632 7180628
                                AN(ff[v]->idx);
633
                        }
634
#ifdef CHECK2
635
                        chk2(bh);
636
#endif
637 28004648
                }
638 56
                fprintf(stderr, "%d updates OK\n", M);
639 56
        }
640 7180656
        while ((fp = VBH_root(bh)) != NULL) {
641 7180628
                CHECK_OBJ(fp, FOO_MAGIC);
642 7180628
                VBH_delete(bh, fp->idx);
643 7180628
                FREE_OBJ(fp);
644
        }
645 28
        VBH_destroy(&bh);
646 28
        AZ(bh);
647 28
        return (0);
648
}
649
#endif