code.grnet.gr Git - archipelago/blob - xseg/xtypes/xbinheap_test.c

   1 /*
   2  * Copyright 2013 GRNET S.A. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or
   5  * without modification, are permitted provided that the following
   6  * conditions are met:
   7  *
   8  *   1. Redistributions of source code must retain the above
   9  *      copyright notice, this list of conditions and the following
  10  *      disclaimer.
  11  *   2. Redistributions in binary form must reproduce the above
  12  *      copyright notice, this list of conditions and the following
  13  *      disclaimer in the documentation and/or other materials
  14  *      provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  17  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  23  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  24  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * The views and conclusions contained in the software and
  30  * documentation are those of the authors and should not be
  31  * interpreted as representing official policies, either expressed
  32  * or implied, of GRNET S.A.
  33  */
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <sys/time.h>
  38 #include "xbinheap.h"
  39
  40 xbinheap_handler *handlers;
  41 int test1(unsigned long n)
  42 {
  43         struct xbinheap h;
  44         xbinheapidx i, r;
  45         long j;
  46         handlers = malloc(sizeof(xbinheap_handler) * n);
  47         xbinheap_init(&h, n, XBINHEAP_MAX, NULL);
  48         for (i = 0; i < n; i++) {
  49                 handlers[i] = xbinheap_insert(&h, i, i);
  50                 if (handlers[i] == NoNode){
  51                         fprintf(stderr, "Error inserting %llu\n", i);
  52                         return -1;
  53                 }
  54         }
  55         for (j = n-1; j >=0; j--) {
  56                 i = j;
  57                 r = xbinheap_extract(&h);
  58                 if (r != i){
  59                         fprintf(stderr, "Extracted invalid value %llu != %llu\n", r, i);
  60                         return -1;
  61                 }
  62         }
  63         for (i = 0; i < n; i++) {
  64                 handlers[i] = xbinheap_insert(&h, i, i);
  65         }
  66         xbinheap_increasekey(&h, handlers[0], n);
  67         r = xbinheap_extract(&h);
  68         if (r != 0){
  69                 fprintf(stderr, "Extracted invalid value after increase %llu != 0\n", r);
  70                 return -1;
  71         }
  72         handlers[0] = xbinheap_insert(&h, n+1, n+1);
  73         printf("handler[0]: %llu\n", handlers[0]);
  74         r = xbinheap_getkey(&h, handlers[0]);
  75         if (r != n+1){
  76                 fprintf(stderr, "getkey: got %llu, instead of %lu\n", r, n+1);
  77                 return -1;
  78         }
  79         r = xbinheap_peak(&h);
  80         if (r != n+1){
  81                 fprintf(stderr, "peak: got %llu, expected %llu", r, n+1);
  82                 return -1;
  83         }
  84
  85         xbinheap_decreasekey(&h, handlers[0], 0);
  86
  87         r = xbinheap_getkey(&h, handlers[0]);
  88         if (r != 0){
  89                 fprintf(stderr, "getkey: got %llu, instead of 0\n", r);
  90                 return -1;
  91         }
  92         r = xbinheap_peak(&h);
  93         if (r == n+1){
  94                 fprintf(stderr, "peak: got %llu, expected diffrent", n+1);
  95                 return -1;
  96         }
  97
  98
  99
 100         return 0;
 101 }
 102
 103 int main(int argc, const char *argv[])
 104 {
 105         struct timeval start, end, tv;
 106         int r;
 107         int n = atoi(argv[1]);
 108
 109         fprintf(stderr, "Running test1\n");
 110         gettimeofday(&start, NULL);
 111         r = test1(n);
 112         if (r < 0){
 113                 fprintf(stderr, "Test1: FAILED\n");
 114                 return -1;
 115         }
 116         gettimeofday(&end, NULL);
 117         timersub(&end, &start, &tv);
 118         fprintf(stderr, "Test1: PASSED\n");
 119         fprintf(stderr, "Test time: %ds %dusec\n\n", (int)tv.tv_sec, (int)tv.tv_usec);
 120         return 0;
 121 }