test_min_heap.c revision fb3e20e0 
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#ifdef _MSC_VER
50    prev_val = 0;
51#endif
52    for (i = 0; i < MAX_ELEMS; ++i)
53    {
54        p = lsquic_mh_pop(&heap);
55        if (i)
56            assert((uintptr_t) p >= prev_val);
57        prev_val = (uintptr_t) p;
58    }
59
60    heap.mh_nelem = 0;
61    for (i = MAX_ELEMS; i > 0; --i)
62        lsquic_mh_insert(&heap, (void *) i, i);
63    verify_min_heap(&heap);
64    for (i = 0; i < MAX_ELEMS; ++i)
65    {
66        p = lsquic_mh_pop(&heap);
67        if (i)
68            assert((uintptr_t) p >= prev_val);
69        prev_val = (uintptr_t) p;
70    }
71
72    heap.mh_nelem = 0;
73
74#if FLOYD
75    /* Now use Floyd method */
76    heap.mh_nelem = 0;
77    for (i = 0; i < MAX_ELEMS; ++i)
78        lsquic_mh_push(&heap, NULL, i);
79    lsquic_mh_heapify(&heap);
80    verify_min_heap(&heap);
81
82    heap.mh_nelem = 0;
83    for (i = MAX_ELEMS; i > 0; --i)
84        lsquic_mh_push(&heap, NULL, i);
85    lsquic_mh_heapify(&heap);
86    verify_min_heap(&heap);
87#endif
88}
89
90
91int
92main (int argc, char **argv)
93{
94    if (argc == 1)
95    {
96        test_min_heap();
97        return 0;
98    }
99
100    if (argc != 4)
101    {
102        fprintf(stderr, "usage: %s nelems iters method\n"
103                        "  method is 0: insert; 1: floyd\n", argv[0]);
104        return 1;
105    }
106
107    unsigned i, j, n_iters, nelems;
108    struct min_heap_elem *els;
109    unsigned *vals;
110    struct min_heap heap;
111
112    nelems = atoi(argv[1]);
113    n_iters = atoi(argv[2]);
114#if FLOYD
115    const int floyd = atoi(argv[3]);
116#endif
117
118    vals = malloc(sizeof(vals[0]) * nelems);
119    assert(vals);
120    for (i = 0; i < nelems; ++i)
121        vals[i] = rand();
122    els = malloc(sizeof(els[0]) * nelems);
123    assert(els);
124    heap.mh_elems = els;
125    heap.mh_nalloc = nelems;
126    heap.mh_nelem = 0;
127#if FLOYD
128    if (floyd)
129    {
130        for (i = 0; i < nelems; ++i)
131            lsquic_mh_push(&heap, NULL, vals[i]);
132        lsquic_mh_heapify(&heap);
133    }
134    else
135#endif
136        for (i = 0; i < nelems; ++i)
137            lsquic_mh_insert(&heap, NULL, vals[i]);
138    verify_min_heap(&heap);
139
140#if FLOYD
141    if (floyd)
142    {
143        for (j = 0; j < n_iters; ++j)
144        {
145            heap.mh_nelem = 0;
146            for (i = 0; i < nelems; ++i)
147                lsquic_mh_push(&heap, NULL, vals[i]);
148            lsquic_mh_heapify(&heap);
149        }
150    }
151    else
152#endif
153    {
154        for (j = 0; j < n_iters; ++j)
155        {
156            heap.mh_nelem = 0;
157            for (i = 0; i < nelems; ++i)
158                lsquic_mh_insert(&heap, NULL, vals[i]);
159        }
160    }
161
162    free(els);
163    free(vals);
164    return 0;
165}
166