| 1 |
|
| #include "tvcommon.h" |
| 2 |
|
| |
| 3 |
|
| #undef MIN |
| 4 |
|
| #define MIN(a, b) ((a) < (b) ? (a) : (b)) |
| 5 |
|
| #undef MAX |
| 6 |
|
| #define MAX(a, b) ((a) < (b) ? (b) : (a)) |
| 7 |
|
| |
| 8 |
|
| |
| 9 |
|
| #ifdef TV_TEST |
| 10 |
|
| |
| 11 |
|
| #undef assert |
| 12 |
|
| #define assert(what) \ |
| 13 |
|
| if (!(what)) { \ |
| 14 |
|
| croak("Assertion failed: file \"%s\", line %d", \ |
| 15 |
|
| __FILE__, __LINE__); \ |
| 16 |
|
| exit(1); \ |
| 17 |
|
| } |
| 18 |
|
| |
| 19 |
|
| #else |
| 20 |
|
| #undef assert |
| 21 |
|
| #define assert(s) |
| 22 |
|
| #endif |
| 23 |
|
| |
| 24 |
|
| #define PRIVATE /*like C++!*/ |
| 25 |
|
| |
| 26 |
|
| /* CCov: fatal TV_PANIC */ |
| 27 |
|
| /* CCov: off */ |
| 28 |
|
| |
| 29 |
|
| #ifdef TV_DEBUG |
| 30 |
|
| static int tv_debug=0; |
| 31 |
|
| void |
| 32 |
0 |
| tv_set_debug(int mask) |
| 33 |
|
| { |
| 34 |
0 |
| tv_debug = mask; |
| 35 |
0 |
| } |
| 36 |
|
| #endif |
| 37 |
|
| |
| 38 |
|
| #ifdef TV_TEST |
| 39 |
|
| void * |
| 40 |
|
| tv_testmalloc(size_t size) |
| 41 |
|
| { |
| 42 |
|
| void *ptr; |
| 43 |
|
| ptr = safemalloc(size); |
| 44 |
|
| if (ptr != 0) { |
| 45 |
|
| memset(ptr, 0x69, size); /* total paranoia */ |
| 46 |
|
| return ptr; |
| 47 |
|
| } else { |
| 48 |
|
| TV_PANIC("out of memory!"); |
| 49 |
|
| return 0; |
| 50 |
|
| } |
| 51 |
|
| } |
| 52 |
|
| #endif |
| 53 |
|
| |
| 54 |
|
| /* CCov: on */ |
| 55 |
|
| |
| 56 |
|
| XPVTV * |
| 57 |
22 |
| init_tv(XPVTV *tv) |
| 58 |
|
| { |
| 59 |
|
| assert(tv); |
| 60 |
22 |
| TvFLAGS(tv)=0; |
| 61 |
22 |
| TvROOT_set(tv,0); |
| 62 |
22 |
| TvMAX(tv)=0; |
| 63 |
22 |
| TvVERSION(tv)=0; |
| 64 |
22 |
| return tv; |
| 65 |
|
| } |
| 66 |
|
| |
| 67 |
|
| static void |
| 68 |
45 |
| tc_settce(XPVTC *tc, TCE *tce) |
| 69 |
|
| { |
| 70 |
|
| assert(tc); |
| 71 |
|
| assert(tce); |
| 72 |
45 |
▶ | if (TcPATH(tc)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcPATH(tc)) { |
10 |
35 |
45 |
|
| 73 |
10 |
| FREE_TCE(TcPATH(tc)); |
| 74 |
|
| } |
| 75 |
45 |
| TcPATH(tc) = tce; |
| 76 |
45 |
| } |
| 77 |
|
| |
| 78 |
|
| PRIVATE void |
| 79 |
10 |
| tc_extend(XPVTC *tc) |
| 80 |
|
| { |
| 81 |
|
| TCE *ce2; |
| 82 |
|
| assert(tc); |
| 83 |
10 |
| TcMAX(tc) += 7; /* cursors already grow exponentially */ |
| 84 |
10 |
| NEW_TCE(ce2, tc, TcMAX(tc)); |
| 85 |
|
| /* Copy(TcPATH(tc), ce2, TcFILL(tc), TCE); /* Copy is a perl macro! XXX */ |
| 86 |
10 |
| memcpy(ce2, TcPATH(tc), TcFILL(tc)*sizeof(TCE)); |
| 87 |
10 |
| tc_settce(tc, ce2); |
| 88 |
10 |
| } |
| 89 |
|
| |
| 90 |
|
| PRIVATE void |
| 91 |
93302 |
| tc_reset(XPVTC *tc) |
| 92 |
|
| { |
| 93 |
|
| XPVTV *tv; |
| 94 |
93302 |
| tv=TcTV(tc); |
| 95 |
|
| assert(tc); |
| 96 |
|
| assert(tv); |
| 97 |
93302 |
| TcVERSION(tc) = TvVERSION(tv); |
| 98 |
93302 |
| TcMATCH_off(tc); |
| 99 |
93302 |
| TcSTARTEND_off(tc); |
| 100 |
93302 |
| TcFILL(tc) = 0; |
| 101 |
93302 |
| TcSTART_on(tc); |
| 102 |
93302 |
| TcPOS(tc) = -1; |
| 103 |
93302 |
| TcFORWARD_on(tc); |
| 104 |
93302 |
| } |
| 105 |
|
| |
| 106 |
|
| void |
| 107 |
39316 |
| tc_refocus(XPVTC *tc, XPVTV *tv) |
| 108 |
|
| { |
| 109 |
39316 |
| TcTV(tc) = tv; |
| 110 |
39316 |
▶ | if (tv) tc_reset(tc); |
Branch: 1 branch
| Branch | True | False | Total |
| if (tv) tc_reset(tc); |
19672 |
19644 |
39316 |
|
| 111 |
39316 |
| } |
| 112 |
|
| |
| 113 |
|
| XPVTC * |
| 114 |
35 |
| init_tc(XPVTC *tc) |
| 115 |
|
| { |
| 116 |
|
| TCE *tce2; |
| 117 |
|
| assert(tc); |
| 118 |
35 |
| TcTV(tc) = 0; |
| 119 |
35 |
| TcFLAGS(tc) = 0; |
| 120 |
|
| #ifdef TV_STATS |
| 121 |
35 |
| tc->xtc_stats = (I32*) safemalloc(sizeof(I32)*TCS_MAX); /* XXX */ |
| 122 |
|
| SCOPE { |
| 123 |
|
| int xa; |
| 124 |
350 |
▶ | for (xa=0; xa < TCS_MAX; xa++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (xa=0; xa < TCS_MAX; xa++) { |
315 |
35 |
350 |
|
| 125 |
315 |
| TcSTAT(tc,xa) = 0; |
| 126 |
|
| } |
| 127 |
|
| } |
| 128 |
|
| #endif |
| 129 |
35 |
| TcMAX(tc) = 7; |
| 130 |
35 |
| TcPATH(tc) = 0; |
| 131 |
|
| /* Cannot scale proportional to TvMAX because TV might not be set! */ |
| 132 |
35 |
| NEW_TCE(tce2, tc,TcMAX(tc)); |
| 133 |
35 |
| tc_settce(tc, tce2); |
| 134 |
35 |
| return tc; |
| 135 |
|
| } |
| 136 |
|
| |
| 137 |
|
| void |
| 138 |
28 |
| free_tc(XPVTC *tc) |
| 139 |
|
| { |
| 140 |
|
| assert(TcPATH(tc)); |
| 141 |
28 |
| FREE_TCE(TcPATH(tc)); |
| 142 |
|
| #ifdef TV_STATS |
| 143 |
28 |
| safefree(tc->xtc_stats); /*macroize XXX*/ |
| 144 |
|
| #endif |
| 145 |
28 |
| FREE_XPVTC(tc); |
| 146 |
28 |
| } |
| 147 |
|
| |
| 148 |
|
| PRIVATE void |
| 149 |
18542 |
| tc_adjust_treefill(XPVTC *tc, int delta) |
| 150 |
|
| { |
| 151 |
|
| register int lx; |
| 152 |
|
| assert(tc); |
| 153 |
59419 |
▶ | for (lx=0; lx < TcFILL(tc); lx++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (lx=0; lx < TcFILL(tc); lx++) { |
40877 |
18542 |
59419 |
|
| 154 |
40877 |
| TnTREEFILL(TcTN(tc, lx)) += delta; |
| 155 |
|
| } |
| 156 |
18542 |
| } |
| 157 |
|
| |
| 158 |
|
| I32 |
| 159 |
3013 |
| tc_pos(XPVTC *tc) |
| 160 |
|
| { |
| 161 |
|
| XPVTV *tv; |
| 162 |
|
| assert(tc); |
| 163 |
3013 |
| tv=TcTV(tc); |
| 164 |
3013 |
▶ | TcSYNCCHECK(tc,tv); |
Branch: 1 branch
| Branch | True | False | Total |
| TcSYNCCHECK(tc,tv); |
0 |
3013 |
3013 |
|
| 165 |
3013 |
▶ | if (TcMATCH(tc)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcMATCH(tc)) { |
2918 |
95 |
3013 |
|
| 166 |
2918 |
| return TcPOS(tc); |
| 167 |
95 |
▶ | } else if (TcPOS(tc) == -1) { /*cover both at START cases */ |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (TcPOS(tc) == -1) { /*cover both at START cases */ |
49 |
46 |
95 |
|
| 168 |
49 |
| return -1; |
| 169 |
46 |
▶ | } else if (TcEND(tc)) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (TcEND(tc)) { |
42 |
4 |
46 |
|
| 170 |
42 |
| return TcPOS(tc); |
| 171 |
4 |
▶ | } else if (TcPOS(tc) == TvFILL(tv)-1) { /*at END (no match)*/ |
Branch: 2 branches
| Branch | True | False | Total |
| } else if (TcPOS(tc) == TvFILL(tv)-1) { /*at END (no match)*/ |
4 |
0 |
4 |
| } else if (TcPOS(tc) == TvFILL(tv)-1) { /*at END (no match)*/ |
2 |
2 |
4 |
|
| 172 |
2 |
| return TcPOS(tc)+1; |
| 173 |
|
| } else { |
| 174 |
2 |
| TV_PANIC("TV: attempt to get the position of an unpositioned cursor"); |
| 175 |
|
| return 0; |
| 176 |
|
| } |
| 177 |
|
| } |
| 178 |
|
| |
| 179 |
|
| PRIVATE int |
| 180 |
10954 |
| tc_stepnode(XPVTC *tc, I32 delta) |
| 181 |
|
| { |
| 182 |
|
| assert(tc); |
| 183 |
|
| /* TcSYNCCHECK(tc); assume caller already checked */ |
| 184 |
10954 |
▶ | DEBUG_step(warn("step node %d", delta)); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("step node %d", delta)); |
0 |
10954 |
10954 |
|
| 185 |
10954 |
▶ | if (TcFILL(tc)==0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc)==0) { |
256 |
10698 |
10954 |
|
| 186 |
|
| XPVTV *tv; |
| 187 |
|
| TN0 *tn; |
| 188 |
256 |
| tv=TcTV(tc); |
| 189 |
256 |
| tn = TvROOT(tv); |
| 190 |
256 |
▶ | if (!tn) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tn) { |
2 |
254 |
256 |
|
| 191 |
2 |
| return 0; |
| 192 |
254 |
▶ | } else if ((TcSTART(tc) && delta < 0) || |
Branch: 2 branches
| Branch | True | False | Total |
| } else if ((TcSTART(tc) && delta < 0) || |
76 |
178 |
254 |
| } else if ((TcSTART(tc) && delta < 0) || |
64 |
12 |
76 |
|
| 193 |
242 |
▶ | (TcEND(tc) && delta > 0) /*OK*/) { |
Branch: 2 branches
| Branch | True | False | Total |
| (TcEND(tc) && delta > 0) /*OK*/) { |
76 |
166 |
242 |
| (TcEND(tc) && delta > 0) /*OK*/) { |
12 |
64 |
76 |
|
| 194 |
24 |
▶ | DEBUG_step(warn("stepped beyond range")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("stepped beyond range")); |
0 |
24 |
24 |
|
| 195 |
24 |
| return 0; |
| 196 |
|
| } |
| 197 |
230 |
| TcSTARTEND_off(tc); |
| 198 |
230 |
▶ | TcPUSH(tc, tn); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, tn); |
0 |
230 |
230 |
|
| 199 |
|
| } |
| 200 |
10928 |
▶ | if (delta > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (delta > 0) { |
9575 |
1353 |
10928 |
|
| 201 |
9575 |
▶ | TcGOFWD(tc); |
Branch: 3 branches
| Branch | True | False | Total |
| TcGOFWD(tc); |
9110 |
465 |
9575 |
| TcGOFWD(tc); |
0 |
465 |
465 |
| TcGOFWD(tc); |
343 |
122 |
465 |
|
| 202 |
|
| do { |
| 203 |
|
| register TCE *ce; |
| 204 |
|
| register TN0 *down; |
| 205 |
10081 |
| FORWARD: |
| 206 |
10546 |
| TcRSTAT(tc, TCS_STEPNODE, 1); |
| 207 |
10546 |
| ce = TcCEx(tc); |
| 208 |
10546 |
▶ | if (!CeLEFT(ce) && !CeRIGHT(ce)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!CeLEFT(ce) && !CeRIGHT(ce)) { |
1166 |
9380 |
10546 |
| if (!CeLEFT(ce) && !CeRIGHT(ce)) { |
1095 |
71 |
1166 |
|
| 209 |
1095 |
▶ | DEBUG_step(warn("left extreme")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("left extreme")); |
0 |
1095 |
1095 |
|
| 210 |
1095 |
| CeLEFT_on(ce); |
| 211 |
1532 |
▶ | while (down = TnLEFT(CeTN(ce))) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (down = TnLEFT(CeTN(ce))) { |
437 |
1095 |
1532 |
|
| 212 |
437 |
▶ | TcPUSH(tc, down); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, down); |
3 |
434 |
437 |
|
| 213 |
437 |
| ce = TcCEx(tc); |
| 214 |
437 |
| CeLEFT_on(ce); |
| 215 |
|
| } |
| 216 |
1095 |
| --delta; |
| 217 |
1095 |
| continue; |
| 218 |
|
| } |
| 219 |
9451 |
| --delta; |
| 220 |
9451 |
▶ | if (!CeRIGHT(ce) && (down = TnRIGHT(CeTN(ce)))) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!CeRIGHT(ce) && (down = TnRIGHT(CeTN(ce)))) { |
9380 |
71 |
9451 |
| if (!CeRIGHT(ce) && (down = TnRIGHT(CeTN(ce)))) { |
971 |
8409 |
9380 |
|
| 221 |
971 |
▶ | DEBUG_step(warn("right")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("right")); |
0 |
971 |
971 |
|
| 222 |
971 |
| CeLEFT_off(ce); |
| 223 |
971 |
| CeRIGHT_on(ce); |
| 224 |
971 |
▶ | TcPUSH(tc, down); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, down); |
0 |
971 |
971 |
|
| 225 |
971 |
| goto FORWARD; |
| 226 |
|
| } |
| 227 |
8480 |
▶ | DEBUG_step(warn("popping")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("popping")); |
0 |
8480 |
8480 |
|
| 228 |
|
| do { |
| 229 |
11031 |
| TcPOP(tc); |
| 230 |
11031 |
▶ | if (TcFILL(tc) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc) == 0) { |
6301 |
4730 |
11031 |
|
| 231 |
6301 |
| delta=0; |
| 232 |
6301 |
| break; |
| 233 |
|
| } |
| 234 |
4730 |
▶ | } while (CeRIGHT(TcCEx(tc))); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (CeRIGHT(TcCEx(tc))); |
2551 |
2179 |
4730 |
|
| 235 |
9575 |
▶ | } while (delta > 0); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (delta > 0); |
0 |
9575 |
9575 |
|
| 236 |
|
| } |
| 237 |
1353 |
▶ | else if (delta < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| else if (delta < 0) { |
1353 |
0 |
1353 |
|
| 238 |
1353 |
▶ | TcGOBWD(tc); |
Branch: 3 branches
| Branch | True | False | Total |
| TcGOBWD(tc); |
647 |
706 |
1353 |
| TcGOBWD(tc); |
0 |
706 |
706 |
| TcGOBWD(tc); |
600 |
106 |
706 |
|
| 239 |
|
| do { |
| 240 |
|
| register TCE *ce; |
| 241 |
|
| register TN0 *down; |
| 242 |
1086 |
| BACKWARD: |
| 243 |
1792 |
| TcRSTAT(tc, TCS_STEPNODE, 1); |
| 244 |
1792 |
| ce = TcCEx(tc); |
| 245 |
1792 |
▶ | if (!CeRIGHT(ce) && !CeLEFT(ce)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!CeRIGHT(ce) && !CeLEFT(ce)) { |
545 |
1247 |
1792 |
| if (!CeRIGHT(ce) && !CeLEFT(ce)) { |
545 |
0 |
545 |
|
| 246 |
545 |
▶ | DEBUG_step(warn("right extreme")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("right extreme")); |
0 |
545 |
545 |
|
| 247 |
545 |
| CeRIGHT_on(ce); |
| 248 |
961 |
▶ | while (down = TnRIGHT(CeTN(ce))) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (down = TnRIGHT(CeTN(ce))) { |
416 |
545 |
961 |
|
| 249 |
416 |
▶ | TcPUSH(tc, down); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, down); |
2 |
414 |
416 |
|
| 250 |
416 |
| ce = TcCEx(tc); |
| 251 |
416 |
| CeRIGHT_on(ce); |
| 252 |
|
| } |
| 253 |
545 |
| ++delta; |
| 254 |
545 |
| continue; |
| 255 |
|
| } |
| 256 |
1247 |
| ++delta; |
| 257 |
1247 |
▶ | if (!CeLEFT(ce) && (down = TnLEFT(CeTN(ce)))) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!CeLEFT(ce) && (down = TnLEFT(CeTN(ce)))) { |
1247 |
0 |
1247 |
| if (!CeLEFT(ce) && (down = TnLEFT(CeTN(ce)))) { |
439 |
808 |
1247 |
|
| 258 |
439 |
▶ | DEBUG_step(warn("left")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("left")); |
0 |
439 |
439 |
|
| 259 |
439 |
| CeRIGHT_off(ce); |
| 260 |
439 |
| CeLEFT_on(ce); |
| 261 |
439 |
▶ | TcPUSH(tc, down); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, down); |
0 |
439 |
439 |
|
| 262 |
439 |
| goto BACKWARD; |
| 263 |
|
| } |
| 264 |
808 |
▶ | DEBUG_step(warn("popping")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("popping")); |
0 |
808 |
808 |
|
| 265 |
|
| do { |
| 266 |
1159 |
| TcPOP(tc); |
| 267 |
1159 |
▶ | if (TcFILL(tc) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc) == 0) { |
171 |
988 |
1159 |
|
| 268 |
171 |
| delta=0; |
| 269 |
171 |
| break; |
| 270 |
|
| } |
| 271 |
988 |
▶ | } while (CeLEFT(TcCEx(tc))); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (CeLEFT(TcCEx(tc))); |
351 |
637 |
988 |
|
| 272 |
1353 |
▶ | } while (delta < 0); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (delta < 0); |
0 |
1353 |
1353 |
|
| 273 |
|
| } |
| 274 |
10928 |
| return TcFILL(tc) > 0; |
| 275 |
|
| } |
| 276 |
|
| |
| 277 |
|
| PRIVATE void |
| 278 |
1228 |
| tn_recalc(XPVTC *tc, TN0 *tn) |
| 279 |
|
| { |
| 280 |
1228 |
| int total = TnFILL(tn); |
| 281 |
1228 |
▶ | if (TnLEFT(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnLEFT(tn)) { |
577 |
651 |
1228 |
|
| 282 |
577 |
| total += TnTREEFILL(TnLEFT(tn)); |
| 283 |
|
| } |
| 284 |
1228 |
▶ | if (TnRIGHT(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnRIGHT(tn)) { |
553 |
675 |
1228 |
|
| 285 |
553 |
| total += TnTREEFILL(TnRIGHT(tn)); |
| 286 |
|
| } |
| 287 |
1228 |
| TnTREEFILL(tn) = total; |
| 288 |
1228 |
▶ | TnDEPTH(tn) = TnCALCDEPTH(tn); |
Branch: 4 branches
| Branch | True | False | Total |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
577 |
651 |
1228 |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
314 |
263 |
577 |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
263 |
651 |
914 |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
239 |
412 |
651 |
|
| 289 |
1228 |
| TcRSTAT(tc, TCS_DEPTHCALC, 1); |
| 290 |
1228 |
| TcRSTAT(tc, TCS_TNRECALC, 1); |
| 291 |
1228 |
| } |
| 292 |
|
| |
| 293 |
|
| static void |
| 294 |
110 |
| tn_recalc_r(TN0 *tn) |
| 295 |
|
| { |
| 296 |
110 |
| int total = TnFILL(tn); |
| 297 |
110 |
▶ | if (TnLEFT(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnLEFT(tn)) { |
52 |
58 |
110 |
|
| 298 |
52 |
| tn_recalc_r(TnLEFT(tn)); |
| 299 |
52 |
| total += TnTREEFILL(TnLEFT(tn)); |
| 300 |
|
| } |
| 301 |
110 |
▶ | if (TnRIGHT(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnRIGHT(tn)) { |
56 |
54 |
110 |
|
| 302 |
56 |
| tn_recalc_r(TnRIGHT(tn)); |
| 303 |
56 |
| total += TnTREEFILL(TnRIGHT(tn)); |
| 304 |
|
| } |
| 305 |
110 |
| TnTREEFILL(tn) = total; |
| 306 |
110 |
▶ | TnDEPTH(tn) = TnCALCDEPTH(tn); |
Branch: 4 branches
| Branch | True | False | Total |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
52 |
58 |
110 |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
37 |
15 |
52 |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
15 |
58 |
73 |
| TnDEPTH(tn) = TnCALCDEPTH(tn); |
19 |
39 |
58 |
|
| 307 |
110 |
| } |
| 308 |
|
| |
| 309 |
|
| /*------- ------- ------- ------- ------- ------- ------- -------*/ |
| 310 |
|
| |
| 311 |
|
| static void |
| 312 |
269 |
| tc_setnode(XPVTC *tc, int level, int top, TN0 *tn) |
| 313 |
|
| { |
| 314 |
269 |
▶ | TCE *down = level+1 < TcFILL(tc)? TcCE(tc,level+1) : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| TCE *down = level+1 < TcFILL(tc)? TcCE(tc,level+1) : 0; |
264 |
5 |
269 |
|
| 315 |
269 |
| TCE *ce = TcCE(tc,level); |
| 316 |
|
| assert(tn); |
| 317 |
269 |
| CeTN_set(ce, tn); |
| 318 |
269 |
▶ | if (level > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (level > 0) { |
257 |
12 |
269 |
|
| 319 |
257 |
| TCE *up = TcCE(tc,level-1); |
| 320 |
257 |
| TN0 *mom = CeTN(up); |
| 321 |
257 |
▶ | if (top) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (top) { |
231 |
26 |
257 |
|
| 322 |
231 |
▶ | if (CeLEFT(up)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (CeLEFT(up)) { |
125 |
106 |
231 |
|
| 323 |
125 |
| TnLEFT_set(mom, tn); |
| 324 |
|
| } else { |
| 325 |
106 |
| TnRIGHT_set(mom, tn); |
| 326 |
|
| } |
| 327 |
|
| } else { |
| 328 |
26 |
▶ | if (TnLEFT(mom) == tn) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnLEFT(mom) == tn) { |
14 |
12 |
26 |
|
| 329 |
14 |
| CeRIGHT_off(up); |
| 330 |
14 |
| CeLEFT_on(up); |
| 331 |
|
| } else { |
| 332 |
|
| assert(TnRIGHT(mom) == tn); |
| 333 |
12 |
| CeLEFT_off(up); |
| 334 |
12 |
| CeRIGHT_on(up); |
| 335 |
|
| } |
| 336 |
26 |
▶ | if (down) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (down) { |
23 |
3 |
26 |
|
| 337 |
23 |
▶ | if (TnLEFT(tn) == CeTN(down)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnLEFT(tn) == CeTN(down)) { |
12 |
11 |
23 |
|
| 338 |
12 |
| CeRIGHT_off(ce); |
| 339 |
12 |
| CeLEFT_on(ce); |
| 340 |
11 |
▶ | } else if (TnRIGHT(tn) == CeTN(down)) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (TnRIGHT(tn) == CeTN(down)) { |
11 |
0 |
11 |
|
| 341 |
11 |
| CeLEFT_off(ce); |
| 342 |
11 |
| CeRIGHT_on(ce); |
| 343 |
|
| } |
| 344 |
|
| } |
| 345 |
|
| } |
| 346 |
|
| } else { |
| 347 |
|
| XPVTV *tv; |
| 348 |
12 |
| tv=TcTV(tc); |
| 349 |
12 |
| TvROOT_set(tv, tn); |
| 350 |
|
| assert(top); |
| 351 |
|
| } |
| 352 |
269 |
▶ | if (!down) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!down) { |
5 |
264 |
269 |
|
| 353 |
5 |
▶ | TcFLOW(tc); |
Branch: 1 branch
| Branch | True | False | Total |
| TcFLOW(tc); |
5 |
0 |
5 |
|
| 354 |
|
| } |
| 355 |
269 |
| } |
| 356 |
|
| |
| 357 |
|
| static int |
| 358 |
1745 |
| tc_rotate1(XPVTC *tc, int xl, int looseness) |
| 359 |
|
| { |
| 360 |
1745 |
| int forced = looseness < 0; |
| 361 |
1745 |
| TCE *ce1 = TcCE(tc, xl); |
| 362 |
1745 |
| TCE *ce2 = TcCE(tc, xl+1); |
| 363 |
1745 |
▶ | TCE *ce3 = (xl+2 < TcFILL(tc)? TcCE(tc, xl+2) : 0); |
Branch: 1 branch
| Branch | True | False | Total |
| TCE *ce3 = (xl+2 < TcFILL(tc)? TcCE(tc, xl+2) : 0); |
1155 |
590 |
1745 |
|
| 364 |
1745 |
| TN0 *n1 = CeTN(ce1); |
| 365 |
1745 |
| TN0 *n2 = CeTN(ce2); |
| 366 |
|
| int side1; |
| 367 |
|
| int side2; |
| 368 |
|
| assert(xl+1 < TcFILL(tc)); |
| 369 |
1745 |
▶ | if (CeRIGHT(ce1)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (CeRIGHT(ce1)) { |
962 |
783 |
1745 |
|
| 370 |
962 |
| side1 = 0; |
| 371 |
962 |
| side2 = 1; |
| 372 |
|
| } else { |
| 373 |
783 |
| side1 = 1; |
| 374 |
783 |
| side2 = 0; |
| 375 |
|
| } |
| 376 |
|
| SCOPE { |
| 377 |
1745 |
| TN0 *na = TnKID(n1,side1); |
| 378 |
1745 |
| TN0 *nb = TnKID(n2,side1); |
| 379 |
1745 |
| TN0 *nc = TnKID(n2,side2); |
| 380 |
3298 |
▶ | if (forced || |
Branch: 2 branches
| Branch | True | False | Total |
| if (forced || |
1553 |
192 |
1745 |
| if (forced || |
37 |
1516 |
1553 |
|
| 381 |
1553 |
▶ | MAX(TnDEPTHx(na)+1, TnDEPTHx(nb)) + looseness < TnDEPTHx(nc) /*OK*/) { |
Branch: 3 branches
| Branch | True | False | Total |
| MAX(TnDEPTHx(na)+1, TnDEPTHx(nb)) + looseness < TnDEPTHx(nc) /*OK*/) { |
1109 |
444 |
1553 |
| MAX(TnDEPTHx(na)+1, TnDEPTHx(nb)) + looseness < TnDEPTHx(nc) /*OK*/) { |
957 |
596 |
1553 |
| MAX(TnDEPTHx(na)+1, TnDEPTHx(nb)) + looseness < TnDEPTHx(nc) /*OK*/) { |
1202 |
351 |
1553 |
|
| 382 |
|
| int type; |
| 383 |
229 |
| TcRSTAT(tc, TCS_ROTATE1, 1); |
| 384 |
229 |
▶ | if (!ce3) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ce3) { |
200 |
29 |
229 |
|
| 385 |
200 |
| type = 0; |
| 386 |
29 |
▶ | } else if (CeTN(ce3) == nc) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (CeTN(ce3) == nc) { |
27 |
2 |
29 |
|
| 387 |
27 |
| type = 1; |
| 388 |
|
| } else { |
| 389 |
|
| assert(CeTN(ce3) == nb); |
| 390 |
2 |
| type = 2; |
| 391 |
|
| } |
| 392 |
229 |
▶ | DEBUG_rotate(warn("rotate L/R type %d/%d at %d", side1, type, xl)); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_rotate(warn("rotate L/R type %d/%d at %d", side1, type, xl)); |
0 |
229 |
229 |
|
| 393 |
229 |
| TnKID_set(n2,side1, n1); |
| 394 |
229 |
| TnKID_set(n2,side2, nc); |
| 395 |
229 |
| TnKID_set(n1,side1, na); |
| 396 |
229 |
| TnKID_set(n1,side2, nb); |
| 397 |
229 |
| tc_setnode(tc, xl, 1, n2); |
| 398 |
229 |
▶ | if (type == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (type == 0) { |
200 |
29 |
229 |
|
| 399 |
400 |
▶ | TcCUT(tc, xl); |
Branch: 1 branch
| Branch | True | False | Total |
| TcCUT(tc, xl); |
200 |
200 |
400 |
|
| 400 |
29 |
▶ | } else if (type == 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (type == 1) { |
27 |
2 |
29 |
|
| 401 |
152 |
▶ | TcCUT(tc, xl); |
Branch: 1 branch
| Branch | True | False | Total |
| TcCUT(tc, xl); |
125 |
27 |
152 |
|
| 402 |
2 |
▶ | } else if (type == 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (type == 2) { |
2 |
0 |
2 |
|
| 403 |
2 |
| tc_setnode(tc, xl+1, 0, n1); |
| 404 |
|
| } else |
| 405 |
0 |
| croak("assertion failed"); |
| 406 |
229 |
| tn_recalc(tc,n1); |
| 407 |
229 |
| tn_recalc(tc,n2); |
| 408 |
1007 |
▶ | TcFIXDEPTHABOVE(tc, xl); |
Branch: 5 branches
| Branch | True | False | Total |
| TcFIXDEPTHABOVE(tc, xl); |
750 |
28 |
778 |
| TcFIXDEPTHABOVE(tc, xl); |
667 |
83 |
750 |
| TcFIXDEPTHABOVE(tc, xl); |
83 |
28 |
111 |
| TcFIXDEPTHABOVE(tc, xl); |
28 |
0 |
28 |
| TcFIXDEPTHABOVE(tc, xl); |
778 |
229 |
1007 |
|
| 409 |
229 |
| return 1; |
| 410 |
|
| } |
| 411 |
|
| } |
| 412 |
1516 |
| return 0; |
| 413 |
|
| } |
| 414 |
|
| |
| 415 |
|
| static int |
| 416 |
1169 |
| tc_rotate2(XPVTC *tc, int xl, int looseness) |
| 417 |
|
| { |
| 418 |
1169 |
| int forced = looseness < 0; |
| 419 |
1169 |
| TCE *ce1 = TcCE(tc, xl); |
| 420 |
1169 |
| TCE *ce2 = TcCE(tc, xl+1); |
| 421 |
1169 |
| TCE *ce3 = TcCE(tc, xl+2); |
| 422 |
1169 |
▶ | TCE *ce4 = (xl+3 < TcFILL(tc)? TcCE(tc, xl+3) : 0); |
Branch: 1 branch
| Branch | True | False | Total |
| TCE *ce4 = (xl+3 < TcFILL(tc)? TcCE(tc, xl+3) : 0); |
839 |
330 |
1169 |
|
| 423 |
1169 |
| TN0 *n1 = CeTN(ce1); |
| 424 |
1169 |
| TN0 *n2 = CeTN(ce2); |
| 425 |
1169 |
| TN0 *n3 = CeTN(ce3); |
| 426 |
|
| int side1; |
| 427 |
|
| int side2; |
| 428 |
|
| assert(xl+2 < TcFILL(tc)); |
| 429 |
1169 |
▶ | if (CeRIGHT(ce1) && CeLEFT(ce2)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (CeRIGHT(ce1) && CeLEFT(ce2)) { |
670 |
499 |
1169 |
| if (CeRIGHT(ce1) && CeLEFT(ce2)) { |
238 |
432 |
670 |
|
| 430 |
238 |
| side1=0; |
| 431 |
238 |
| side2=1; |
| 432 |
931 |
▶ | } else if (CeLEFT(ce1) && CeRIGHT(ce2)) { |
Branch: 2 branches
| Branch | True | False | Total |
| } else if (CeLEFT(ce1) && CeRIGHT(ce2)) { |
499 |
432 |
931 |
| } else if (CeLEFT(ce1) && CeRIGHT(ce2)) { |
223 |
276 |
499 |
|
| 433 |
223 |
| side1=1; |
| 434 |
223 |
| side2=0; |
| 435 |
|
| } else { |
| 436 |
708 |
| return 0; |
| 437 |
|
| } |
| 438 |
|
| SCOPE { |
| 439 |
461 |
| TN0 *na = TnKID(n1,side1); |
| 440 |
461 |
| TN0 *nb = TnKID(n3,side1); |
| 441 |
461 |
| TN0 *nc = TnKID(n3,side2); |
| 442 |
461 |
▶ | if (forced || TnDEPTHx(na)+1 + looseness < TnDEPTH(n3)-1 /*OK*/) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (forced || TnDEPTHx(na)+1 + looseness < TnDEPTH(n3)-1 /*OK*/) { |
461 |
0 |
461 |
| if (forced || TnDEPTHx(na)+1 + looseness < TnDEPTH(n3)-1 /*OK*/) { |
391 |
70 |
461 |
| if (forced || TnDEPTHx(na)+1 + looseness < TnDEPTH(n3)-1 /*OK*/) { |
14 |
447 |
461 |
|
| 443 |
|
| int type; |
| 444 |
14 |
| TcRSTAT(tc, TCS_ROTATE2, 1); |
| 445 |
|
| /*tc_dump(tc); |
| 446 |
|
| warn("level=%d/%d ce4=%p", xl, TcFILL(tc), ce4? CeTN(ce4) : 0);/**/ |
| 447 |
14 |
▶ | if (!ce4) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ce4) { |
2 |
12 |
14 |
|
| 448 |
2 |
| type = 0; |
| 449 |
12 |
▶ | } else if (CeTN(ce4) == nc) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (CeTN(ce4) == nc) { |
3 |
9 |
12 |
|
| 450 |
3 |
| type = 1; |
| 451 |
|
| } else { |
| 452 |
|
| assert(CeTN(ce4) == nb); |
| 453 |
9 |
| type = 2; |
| 454 |
|
| } |
| 455 |
14 |
▶ | DEBUG_rotate(warn("rotate LR/RL type %d/%d at %d", side1, type, xl)); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_rotate(warn("rotate LR/RL type %d/%d at %d", side1, type, xl)); |
0 |
14 |
14 |
|
| 456 |
14 |
| TnKID_set(n3,side1, n1); |
| 457 |
14 |
| TnKID_set(n3,side2, n2); |
| 458 |
14 |
| TnKID_set(n1,side1, na); |
| 459 |
14 |
| TnKID_set(n1,side2, nb); |
| 460 |
14 |
| TnKID_set(n2,side1, nc); |
| 461 |
14 |
▶ | if (type == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (type == 0) { |
2 |
12 |
14 |
|
| 462 |
6 |
▶ | TcCUT(tc, xl); |
Branch: 1 branch
| Branch | True | False | Total |
| TcCUT(tc, xl); |
4 |
2 |
6 |
|
| 463 |
2 |
▶ | TcCUT(tc, xl+1); |
Branch: 1 branch
| Branch | True | False | Total |
| TcCUT(tc, xl+1); |
0 |
2 |
2 |
|
| 464 |
2 |
| tc_setnode(tc, xl, 1, n3); |
| 465 |
12 |
▶ | } else if (type == 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (type == 1) { |
3 |
9 |
12 |
|
| 466 |
11 |
▶ | TcCUT(tc, xl+2); |
Branch: 1 branch
| Branch | True | False | Total |
| TcCUT(tc, xl+2); |
8 |
3 |
11 |
|
| 467 |
3 |
| tc_setnode(tc, xl, 1, n3); |
| 468 |
3 |
| tc_setnode(tc, xl+1, 0, n2); |
| 469 |
3 |
| tc_setnode(tc, xl+2, 0, nc); |
| 470 |
9 |
▶ | } else if (type == 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (type == 2) { |
9 |
0 |
9 |
|
| 471 |
36 |
▶ | TcCUT(tc, xl+2); |
Branch: 1 branch
| Branch | True | False | Total |
| TcCUT(tc, xl+2); |
27 |
9 |
36 |
|
| 472 |
9 |
| tc_setnode(tc, xl, 1, n3); |
| 473 |
9 |
| tc_setnode(tc, xl+1, 0, n1); |
| 474 |
9 |
| tc_setnode(tc, xl+2, 0, nb); |
| 475 |
|
| } else |
| 476 |
0 |
| croak("assertion failed"); |
| 477 |
14 |
| tn_recalc(tc,n1); |
| 478 |
14 |
| tn_recalc(tc,n2); |
| 479 |
14 |
| tn_recalc(tc,n3); |
| 480 |
38 |
▶ | TcFIXDEPTHABOVE(tc, xl); |
Branch: 5 branches
| Branch | True | False | Total |
| TcFIXDEPTHABOVE(tc, xl); |
24 |
0 |
24 |
| TcFIXDEPTHABOVE(tc, xl); |
24 |
0 |
24 |
| TcFIXDEPTHABOVE(tc, xl); |
0 |
0 |
0 |
| TcFIXDEPTHABOVE(tc, xl); |
0 |
0 |
0 |
| TcFIXDEPTHABOVE(tc, xl); |
24 |
14 |
38 |
|
| 481 |
14 |
| return 1; |
| 482 |
|
| } |
| 483 |
|
| } |
| 484 |
447 |
| return 0; |
| 485 |
|
| } |
| 486 |
|
| |
| 487 |
|
| PRIVATE int |
| 488 |
407 |
| tc_rotate(XPVTC *tc, int looseness) |
| 489 |
|
| { |
| 490 |
407 |
| int rotations=0; |
| 491 |
|
| int xl; |
| 492 |
|
| assert(TcMATCH(tc)); |
| 493 |
407 |
▶ | if (TcFILL(tc) < 2) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc) < 2) return 0; |
9 |
398 |
407 |
|
| 494 |
|
| |
| 495 |
1567 |
▶ | for (xl=TcFILL(tc)-3; xl >= 0; xl--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (xl=TcFILL(tc)-3; xl >= 0; xl--) { |
1169 |
398 |
1567 |
|
| 496 |
1169 |
▶ | if (tc_rotate2(tc, xl, looseness)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (tc_rotate2(tc, xl, looseness)) { |
14 |
1155 |
1169 |
|
| 497 |
14 |
| ++rotations; |
| 498 |
14 |
▶ | if (xl+2 >= TcFILL(tc)) xl--; /* tc_rotate2 might fixup 2 levels */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (xl+2 >= TcFILL(tc)) xl--; /* tc_rotate2 might fixup 2 levels */ |
2 |
12 |
14 |
|
| 499 |
|
| } else { |
| 500 |
1155 |
| rotations += tc_rotate1(tc, xl, looseness); |
| 501 |
|
| } |
| 502 |
|
| } |
| 503 |
398 |
| xl = TcFILL(tc)-2; |
| 504 |
398 |
▶ | if (xl >= 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (xl >= 0) { |
398 |
0 |
398 |
|
| 505 |
398 |
| rotations += tc_rotate1(tc, xl, looseness); |
| 506 |
|
| } |
| 507 |
398 |
| return rotations; |
| 508 |
|
| } |
| 509 |
|
| |
| 510 |
|
| PRIVATE int |
| 511 |
138 |
| tc_freetn(XPVTC *tc, XPVTV *tv, TN0 *tn, void(*dtor)(TN0*)) |
| 512 |
|
| { |
| 513 |
138 |
| int stepnext=0; |
| 514 |
138 |
▶ | int left = TnDEPTHx(TnLEFT(tn)); |
Branch: 1 branch
| Branch | True | False | Total |
| int left = TnDEPTHx(TnLEFT(tn)); |
64 |
74 |
138 |
|
| 515 |
138 |
▶ | int right = TnDEPTHx(TnRIGHT(tn)); |
Branch: 1 branch
| Branch | True | False | Total |
| int right = TnDEPTHx(TnRIGHT(tn)); |
64 |
74 |
138 |
|
| 516 |
|
| assert(TvVERSION(tv) == TcVERSION(tc)); |
| 517 |
|
| assert(TnEMPTY(tn)); |
| 518 |
330 |
▶ | while (left || right) { |
Branch: 2 branches
| Branch | True | False | Total |
| while (left || right) { |
151 |
179 |
330 |
| while (left || right) { |
41 |
138 |
179 |
|
| 519 |
192 |
▶ | if (left > right) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (left > right) { |
91 |
101 |
192 |
|
| 520 |
91 |
| CeLEFT_on(TcCEx(tc)); |
| 521 |
91 |
▶ | TcPUSH(tc, TnLEFT(tn)); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, TnLEFT(tn)); |
0 |
91 |
91 |
|
| 522 |
91 |
| tc_rotate1(tc, TcFILL(tc) - 2, -1); |
| 523 |
91 |
| CeRIGHT_on(TcCEx(tc)); |
| 524 |
91 |
▶ | TcPUSH(tc, TnRIGHT(TcTNx(tc))); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, TnRIGHT(TcTNx(tc))); |
0 |
91 |
91 |
|
| 525 |
|
| } else { |
| 526 |
101 |
| CeRIGHT_on(TcCEx(tc)); |
| 527 |
101 |
▶ | TcPUSH(tc, TnRIGHT(tn)); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, TnRIGHT(tn)); |
0 |
101 |
101 |
|
| 528 |
101 |
| tc_rotate1(tc, TcFILL(tc) - 2, -1); |
| 529 |
101 |
| CeLEFT_on(TcCEx(tc)); |
| 530 |
101 |
▶ | TcPUSH(tc, TnLEFT(TcTNx(tc))); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, TnLEFT(TcTNx(tc))); |
0 |
101 |
101 |
|
| 531 |
|
| } |
| 532 |
|
| assert(TcTNx(tc) == tn); |
| 533 |
192 |
▶ | left = TnDEPTHx(TnLEFT(tn)); |
Branch: 1 branch
| Branch | True | False | Total |
| left = TnDEPTHx(TnLEFT(tn)); |
87 |
105 |
192 |
|
| 534 |
192 |
▶ | right = TnDEPTHx(TnRIGHT(tn)); |
Branch: 1 branch
| Branch | True | False | Total |
| right = TnDEPTHx(TnRIGHT(tn)); |
68 |
124 |
192 |
|
| 535 |
|
| } |
| 536 |
138 |
| TcPOP(tc); |
| 537 |
138 |
▶ | if (TcFILL(tc)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc)) { |
134 |
4 |
138 |
|
| 538 |
134 |
| TCE *ce = TcCEx(tc); |
| 539 |
134 |
| TN0 *mom = CeTN(ce); |
| 540 |
134 |
▶ | if (TnLEFT(mom) == tn) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TnLEFT(mom) == tn) { |
63 |
71 |
134 |
|
| 541 |
63 |
| (*dtor)(tn); |
| 542 |
63 |
| FREE_TN(tn); |
| 543 |
63 |
| TnLEFT_set(mom,0); |
| 544 |
63 |
| TcSLOT(tc) = 0; |
| 545 |
|
| } else { |
| 546 |
|
| assert(tn == TnRIGHT(mom)); |
| 547 |
71 |
| (*dtor)(tn); |
| 548 |
71 |
| FREE_TN(tn); |
| 549 |
71 |
| TnRIGHT_set(mom,0); |
| 550 |
71 |
| TcSLOT(tc) = TnFILL(mom)-1; |
| 551 |
71 |
| ++stepnext; |
| 552 |
|
| } |
| 553 |
134 |
| tn_recalc(tc,mom); |
| 554 |
671 |
▶ | TcFIXDEPTHABOVE(tc, TcFILL(tc)-1); |
Branch: 5 branches
| Branch | True | False | Total |
| TcFIXDEPTHABOVE(tc, TcFILL(tc)-1); |
518 |
19 |
537 |
| TcFIXDEPTHABOVE(tc, TcFILL(tc)-1); |
458 |
60 |
518 |
| TcFIXDEPTHABOVE(tc, TcFILL(tc)-1); |
60 |
19 |
79 |
| TcFIXDEPTHABOVE(tc, TcFILL(tc)-1); |
19 |
0 |
19 |
| TcFIXDEPTHABOVE(tc, TcFILL(tc)-1); |
537 |
134 |
671 |
|
| 555 |
|
| } else { |
| 556 |
|
| assert(TvROOT(tv) == tn); |
| 557 |
4 |
| (*dtor)(tn); |
| 558 |
4 |
| FREE_TN(tn); |
| 559 |
4 |
| TvROOT_set(tv,0); |
| 560 |
4 |
| --TcPOS(tc); |
| 561 |
4 |
| TcMATCH_off(tc); |
| 562 |
4 |
| TcSTART_on(tc); |
| 563 |
|
| } |
| 564 |
138 |
| TvMAX(tv) -= 1; |
| 565 |
138 |
| return stepnext; |
| 566 |
|
| } |
| 567 |
|
| |
| 568 |
|
| PRIVATE void |
| 569 |
2 |
| tv_recalc(XPVTV *tv) |
| 570 |
|
| { |
| 571 |
2 |
| TN0 *top = TvROOT(tv); |
| 572 |
|
| assert(top); |
| 573 |
2 |
| tn_recalc_r(top); |
| 574 |
2 |
| } |
| 575 |
|
| |
| 576 |
|
| int |
| 577 |
2 |
| tv_balance(XPVTC *tc, int looseness) |
| 578 |
|
| { |
| 579 |
|
| int rot; |
| 580 |
2 |
| int total=0; |
| 581 |
|
| XPVTV *tv; |
| 582 |
2 |
| tv=TcTV(tc); |
| 583 |
2 |
| tc_moveto(tc,0); |
| 584 |
2 |
| TcPOS(tc) = -2; |
| 585 |
|
| do { |
| 586 |
110 |
| rot = tc_rotate(tc, looseness); |
| 587 |
110 |
| total += rot; |
| 588 |
110 |
▶ | } while (tc_stepnode(tc,1)); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (tc_stepnode(tc,1)); |
108 |
2 |
110 |
|
| 589 |
2 |
| ++TvVERSION(tv); |
| 590 |
2 |
| return total; |
| 591 |
|
| } |
| 592 |
|
| |
| 593 |
|
| void |
| 594 |
6407 |
| tc_moveto(XPVTC *tc, I32 xto) |
| 595 |
|
| { |
| 596 |
|
| XPVTV *tv; |
| 597 |
|
| TCE *ce; |
| 598 |
|
| TN0 *tn, *down; |
| 599 |
|
| register int cur; |
| 600 |
|
| register int tree; |
| 601 |
|
| |
| 602 |
|
| assert(tc); |
| 603 |
6407 |
| tv=TcTV(tc); |
| 604 |
6407 |
▶ | if (TvFILL(tv) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (TvFILL(tv) == 0) { |
6401 |
6 |
6407 |
| if (TvFILL(tv) == 0) { |
0 |
6401 |
6401 |
|
| 605 |
6 |
| tc_reset(tc); |
| 606 |
6 |
| return; |
| 607 |
|
| } |
| 608 |
6401 |
▶ | if (xto <= -1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (xto <= -1) { |
1488 |
4913 |
6401 |
|
| 609 |
1488 |
| xto = -1; |
| 610 |
1488 |
| TcPOS(tc)=-1; |
| 611 |
4913 |
▶ | } else if (xto >= TvFILL(tv)) { |
Branch: 2 branches
| Branch | True | False | Total |
| } else if (xto >= TvFILL(tv)) { |
4913 |
0 |
4913 |
| } else if (xto >= TvFILL(tv)) { |
4743 |
170 |
4913 |
|
| 612 |
4743 |
▶ | xto = TvFILL(tv); |
Branch: 1 branch
| Branch | True | False | Total |
| xto = TvFILL(tv); |
4743 |
0 |
4743 |
|
| 613 |
4743 |
| TcPOS(tc)=xto-1; |
| 614 |
|
| } else { |
| 615 |
170 |
| TcPOS(tc)=xto; |
| 616 |
|
| } |
| 617 |
6401 |
| TcMATCH_off(tc); |
| 618 |
6401 |
| TcSTARTEND_off(tc); |
| 619 |
6401 |
| TcFORWARD_on(tc); |
| 620 |
6401 |
| TcVERSION(tc) = TvVERSION(tv); |
| 621 |
6401 |
| TcFILL(tc) = 0; |
| 622 |
6401 |
▶ | TcPUSH(tc, TvROOT(tv)); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, TvROOT(tv)); |
0 |
6401 |
6401 |
|
| 623 |
6401 |
| cur=0; |
| 624 |
|
| |
| 625 |
|
| /* right to left might be faster when xto > TvFILL(tv)/2 XXX */ |
| 626 |
804 |
| DOWN: |
| 627 |
7205 |
| ce = TcCEx(tc); |
| 628 |
7205 |
| tn = CeTN(ce); |
| 629 |
7205 |
| tree=0; |
| 630 |
7205 |
▶ | if (down = TnLEFT(CeTN(ce))) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (down = TnLEFT(CeTN(ce))) { |
424 |
6781 |
7205 |
|
| 631 |
424 |
| tree = TnTREEFILL(down); |
| 632 |
|
| } |
| 633 |
7205 |
▶ | if (xto < cur + tree) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (xto < cur + tree) { |
1688 |
5517 |
7205 |
|
| 634 |
1688 |
| CeLEFT_on(ce); |
| 635 |
1688 |
▶ | if (down) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (down) { |
200 |
1488 |
1688 |
|
| 636 |
200 |
▶ | TcPUSH(tc, down); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, down); |
0 |
200 |
200 |
|
| 637 |
200 |
| goto DOWN; |
| 638 |
|
| } else { |
| 639 |
1488 |
| CeLEFT_off(ce); |
| 640 |
1488 |
| TcSLOT(tc) = -1; |
| 641 |
1488 |
| return; /* no match at the left most */ |
| 642 |
|
| } |
| 643 |
|
| } |
| 644 |
5517 |
| cur += tree; |
| 645 |
5517 |
▶ | if (xto >= cur && xto < cur+TnFILL(tn)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (xto >= cur && xto < cur+TnFILL(tn)) { |
5517 |
0 |
5517 |
| if (xto >= cur && xto < cur+TnFILL(tn)) { |
170 |
5347 |
5517 |
|
| 646 |
170 |
| TcSLOT(tc) = xto - cur; |
| 647 |
170 |
| CeLEFT_on(ce); |
| 648 |
170 |
| TcMATCH_on(tc); |
| 649 |
170 |
| return; |
| 650 |
|
| } |
| 651 |
5347 |
| cur += TnFILL(tn); |
| 652 |
5347 |
| CeRIGHT_on(ce); |
| 653 |
5347 |
▶ | if (down = TnRIGHT(CeTN(ce))) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (down = TnRIGHT(CeTN(ce))) { |
604 |
4743 |
5347 |
|
| 654 |
604 |
| tree = TnTREEFILL(down); |
| 655 |
|
| assert(xto <= cur + tree); |
| 656 |
604 |
▶ | TcPUSH(tc, down); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPUSH(tc, down); |
0 |
604 |
604 |
|
| 657 |
604 |
| goto DOWN; |
| 658 |
|
| } |
| 659 |
4743 |
| TcSLOT(tc) = TnFILL(tn)-1; |
| 660 |
|
| /* no match at the right most */ |
| 661 |
|
| } |
| 662 |
|
| |
| 663 |
|
| int |
| 664 |
38963 |
| tc_step(XPVTC *tc, I32 delta) |
| 665 |
|
| { |
| 666 |
|
| XPVTV *tv; |
| 667 |
|
| assert(tc); |
| 668 |
38963 |
| tv=TcTV(tc); |
| 669 |
38963 |
▶ | TcSYNCCHECK(tc,tv); |
Branch: 1 branch
| Branch | True | False | Total |
| TcSYNCCHECK(tc,tv); |
0 |
38963 |
38963 |
|
| 670 |
38963 |
▶ | if (delta==0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (delta==0) { |
2 |
38961 |
38963 |
|
| 671 |
2 |
| TV_PANIC("TV: cannot step by zero elements"); |
| 672 |
|
| } |
| 673 |
38961 |
▶ | DEBUG_step(warn("step %d", delta)); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("step %d", delta)); |
0 |
38961 |
38961 |
|
| 674 |
|
| /* pre-flight check */ |
| 675 |
38961 |
▶ | if (TcFILL(tc)==0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc)==0) { |
154 |
38807 |
38961 |
|
| 676 |
|
| TN0 *tn; |
| 677 |
154 |
▶ | int dir = delta < 0 ? -1 : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| int dir = delta < 0 ? -1 : 1; |
76 |
78 |
154 |
|
| 678 |
154 |
▶ | if (!tc_stepnode(tc, dir)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tc_stepnode(tc, dir)) { |
26 |
128 |
154 |
|
| 679 |
26 |
| return 0; |
| 680 |
|
| } |
| 681 |
128 |
| tn = TcTNx(tc); |
| 682 |
128 |
▶ | TcSLOT(tc) = delta > 0 ? 0 : TnFILL(tn)-1; |
Branch: 1 branch
| Branch | True | False | Total |
| TcSLOT(tc) = delta > 0 ? 0 : TnFILL(tn)-1; |
64 |
64 |
128 |
|
| 683 |
128 |
| TcPOS(tc) += delta; |
| 684 |
128 |
| delta -= dir; |
| 685 |
|
| } else { |
| 686 |
38807 |
▶ | if (!TcMATCH(tc)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!TcMATCH(tc)) { |
16786 |
22021 |
38807 |
|
| 687 |
16786 |
▶ | if (delta < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (delta < 0) { |
1396 |
15390 |
16786 |
|
| 688 |
1396 |
| TCE *ce = TcCEx(tc); |
| 689 |
1396 |
▶ | if (TcSLOT(tc) == -1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcSLOT(tc) == -1) { |
46 |
1350 |
1396 |
|
| 690 |
46 |
| ++TcSLOT(tc); |
| 691 |
46 |
| ++TcPOS(tc); |
| 692 |
46 |
▶ | DEBUG_step(warn("no match at slot=-1")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("no match at slot=-1")); |
0 |
46 |
46 |
|
| 693 |
|
| } else { |
| 694 |
1350 |
| ++delta; |
| 695 |
1350 |
▶ | DEBUG_step(warn("no match")); |
Branch: 1 branch
| Branch | True | False | Total |
| DEBUG_step(warn("no match")); |
0 |
1350 |
1350 |
|
| 696 |
|
| } |
| 697 |
|
| } |
| 698 |
16786 |
▶ | TcFLOW(tc); |
Branch: 1 branch
| Branch | True | False | Total |
| TcFLOW(tc); |
16786 |
0 |
16786 |
|
| 699 |
|
| } |
| 700 |
38807 |
| TcPOS(tc) += delta; |
| 701 |
|
| } |
| 702 |
38935 |
| TcSTARTEND_off(tc); |
| 703 |
38935 |
| TcMATCH_on(tc); |
| 704 |
38935 |
▶ | if (delta > 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (delta > 0) { |
33023 |
5912 |
38935 |
|
| 705 |
33023 |
| TN0 *tn = TcTNx(tc); |
| 706 |
33023 |
▶ | TcGOFWD(tc); |
Branch: 3 branches
| Branch | True | False | Total |
| TcGOFWD(tc); |
50 |
32973 |
33023 |
| TcGOFWD(tc); |
0 |
50 |
50 |
| TcGOFWD(tc); |
50 |
0 |
50 |
|
| 707 |
33023 |
▶ | if (TcSLOT(tc) + delta < TnFILL(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcSLOT(tc) + delta < TnFILL(tn)) { |
25875 |
7148 |
33023 |
|
| 708 |
25875 |
| TcSLOT(tc) += delta; |
| 709 |
|
| } else { |
| 710 |
7148 |
| delta -= TnFILL(tn)-1 - TcSLOT(tc); |
| 711 |
7148 |
| --delta; |
| 712 |
7148 |
▶ | if (!tc_stepnode(tc, 1)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tc_stepnode(tc, 1)) { |
6255 |
893 |
7148 |
|
| 713 |
6255 |
| goto DONE; |
| 714 |
|
| } |
| 715 |
|
| assert(TcFILL(tc) > 0); |
| 716 |
893 |
| tn = TcTNx(tc); |
| 717 |
935 |
▶ | while (delta >= TnFILL(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (delta >= TnFILL(tn)) { |
42 |
893 |
935 |
|
| 718 |
42 |
| delta -= TnFILL(tn); |
| 719 |
42 |
▶ | if (!tc_stepnode(tc, 1)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tc_stepnode(tc, 1)) { |
0 |
42 |
42 |
|
| 720 |
0 |
| goto DONE; |
| 721 |
|
| } |
| 722 |
|
| assert(TcFILL(tc) > 0); |
| 723 |
42 |
| tn = TcTNx(tc); |
| 724 |
|
| } |
| 725 |
893 |
| TcSLOT(tc) = delta; |
| 726 |
|
| } |
| 727 |
5912 |
▶ | } else if (delta < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (delta < 0) { |
1440 |
4472 |
5912 |
|
| 728 |
4472 |
| TN0 *tn = TcTNx(tc); |
| 729 |
4472 |
▶ | TcGOBWD(tc); |
Branch: 3 branches
| Branch | True | False | Total |
| TcGOBWD(tc); |
150 |
4322 |
4472 |
| TcGOBWD(tc); |
0 |
150 |
150 |
| TcGOBWD(tc); |
150 |
0 |
150 |
|
| 730 |
4472 |
▶ | if (TcSLOT(tc) + delta >= 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcSLOT(tc) + delta >= 0) { |
3877 |
595 |
4472 |
|
| 731 |
3877 |
| TcSLOT(tc) += delta; |
| 732 |
|
| } else { |
| 733 |
595 |
| delta += TcSLOT(tc); |
| 734 |
595 |
| ++delta; |
| 735 |
595 |
▶ | if (!tc_stepnode(tc, -1)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tc_stepnode(tc, -1)) { |
109 |
486 |
595 |
|
| 736 |
109 |
| goto DONE; |
| 737 |
|
| } |
| 738 |
|
| assert(TcFILL(tc) > 0); |
| 739 |
486 |
| tn = TcTNx(tc); |
| 740 |
536 |
▶ | while (-delta >= TnFILL(tn)) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (-delta >= TnFILL(tn)) { |
52 |
484 |
536 |
|
| 741 |
52 |
| delta += TnFILL(tn); |
| 742 |
52 |
▶ | if (!tc_stepnode(tc, -1)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!tc_stepnode(tc, -1)) { |
2 |
50 |
52 |
|
| 743 |
2 |
| goto DONE; |
| 744 |
|
| } |
| 745 |
|
| assert(TcFILL(tc) > 0); |
| 746 |
50 |
| tn = TcTNx(tc); |
| 747 |
|
| } |
| 748 |
484 |
| TcSLOT(tc) = TnFILL(tn)-1 +delta; |
| 749 |
|
| } |
| 750 |
|
| } |
| 751 |
1440 |
| DONE: |
| 752 |
38935 |
▶ | if (TcFILL(tc) == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFILL(tc) == 0) { |
6366 |
32569 |
38935 |
|
| 753 |
6366 |
| TcMATCH_off(tc); |
| 754 |
6366 |
▶ | if (TcFORWARD(tc)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (TcFORWARD(tc)) { |
6255 |
111 |
6366 |
|
| 755 |
6255 |
▶ | TcPOS(tc) = TvFILL(tv); |
Branch: 1 branch
| Branch | True | False | Total |
| TcPOS(tc) = TvFILL(tv); |
6255 |
0 |
6255 |
|
| 756 |
6255 |
| TcEND_on(tc); |
| 757 |
|
| } else { |
| 758 |
111 |
| TcPOS(tc) = -1; |
| 759 |
111 |
| TcSTART_on(tc); |
| 760 |
|
| } |
| 761 |
6366 |
| return 0; |
| 762 |
|
| } else { |
| 763 |
32569 |
| TcMATCH_on(tc); |
| 764 |
32569 |
| return 1; |
| 765 |
|
| } |
| 766 |
|
| } |
| 767 |
|
| |
| 768 |
|
| /* CCOV: off */ |
| 769 |
|
| |
| 770 |
|
| /* avoid surprises with built-in memory copying |
| 771 |
|
| optimize XXX |
| 772 |
|
| PRIVATE void |
| 773 |
|
| tv_memmove(void *dst, void *src, int len) |
| 774 |
|
| { |
| 775 |
|
| unsigned long dstp = (long) dst; |
| 776 |
|
| unsigned long srcp = (long) src; |
| 777 |
|
| |
| 778 |
|
| if (dstp - srcp >= len) { |
| 779 |
|
| int xx; |
| 780 |
|
| for (xx=0; xx < len; xx++) { |
| 781 |
|
| ((char*)dst)[xx] = ((char*)src)[xx]; |
| 782 |
|
| } |
| 783 |
|
| } else { |
| 784 |
|
| int xx; |
| 785 |
|
| for (xx=len-1; xx >= 0; xx--) { |
| 786 |
|
| ((char*)dst)[xx] = ((char*)src)[xx]; |
| 787 |
|
| } |
| 788 |
|
| } |
| 789 |
|
| } |
| 790 |
|
| /**/ |
| 791 |
|
| |
| 792 |
|
| #ifdef TV_STATS |
| 793 |
|
| |
| 794 |
|
| char * |
| 795 |
0 |
| tc_getstat(XPVTC *tc, int xx, I32 *val) |
| 796 |
|
| { |
| 797 |
|
| assert(val); |
| 798 |
0 |
| switch (xx) { |
| 799 |
0 |
| case TCS_ROTATE1: *val = TcSTAT(tc, xx); return "rotate1"; |
| 800 |
0 |
| case TCS_ROTATE2: *val = TcSTAT(tc, xx); return "rotate2"; |
| 801 |
0 |
| case TCS_COPYSLOT: *val = TcSTAT(tc, xx); return "copyslot"; |
| 802 |
0 |
| case TCS_STEPNODE: *val = TcSTAT(tc, xx); return "stepnode"; |
| 803 |
0 |
| case TCS_INSERT: *val = TcSTAT(tc, xx); return "insert"; |
| 804 |
0 |
| case TCS_DELETE: *val = TcSTAT(tc, xx); return "delete"; |
| 805 |
0 |
| case TCS_KEYCMP: *val = TcSTAT(tc, xx); return "keycmp"; |
| 806 |
0 |
| case TCS_DEPTHCALC: *val = TcSTAT(tc, xx); return "depthcalc"; |
| 807 |
0 |
| case TCS_TNRECALC: *val = TcSTAT(tc, xx); return "tn_recalc"; |
| 808 |
0 |
| default: return 0; |
| 809 |
|
| } |
| 810 |
|
| } |
| 811 |
|
| |
| 812 |
|
| #endif |
| 813 |
|
| |
| 814 |
|
| |
| 815 |
|
| |
| 816 |
|
| |
| 817 |
|
| |
| 818 |
|
| |
| 819 |
|
| /* |
| 820 |
|
| Copyright © 1997-1999 Joshua Nathaniel Pritikin. All rights reserved. |
| 821 |
|
| |
| 822 |
|
| This package is free software and is provided "as is" without express |
| 823 |
|
| or implied warranty. It may be used, redistributed and/or modified |
| 824 |
|
| under the terms of the Perl Artistic License (see |
| 825 |
|
| http://www.perl.com/perl/misc/Artistic.html) |
| 826 |
|
| */ |