chiark - git - mdw - xyla/blob - rbregress.in

   1 ;;; Regression testing for red-black trees.
   2
   3 :
   4 :;; `rbtree_join' could look for a sibling node's colour without checking
   5 :;; that it actually existed.
   6
   7 = (_ *0 (_ 3 _)) D!
   8 ( 6k ~ D!
   9
  10 :
  11 :;; In `rbtree_split' with an empty path, the root of the initial tree
  12 :;; wasn't forcibly blackened.  Make sure this is done and that the
  13 :;; black heights are correctly tracked.  This causes all manner of
  14 :;; trouble otherwise, including leaking nodes because `rbtree_join'
  15 :;; assumes that a tree with zero black-height must be empty -- which
  16 :;; is true.
  17 =                                       ((((_ *12 _)
  18                         *13
  19                                         (_ *14 _))
  20                 16
  21                                         ((_ *17 _)
  22                         *18
  23                                         (_ *19
  24                                                 (_ 23 _))))
  25         *24
  26                                         (((_ *28 _)
  27                                 32
  28                                         (_ *35 _))
  29                         *36
  30                                         (_ *37
  31                                                 (_ 39 _))))
  32 D! 22@ / D! ) D! ) D!
  33
  34 :
  35 :;; The hairy test case which found both of these bugs.
  36 =                                               (((((_ 0 _)
  37                                         *3 _)
  38                         *6
  39                                         (_ *9_))
  40                 11
  41                                                 (((_ 12 _)
  42                                         *21 _)
  43                         *22
  44                                         ((_ *27
  45                                                 (_ 28 _))
  46                                 31
  47                                         (_ *35 _))))
  48         *41
  49                                                 (((_ 49 _)
  50                                         *50
  51                                                 (_ 55 _))
  52                         *57
  53                                         (_ *59 _)))
  54 D!
  55
  56 (
  57 =                                               (((((_ *0
  58                                                         (_ 1 _))
  59                                 *3
  60                                                 (_ *4 _))
  61                         6
  62                                                         (((_ 11 _)
  63                                                 *12 _)
  64                                 *13
  65                                                 (_ *14 _)))
  66                 *16
  67                                                 (((_ *17 _)
  68                                 *18
  69                                                 (_ *19
  70                                                         (_ 23 _)))
  71                         24
  72                                                 (((_ *28 _)
  73                                         32
  74                                                 (_ *35 _))
  75                                 *36
  76                                                 (_ *37 _))))
  77         *39
  78                                                 (((_ *41 _)
  79                                 *43
  80                                                 (_ *44
  81                                                         (_ 45 _)))
  82                 *52
  83                                                 (((_ *53 _)
  84                                         56
  85                                                 (_ *58 _))
  86                                 *60
  87                                                 (_ *61 _))))
  88 D!
  89
  90 \ D! ) D! ) D!
  91
  92 :
  93 :;; `rbtree_splitroot' just could not track subtree heights correctly.
  94
  95 =                                               (((((_ *4
  96                                                         (_ 6 _))
  97                                 *10
  98                                                 (_ *11 _))
  99                         13
 100                                                 ((_ *17 _)
 101                                 *18
 102                                                         ((_ 19 _)
 103                                                 *20 _)))
 104                 *22
 105                                                 ((_ *23 _)
 106                                 *25
 107                                                         ((_ 26 _)
 108                                                 *27 _)))
 109         *30
 110                                                         ((((_ 32 _)
 111                                                 *33 _)
 112                                 *34
 113                                                 ((_ *36
 114                                                         (_ 38 _))
 115                                         40
 116                                                 (_ *41 _)))
 117                 *43
 118                                                         (((_ 45 _)
 119                                                 *46 _)
 120                                 *48
 121                                                         (((_ 49 _)
 122                                                 *51 _)
 123                                         53
 124                                                 (_ *61
 125                                                         (_ 62 _))))))
 126 D!
 127
 128 (
 129 =                                       (((((_ *6 _)
 130                                 15
 131                                         (_ *16 _))
 132                         *23
 133                                         (_ *24 _))
 134                 33
 135                                         (((_ *35 _)
 136                                 36
 137                                         (_ *37
 138                                                 (_ 39 _)))
 139                         *40
 140                                         ((_ *43 _)
 141                                 47
 142                                         (_ *48
 143                                                 (_ 49 _)))))
 144         *50
 145                                         ((_ *57 _)
 146                         *59
 147                                                 ((_ 61 _)
 148                                         *62 _)))
 149 D!
 150
 151 | D! ) D!