home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / reviewed / volume03 / chipset2 / 09 < prev    next >
Encoding:
Text File  |  1993-03-13  |  25.0 KB  |  932 lines
  1. From decwrl!athertn!sander.cupertino.ca.us!paul@cs.purdue.edu Wed Jan  6 13:53:43 EST 1993
  2. Submit chipset-2 09/10 
  3. #! /bin/sh
  4. # This is a shell archive.  Remove anything before this line, then unpack
  5. # it by saving it into a file and typing "sh file".  To overwrite existing
  6. # files, type "sh file -c".  You can also feed this as standard input via
  7. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  8. # will see the following message at the end:
  9. #        "End of archive 9 (of 10)."
  10. # Contents:  src/btree/test.c
  11. # Wrapped by paul@sander on Sun Nov 22 15:41:55 1992
  12. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  13. if test -f src/btree/test.c -a "${1}" != "-c" ; then 
  14.   echo shar: Will not over-write existing file \"src/btree/test.c\"
  15. else
  16. echo shar: Extracting \"src/btree/test.c\" \(23159 characters\)
  17. sed "s/^X//" >src/btree/test.c <<'END_OF_src/btree/test.c'
  18. X/************************************************************************
  19. X *
  20. X * test.c -- This program tests the in-memory B-tree implementation.  It
  21. X *           attempts to cover all branches of control less those taken
  22. X *           when malloc fails.  Perhaps one day a debugging allocator can
  23. X *           be hooked in to test those as well.
  24. X *
  25. X * This file is part of a suite of programs called Software Chipset.
  26. X * The source code for Software Chipset has been released into the
  27. X * public domain by its author, Paul Sander.
  28. X *
  29. X ************************************************************************/
  30. X
  31. X#include <stdio.h>
  32. X#include "btree.h"
  33. X
  34. X/* These are the B-tree operations that the program tests */
  35. X
  36. Xenum ops { SETUP, FREESETUP, NEW, DESTROY, INSERT, DELETE, SEARCH,
  37. X           TRAVERSE, FIRST, LAST, NEXT, PREV, RANK, DELRANK, DATA, SETDATA,
  38. X           END
  39. X};
  40. X
  41. Xtypedef enum ops OP;
  42. X
  43. Xchar *opnames[] = {"setup","freesetup","new","destroy","insert","delete",
  44. X                   "search","traverse","first","last","next","prev","rank",
  45. X                   "delrank","data","setdata","end"
  46. X};
  47. X
  48. X/*
  49. X * The following structure describes a test case.  An array of these
  50. X * is given to an interpreter which performs each test and reports the
  51. X * results.
  52. X */
  53. X
  54. Xstruct testcase {
  55. X    OP    op;        /* Operation */
  56. X    int    key;        /* Insertion/seek key */
  57. X    int    data;        /* Application-specific or expected data */
  58. X    int    data2;        /* Secondary data */
  59. X    int    result;        /* Return code or expected result */
  60. X    int    dump;        /* If not zero, dumps tree for debugging */
  61. X};
  62. X
  63. Xtypedef struct testcase CASE;
  64. X
  65. X/* Value of "key" when calling bt_destroy */
  66. X#define    FREEKEY        1    /* call freeKey() */
  67. X#define    FREEDATA    2    /* call freeData() */
  68. X
  69. X/* This is the list of test cases that make up the suite. */
  70. X
  71. XCASE suite[] = {
  72. X/* ------------    OP        key    data    data2    result    dump    */
  73. X    {    SETUP,        0,    0,    0,    0,    0    },
  74. X    {    FREESETUP,    0,    0,    0,    0,    0    },
  75. X    {    NEW,        0,    0,    0,    0,    0    },
  76. X    {    DESTROY,    0,    0,    0,    0,    0    },
  77. X    {    INSERT,        0,    0,    0,    0,    0    },
  78. X    {    DELETE,        0,    0,    0,    0,    0    },
  79. X    {    SEARCH,        0,    0,    0,    0,    0    },
  80. X    {    TRAVERSE,    1,    0,    0,    0,    0    },
  81. X    {    FIRST,        0,    0,    0,    0,    0    },
  82. X    {    LAST,        0,    0,    0,    0,    0    },
  83. X    {    NEXT,        0,    0,    0,    0,    0    },
  84. X    {    PREV,        0,    0,    0,    0,    0    },
  85. X    {    RANK,        0,    0,    0,    0,    0    },
  86. X    {    DELRANK,    0,    0,    0,    0,    0    },
  87. X    {    SETDATA,    0,    0,    0,    0,    0    },
  88. X    {    DATA,        0,    0,    0,    0,    0    },
  89. X    {    SETUP,        0,    1,    0,    0,    0    },
  90. X    {    SETUP,        2,    1,    1,    0,    0    },
  91. X    {    SETUP,        3,    0,    1,    1,    0    },
  92. X    {    NEW,        0,    0,    0,    1,    0    },
  93. X    {    DELETE,        0,    0,    0,    0,    0    },
  94. X    {    SEARCH,        0,    0,    0,    0,    0    },
  95. X    {    TRAVERSE,    1,    0,    0,    0,    0    },
  96. X    {    FIRST,        0,    0,    0,    0,    0    },
  97. X    {    NEXT,        0,    0,    0,    0,    0    },
  98. X    {    NEXT,        0,    0,    0,    0,    0    },
  99. X    {    PREV,        0,    0,    0,    0,    0    },
  100. X    {    PREV,        0,    0,    0,    0,    0    },
  101. X    {    LAST,        0,    0,    0,    0,    0    },
  102. X    {    PREV,        0,    0,    0,    0,    0    },
  103. X    {    PREV,        0,    0,    0,    0,    0    },
  104. X    {    NEXT,        0,    0,    0,    0,    0    },
  105. X    {    NEXT,        0,    0,    0,    0,    0    },
  106. X    {    FIRST,        0,    0,    0,    0,    0    },
  107. X    {    PREV,        0,    0,    0,    0,    0    },
  108. X    {    LAST,        0,    0,    0,    0,    0    },
  109. X    {    NEXT,        0,    0,    0,    0,    0    },
  110. X    {    RANK,        0,    0,    0,    0,    0    },
  111. X    {    DELRANK,    0,    0,    0,    0,    0    },
  112. X    {    SETDATA,    0,    5,    0,    0,    0    },
  113. X    {    DATA,        0,    5,    0,    0,    0    },
  114. X    {    DELETE,        5,    0,    0,    0,    0    },
  115. X    {    SEARCH,        5,    0,    0,    0,    0    },
  116. X    {    RANK,        -1,    0,    0,    0,    0    },
  117. X    {    RANK,        2,    0,    0,    0,    0    },
  118. X    {    DELRANK,    -1,    0,    0,    0,    0    },
  119. X    {    DELRANK,    2,    0,    0,    0,    0    },
  120. X    {    DESTROY,    0,    0,    0,    0,    0    },
  121. X    {    NEW,        0,    0,    0,    1,    0    },
  122. X    {    INSERT,        500,    0,    0,    1,    0    },
  123. X    {    INSERT,        500,    0,    0,    -1,    0    },
  124. X    {    SEARCH,        500,    0,    0,    1,    0    },
  125. X    {    TRAVERSE,    1,    20,    0,    1,    0    },
  126. X    {    TRAVERSE,    0,    0,    0,    0,    0    },
  127. X    {    FIRST,        500,    0,    0,    1,    0    },
  128. X    {    NEXT,        0,    0,    0,    0,    0    },
  129. X    {    NEXT,        0,    0,    0,    0,    0    },
  130. X    {    SEARCH,        250,    0,    0,    0,    0    },
  131. X    {    NEXT,        500,    0,    0,    1,    0    },
  132. X    {    NEXT,        0,    0,    0,    0,    0    },
  133. X    {    LAST,        500,    0,    0,    1,    0    },
  134. X    {    PREV,        0,    0,    0,    0,    0    },
  135. X    {    PREV,        0,    0,    0,    0,    0    },
  136. X    {    SEARCH,        750,    0,    0,    0,    0    },
  137. X    {    PREV,        500,    0,    0,    1,    0    },
  138. X    {    PREV,        0,    0,    0,    0,    0    },
  139. X    {    RANK,        0,    0,    0,    500,    0    },
  140. X    {    RANK,        1,    0,    0,    0,    0    },
  141. X    {    DELRANK,    1,    0,    0,    0,    0    },
  142. X    {    DESTROY,    0,    0,    0,    0,    0    },
  143. X    {    NEW,        0,    0,    0,    1,    0    },
  144. X    {    INSERT,        600,    20,    0,    1,    0    },
  145. X    {    INSERT,        600,    30,    0,    -1,    0    },
  146. X    {    SEARCH,        600,    0,    0,    1,    0    },
  147. X    {    SEARCH,        600,    20,    0,    1,    0    },
  148. X    {    TRAVERSE,    1,    50,    0,    1,    0    },
  149. X    {    FIRST,        600,    0,    0,    1,    0    },
  150. X    {    FIRST,        600,    20,    0,    1,    0    },
  151. X    {    NEXT,        0,    0,    0,    0,    0    },
  152. X    {    NEXT,        0,    0,    0,    0,    0    },
  153. X    {    SEARCH,        250,    0,    0,    0,    0    },
  154. X    {    NEXT,        600,    0,    0,    1,    0    },
  155. X    {    NEXT,        0,    0,    0,    0,    0    },
  156. X    {    SEARCH,        250,    0,    0,    0,    0    },
  157. X    {    NEXT,        600,    20,    0,    1,    0    },
  158. X    {    NEXT,        0,    0,    0,    0,    0    },
  159. X    {    LAST,        600,    0,    0,    1,    0    },
  160. X    {    LAST,        600,    20,    0,    1,    0    },
  161. X    {    PREV,        0,    0,    0,    0,    0    },
  162. X    {    PREV,        0,    0,    0,    0,    0    },
  163. X    {    SEARCH,        750,    0,    0,    0,    0    },
  164. X    {    PREV,        600,    0,    0,    1,    0    },
  165. X    {    PREV,        0,    0,    0,    0,    0    },
  166. X    {    SEARCH,        750,    0,    0,    0,    0    },
  167. X    {    PREV,        600,    20,    0,    1,    0    },
  168. X    {    PREV,        0,    0,    0,    0,    0    },
  169. X    {    RANK,        0,    0,    0,    600,    0    },
  170. X    {    RANK,        0,    20,    0,    600,    0    },
  171. X    {    DESTROY,    0,    0,    0,    0,    0    },
  172. X    {    NEW,        0,    0,    0,    1,    0    },
  173. X    {    INSERT,        500,    50,    0,    1,    0    },
  174. X    {    NEXT,        0,    0,    0,    0,    0    },
  175. X    {    INSERT,        900,    90,    0,    1,    0    },
  176. X    {    PREV,        0,    0,    0,    0,    0    },
  177. X    {    INSERT,        100,    10,    0,    1,    0    },
  178. X    {    INSERT,        200,    20,    0,    1,    0    },
  179. X    {    INSERT,        800,    80,    0,    1,    0    },
  180. X    {    INSERT,        700,    70,    0,    1,    0    },
  181. X    {    INSERT,        1000,    100,    0,    1,    0    },
  182. X    {    INSERT,        600,    60,    0,    1,    0    },
  183. X    {    TRAVERSE,    1,    0,    0,    8,    0    },
  184. X    {    INSERT,        0,    0,    0,    0,    0    },
  185. X    {    INSERT,        500,    0,    0,    -1,    0    },
  186. X    {    INSERT,        900,    0,    0,    -1,    0    },
  187. X    {    INSERT,        100,    0,    0,    -1,    0    },
  188. X    {    INSERT,        200,    0,    0,    -1,    0    },
  189. X    {    INSERT,        800,    0,    0,    -1,    0    },
  190. X    {    INSERT,        700,    0,    0,    -1,    0    },
  191. X    {    INSERT,        1000,    0,    0,    -1,    0    },
  192. X    {    INSERT,        600,    0,    0,    -1,    0    },
  193. X    {    SEARCH,        50,    0,    0,    0,    0    },
  194. X    {    SEARCH,        100,    0,    0,    1,    0    },
  195. X    {    SEARCH,        150,    0,    0,    0,    0    },
  196. X    {    SEARCH,        200,    0,    0,    1,    0    },
  197. X    {    SEARCH,        250,    0,    0,    0,    0    },
  198. X    {    SEARCH,        500,    0,    0,    1,    0    },
  199. X    {    SEARCH,        550,    0,    0,    0,    0    },
  200. X    {    SEARCH,        600,    0,    0,    1,    0    },
  201. X    {    SEARCH,        650,    0,    0,    0,    0    },
  202. X    {    SEARCH,        700,    0,    0,    1,    0    },
  203. X    {    SEARCH,        750,    0,    0,    0,    0    },
  204. X    {    SEARCH,        800,    0,    0,    1,    0    },
  205. X    {    SEARCH,        850,    0,    0,    0,    0    },
  206. X    {    SEARCH,        900,    0,    0,    1,    0    },
  207. X    {    SEARCH,        950,    0,    0,    0,    0    },
  208. X    {    SEARCH,        1000,    0,    0,    1,    0    },
  209. X    {    SEARCH,        1100,    0,    0,    0,    0    },
  210. X    {    FIRST,        100,    0,    0,    1,    0    },
  211. X    {    PREV,        0,    0,    0,    0,    0    },
  212. X    {    NEXT,        100,    10,    0,    1,    0    },
  213. X    {    LAST,        1000,    0,    0,    1,    0    },
  214. X    {    NEXT,        0,    0,    0,    0,    0    },
  215. X    {    PREV,        1000,    100,    0,    1,    0    },
  216. X    {    SEARCH,        50,    0,    0,    0,    0    },
  217. X    {    NEXT,        100,    10,    0,    1,    0    },
  218. X    {    NEXT,        200,    20,    0,    1,    0    },
  219. X    {    NEXT,        500,    50,    0,    1,    0    },
  220. X    {    NEXT,        600,    60,    0,    1,    0    },
  221. X    {    NEXT,        700,    0,    0,    1,    0    },
  222. X    {    NEXT,        800,    0,    0,    1,    0    },
  223. X    {    NEXT,        900,    0,    0,    1,    0    },
  224. X    {    NEXT,        1000,    0,    0,    1,    0    },
  225. X    {    NEXT,        0,    0,    0,    0,    0    },
  226. X    {    SEARCH,        1100,    0,    0,    0,    0    },
  227. X    {    PREV,        1000,    100,    0,    1,    0    },
  228. X    {    PREV,        900,    90,    0,    1,    0    },
  229. X    {    PREV,        800,    80,    0,    1,    0    },
  230. X    {    PREV,        700,    70,    0,    1,    0    },
  231. X    {    PREV,        600,    0,    0,    1,    0    },
  232. X    {    PREV,        500,    0,    0,    1,    0    },
  233. X    {    PREV,        200,    0,    0,    1,    0    },
  234. X    {    PREV,        100,    0,    0,    1,    0    },
  235. X    {    PREV,        0,    0,    0,    0,    0    },
  236. X    {    INSERT,        300,    30,    0,    1,    0    },
  237. X    {    INSERT,        50,    5,    0,    1,    0    },
  238. X    {    INSERT,        1100,    110,    0,    1,    0    },
  239. X    {    SEARCH,        10,    0,    0,    0,    0    },
  240. X    {    NEXT,        50,    5,    0,    1,    0    },
  241. X    {    NEXT,        100,    10,    0,    1,    0    },
  242. X    {    NEXT,        200,    20,    0,    1,    0    },
  243. X    {    NEXT,        300,    30,    0,    1,    0    },
  244. X    {    NEXT,        500,    50,    0,    1,    0    },
  245. X    {    NEXT,        600,    60,    0,    1,    0    },
  246. X    {    NEXT,        700,    0,    0,    1,    0    },
  247. X    {    NEXT,        800,    0,    0,    1,    0    },
  248. X    {    NEXT,        900,    0,    0,    1,    0    },
  249. X    {    NEXT,        1000,    0,    0,    1,    0    },
  250. X    {    NEXT,        1100,    0,    0,    1,    0    },
  251. X    {    NEXT,        0,    0,    0,    0,    0    },
  252. X    {    SEARCH,        1200,    0,    0,    0,    0    },
  253. X    {    PREV,        1100,    110,    0,    1,    0    },
  254. X    {    PREV,        1000,    100,    0,    1,    0    },
  255. X    {    PREV,        900,    90,    0,    1,    0    },
  256. X    {    PREV,        800,    80,    0,    1,    0    },
  257. X    {    PREV,        700,    70,    0,    1,    0    },
  258. X    {    PREV,        600,    0,    0,    1,    0    },
  259. X    {    PREV,        500,    0,    0,    1,    0    },
  260. X    {    PREV,        300,    0,    0,    1,    0    },
  261. X    {    PREV,        200,    0,    0,    1,    0    },
  262. X    {    PREV,        100,    0,    0,    1,    0    },
  263. X    {    PREV,        50,    0,    0,    1,    0    },
  264. X    {    PREV,        0,    0,    0,    0,    0    },
  265. X    {    RANK,        0,    5,    0,    50,    0    },
  266. X    {    RANK,        1,    10,    0,    100,    0    },
  267. X    {    RANK,        2,    20,    0,    200,    0    },
  268. X    {    RANK,        3,    30,    0,    300,    0    },
  269. X    {    RANK,        4,    50,    0,    500,    0    },
  270. X    {    RANK,        6,    70,    0,    700,    0    },
  271. X    {    RANK,        10,    110,    0,    1100,    0    },
  272. X    {    RANK,        11,    0,    0,    0,    0    },
  273. X    {    DESTROY,    1,    0,    0,    11,    0    },
  274. X    {    FREESETUP,    0,    0,    0,    0,    0    },
  275. X    {    SETUP,        5,    0,    1,    1,    0    },
  276. X    {    NEW,        0,    0,    0,    1,    0    },
  277. X    {    TRAVERSE,    1,    23,    0,    0,    0    },
  278. X    {    INSERT,        3000,    300,    0,    1,    0    },
  279. X    {    INSERT,        5000,    500,    0,    1,    0    },
  280. X    {    INSERT,        7000,    700,    0,    1,    0    },
  281. X    {    INSERT,        9000,    900,    0,    1,    0    },
  282. X    {    INSERT,        2000,    200,    0,    1,    0    },
  283. X    {    INSERT,        4000,    400,    0,    1,    0    },
  284. X    {    INSERT,        1000,    100,    0,    1,    0    },
  285. X    {    INSERT,        4500,    450,    0,    1,    0    },
  286. X    {    INSERT,        3500,    350,    0,    1,    0    },
  287. X    {    INSERT,        2500,    250,    0,    1,    0    },
  288. X    {    INSERT,        8000,    800,    0,    1,    0    },
  289. X    {    INSERT,        500,    50,    0,    1,    0    },
  290. X    {    INSERT,        1500,    150,    0,    1,    0    },
  291. X    {    INSERT,        6000,    600,    0,    1,    0    },
  292. X    {    INSERT,        3750,    375,    0,    1,    0    },
  293. X    {    INSERT,        7500,    750,    0,    1,    0    },
  294. X    {    INSERT,        2750,    275,    0,    1,    0    },
  295. X    {    INSERT,        4750,    475,    0,    1,    0    },
  296. X    {    INSERT,        3250,    325,    0,    1,    0    },
  297. X    {    DELRANK,    0,    50,    0,    500,    0    },
  298. X    {    DELRANK,    2,    200,    0,    2000,    0    },
  299. X    {    DELRANK,    5,    325,    0,    3250,    0    },
  300. X    {    INSERT,        3250,    325,    0,    1,    0    },
  301. X    {    INSERT,        2000,    200,    0,    1,    0    },
  302. X    {    INSERT,        8500,    850,    0,    1,    0    },
  303. X    {    INSERT,        9500,    950,    0,    1,    0    },
  304. X    {    INSERT,        3300,    330,    0,    1,    0    },
  305. X    {    DELETE,        4000,    400,    0,    1,    0    },
  306. X    {    DELETE,        9250,    0,    0,    0,    0    },
  307. X    {    DELETE,        6000,    600,    0,    1,    0    },
  308. X    {    DELETE,        9500,    950,    0,    1,    0    },
  309. X    {    INSERT,        6000,    600,    0,    1,    0    },
  310. X    {    INSERT,        9500,    950,    0,    1,    0    },
  311. X    {    INSERT,        4000,    400,    0,    1,    0    },
  312. X    {    INSERT,        6500,    650,    0,    1,    0    },
  313. X    {    INSERT,        8750,    875,    0,    1,    0    },
  314. X    {    INSERT,        5500,    550,    0,    1,    0    },
  315. X    {    DELETE,        6500,    0,    0,    1,    0    },
  316. X    {    DELETE,        7000,    0,    0,    1,    0    },
  317. X    {    DELRANK,    13,    500,    0,    5000,    0    },
  318. X    {    INSERT,        500,    50,    0,    1,    0    },
  319. X    {    INSERT,        9200,    920,    0,    1,    0    },
  320. X    {    INSERT,        9600,    960,    0,    1,    0    },
  321. X    {    INSERT,        4100,    410,    0,    1,    0    },
  322. X    {    INSERT,        4200,    420,    0,    1,    0    },
  323. X    {    INSERT,        3100,    310,    0,    1,    0    },
  324. X    {    INSERT,        3200,    320,    0,    1,    0    },
  325. X    {    INSERT,        1100,    110,    0,    1,    0    },
  326. X    {    INSERT,        1200,    120,    0,    1,    0    },
  327. X    {    INSERT,        1300,    130,    0,    1,    0    },
  328. X    {    INSERT,        1400,    140,    0,    1,    0    },
  329. X    {    INSERT,        1600,    160,    0,    1,    0    },
  330. X    {    INSERT,        1700,    170,    0,    1,    0    },
  331. X    {    INSERT,        1800,    180,    0,    1,    0    },
  332. X    {    INSERT,        8250,    825,    0,    1,    0    },
  333. X    {    DELETE,        3100,    0,    0,    1,    0    },
  334. X    {    DELETE,        3200,    0,    0,    1,    0    },
  335. X    {    INSERT,        3200,    320,    0,    1,    0    },
  336. X    {    INSERT,        3100,    310,    0,    1,    0    },
  337. X    {    DESTROY,    3,    0,    0,    36,    0    },
  338. X    {    NEW,        0,    0,    0,    1,    0    },
  339. X    {    INSERT,        100,    0,    0,    1,    0    },
  340. X    {    INSERT,        99,    0,    0,    1,    0    },
  341. X    {    INSERT,        98,    0,    0,    1,    0    },
  342. X    {    INSERT,        97,    0,    0,    1,    0    },
  343. X    {    INSERT,        96,    0,    0,    1,    0    },
  344. X    {    INSERT,        95,    0,    0,    1,    0    },
  345. X    {    INSERT,        94,    0,    0,    1,    0    },
  346. X    {    INSERT,        93,    0,    0,    1,    0    },
  347. X    {    INSERT,        92,    0,    0,    1,    0    },
  348. X    {    INSERT,        91,    0,    0,    1,    0    },
  349. X    {    INSERT,        90,    0,    0,    1,    0    },
  350. X    {    INSERT,        89,    0,    0,    1,    0    },
  351. X    {    INSERT,        88,    0,    0,    1,    0    },
  352. X    {    INSERT,        87,    0,    0,    1,    0    },
  353. X    {    INSERT,        86,    0,    0,    1,    0    },
  354. X    {    INSERT,        85,    0,    0,    1,    0    },
  355. X    {    INSERT,        84,    0,    0,    1,    0    },
  356. X    {    INSERT,        83,    0,    0,    1,    0    },
  357. X    {    INSERT,        82,    0,    0,    1,    0    },
  358. X    {    INSERT,        81,    0,    0,    1,    0    },
  359. X    {    INSERT,        80,    0,    0,    1,    0    },
  360. X    {    INSERT,        79,    0,    0,    1,    0    },
  361. X    {    INSERT,        78,    0,    0,    1,    0    },
  362. X    {    INSERT,        77,    0,    0,    1,    0    },
  363. X    {    INSERT,        76,    0,    0,    1,    0    },
  364. X    {    INSERT,        75,    0,    0,    1,    0    },
  365. X    {    INSERT,        74,    0,    0,    1,    0    },
  366. X    {    INSERT,        73,    0,    0,    1,    0    },
  367. X    {    INSERT,        72,    0,    0,    1,    0    },
  368. X    {    INSERT,        71,    0,    0,    1,    0    },
  369. X    {    INSERT,        70,    0,    0,    1,    0    },
  370. X    {    INSERT,        69,    0,    0,    1,    0    },
  371. X    {    DESTROY,    3,    0,    0,    32,    0    },
  372. X    {    FREESETUP,    0,    0,    0,    0,    0    },
  373. X    {    SETUP,        10,    0,    1,    1,    0    },
  374. X    {    NEW,        0,    0,    0,    1,    0    },
  375. X    {    INSERT,        2,    20,    0,    1,    0    },
  376. X    {    INSERT,        3,    30,    0,    1,    0    },
  377. X    {    INSERT,        4,    40,    0,    1,    0    },
  378. X    {    INSERT,        5,    50,    0,    1,    0    },
  379. X    {    INSERT,        6,    60,    0,    1,    0    },
  380. X    {    INSERT,        7,    70,    0,    1,    0    },
  381. X    {    INSERT,        8,    80,    0,    1,    0    },
  382. X    {    INSERT,        9,    90,    0,    1,    0    },
  383. X    {    INSERT,        10,    100,    0,    1,    0    },
  384. X    {    SEARCH,        2,    0,    0,    1,    0    },
  385. X    {    SEARCH,        3,    0,    0,    1,    0    },
  386. X    {    SEARCH,        4,    0,    0,    1,    0    },
  387. X    {    SEARCH,        5,    0,    0,    1,    0    },
  388. X    {    SEARCH,        6,    0,    0,    1,    0    },
  389. X    {    SEARCH,        7,    0,    0,    1,    0    },
  390. X    {    SEARCH,        8,    0,    0,    1,    0    },
  391. X    {    SEARCH,        9,    0,    0,    1,    0    },
  392. X    {    SEARCH,        10,    0,    0,    1,    0    },
  393. X    {    SEARCH,        1,    0,    0,    0,    0    },
  394. X    {    SEARCH,        11,    0,    0,    0,    0    },
  395. X    {    DESTROY,    2,    0,    0,    9,    0    },
  396. X    {    FREESETUP,    0,    0,    0,    0,    0    },
  397. X/* ------------    OP        key    data    data2    result    dump    */
  398. X    {    END,        0,    0,    0,    0,    0    }
  399. X};
  400. X
  401. X/* This is the comparison function */
  402. X
  403. X#ifdef __STDC__
  404. Xint comp(void *key1, void *key2)
  405. X#else
  406. Xint comp(key1,key2)
  407. Xvoid    *key1;
  408. Xvoid    *key2;
  409. X#endif
  410. X{
  411. X    return *((int*)key1) - *((int*)key2);
  412. X}
  413. X
  414. X/* This function displays a key and its data */
  415. X#ifdef __STDC__
  416. Xvoid dumpKey(void *key,void *data,void *info)
  417. X#else
  418. Xvoid dumpKey(key,data,info)
  419. Xvoid    *key;
  420. Xvoid    *data;
  421. Xvoid    *info;
  422. X#endif
  423. X{
  424. X    printf("key = %4.4d, data = ",*(int*)key);
  425. X    if (data != NULL) printf("%4.4d\n",*(int*)data);
  426. X    else printf("(NULL)\n");
  427. X    return;
  428. X}
  429. X
  430. X/*
  431. X * These functions are called by bt_destroy, and count the number of
  432. X * key and data structures are freed, and also verify that the info
  433. X * parameter is passed properly.  Some attempt is made to be sure that
  434. X * the data are freed before the key.
  435. X */
  436. X
  437. Xint    freedKeys;    /* Number of keys freed */
  438. Xint    freedData;    /* Number of data records freed */
  439. Xint    *expInfo;    /* Expected value of info */
  440. Xint    infoOk;        /* Indicates that the info was always correct */
  441. Xint    freeOk;        /* Indicates that the freeKey and freeData functions
  442. X             * were called correctly
  443. X             */
  444. X
  445. X#ifdef __STDC__
  446. Xvoid freeKey(void *key, void *info)
  447. X#else
  448. Xvoid freeKey(key,info)
  449. Xvoid    *key;
  450. Xvoid    *info;
  451. X#endif
  452. X{
  453. X    freedKeys++;
  454. X    if ((int*) info != expInfo) infoOk = 0;
  455. X    if ((freedData >= 0) && (freedKeys != freedData)) freeOk = 0;
  456. X}
  457. X
  458. X#ifdef __STDC__
  459. Xvoid freeData(void *key, void *info)
  460. X#else
  461. Xvoid freeData(key,info)
  462. Xvoid    *key;
  463. Xvoid    *info;
  464. X#endif
  465. X{
  466. X    if ((freedKeys >= 0) && (freedKeys != freedData)) freeOk = 0;
  467. X    freedData++;
  468. X    if ((int*) info != expInfo) infoOk = 0;
  469. X}
  470. X
  471. X/*
  472. X * The following variables and the visit() function are used for testing
  473. X * the bt_traverse() function.
  474. X */
  475. X
  476. Xint    lastKey;    /* Last key encountered by bt_traverse */
  477. Xint    travOk;        /* Traversal successful */
  478. Xint    visited;    /* Number of nodes visited */
  479. X
  480. X#ifdef __STDC__
  481. Xvoid visit(void *key, void *info, void *data)
  482. X#else
  483. Xvoid visit(key,info,data)
  484. Xvoid    *key;
  485. Xvoid    *info;
  486. Xvoid    *data;
  487. X#endif
  488. X{
  489. X    visited++;
  490. X    if ((lastKey != 0) && (*(int*)key <= lastKey)) travOk = 0;
  491. X    else if ((int*) info != expInfo) travOk = 0;
  492. X    lastKey = *(int*) key;
  493. X    return;
  494. X}
  495. X
  496. X/* The test suite starts here... */
  497. X
  498. X#ifdef __STDC__
  499. Xint main(int argc, char **argv)
  500. X#else
  501. Xint main(argc,argv)
  502. Xint    argc;
  503. Xchar    **argv;
  504. X#endif
  505. X{
  506. X    int        i;        /* Loop counter */
  507. X    int        ok;        /* Current test succeeded */
  508. X    int        fail;        /* Any test failed */
  509. X    int        done;        /* Holds size of test table */
  510. X    int        intval;        /* Integer value */
  511. X    void        *ptrval;    /* Pointer value */
  512. X    void        *ptrval2;    /* Pointer value */
  513. X    BTREE        tree;        /* B-tree under test */
  514. X    BT_SETUP    setup;        /* Configuration data for B-tree */
  515. X
  516. X    /* Initialization */
  517. X    fail = 0;
  518. X    tree = (BTREE) NULL;
  519. X    setup = (BT_SETUP) NULL;
  520. X
  521. X    /* Compute the number of test cases there are */
  522. X    done = sizeof(suite)/sizeof(CASE);
  523. X
  524. X    /* Display heading */
  525. X    printf("test OP         key   data  data2  result  intval ptrval  ptrval2  pass\n");
  526. X    for (i = 0; (i < done) && (suite[i].op != END); i++)
  527. X    {
  528. X        /* Initialize test case */
  529. X        ok = 1;
  530. X        intval = 0;
  531. X        ptrval = NULL;
  532. X        ptrval2 = NULL;
  533. X
  534. X        /* Perform test */
  535. X        switch (suite[i].op)
  536. X        {
  537. X    case SETUP:
  538. X            /*
  539. X             * Test case:  key = B-tree order,
  540. X             *             data2 = 0 if no comparison function,
  541. X             *             data = global data,
  542. X             *             result = 0 if NULL expected
  543. X             */
  544. X            setup = bt_setup(suite[i].key,
  545. X                      (suite[i].data2 ? comp : (int (*)()) NULL),
  546. X                      (void*) (suite[i].data ? &suite[i].data
  547. X                                             : NULL));
  548. X            ok = (suite[i].result != (setup == (BT_SETUP) NULL));
  549. X            break;
  550. X
  551. X    case FREESETUP:
  552. X            bt_freeSetup(setup);
  553. X            setup = (BT_SETUP) NULL;
  554. X            break;
  555. X
  556. X    case NEW:
  557. X            /* Test case:  result = 0 if NULL expected */
  558. X            tree = bt_new(setup);
  559. X            ok = (suite[i].result != (tree == (BTREE) NULL));
  560. X            break;
  561. X
  562. X    case DESTROY:
  563. X            /* Test case:  result = number of keys to be freed,
  564. X             *             key    = 0 if neither free fn is called,
  565. X             *                      FREEKEY if freeKey() only
  566. X             *                      FREEDATA if freeData() only
  567. X             *                      FREEKEY+FREEDATA if both
  568. X             *             data   = info parameter
  569. X             */
  570. X            infoOk = 1;
  571. X            freeOk = 1;
  572. X            expInfo = &suite[i].data;
  573. X            switch (suite[i].key)
  574. X            {
  575. X        case 0:
  576. X                /* Fails only if dumps core or hangs */
  577. X                freedKeys = -1;
  578. X                freedData = -1;
  579. X                bt_destroy(tree,NULL,NULL,&suite[i].data);
  580. X                break;
  581. X        case FREEKEY:
  582. X                freedKeys = 0;
  583. X                freedData = -1;
  584. X                bt_destroy(tree,freeKey,NULL,&suite[i].data);
  585. X                break;
  586. X        case FREEDATA:
  587. X                freedKeys = -1;
  588. X                freedData = 0;
  589. X                bt_destroy(tree,NULL,freeData,&suite[i].data);
  590. X                break;
  591. X        default:
  592. X                freedKeys = 0;
  593. X                freedData = 0;
  594. X                bt_destroy(tree,freeKey,freeData,
  595. X                           &suite[i].data);
  596. X                break;
  597. X            }
  598. X            tree = NULL;
  599. X            if (!freeOk || !infoOk) ok = 0;
  600. X            if ((freedKeys >= 0) && (freedKeys != suite[i].result))
  601. X                ok = 0;
  602. X            if ((freedData >= 0) && (freedData != suite[i].result))
  603. X                ok = 0;
  604. X            break;
  605. X
  606. X    case INSERT:
  607. X            /* Test case:  key    = key to be inserted
  608. X             *             data   = data to be stored with it
  609. X             *             result = expected val of bt_insert()
  610. X             */
  611. X            intval = bt_insert(tree,
  612. X                            suite[i].key ? &suite[i].key : NULL,
  613. X                            suite[i].data ? &suite[i].data : NULL);
  614. X            if (intval != suite[i].result) ok = 0;
  615. X            break;
  616. X
  617. X    case DELETE:
  618. X            /* Test case:  key    = key to be deleted
  619. X             *             data   = expected data returned by
  620. X             *                      bt_delete
  621. X             *             result = 0 if failure expected
  622. X             */
  623. X            ptrval2 = bt_delete(tree,
  624. X                              suite[i].key ? &suite[i].key : NULL,
  625. X                              suite[i].data ? &ptrval : NULL);
  626. X            if (suite[i].key == 0)
  627. X            {
  628. X                if (ptrval2 != NULL) ok = 0;
  629. X            }
  630. X            else
  631. X            {
  632. X                if (ptrval2 == NULL)
  633. X                {
  634. X                    if (suite[i].result) ok = 0;
  635. X                }
  636. X                else
  637. X                {
  638. X                    if (*(int*)ptrval2 != suite[i].key)
  639. X                    {
  640. X                        ok = 0;
  641. X                    }
  642. X                }
  643. X            }
  644. X            if (suite[i].data != 0)
  645. X            {
  646. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  647. X            }
  648. X            else
  649. X            {
  650. X                if (ptrval != NULL) ok = 0;
  651. X            }
  652. X            break;
  653. X
  654. X    case SEARCH:
  655. X            /* Test case:  key    = key to be sought
  656. X             *             data   = expected data returned by
  657. X             *                      bt_search
  658. X             *             result = 0 if failure expected
  659. X             */
  660. X            ptrval2 = bt_search(tree,
  661. X                              suite[i].key ? &suite[i].key : NULL,
  662. X                              suite[i].data ? &ptrval : NULL);
  663. X            if (suite[i].key == 0)
  664. X            {
  665. X                if (ptrval2 != NULL) ok = 0;
  666. X            }
  667. X            else
  668. X            {
  669. X                if (ptrval2 == NULL)
  670. X                {
  671. X                    if (suite[i].result) ok = 0;
  672. X                }
  673. X                else
  674. X                {
  675. X                    if (*(int*)ptrval2 != suite[i].key)
  676. X                    {
  677. X                        ok = 0;
  678. X                    }
  679. X                }
  680. X            }
  681. X            if (suite[i].data != 0)
  682. X            {
  683. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  684. X            }
  685. X            else
  686. X            {
  687. X                if (ptrval != NULL) ok = 0;
  688. X            }
  689. X            break;
  690. X
  691. X    case TRAVERSE:
  692. X            /* Test case:  data   = info passed to bt_traverse
  693. X             *             key    = 0 if NULL is passed as fn
  694. X             *             result = the expected number of times
  695. X             *                      visit() is called
  696. X             */
  697. X            visited = 0;
  698. X            travOk = 1;
  699. X            expInfo = &suite[i].data;
  700. X            lastKey = 0;
  701. X            bt_traverse(tree, (suite[i].key ? visit : NULL),
  702. X                        &suite[i].data);
  703. X            ok = travOk;
  704. X            if (visited != suite[i].result) ok = 0;
  705. X            break;
  706. X
  707. X    case FIRST:
  708. X            /* Test case:  key    = expected key returned
  709. X             *             data   = expected data
  710. X             *             result = 0 if tree is empty
  711. X             */
  712. X            ptrval2 = bt_first(tree,
  713. X                               suite[i].data ? &ptrval : NULL);
  714. X            if (suite[i].result)
  715. X            {
  716. X                if (*(int*)ptrval2 != suite[i].key) ok = 0;
  717. X            }
  718. X            else
  719. X            {
  720. X                if (ptrval2 != NULL) ok = 0;
  721. X            }
  722. X            if (suite[i].data)
  723. X            {
  724. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  725. X            }
  726. X            else
  727. X            {
  728. X                if (ptrval != NULL) ok = 0;
  729. X            }
  730. X            break;
  731. X
  732. X    case LAST:
  733. X            /* Test case:  key    = expected key returned
  734. X             *             data   = expected data
  735. X             *             result = 0 if tree is empty
  736. X             */
  737. X            ptrval2 = bt_last(tree,
  738. X                               suite[i].data ? &ptrval : NULL);
  739. X            if (suite[i].result)
  740. X            {
  741. X                if (*(int*)ptrval2 != suite[i].key) ok = 0;
  742. X            }
  743. X            else
  744. X            {
  745. X                if (ptrval2 != NULL) ok = 0;
  746. X            }
  747. X            if (suite[i].data)
  748. X            {
  749. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  750. X            }
  751. X            else
  752. X            {
  753. X                if (ptrval != NULL) ok = 0;
  754. X            }
  755. X            break;
  756. X
  757. X    case NEXT:
  758. X            /* Test case:  key    = expected key returned
  759. X             *             data   = expected data
  760. X             *             result = 0 if last key was found
  761. X             */
  762. X            ptrval2 = bt_next(tree,
  763. X                               suite[i].data ? &ptrval : NULL);
  764. X            if (suite[i].result)
  765. X            {
  766. X                if (*(int*)ptrval2 != suite[i].key) ok = 0;
  767. X            }
  768. X            else
  769. X            {
  770. X                if (ptrval2 != NULL) ok = 0;
  771. X            }
  772. X            if (suite[i].data)
  773. X            {
  774. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  775. X            }
  776. X            else
  777. X            {
  778. X                if (ptrval != NULL) ok = 0;
  779. X            }
  780. X            break;
  781. X
  782. X    case PREV:
  783. X            /* Test case:  key    = expected key returned
  784. X             *             data   = expected data
  785. X             *             result = 0 if first key was found
  786. X             */
  787. X            ptrval2 = bt_prev(tree,
  788. X                               suite[i].data ? &ptrval : NULL);
  789. X            if (suite[i].result)
  790. X            {
  791. X                if (*(int*)ptrval2 != suite[i].key) ok = 0;
  792. X            }
  793. X            else
  794. X            {
  795. X                if (ptrval2 != NULL) ok = 0;
  796. X            }
  797. X            if (suite[i].data)
  798. X            {
  799. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  800. X            }
  801. X            else
  802. X            {
  803. X                if (ptrval != NULL) ok = 0;
  804. X            }
  805. X            break;
  806. X
  807. X    case RANK:
  808. X            /* Test case:  key    = rank searched for
  809. X             *             data   = expected data
  810. X             *             result = expected key
  811. X             */
  812. X            ptrval2 = bt_rank(tree,suite[i].key,
  813. X                              suite[i].data ? &ptrval : NULL);
  814. X            if (suite[i].result != 0)
  815. X            {
  816. X                if (*(int*)ptrval2 != suite[i].result) ok = 0;
  817. X            }
  818. X            else
  819. X            {
  820. X                if (ptrval2 != NULL) ok = 0;
  821. X            }
  822. X            if (suite[i].data != 0)
  823. X            {
  824. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  825. X            }
  826. X            break;
  827. X
  828. X    case DELRANK:
  829. X            /* Test case:  key    = rank to be deleted
  830. X             *             data   = expected data
  831. X             *             result = expected key
  832. X             */
  833. X            ptrval2 = bt_delRank(tree,suite[i].key,
  834. X                                 suite[i].data ? &ptrval : NULL);
  835. X            if (suite[i].result != 0)
  836. X            {
  837. X                if (*(int*)ptrval2 != suite[i].result) ok = 0;
  838. X            }
  839. X            else
  840. X            {
  841. X                if (ptrval2 != NULL) ok = 0;
  842. X            }
  843. X            if (suite[i].data != 0)
  844. X            {
  845. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  846. X            }
  847. X            break;
  848. X
  849. X    case DATA:
  850. X            /* Test case:  data = expected data */
  851. X            ptrval = bt_data(tree);
  852. X            if (suite[i].data != 0)
  853. X            {
  854. X                if (*(int*)ptrval != suite[i].data) ok = 0;
  855. X            }
  856. X            else
  857. X            {
  858. X                if (ptrval != NULL) ok = 0;
  859. X            }
  860. X            break;
  861. X
  862. X    case SETDATA:
  863. X            /* Test case:  data = new data */
  864. X            bt_setData(tree,&suite[i].data);
  865. X            break;
  866. X
  867. X    default:
  868. X            break;
  869. X        }
  870. X
  871. X        /* Note test case failure */
  872. X        if (!ok) fail = 1;
  873. X
  874. X        /* Display result of test case */
  875. X        printf("%4.4d %-9.9s %5.4d %5.4d %5.4d  %5.4d   %5.4d   ",
  876. X               i,opnames[suite[i].op],suite[i].key,suite[i].data,
  877. X               suite[i].data2,suite[i].result,intval);
  878. X        if (ptrval == NULL) printf(" NULL   ");
  879. X        else printf("%5.4d   ",*(int*)ptrval);
  880. X        if (ptrval2 == NULL) printf(" NULL    ");
  881. X        else printf("%5.4d    ",*(int*)ptrval2);
  882. X        if (ok) printf("yes  ");
  883. X        else printf("no   ");
  884. X        printf("\n");
  885. X
  886. X        /* Dump the tree if requested */
  887. X        if ((suite[i].dump) && (tree != NULL))
  888. X        {
  889. X            printf("Contents of tree:\n");
  890. X            bt_dump(tree,dumpKey,NULL);
  891. X        }
  892. X    }
  893. X    if (suite[i].op == END)
  894. X    {
  895. X        i = done;
  896. X    }
  897. X
  898. X    /* Display summary */
  899. X    printf("TEST %s\n",(fail ? "FAILED" : "PASSED"));
  900. X
  901. X    /* Return 0 on success, non-zero on failure */
  902. X    return ((i != done) || fail);
  903. X}
  904. X
  905. X/********* End of file *********/
  906. X
  907. END_OF_src/btree/test.c
  908. if test 23159 -ne `wc -c <src/btree/test.c`; then
  909.     echo shar: \"src/btree/test.c\" unpacked with wrong size!
  910. fi
  911. # end of overwriting check
  912. fi
  913. echo shar: End of archive 9 \(of 10\).
  914. cp /dev/null ark9isdone
  915. MISSING=""
  916. for I in 1 2 3 4 5 6 7 8 9 10 ; do
  917.     if test ! -f ark${I}isdone ; then
  918.     MISSING="${MISSING} ${I}"
  919.     fi
  920. done
  921. if test "${MISSING}" = "" ; then
  922.     echo You have unpacked all 10 archives.
  923.     echo "Now edit common.mk and do a 'make all'"
  924.     rm -f ark[1-9]isdone ark[1-9][0-9]isdone
  925. else
  926.     echo You still need to unpack the following archives:
  927.     echo "        " ${MISSING}
  928. fi
  929. ##  End of shell archive.
  930. exit 0
  931.  
  932.