Hex Artifact Content
Not logged in

Artifact 769cd700cbe9d7cb93a1f4e538fc8488ca31840b:


0000: 23 69 6e 63 6c 75 64 65 20 22 74 65 73 74 2f 6a  #include "test/j
0010: 65 6d 61 6c 6c 6f 63 5f 74 65 73 74 2e 68 22 0a  emalloc_test.h".
0020: 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20  .typedef struct 
0030: 6e 6f 64 65 5f 73 20 6e 6f 64 65 5f 74 3b 0a 0a  node_s node_t;..
0040: 73 74 72 75 63 74 20 6e 6f 64 65 5f 73 20 7b 0a  struct node_s {.
0050: 23 64 65 66 69 6e 65 09 4e 4f 44 45 5f 4d 41 47  #define.NODE_MAG
0060: 49 43 20 30 78 39 38 32 33 61 66 37 65 0a 09 75  IC 0x9823af7e..u
0070: 69 6e 74 33 32 5f 74 20 6d 61 67 69 63 3b 0a 09  int32_t magic;..
0080: 70 68 6e 28 6e 6f 64 65 5f 74 29 20 6c 69 6e 6b  phn(node_t) link
0090: 3b 0a 09 75 69 6e 74 36 34 5f 74 20 6b 65 79 3b  ;..uint64_t key;
00a0: 0a 7d 3b 0a 0a 73 74 61 74 69 63 20 69 6e 74 0a  .};..static int.
00b0: 6e 6f 64 65 5f 63 6d 70 28 63 6f 6e 73 74 20 6e  node_cmp(const n
00c0: 6f 64 65 5f 74 20 2a 61 2c 20 63 6f 6e 73 74 20  ode_t *a, const 
00d0: 6e 6f 64 65 5f 74 20 2a 62 29 0a 7b 0a 09 69 6e  node_t *b).{..in
00e0: 74 20 72 65 74 3b 0a 0a 09 72 65 74 20 3d 20 28  t ret;...ret = (
00f0: 61 2d 3e 6b 65 79 20 3e 20 62 2d 3e 6b 65 79 29  a->key > b->key)
0100: 20 2d 20 28 61 2d 3e 6b 65 79 20 3c 20 62 2d 3e   - (a->key < b->
0110: 6b 65 79 29 3b 0a 09 69 66 20 28 72 65 74 20 3d  key);..if (ret =
0120: 3d 20 30 29 20 7b 0a 09 09 2f 2a 0a 09 09 20 2a  = 0) {.../*... *
0130: 20 44 75 70 6c 69 63 61 74 65 73 20 61 72 65 20   Duplicates are 
0140: 6e 6f 74 20 61 6c 6c 6f 77 65 64 20 69 6e 20 74  not allowed in t
0150: 68 65 20 68 65 61 70 2c 20 73 6f 20 66 6f 72 63  he heap, so forc
0160: 65 20 61 6e 0a 09 09 20 2a 20 61 72 62 69 74 72  e an... * arbitr
0170: 61 72 79 20 6f 72 64 65 72 69 6e 67 20 66 6f 72  ary ordering for
0180: 20 6e 6f 6e 2d 69 64 65 6e 74 69 63 61 6c 20 69   non-identical i
0190: 74 65 6d 73 20 77 69 74 68 20 65 71 75 61 6c 20  tems with equal 
01a0: 6b 65 79 73 2e 0a 09 09 20 2a 2f 0a 09 09 72 65  keys.... */...re
01b0: 74 20 3d 20 28 28 28 75 69 6e 74 70 74 72 5f 74  t = (((uintptr_t
01c0: 29 61 29 20 3e 20 28 28 75 69 6e 74 70 74 72 5f  )a) > ((uintptr_
01d0: 74 29 62 29 29 0a 09 09 20 20 20 20 2d 20 28 28  t)b))...    - ((
01e0: 28 75 69 6e 74 70 74 72 5f 74 29 61 29 20 3c 20  (uintptr_t)a) < 
01f0: 28 28 75 69 6e 74 70 74 72 5f 74 29 62 29 29 3b  ((uintptr_t)b));
0200: 0a 09 7d 0a 09 72 65 74 75 72 6e 20 28 72 65 74  ..}..return (ret
0210: 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 69 6e 74  );.}..static int
0220: 0a 6e 6f 64 65 5f 63 6d 70 5f 6d 61 67 69 63 28  .node_cmp_magic(
0230: 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 61 2c  const node_t *a,
0240: 20 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 62   const node_t *b
0250: 29 20 7b 0a 0a 09 61 73 73 65 72 74 5f 75 33 32  ) {...assert_u32
0260: 5f 65 71 28 61 2d 3e 6d 61 67 69 63 2c 20 4e 4f  _eq(a->magic, NO
0270: 44 45 5f 4d 41 47 49 43 2c 20 22 42 61 64 20 6d  DE_MAGIC, "Bad m
0280: 61 67 69 63 22 29 3b 0a 09 61 73 73 65 72 74 5f  agic");..assert_
0290: 75 33 32 5f 65 71 28 62 2d 3e 6d 61 67 69 63 2c  u32_eq(b->magic,
02a0: 20 4e 4f 44 45 5f 4d 41 47 49 43 2c 20 22 42 61   NODE_MAGIC, "Ba
02b0: 64 20 6d 61 67 69 63 22 29 3b 0a 0a 09 72 65 74  d magic");...ret
02c0: 75 72 6e 20 28 6e 6f 64 65 5f 63 6d 70 28 61 2c  urn (node_cmp(a,
02d0: 20 62 29 29 3b 0a 7d 0a 0a 74 79 70 65 64 65 66   b));.}..typedef
02e0: 20 70 68 28 6e 6f 64 65 5f 74 29 20 68 65 61 70   ph(node_t) heap
02f0: 5f 74 3b 0a 70 68 5f 67 65 6e 28 73 74 61 74 69  _t;.ph_gen(stati
0300: 63 2c 20 68 65 61 70 5f 2c 20 68 65 61 70 5f 74  c, heap_, heap_t
0310: 2c 20 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c 20  , node_t, link, 
0320: 6e 6f 64 65 5f 63 6d 70 5f 6d 61 67 69 63 29 3b  node_cmp_magic);
0330: 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 0a 6e 6f  ..static void.no
0340: 64 65 5f 70 72 69 6e 74 28 63 6f 6e 73 74 20 6e  de_print(const n
0350: 6f 64 65 5f 74 20 2a 6e 6f 64 65 2c 20 75 6e 73  ode_t *node, uns
0360: 69 67 6e 65 64 20 64 65 70 74 68 29 0a 7b 0a 09  igned depth).{..
0370: 75 6e 73 69 67 6e 65 64 20 69 3b 0a 09 6e 6f 64  unsigned i;..nod
0380: 65 5f 74 20 2a 6c 65 66 74 6d 6f 73 74 5f 63 68  e_t *leftmost_ch
0390: 69 6c 64 2c 20 2a 73 69 62 6c 69 6e 67 3b 0a 0a  ild, *sibling;..
03a0: 09 66 6f 72 20 28 69 20 3d 20 30 3b 20 69 20 3c  .for (i = 0; i <
03b0: 20 64 65 70 74 68 3b 20 69 2b 2b 29 0a 09 09 6d   depth; i++)...m
03c0: 61 6c 6c 6f 63 5f 70 72 69 6e 74 66 28 22 5c 74  alloc_printf("\t
03d0: 22 29 3b 0a 09 6d 61 6c 6c 6f 63 5f 70 72 69 6e  ");..malloc_prin
03e0: 74 66 28 22 25 32 22 46 4d 54 75 36 34 22 5c 6e  tf("%2"FMTu64"\n
03f0: 22 2c 20 6e 6f 64 65 2d 3e 6b 65 79 29 3b 0a 0a  ", node->key);..
0400: 09 6c 65 66 74 6d 6f 73 74 5f 63 68 69 6c 64 20  .leftmost_child 
0410: 3d 20 70 68 6e 5f 6c 63 68 69 6c 64 5f 67 65 74  = phn_lchild_get
0420: 28 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c 20 6e  (node_t, link, n
0430: 6f 64 65 29 3b 0a 09 69 66 20 28 6c 65 66 74 6d  ode);..if (leftm
0440: 6f 73 74 5f 63 68 69 6c 64 20 3d 3d 20 4e 55 4c  ost_child == NUL
0450: 4c 29 0a 09 09 72 65 74 75 72 6e 3b 0a 09 6e 6f  L)...return;..no
0460: 64 65 5f 70 72 69 6e 74 28 6c 65 66 74 6d 6f 73  de_print(leftmos
0470: 74 5f 63 68 69 6c 64 2c 20 64 65 70 74 68 20 2b  t_child, depth +
0480: 20 31 29 3b 0a 0a 09 66 6f 72 20 28 73 69 62 6c   1);...for (sibl
0490: 69 6e 67 20 3d 20 70 68 6e 5f 6e 65 78 74 5f 67  ing = phn_next_g
04a0: 65 74 28 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c  et(node_t, link,
04b0: 20 6c 65 66 74 6d 6f 73 74 5f 63 68 69 6c 64 29   leftmost_child)
04c0: 3b 20 73 69 62 6c 69 6e 67 20 21 3d 0a 09 20 20  ; sibling !=..  
04d0: 20 20 4e 55 4c 4c 3b 20 73 69 62 6c 69 6e 67 20    NULL; sibling 
04e0: 3d 20 70 68 6e 5f 6e 65 78 74 5f 67 65 74 28 6e  = phn_next_get(n
04f0: 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c 20 73 69 62  ode_t, link, sib
0500: 6c 69 6e 67 29 29 20 7b 0a 09 09 6e 6f 64 65 5f  ling)) {...node_
0510: 70 72 69 6e 74 28 73 69 62 6c 69 6e 67 2c 20 64  print(sibling, d
0520: 65 70 74 68 20 2b 20 31 29 3b 0a 09 7d 0a 7d 0a  epth + 1);..}.}.
0530: 0a 73 74 61 74 69 63 20 76 6f 69 64 0a 68 65 61  .static void.hea
0540: 70 5f 70 72 69 6e 74 28 63 6f 6e 73 74 20 68 65  p_print(const he
0550: 61 70 5f 74 20 2a 68 65 61 70 29 0a 7b 0a 09 6e  ap_t *heap).{..n
0560: 6f 64 65 5f 74 20 2a 61 75 78 65 6c 6d 3b 0a 0a  ode_t *auxelm;..
0570: 09 6d 61 6c 6c 6f 63 5f 70 72 69 6e 74 66 28 22  .malloc_printf("
0580: 76 76 76 20 68 65 61 70 20 25 70 20 76 76 76 5c  vvv heap %p vvv\
0590: 6e 22 2c 20 68 65 61 70 29 3b 0a 09 69 66 20 28  n", heap);..if (
05a0: 68 65 61 70 2d 3e 70 68 5f 72 6f 6f 74 20 3d 3d  heap->ph_root ==
05b0: 20 4e 55 4c 4c 29 0a 09 09 67 6f 74 6f 20 6c 61   NULL)...goto la
05c0: 62 65 6c 5f 72 65 74 75 72 6e 3b 0a 0a 09 6e 6f  bel_return;...no
05d0: 64 65 5f 70 72 69 6e 74 28 68 65 61 70 2d 3e 70  de_print(heap->p
05e0: 68 5f 72 6f 6f 74 2c 20 30 29 3b 0a 0a 09 66 6f  h_root, 0);...fo
05f0: 72 20 28 61 75 78 65 6c 6d 20 3d 20 70 68 6e 5f  r (auxelm = phn_
0600: 6e 65 78 74 5f 67 65 74 28 6e 6f 64 65 5f 74 2c  next_get(node_t,
0610: 20 6c 69 6e 6b 2c 20 68 65 61 70 2d 3e 70 68 5f   link, heap->ph_
0620: 72 6f 6f 74 29 3b 20 61 75 78 65 6c 6d 20 21 3d  root); auxelm !=
0630: 20 4e 55 4c 4c 3b 0a 09 20 20 20 20 61 75 78 65   NULL;..    auxe
0640: 6c 6d 20 3d 20 70 68 6e 5f 6e 65 78 74 5f 67 65  lm = phn_next_ge
0650: 74 28 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c 20  t(node_t, link, 
0660: 61 75 78 65 6c 6d 29 29 20 7b 0a 09 09 61 73 73  auxelm)) {...ass
0670: 65 72 74 5f 70 74 72 5f 65 71 28 70 68 6e 5f 6e  ert_ptr_eq(phn_n
0680: 65 78 74 5f 67 65 74 28 6e 6f 64 65 5f 74 2c 20  ext_get(node_t, 
0690: 6c 69 6e 6b 2c 20 70 68 6e 5f 70 72 65 76 5f 67  link, phn_prev_g
06a0: 65 74 28 6e 6f 64 65 5f 74 2c 0a 09 09 20 20 20  et(node_t,...   
06b0: 20 6c 69 6e 6b 2c 20 61 75 78 65 6c 6d 29 29 2c   link, auxelm)),
06c0: 20 61 75 78 65 6c 6d 2c 0a 09 09 20 20 20 20 22   auxelm,...    "
06d0: 61 75 78 65 6c 6d 27 73 20 70 72 65 76 20 64 6f  auxelm's prev do
06e0: 65 73 6e 27 74 20 6c 69 6e 6b 20 74 6f 20 61 75  esn't link to au
06f0: 78 65 6c 6d 22 29 3b 0a 09 09 6e 6f 64 65 5f 70  xelm");...node_p
0700: 72 69 6e 74 28 61 75 78 65 6c 6d 2c 20 30 29 3b  rint(auxelm, 0);
0710: 0a 09 7d 0a 0a 6c 61 62 65 6c 5f 72 65 74 75 72  ..}..label_retur
0720: 6e 3a 0a 09 6d 61 6c 6c 6f 63 5f 70 72 69 6e 74  n:..malloc_print
0730: 66 28 22 5e 5e 5e 20 68 65 61 70 20 25 70 20 5e  f("^^^ heap %p ^
0740: 5e 5e 5c 6e 22 2c 20 68 65 61 70 29 3b 0a 7d 0a  ^^\n", heap);.}.
0750: 0a 73 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64  .static unsigned
0760: 0a 6e 6f 64 65 5f 76 61 6c 69 64 61 74 65 28 63  .node_validate(c
0770: 6f 6e 73 74 20 6e 6f 64 65 5f 74 20 2a 6e 6f 64  onst node_t *nod
0780: 65 2c 20 63 6f 6e 73 74 20 6e 6f 64 65 5f 74 20  e, const node_t 
0790: 2a 70 61 72 65 6e 74 29 0a 7b 0a 09 75 6e 73 69  *parent).{..unsi
07a0: 67 6e 65 64 20 6e 6e 6f 64 65 73 20 3d 20 31 3b  gned nnodes = 1;
07b0: 0a 09 6e 6f 64 65 5f 74 20 2a 6c 65 66 74 6d 6f  ..node_t *leftmo
07c0: 73 74 5f 63 68 69 6c 64 2c 20 2a 73 69 62 6c 69  st_child, *sibli
07d0: 6e 67 3b 0a 0a 09 69 66 20 28 70 61 72 65 6e 74  ng;...if (parent
07e0: 20 21 3d 20 4e 55 4c 4c 29 20 7b 0a 09 09 61 73   != NULL) {...as
07f0: 73 65 72 74 5f 64 5f 67 65 28 6e 6f 64 65 5f 63  sert_d_ge(node_c
0800: 6d 70 5f 6d 61 67 69 63 28 6e 6f 64 65 2c 20 70  mp_magic(node, p
0810: 61 72 65 6e 74 29 2c 20 30 2c 0a 09 09 20 20 20  arent), 0,...   
0820: 20 22 43 68 69 6c 64 20 69 73 20 6c 65 73 73 20   "Child is less 
0830: 74 68 61 6e 20 70 61 72 65 6e 74 22 29 3b 0a 09  than parent");..
0840: 7d 0a 0a 09 6c 65 66 74 6d 6f 73 74 5f 63 68 69  }...leftmost_chi
0850: 6c 64 20 3d 20 70 68 6e 5f 6c 63 68 69 6c 64 5f  ld = phn_lchild_
0860: 67 65 74 28 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b  get(node_t, link
0870: 2c 20 6e 6f 64 65 29 3b 0a 09 69 66 20 28 6c 65  , node);..if (le
0880: 66 74 6d 6f 73 74 5f 63 68 69 6c 64 20 3d 3d 20  ftmost_child == 
0890: 4e 55 4c 4c 29 0a 09 09 72 65 74 75 72 6e 20 28  NULL)...return (
08a0: 6e 6e 6f 64 65 73 29 3b 0a 09 61 73 73 65 72 74  nnodes);..assert
08b0: 5f 70 74 72 5f 65 71 28 28 76 6f 69 64 20 2a 29  _ptr_eq((void *)
08c0: 70 68 6e 5f 70 72 65 76 5f 67 65 74 28 6e 6f 64  phn_prev_get(nod
08d0: 65 5f 74 2c 20 6c 69 6e 6b 2c 20 6c 65 66 74 6d  e_t, link, leftm
08e0: 6f 73 74 5f 63 68 69 6c 64 29 2c 0a 09 20 20 20  ost_child),..   
08f0: 20 28 76 6f 69 64 20 2a 29 6e 6f 64 65 2c 20 22   (void *)node, "
0900: 4c 65 66 74 6d 6f 73 74 20 63 68 69 6c 64 20 64  Leftmost child d
0910: 6f 65 73 20 6e 6f 74 20 6c 69 6e 6b 20 74 6f 20  oes not link to 
0920: 6e 6f 64 65 22 29 3b 0a 09 6e 6e 6f 64 65 73 20  node");..nnodes 
0930: 2b 3d 20 6e 6f 64 65 5f 76 61 6c 69 64 61 74 65  += node_validate
0940: 28 6c 65 66 74 6d 6f 73 74 5f 63 68 69 6c 64 2c  (leftmost_child,
0950: 20 6e 6f 64 65 29 3b 0a 0a 09 66 6f 72 20 28 73   node);...for (s
0960: 69 62 6c 69 6e 67 20 3d 20 70 68 6e 5f 6e 65 78  ibling = phn_nex
0970: 74 5f 67 65 74 28 6e 6f 64 65 5f 74 2c 20 6c 69  t_get(node_t, li
0980: 6e 6b 2c 20 6c 65 66 74 6d 6f 73 74 5f 63 68 69  nk, leftmost_chi
0990: 6c 64 29 3b 20 73 69 62 6c 69 6e 67 20 21 3d 0a  ld); sibling !=.
09a0: 09 20 20 20 20 4e 55 4c 4c 3b 20 73 69 62 6c 69  .    NULL; sibli
09b0: 6e 67 20 3d 20 70 68 6e 5f 6e 65 78 74 5f 67 65  ng = phn_next_ge
09c0: 74 28 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c 20  t(node_t, link, 
09d0: 73 69 62 6c 69 6e 67 29 29 20 7b 0a 09 09 61 73  sibling)) {...as
09e0: 73 65 72 74 5f 70 74 72 5f 65 71 28 70 68 6e 5f  sert_ptr_eq(phn_
09f0: 6e 65 78 74 5f 67 65 74 28 6e 6f 64 65 5f 74 2c  next_get(node_t,
0a00: 20 6c 69 6e 6b 2c 20 70 68 6e 5f 70 72 65 76 5f   link, phn_prev_
0a10: 67 65 74 28 6e 6f 64 65 5f 74 2c 0a 09 09 20 20  get(node_t,...  
0a20: 20 20 6c 69 6e 6b 2c 20 73 69 62 6c 69 6e 67 29    link, sibling)
0a30: 29 2c 20 73 69 62 6c 69 6e 67 2c 0a 09 09 20 20  ), sibling,...  
0a40: 20 20 22 73 69 62 6c 69 6e 67 27 73 20 70 72 65    "sibling's pre
0a50: 76 20 64 6f 65 73 6e 27 74 20 6c 69 6e 6b 20 74  v doesn't link t
0a60: 6f 20 73 69 62 6c 69 6e 67 22 29 3b 0a 09 09 6e  o sibling");...n
0a70: 6e 6f 64 65 73 20 2b 3d 20 6e 6f 64 65 5f 76 61  nodes += node_va
0a80: 6c 69 64 61 74 65 28 73 69 62 6c 69 6e 67 2c 20  lidate(sibling, 
0a90: 6e 6f 64 65 29 3b 0a 09 7d 0a 09 72 65 74 75 72  node);..}..retur
0aa0: 6e 20 28 6e 6e 6f 64 65 73 29 3b 0a 7d 0a 0a 73  n (nnodes);.}..s
0ab0: 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64 0a 68  tatic unsigned.h
0ac0: 65 61 70 5f 76 61 6c 69 64 61 74 65 28 63 6f 6e  eap_validate(con
0ad0: 73 74 20 68 65 61 70 5f 74 20 2a 68 65 61 70 29  st heap_t *heap)
0ae0: 0a 7b 0a 09 75 6e 73 69 67 6e 65 64 20 6e 6e 6f  .{..unsigned nno
0af0: 64 65 73 20 3d 20 30 3b 0a 09 6e 6f 64 65 5f 74  des = 0;..node_t
0b00: 20 2a 61 75 78 65 6c 6d 3b 0a 0a 09 69 66 20 28   *auxelm;...if (
0b10: 68 65 61 70 2d 3e 70 68 5f 72 6f 6f 74 20 3d 3d  heap->ph_root ==
0b20: 20 4e 55 4c 4c 29 0a 09 09 67 6f 74 6f 20 6c 61   NULL)...goto la
0b30: 62 65 6c 5f 72 65 74 75 72 6e 3b 0a 0a 09 6e 6e  bel_return;...nn
0b40: 6f 64 65 73 20 2b 3d 20 6e 6f 64 65 5f 76 61 6c  odes += node_val
0b50: 69 64 61 74 65 28 68 65 61 70 2d 3e 70 68 5f 72  idate(heap->ph_r
0b60: 6f 6f 74 2c 20 4e 55 4c 4c 29 3b 0a 0a 09 66 6f  oot, NULL);...fo
0b70: 72 20 28 61 75 78 65 6c 6d 20 3d 20 70 68 6e 5f  r (auxelm = phn_
0b80: 6e 65 78 74 5f 67 65 74 28 6e 6f 64 65 5f 74 2c  next_get(node_t,
0b90: 20 6c 69 6e 6b 2c 20 68 65 61 70 2d 3e 70 68 5f   link, heap->ph_
0ba0: 72 6f 6f 74 29 3b 20 61 75 78 65 6c 6d 20 21 3d  root); auxelm !=
0bb0: 20 4e 55 4c 4c 3b 0a 09 20 20 20 20 61 75 78 65   NULL;..    auxe
0bc0: 6c 6d 20 3d 20 70 68 6e 5f 6e 65 78 74 5f 67 65  lm = phn_next_ge
0bd0: 74 28 6e 6f 64 65 5f 74 2c 20 6c 69 6e 6b 2c 20  t(node_t, link, 
0be0: 61 75 78 65 6c 6d 29 29 20 7b 0a 09 09 61 73 73  auxelm)) {...ass
0bf0: 65 72 74 5f 70 74 72 5f 65 71 28 70 68 6e 5f 6e  ert_ptr_eq(phn_n
0c00: 65 78 74 5f 67 65 74 28 6e 6f 64 65 5f 74 2c 20  ext_get(node_t, 
0c10: 6c 69 6e 6b 2c 20 70 68 6e 5f 70 72 65 76 5f 67  link, phn_prev_g
0c20: 65 74 28 6e 6f 64 65 5f 74 2c 0a 09 09 20 20 20  et(node_t,...   
0c30: 20 6c 69 6e 6b 2c 20 61 75 78 65 6c 6d 29 29 2c   link, auxelm)),
0c40: 20 61 75 78 65 6c 6d 2c 0a 09 09 20 20 20 20 22   auxelm,...    "
0c50: 61 75 78 65 6c 6d 27 73 20 70 72 65 76 20 64 6f  auxelm's prev do
0c60: 65 73 6e 27 74 20 6c 69 6e 6b 20 74 6f 20 61 75  esn't link to au
0c70: 78 65 6c 6d 22 29 3b 0a 09 09 6e 6e 6f 64 65 73  xelm");...nnodes
0c80: 20 2b 3d 20 6e 6f 64 65 5f 76 61 6c 69 64 61 74   += node_validat
0c90: 65 28 61 75 78 65 6c 6d 2c 20 4e 55 4c 4c 29 3b  e(auxelm, NULL);
0ca0: 0a 09 7d 0a 0a 6c 61 62 65 6c 5f 72 65 74 75 72  ..}..label_retur
0cb0: 6e 3a 0a 09 69 66 20 28 66 61 6c 73 65 29 0a 09  n:..if (false)..
0cc0: 09 68 65 61 70 5f 70 72 69 6e 74 28 68 65 61 70  .heap_print(heap
0cd0: 29 3b 0a 09 72 65 74 75 72 6e 20 28 6e 6e 6f 64  );..return (nnod
0ce0: 65 73 29 3b 0a 7d 0a 0a 54 45 53 54 5f 42 45 47  es);.}..TEST_BEG
0cf0: 49 4e 28 74 65 73 74 5f 70 68 5f 65 6d 70 74 79  IN(test_ph_empty
0d00: 29 0a 7b 0a 09 68 65 61 70 5f 74 20 68 65 61 70  ).{..heap_t heap
0d10: 3b 0a 0a 09 68 65 61 70 5f 6e 65 77 28 26 68 65  ;...heap_new(&he
0d20: 61 70 29 3b 0a 09 61 73 73 65 72 74 5f 74 72 75  ap);..assert_tru
0d30: 65 28 68 65 61 70 5f 65 6d 70 74 79 28 26 68 65  e(heap_empty(&he
0d40: 61 70 29 2c 20 22 48 65 61 70 20 73 68 6f 75 6c  ap), "Heap shoul
0d50: 64 20 62 65 20 65 6d 70 74 79 22 29 3b 0a 09 61  d be empty");..a
0d60: 73 73 65 72 74 5f 70 74 72 5f 6e 75 6c 6c 28 68  ssert_ptr_null(h
0d70: 65 61 70 5f 66 69 72 73 74 28 26 68 65 61 70 29  eap_first(&heap)
0d80: 2c 20 22 55 6e 65 78 70 65 63 74 65 64 20 6e 6f  , "Unexpected no
0d90: 64 65 22 29 3b 0a 7d 0a 54 45 53 54 5f 45 4e 44  de");.}.TEST_END
0da0: 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 0a 6e 6f  ..static void.no
0db0: 64 65 5f 72 65 6d 6f 76 65 28 68 65 61 70 5f 74  de_remove(heap_t
0dc0: 20 2a 68 65 61 70 2c 20 6e 6f 64 65 5f 74 20 2a   *heap, node_t *
0dd0: 6e 6f 64 65 29 0a 7b 0a 0a 09 68 65 61 70 5f 72  node).{...heap_r
0de0: 65 6d 6f 76 65 28 68 65 61 70 2c 20 6e 6f 64 65  emove(heap, node
0df0: 29 3b 0a 0a 09 6e 6f 64 65 2d 3e 6d 61 67 69 63  );...node->magic
0e00: 20 3d 20 30 3b 0a 7d 0a 0a 73 74 61 74 69 63 20   = 0;.}..static 
0e10: 6e 6f 64 65 5f 74 20 2a 0a 6e 6f 64 65 5f 72 65  node_t *.node_re
0e20: 6d 6f 76 65 5f 66 69 72 73 74 28 68 65 61 70 5f  move_first(heap_
0e30: 74 20 2a 68 65 61 70 29 0a 7b 0a 09 6e 6f 64 65  t *heap).{..node
0e40: 5f 74 20 2a 6e 6f 64 65 20 3d 20 68 65 61 70 5f  _t *node = heap_
0e50: 72 65 6d 6f 76 65 5f 66 69 72 73 74 28 68 65 61  remove_first(hea
0e60: 70 29 3b 0a 09 6e 6f 64 65 2d 3e 6d 61 67 69 63  p);..node->magic
0e70: 20 3d 20 30 3b 0a 09 72 65 74 75 72 6e 20 28 6e   = 0;..return (n
0e80: 6f 64 65 29 3b 0a 7d 0a 0a 54 45 53 54 5f 42 45  ode);.}..TEST_BE
0e90: 47 49 4e 28 74 65 73 74 5f 70 68 5f 72 61 6e 64  GIN(test_ph_rand
0ea0: 6f 6d 29 0a 7b 0a 23 64 65 66 69 6e 65 09 4e 4e  om).{.#define.NN
0eb0: 4f 44 45 53 20 32 35 0a 23 64 65 66 69 6e 65 09  ODES 25.#define.
0ec0: 4e 42 41 47 53 20 32 35 30 0a 23 64 65 66 69 6e  NBAGS 250.#defin
0ed0: 65 09 53 45 45 44 20 34 32 0a 09 73 66 6d 74 5f  e.SEED 42..sfmt_
0ee0: 74 20 2a 73 66 6d 74 3b 0a 09 75 69 6e 74 36 34  t *sfmt;..uint64
0ef0: 5f 74 20 62 61 67 5b 4e 4e 4f 44 45 53 5d 3b 0a  _t bag[NNODES];.
0f00: 09 68 65 61 70 5f 74 20 68 65 61 70 3b 0a 09 6e  .heap_t heap;..n
0f10: 6f 64 65 5f 74 20 6e 6f 64 65 73 5b 4e 4e 4f 44  ode_t nodes[NNOD
0f20: 45 53 5d 3b 0a 09 75 6e 73 69 67 6e 65 64 20 69  ES];..unsigned i
0f30: 2c 20 6a 2c 20 6b 3b 0a 0a 09 73 66 6d 74 20 3d  , j, k;...sfmt =
0f40: 20 69 6e 69 74 5f 67 65 6e 5f 72 61 6e 64 28 53   init_gen_rand(S
0f50: 45 45 44 29 3b 0a 09 66 6f 72 20 28 69 20 3d 20  EED);..for (i = 
0f60: 30 3b 20 69 20 3c 20 4e 42 41 47 53 3b 20 69 2b  0; i < NBAGS; i+
0f70: 2b 29 20 7b 0a 09 09 73 77 69 74 63 68 20 28 69  +) {...switch (i
0f80: 29 20 7b 0a 09 09 63 61 73 65 20 30 3a 0a 09 09  ) {...case 0:...
0f90: 09 2f 2a 20 49 6e 73 65 72 74 20 69 6e 20 6f 72  ./* Insert in or
0fa0: 64 65 72 2e 20 2a 2f 0a 09 09 09 66 6f 72 20 28  der. */....for (
0fb0: 6a 20 3d 20 30 3b 20 6a 20 3c 20 4e 4e 4f 44 45  j = 0; j < NNODE
0fc0: 53 3b 20 6a 2b 2b 29 0a 09 09 09 09 62 61 67 5b  S; j++).....bag[
0fd0: 6a 5d 20 3d 20 6a 3b 0a 09 09 09 62 72 65 61 6b  j] = j;....break
0fe0: 3b 0a 09 09 63 61 73 65 20 31 3a 0a 09 09 09 2f  ;...case 1:..../
0ff0: 2a 20 49 6e 73 65 72 74 20 69 6e 20 72 65 76 65  * Insert in reve
1000: 72 73 65 20 6f 72 64 65 72 2e 20 2a 2f 0a 09 09  rse order. */...
1010: 09 66 6f 72 20 28 6a 20 3d 20 30 3b 20 6a 20 3c  .for (j = 0; j <
1020: 20 4e 4e 4f 44 45 53 3b 20 6a 2b 2b 29 0a 09 09   NNODES; j++)...
1030: 09 09 62 61 67 5b 6a 5d 20 3d 20 4e 4e 4f 44 45  ..bag[j] = NNODE
1040: 53 20 2d 20 6a 20 2d 20 31 3b 0a 09 09 09 62 72  S - j - 1;....br
1050: 65 61 6b 3b 0a 09 09 64 65 66 61 75 6c 74 3a 0a  eak;...default:.
1060: 09 09 09 66 6f 72 20 28 6a 20 3d 20 30 3b 20 6a  ...for (j = 0; j
1070: 20 3c 20 4e 4e 4f 44 45 53 3b 20 6a 2b 2b 29 0a   < NNODES; j++).
1080: 09 09 09 09 62 61 67 5b 6a 5d 20 3d 20 67 65 6e  ....bag[j] = gen
1090: 5f 72 61 6e 64 36 34 5f 72 61 6e 67 65 28 73 66  _rand64_range(sf
10a0: 6d 74 2c 20 4e 4e 4f 44 45 53 29 3b 0a 09 09 7d  mt, NNODES);...}
10b0: 0a 0a 09 09 66 6f 72 20 28 6a 20 3d 20 31 3b 20  ....for (j = 1; 
10c0: 6a 20 3c 3d 20 4e 4e 4f 44 45 53 3b 20 6a 2b 2b  j <= NNODES; j++
10d0: 29 20 7b 0a 09 09 09 2f 2a 20 49 6e 69 74 69 61  ) {..../* Initia
10e0: 6c 69 7a 65 20 68 65 61 70 20 61 6e 64 20 6e 6f  lize heap and no
10f0: 64 65 73 2e 20 2a 2f 0a 09 09 09 68 65 61 70 5f  des. */....heap_
1100: 6e 65 77 28 26 68 65 61 70 29 3b 0a 09 09 09 61  new(&heap);....a
1110: 73 73 65 72 74 5f 75 5f 65 71 28 68 65 61 70 5f  ssert_u_eq(heap_
1120: 76 61 6c 69 64 61 74 65 28 26 68 65 61 70 29 2c  validate(&heap),
1130: 20 30 2c 0a 09 09 09 20 20 20 20 22 49 6e 63 6f   0,....    "Inco
1140: 72 72 65 63 74 20 6e 6f 64 65 20 63 6f 75 6e 74  rrect node count
1150: 22 29 3b 0a 09 09 09 66 6f 72 20 28 6b 20 3d 20  ");....for (k = 
1160: 30 3b 20 6b 20 3c 20 6a 3b 20 6b 2b 2b 29 20 7b  0; k < j; k++) {
1170: 0a 09 09 09 09 6e 6f 64 65 73 5b 6b 5d 2e 6d 61  .....nodes[k].ma
1180: 67 69 63 20 3d 20 4e 4f 44 45 5f 4d 41 47 49 43  gic = NODE_MAGIC
1190: 3b 0a 09 09 09 09 6e 6f 64 65 73 5b 6b 5d 2e 6b  ;.....nodes[k].k
11a0: 65 79 20 3d 20 62 61 67 5b 6b 5d 3b 0a 09 09 09  ey = bag[k];....
11b0: 7d 0a 0a 09 09 09 2f 2a 20 49 6e 73 65 72 74 20  }...../* Insert 
11c0: 6e 6f 64 65 73 2e 20 2a 2f 0a 09 09 09 66 6f 72  nodes. */....for
11d0: 20 28 6b 20 3d 20 30 3b 20 6b 20 3c 20 6a 3b 20   (k = 0; k < j; 
11e0: 6b 2b 2b 29 20 7b 0a 09 09 09 09 68 65 61 70 5f  k++) {.....heap_
11f0: 69 6e 73 65 72 74 28 26 68 65 61 70 2c 20 26 6e  insert(&heap, &n
1200: 6f 64 65 73 5b 6b 5d 29 3b 0a 09 09 09 09 69 66  odes[k]);.....if
1210: 20 28 69 20 25 20 31 33 20 3d 3d 20 31 32 29 20   (i % 13 == 12) 
1220: 7b 0a 09 09 09 09 09 2f 2a 20 54 72 69 67 67 65  {....../* Trigge
1230: 72 20 6d 65 72 67 69 6e 67 2e 20 2a 2f 0a 09 09  r merging. */...
1240: 09 09 09 61 73 73 65 72 74 5f 70 74 72 5f 6e 6f  ...assert_ptr_no
1250: 74 5f 6e 75 6c 6c 28 68 65 61 70 5f 66 69 72 73  t_null(heap_firs
1260: 74 28 26 68 65 61 70 29 2c 0a 09 09 09 09 09 20  t(&heap),...... 
1270: 20 20 20 22 48 65 61 70 20 73 68 6f 75 6c 64 20     "Heap should 
1280: 6e 6f 74 20 62 65 20 65 6d 70 74 79 22 29 3b 0a  not be empty");.
1290: 09 09 09 09 7d 0a 09 09 09 09 61 73 73 65 72 74  ....}.....assert
12a0: 5f 75 5f 65 71 28 68 65 61 70 5f 76 61 6c 69 64  _u_eq(heap_valid
12b0: 61 74 65 28 26 68 65 61 70 29 2c 20 6b 20 2b 20  ate(&heap), k + 
12c0: 31 2c 0a 09 09 09 09 20 20 20 20 22 49 6e 63 6f  1,.....    "Inco
12d0: 72 72 65 63 74 20 6e 6f 64 65 20 63 6f 75 6e 74  rrect node count
12e0: 22 29 3b 0a 09 09 09 7d 0a 0a 09 09 09 61 73 73  ");....}.....ass
12f0: 65 72 74 5f 66 61 6c 73 65 28 68 65 61 70 5f 65  ert_false(heap_e
1300: 6d 70 74 79 28 26 68 65 61 70 29 2c 0a 09 09 09  mpty(&heap),....
1310: 20 20 20 20 22 48 65 61 70 20 73 68 6f 75 6c 64      "Heap should
1320: 20 6e 6f 74 20 62 65 20 65 6d 70 74 79 22 29 3b   not be empty");
1330: 0a 0a 09 09 09 2f 2a 20 52 65 6d 6f 76 65 20 6e  ...../* Remove n
1340: 6f 64 65 73 2e 20 2a 2f 0a 09 09 09 73 77 69 74  odes. */....swit
1350: 63 68 20 28 69 20 25 20 34 29 20 7b 0a 09 09 09  ch (i % 4) {....
1360: 63 61 73 65 20 30 3a 0a 09 09 09 09 66 6f 72 20  case 0:.....for 
1370: 28 6b 20 3d 20 30 3b 20 6b 20 3c 20 6a 3b 20 6b  (k = 0; k < j; k
1380: 2b 2b 29 20 7b 0a 09 09 09 09 09 61 73 73 65 72  ++) {......asser
1390: 74 5f 75 5f 65 71 28 68 65 61 70 5f 76 61 6c 69  t_u_eq(heap_vali
13a0: 64 61 74 65 28 26 68 65 61 70 29 2c 20 6a 20 2d  date(&heap), j -
13b0: 20 6b 2c 0a 09 09 09 09 09 20 20 20 20 22 49 6e   k,......    "In
13c0: 63 6f 72 72 65 63 74 20 6e 6f 64 65 20 63 6f 75  correct node cou
13d0: 6e 74 22 29 3b 0a 09 09 09 09 09 6e 6f 64 65 5f  nt");......node_
13e0: 72 65 6d 6f 76 65 28 26 68 65 61 70 2c 20 26 6e  remove(&heap, &n
13f0: 6f 64 65 73 5b 6b 5d 29 3b 0a 09 09 09 09 09 61  odes[k]);......a
1400: 73 73 65 72 74 5f 75 5f 65 71 28 68 65 61 70 5f  ssert_u_eq(heap_
1410: 76 61 6c 69 64 61 74 65 28 26 68 65 61 70 29 2c  validate(&heap),
1420: 20 6a 20 2d 20 6b 0a 09 09 09 09 09 20 20 20 20   j - k......    
1430: 2d 20 31 2c 20 22 49 6e 63 6f 72 72 65 63 74 20  - 1, "Incorrect 
1440: 6e 6f 64 65 20 63 6f 75 6e 74 22 29 3b 0a 09 09  node count");...
1450: 09 09 7d 0a 09 09 09 09 62 72 65 61 6b 3b 0a 09  ..}.....break;..
1460: 09 09 63 61 73 65 20 31 3a 0a 09 09 09 09 66 6f  ..case 1:.....fo
1470: 72 20 28 6b 20 3d 20 6a 3b 20 6b 20 3e 20 30 3b  r (k = j; k > 0;
1480: 20 6b 2d 2d 29 20 7b 0a 09 09 09 09 09 6e 6f 64   k--) {......nod
1490: 65 5f 72 65 6d 6f 76 65 28 26 68 65 61 70 2c 20  e_remove(&heap, 
14a0: 26 6e 6f 64 65 73 5b 6b 2d 31 5d 29 3b 0a 09 09  &nodes[k-1]);...
14b0: 09 09 09 61 73 73 65 72 74 5f 75 5f 65 71 28 68  ...assert_u_eq(h
14c0: 65 61 70 5f 76 61 6c 69 64 61 74 65 28 26 68 65  eap_validate(&he
14d0: 61 70 29 2c 20 6b 20 2d 20 31 2c 0a 09 09 09 09  ap), k - 1,.....
14e0: 09 20 20 20 20 22 49 6e 63 6f 72 72 65 63 74 20  .    "Incorrect 
14f0: 6e 6f 64 65 20 63 6f 75 6e 74 22 29 3b 0a 09 09  node count");...
1500: 09 09 7d 0a 09 09 09 09 62 72 65 61 6b 3b 0a 09  ..}.....break;..
1510: 09 09 63 61 73 65 20 32 3a 20 7b 0a 09 09 09 09  ..case 2: {.....
1520: 6e 6f 64 65 5f 74 20 2a 70 72 65 76 20 3d 20 4e  node_t *prev = N
1530: 55 4c 4c 3b 0a 09 09 09 09 66 6f 72 20 28 6b 20  ULL;.....for (k 
1540: 3d 20 30 3b 20 6b 20 3c 20 6a 3b 20 6b 2b 2b 29  = 0; k < j; k++)
1550: 20 7b 0a 09 09 09 09 09 6e 6f 64 65 5f 74 20 2a   {......node_t *
1560: 6e 6f 64 65 20 3d 20 6e 6f 64 65 5f 72 65 6d 6f  node = node_remo
1570: 76 65 5f 66 69 72 73 74 28 26 68 65 61 70 29 3b  ve_first(&heap);
1580: 0a 09 09 09 09 09 61 73 73 65 72 74 5f 75 5f 65  ......assert_u_e
1590: 71 28 68 65 61 70 5f 76 61 6c 69 64 61 74 65 28  q(heap_validate(
15a0: 26 68 65 61 70 29 2c 20 6a 20 2d 20 6b 0a 09 09  &heap), j - k...
15b0: 09 09 09 20 20 20 20 2d 20 31 2c 20 22 49 6e 63  ...    - 1, "Inc
15c0: 6f 72 72 65 63 74 20 6e 6f 64 65 20 63 6f 75 6e  orrect node coun
15d0: 74 22 29 3b 0a 09 09 09 09 09 69 66 20 28 70 72  t");......if (pr
15e0: 65 76 20 21 3d 20 4e 55 4c 4c 29 20 7b 0a 09 09  ev != NULL) {...
15f0: 09 09 09 09 61 73 73 65 72 74 5f 64 5f 67 65 28  ....assert_d_ge(
1600: 6e 6f 64 65 5f 63 6d 70 28 6e 6f 64 65 2c 0a 09  node_cmp(node,..
1610: 09 09 09 09 09 20 20 20 20 70 72 65 76 29 2c 20  .....    prev), 
1620: 30 2c 0a 09 09 09 09 09 09 20 20 20 20 22 42 61  0,.......    "Ba
1630: 64 20 72 65 6d 6f 76 61 6c 20 6f 72 64 65 72 22  d removal order"
1640: 29 3b 0a 09 09 09 09 09 7d 0a 09 09 09 09 09 70  );......}......p
1650: 72 65 76 20 3d 20 6e 6f 64 65 3b 0a 09 09 09 09  rev = node;.....
1660: 7d 0a 09 09 09 09 62 72 65 61 6b 3b 0a 09 09 09  }.....break;....
1670: 7d 20 63 61 73 65 20 33 3a 20 7b 0a 09 09 09 09  } case 3: {.....
1680: 6e 6f 64 65 5f 74 20 2a 70 72 65 76 20 3d 20 4e  node_t *prev = N
1690: 55 4c 4c 3b 0a 09 09 09 09 66 6f 72 20 28 6b 20  ULL;.....for (k 
16a0: 3d 20 30 3b 20 6b 20 3c 20 6a 3b 20 6b 2b 2b 29  = 0; k < j; k++)
16b0: 20 7b 0a 09 09 09 09 09 6e 6f 64 65 5f 74 20 2a   {......node_t *
16c0: 6e 6f 64 65 20 3d 20 68 65 61 70 5f 66 69 72 73  node = heap_firs
16d0: 74 28 26 68 65 61 70 29 3b 0a 09 09 09 09 09 61  t(&heap);......a
16e0: 73 73 65 72 74 5f 75 5f 65 71 28 68 65 61 70 5f  ssert_u_eq(heap_
16f0: 76 61 6c 69 64 61 74 65 28 26 68 65 61 70 29 2c  validate(&heap),
1700: 20 6a 20 2d 20 6b 2c 0a 09 09 09 09 09 20 20 20   j - k,......   
1710: 20 22 49 6e 63 6f 72 72 65 63 74 20 6e 6f 64 65   "Incorrect node
1720: 20 63 6f 75 6e 74 22 29 3b 0a 09 09 09 09 09 69   count");......i
1730: 66 20 28 70 72 65 76 20 21 3d 20 4e 55 4c 4c 29  f (prev != NULL)
1740: 20 7b 0a 09 09 09 09 09 09 61 73 73 65 72 74 5f   {.......assert_
1750: 64 5f 67 65 28 6e 6f 64 65 5f 63 6d 70 28 6e 6f  d_ge(node_cmp(no
1760: 64 65 2c 0a 09 09 09 09 09 09 20 20 20 20 70 72  de,.......    pr
1770: 65 76 29 2c 20 30 2c 0a 09 09 09 09 09 09 20 20  ev), 0,.......  
1780: 20 20 22 42 61 64 20 72 65 6d 6f 76 61 6c 20 6f    "Bad removal o
1790: 72 64 65 72 22 29 3b 0a 09 09 09 09 09 7d 0a 09  rder");......}..
17a0: 09 09 09 09 6e 6f 64 65 5f 72 65 6d 6f 76 65 28  ....node_remove(
17b0: 26 68 65 61 70 2c 20 6e 6f 64 65 29 3b 0a 09 09  &heap, node);...
17c0: 09 09 09 61 73 73 65 72 74 5f 75 5f 65 71 28 68  ...assert_u_eq(h
17d0: 65 61 70 5f 76 61 6c 69 64 61 74 65 28 26 68 65  eap_validate(&he
17e0: 61 70 29 2c 20 6a 20 2d 20 6b 0a 09 09 09 09 09  ap), j - k......
17f0: 20 20 20 20 2d 20 31 2c 20 22 49 6e 63 6f 72 72      - 1, "Incorr
1800: 65 63 74 20 6e 6f 64 65 20 63 6f 75 6e 74 22 29  ect node count")
1810: 3b 0a 09 09 09 09 09 70 72 65 76 20 3d 20 6e 6f  ;......prev = no
1820: 64 65 3b 0a 09 09 09 09 7d 0a 09 09 09 09 62 72  de;.....}.....br
1830: 65 61 6b 3b 0a 09 09 09 7d 20 64 65 66 61 75 6c  eak;....} defaul
1840: 74 3a 0a 09 09 09 09 6e 6f 74 5f 72 65 61 63 68  t:.....not_reach
1850: 65 64 28 29 3b 0a 09 09 09 7d 0a 0a 09 09 09 61  ed();....}.....a
1860: 73 73 65 72 74 5f 70 74 72 5f 6e 75 6c 6c 28 68  ssert_ptr_null(h
1870: 65 61 70 5f 66 69 72 73 74 28 26 68 65 61 70 29  eap_first(&heap)
1880: 2c 0a 09 09 09 20 20 20 20 22 48 65 61 70 20 73  ,....    "Heap s
1890: 68 6f 75 6c 64 20 62 65 20 65 6d 70 74 79 22 29  hould be empty")
18a0: 3b 0a 09 09 09 61 73 73 65 72 74 5f 74 72 75 65  ;....assert_true
18b0: 28 68 65 61 70 5f 65 6d 70 74 79 28 26 68 65 61  (heap_empty(&hea
18c0: 70 29 2c 20 22 48 65 61 70 20 73 68 6f 75 6c 64  p), "Heap should
18d0: 20 62 65 20 65 6d 70 74 79 22 29 3b 0a 09 09 7d   be empty");...}
18e0: 0a 09 7d 0a 09 66 69 6e 69 5f 67 65 6e 5f 72 61  ..}..fini_gen_ra
18f0: 6e 64 28 73 66 6d 74 29 3b 0a 23 75 6e 64 65 66  nd(sfmt);.#undef
1900: 20 4e 4e 4f 44 45 53 0a 23 75 6e 64 65 66 20 53   NNODES.#undef S
1910: 45 45 44 0a 7d 0a 54 45 53 54 5f 45 4e 44 0a 0a  EED.}.TEST_END..
1920: 69 6e 74 0a 6d 61 69 6e 28 76 6f 69 64 29 0a 7b  int.main(void).{
1930: 0a 0a 09 72 65 74 75 72 6e 20 28 74 65 73 74 28  ...return (test(
1940: 0a 09 20 20 20 20 74 65 73 74 5f 70 68 5f 65 6d  ..    test_ph_em
1950: 70 74 79 2c 0a 09 20 20 20 20 74 65 73 74 5f 70  pty,..    test_p
1960: 68 5f 72 61 6e 64 6f 6d 29 29 3b 0a 7d 0a        h_random));.}.