tests/nghttp2_pq_test.c

   1 /*
   2  * nghttp2 - HTTP/2 C Library
   3  *
   4  * Copyright (c) 2012 Tatsuhiro Tsujikawa
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining
   7  * a copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sublicense, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  21  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  22  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  23  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24  */
  25 #include "nghttp2_pq_test.h"
  26
  27 #include <CUnit/CUnit.h>
  28
  29 #include "nghttp2_pq.h"
  30
  31 static int pq_less(const void *lhs, const void *rhs) {
  32   return strcmp(lhs, rhs) < 0;
  33 }
  34
  35 void test_nghttp2_pq(void) {
  36   int i;
  37   nghttp2_pq pq;
  38   nghttp2_pq_init(&pq, pq_less, nghttp2_mem_default());
  39   CU_ASSERT(nghttp2_pq_empty(&pq));
  40   CU_ASSERT(0 == nghttp2_pq_size(&pq));
  41   CU_ASSERT(0 == nghttp2_pq_push(&pq, (void *)"foo"));
  42   CU_ASSERT(0 == nghttp2_pq_empty(&pq));
  43   CU_ASSERT(1 == nghttp2_pq_size(&pq));
  44   CU_ASSERT(strcmp("foo", nghttp2_pq_top(&pq)) == 0);
  45   CU_ASSERT(0 == nghttp2_pq_push(&pq, (void *)"bar"));
  46   CU_ASSERT(strcmp("bar", nghttp2_pq_top(&pq)) == 0);
  47   CU_ASSERT(0 == nghttp2_pq_push(&pq, (void *)"baz"));
  48   CU_ASSERT(strcmp("bar", nghttp2_pq_top(&pq)) == 0);
  49   CU_ASSERT(0 == nghttp2_pq_push(&pq, (void *)"C"));
  50   CU_ASSERT(4 == nghttp2_pq_size(&pq));
  51   CU_ASSERT(strcmp("C", nghttp2_pq_top(&pq)) == 0);
  52   nghttp2_pq_pop(&pq);
  53   CU_ASSERT(3 == nghttp2_pq_size(&pq));
  54   CU_ASSERT(strcmp("bar", nghttp2_pq_top(&pq)) == 0);
  55   nghttp2_pq_pop(&pq);
  56   CU_ASSERT(strcmp("baz", nghttp2_pq_top(&pq)) == 0);
  57   nghttp2_pq_pop(&pq);
  58   CU_ASSERT(strcmp("foo", nghttp2_pq_top(&pq)) == 0);
  59   nghttp2_pq_pop(&pq);
  60   CU_ASSERT(nghttp2_pq_empty(&pq));
  61   CU_ASSERT(0 == nghttp2_pq_size(&pq));
  62   CU_ASSERT(NULL == nghttp2_pq_top(&pq));
  63
  64   /* Add bunch of entry to see realloc works */
  65   for (i = 0; i < 10000; ++i) {
  66     CU_ASSERT(0 == nghttp2_pq_push(&pq, (void *)"foo"));
  67     CU_ASSERT((size_t)(i + 1) == nghttp2_pq_size(&pq));
  68   }
  69   for (i = 10000; i > 0; --i) {
  70     CU_ASSERT(NULL != nghttp2_pq_top(&pq));
  71     nghttp2_pq_pop(&pq);
  72     CU_ASSERT((size_t)(i - 1) == nghttp2_pq_size(&pq));
  73   }
  74
  75   nghttp2_pq_free(&pq);
  76 }
  77
  78 typedef struct {
  79   int key;
  80   int val;
  81 } node;
  82
  83 static int node_less(const void *lhs, const void *rhs) {
  84   node *ln = (node *)lhs;
  85   node *rn = (node *)rhs;
  86   return ln->key < rn->key;
  87 }
  88
  89 static int node_update(void *item, void *arg _U_) {
  90   node *nd = (node *)item;
  91   if ((nd->key % 2) == 0) {
  92     nd->key *= -1;
  93     return 1;
  94   } else {
  95     return 0;
  96   }
  97 }
  98
  99 void test_nghttp2_pq_update(void) {
 100   nghttp2_pq pq;
 101   node nodes[10];
 102   int i;
 103   node *nd;
 104   int ans[] = {-8, -6, -4, -2, 0, 1, 3, 5, 7, 9};
 105
 106   nghttp2_pq_init(&pq, node_less, nghttp2_mem_default());
 107
 108   for (i = 0; i < (int)(sizeof(nodes) / sizeof(nodes[0])); ++i) {
 109     nodes[i].key = i;
 110     nodes[i].val = i;
 111     nghttp2_pq_push(&pq, &nodes[i]);
 112   }
 113
 114   nghttp2_pq_update(&pq, node_update, NULL);
 115
 116   for (i = 0; i < (int)(sizeof(nodes) / sizeof(nodes[0])); ++i) {
 117     nd = nghttp2_pq_top(&pq);
 118     CU_ASSERT(ans[i] == nd->key);
 119     nghttp2_pq_pop(&pq);
 120   }
 121
 122   nghttp2_pq_free(&pq);
 123 }