test_min_heap.c revision 9a690580 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2/* Test min heap or benchmark heap creation */
3
4/* Floyd mechanism has been removed.  It's not faster. */
5#define FLOYD 0
6
7#include <assert.h>
8#include <stddef.h>
9#include <stdint.h>
10#include <stdio.h>
11#include <stdlib.h>
12
13#include "lsquic_min_heap.h"
14
15static void
16verify_min_heap (const struct min_heap *heap)
17{
18    unsigned i;
19
20    for (i = 0; i < heap->mh_nelem; ++i)
21    {
22        if (MHE_LCHILD(i) < heap->mh_nelem)
23            assert(heap->mh_elems[i].mhe_val <=
24                        heap->mh_elems[MHE_LCHILD(i)].mhe_val);
25        if (MHE_RCHILD(i) < heap->mh_nelem)
26            assert(heap->mh_elems[i].mhe_val <=
27                        heap->mh_elems[MHE_RCHILD(i)].mhe_val);
28    }
29}
30
31
32#define MAX_ELEMS 1000
33
34static void
35test_min_heap (void)
36{
37    struct min_heap heap;
38    uint64_t i, prev_val;
39    void *p;
40    struct min_heap_elem els[MAX_ELEMS];
41
42    heap.mh_elems = els;
43    heap.mh_nalloc = MAX_ELEMS;
44
45    heap.mh_nelem = 0;
46    for (i = 0; i < MAX_ELEMS; ++i)
47        lsquic_mh_insert(&heap, (void *) i, i);
48    verify_min_heap(&heap);
49    for (i = 0; i < MAX_ELEMS; ++i)
50    {
51        p = lsquic_mh_pop(&heap);
52        if (i)
53            assert((uintptr_t) p >= prev_val);
54        prev_val = (uintptr_t) p;
55    }
56
57    heap.mh_nelem = 0;
58    for (i = MAX_ELEMS; i > 0; --i)
59        lsquic_mh_insert(&heap, (void *) i, i);
60    verify_min_heap(&heap);
61    for (i = 0; i < MAX_ELEMS; ++i)
62    {
63        p = lsquic_mh_pop(&heap);
64        if (i)
65            assert((uintptr_t) p >= prev_val);
66        prev_val = (uintptr_t) p;
67    }
68
69    heap.mh_nelem = 0;
70
71#if FLOYD
72    /* Now use Floyd method */
73    heap.mh_nelem = 0;
74    for (i = 0; i < MAX_ELEMS; ++i)
75        lsquic_mh_push(&heap, NULL, i);
76    lsquic_mh_heapify(&heap);
77    verify_min_heap(&heap);
78
79    heap.mh_nelem = 0;
80    for (i = MAX_ELEMS; i > 0; --i)
81        lsquic_mh_push(&heap, NULL, i);
82    lsquic_mh_heapify(&heap);
83    verify_min_heap(&heap);
84#endif
85}
86
87
88int
89main (int argc, char **argv)
90{
91    if (argc == 1)
92    {
93        test_min_heap();
94        return 0;
95    }
96
97    if (argc != 4)
98    {
99        fprintf(stderr, "usage: %s nelems iters method\n"
100                        "  method is 0: insert; 1: floyd\n", argv[0]);
101        return 1;
102    }
103
104    unsigned i, j, n_iters, nelems;
105    struct min_heap_elem *els;
106    unsigned *vals;
107    struct min_heap heap;
108
109    nelems = atoi(argv[1]);
110    n_iters = atoi(argv[2]);
111#if FLOYD
112    const int floyd = atoi(argv[3]);
113#endif
114
115    vals = malloc(sizeof(vals[0]) * nelems);
116    assert(vals);
117    for (i = 0; i < nelems; ++i)
118        vals[i] = rand();
119    els = malloc(sizeof(els[0]) * nelems);
120    assert(els);
121    heap.mh_elems = els;
122    heap.mh_nalloc = nelems;
123    heap.mh_nelem = 0;
124#if FLOYD
125    if (floyd)
126    {
127        for (i = 0; i < nelems; ++i)
128            lsquic_mh_push(&heap, NULL, vals[i]);
129        lsquic_mh_heapify(&heap);
130    }
131    else
132#endif
133        for (i = 0; i < nelems; ++i)
134            lsquic_mh_insert(&heap, NULL, vals[i]);
135    verify_min_heap(&heap);
136
137#if FLOYD
138    if (floyd)
139    {
140        for (j = 0; j < n_iters; ++j)
141        {
142            heap.mh_nelem = 0;
143            for (i = 0; i < nelems; ++i)
144                lsquic_mh_push(&heap, NULL, vals[i]);
145            lsquic_mh_heapify(&heap);
146        }
147    }
148    else
149#endif
150    {
151        for (j = 0; j < n_iters; ++j)
152        {
153            heap.mh_nelem = 0;
154            for (i = 0; i < nelems; ++i)
155                lsquic_mh_insert(&heap, NULL, vals[i]);
156        }
157    }
158
159    free(els);
160    free(vals);
161    return 0;
162}
163