2
0

lhash_test.c 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239
  1. /*
  2. * Copyright 2017-2020 The OpenSSL Project Authors. All Rights Reserved.
  3. * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
  4. *
  5. * Licensed under the Apache License 2.0 (the "License"). You may not use
  6. * this file except in compliance with the License. You can obtain a copy
  7. * in the file LICENSE in the source distribution or at
  8. * https://www.openssl.org/source/license.html
  9. */
  10. #include <stdio.h>
  11. #include <string.h>
  12. #include <openssl/opensslconf.h>
  13. #include <openssl/lhash.h>
  14. #include <openssl/err.h>
  15. #include <openssl/crypto.h>
  16. #include "internal/nelem.h"
  17. #include "testutil.h"
  18. /*
  19. * The macros below generate unused functions which error out one of the clang
  20. * builds. We disable this check here.
  21. */
  22. #ifdef __clang__
  23. #pragma clang diagnostic ignored "-Wunused-function"
  24. #endif
  25. DEFINE_LHASH_OF_EX(int);
  26. static int int_tests[] = { 65537, 13, 1, 3, -5, 6, 7, 4, -10, -12, -14, 22, 9,
  27. -17, 16, 17, -23, 35, 37, 173, 11 };
  28. static const unsigned int n_int_tests = OSSL_NELEM(int_tests);
  29. static short int_found[OSSL_NELEM(int_tests)];
  30. static short int_not_found;
  31. static unsigned long int int_hash(const int *p)
  32. {
  33. return 3 & *p; /* To force collisions */
  34. }
  35. static int int_cmp(const int *p, const int *q)
  36. {
  37. return *p != *q;
  38. }
  39. static int int_find(int n)
  40. {
  41. unsigned int i;
  42. for (i = 0; i < n_int_tests; i++)
  43. if (int_tests[i] == n)
  44. return i;
  45. return -1;
  46. }
  47. static void int_doall(int *v)
  48. {
  49. const int n = int_find(*v);
  50. if (n < 0)
  51. int_not_found++;
  52. else
  53. int_found[n]++;
  54. }
  55. static void int_doall_arg(int *p, short *f)
  56. {
  57. const int n = int_find(*p);
  58. if (n < 0)
  59. int_not_found++;
  60. else
  61. f[n]++;
  62. }
  63. IMPLEMENT_LHASH_DOALL_ARG(int, short);
  64. static int test_int_lhash(void)
  65. {
  66. static struct {
  67. int data;
  68. int null;
  69. } dels[] = {
  70. { 65537, 0 },
  71. { 173, 0 },
  72. { 999, 1 },
  73. { 37, 0 },
  74. { 1, 0 },
  75. { 34, 1 }
  76. };
  77. const unsigned int n_dels = OSSL_NELEM(dels);
  78. LHASH_OF(int) *h = lh_int_new(&int_hash, &int_cmp);
  79. unsigned int i;
  80. int testresult = 0, j, *p;
  81. if (!TEST_ptr(h))
  82. goto end;
  83. /* insert */
  84. for (i = 0; i < n_int_tests; i++)
  85. if (!TEST_ptr_null(lh_int_insert(h, int_tests + i))) {
  86. TEST_info("int insert %d", i);
  87. goto end;
  88. }
  89. /* num_items */
  90. if (!TEST_int_eq(lh_int_num_items(h), n_int_tests))
  91. goto end;
  92. /* retrieve */
  93. for (i = 0; i < n_int_tests; i++)
  94. if (!TEST_int_eq(*lh_int_retrieve(h, int_tests + i), int_tests[i])) {
  95. TEST_info("lhash int retrieve value %d", i);
  96. goto end;
  97. }
  98. for (i = 0; i < n_int_tests; i++)
  99. if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + i), int_tests + i)) {
  100. TEST_info("lhash int retrieve address %d", i);
  101. goto end;
  102. }
  103. j = 1;
  104. if (!TEST_ptr_eq(lh_int_retrieve(h, &j), int_tests + 2))
  105. goto end;
  106. /* replace */
  107. j = 13;
  108. if (!TEST_ptr(p = lh_int_insert(h, &j)))
  109. goto end;
  110. if (!TEST_ptr_eq(p, int_tests + 1))
  111. goto end;
  112. if (!TEST_ptr_eq(lh_int_retrieve(h, int_tests + 1), &j))
  113. goto end;
  114. /* do_all */
  115. memset(int_found, 0, sizeof(int_found));
  116. int_not_found = 0;
  117. lh_int_doall(h, &int_doall);
  118. if (!TEST_int_eq(int_not_found, 0)) {
  119. TEST_info("lhash int doall encountered a not found condition");
  120. goto end;
  121. }
  122. for (i = 0; i < n_int_tests; i++)
  123. if (!TEST_int_eq(int_found[i], 1)) {
  124. TEST_info("lhash int doall %d", i);
  125. goto end;
  126. }
  127. /* do_all_arg */
  128. memset(int_found, 0, sizeof(int_found));
  129. int_not_found = 0;
  130. lh_int_doall_short(h, int_doall_arg, int_found);
  131. if (!TEST_int_eq(int_not_found, 0)) {
  132. TEST_info("lhash int doall arg encountered a not found condition");
  133. goto end;
  134. }
  135. for (i = 0; i < n_int_tests; i++)
  136. if (!TEST_int_eq(int_found[i], 1)) {
  137. TEST_info("lhash int doall arg %d", i);
  138. goto end;
  139. }
  140. /* delete */
  141. for (i = 0; i < n_dels; i++) {
  142. const int b = lh_int_delete(h, &dels[i].data) == NULL;
  143. if (!TEST_int_eq(b ^ dels[i].null, 0)) {
  144. TEST_info("lhash int delete %d", i);
  145. goto end;
  146. }
  147. }
  148. /* error */
  149. if (!TEST_int_eq(lh_int_error(h), 0))
  150. goto end;
  151. testresult = 1;
  152. end:
  153. lh_int_free(h);
  154. return testresult;
  155. }
  156. static unsigned long int stress_hash(const int *p)
  157. {
  158. return *p;
  159. }
  160. static int test_stress(void)
  161. {
  162. LHASH_OF(int) *h = lh_int_new(&stress_hash, &int_cmp);
  163. const unsigned int n = 2500000;
  164. unsigned int i;
  165. int testresult = 0, *p;
  166. if (!TEST_ptr(h))
  167. goto end;
  168. /* insert */
  169. for (i = 0; i < n; i++) {
  170. p = OPENSSL_malloc(sizeof(i));
  171. if (!TEST_ptr(p)) {
  172. TEST_info("lhash stress out of memory %d", i);
  173. goto end;
  174. }
  175. *p = 3 * i + 1;
  176. lh_int_insert(h, p);
  177. }
  178. /* num_items */
  179. if (!TEST_int_eq(lh_int_num_items(h), n))
  180. goto end;
  181. /* delete in a different order */
  182. for (i = 0; i < n; i++) {
  183. const int j = (7 * i + 4) % n * 3 + 1;
  184. if (!TEST_ptr(p = lh_int_delete(h, &j))) {
  185. TEST_info("lhash stress delete %d\n", i);
  186. goto end;
  187. }
  188. if (!TEST_int_eq(*p, j)) {
  189. TEST_info("lhash stress bad value %d", i);
  190. goto end;
  191. }
  192. OPENSSL_free(p);
  193. }
  194. testresult = 1;
  195. end:
  196. lh_int_free(h);
  197. return testresult;
  198. }
  199. int setup_tests(void)
  200. {
  201. ADD_TEST(test_int_lhash);
  202. ADD_TEST(test_stress);
  203. return 1;
  204. }