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

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <sys/time.h>
   4 #include "xbinheap.h"
   5
   6 xbinheap_handler *handlers;
   7 int test1(unsigned long n)
   8 {
   9         struct xbinheap h;
  10         xbinheapidx i, r;
  11         long j;
  12         handlers = malloc(sizeof(xbinheap_handler) * n);
  13         xbinheap_init(&h, n, XBINHEAP_MAX, NULL);
  14         for (i = 0; i < n; i++) {
  15                 handlers[i] = xbinheap_insert(&h, i, i);
  16                 if (handlers[i] == NoNode){
  17                         fprintf(stderr, "Error inserting %llu\n", i);
  18                         return -1;
  19                 }
  20         }
  21         for (j = n-1; j >=0; j--) {
  22                 i = j;
  23                 r = xbinheap_extract(&h);
  24                 if (r != i){
  25                         fprintf(stderr, "Extracted invalid value %llu != %llu\n", r, i);
  26                         return -1;
  27                 }
  28         }
  29         for (i = 0; i < n; i++) {
  30                 handlers[i] = xbinheap_insert(&h, i, i);
  31         }
  32         xbinheap_increasekey(&h, handlers[0], n);
  33         r = xbinheap_extract(&h);
  34         if (r != 0){
  35                 fprintf(stderr, "Extracted invalid value after increase %llu != 0\n", r);
  36                 return -1;
  37         }
  38         handlers[0] = xbinheap_insert(&h, n+1, n+1);
  39         printf("handler[0]: %llu\n", handlers[0]);
  40         r = xbinheap_getkey(&h, handlers[0]);
  41         if (r != n+1){
  42                 fprintf(stderr, "getkey: got %llu, instead of %lu\n", r, n+1);
  43                 return -1;
  44         }
  45         r = xbinheap_peak(&h);
  46         if (r != n+1){
  47                 fprintf(stderr, "peak: got %llu, expected %llu", r, n+1);
  48                 return -1;
  49         }
  50
  51         xbinheap_decreasekey(&h, handlers[0], 0);
  52
  53         r = xbinheap_getkey(&h, handlers[0]);
  54         if (r != 0){
  55                 fprintf(stderr, "getkey: got %llu, instead of 0\n", r);
  56                 return -1;
  57         }
  58         r = xbinheap_peak(&h);
  59         if (r == n+1){
  60                 fprintf(stderr, "peak: got %llu, expected diffrent", n+1);
  61                 return -1;
  62         }
  63
  64
  65
  66         return 0;
  67 }
  68
  69 int main(int argc, const char *argv[])
  70 {
  71         struct timeval start, end, tv;
  72         int r;
  73         int n = atoi(argv[1]);
  74
  75         fprintf(stderr, "Running test1\n");
  76         gettimeofday(&start, NULL);
  77         r = test1(n);
  78         if (r < 0){
  79                 fprintf(stderr, "Test1: FAILED\n");
  80                 return -1;
  81         }
  82         gettimeofday(&end, NULL);
  83         timersub(&end, &start, &tv);
  84         fprintf(stderr, "Test1: PASSED\n");
  85         fprintf(stderr, "Test time: %ds %dusec\n\n", (int)tv.tv_sec, (int)tv.tv_usec);
  86         return 0;
  87 }