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