1 /*
2 * Copyright (c) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
3 * 2002, 2003, 2004
4 * Ohio University.
5 *
6 * ---
7 *
8 * Starting with the release of tcptrace version 6 in 2001, tcptrace
9 * is licensed under the GNU General Public License (GPL). We believe
10 * that, among the available licenses, the GPL will do the best job of
11 * allowing tcptrace to continue to be a valuable, freely-available
12 * and well-maintained tool for the networking community.
13 *
14 * Previous versions of tcptrace were released under a license that
15 * was much less restrictive with respect to how tcptrace could be
16 * used in commercial products. Because of this, I am willing to
17 * consider alternate license arrangements as allowed in Section 10 of
18 * the GNU GPL. Before I would consider licensing tcptrace under an
19 * alternate agreement with a particular individual or company,
20 * however, I would have to be convinced that such an alternative
21 * would be to the greater benefit of the networking community.
22 *
23 * ---
24 *
25 * This file is part of Tcptrace.
26 *
27 * Tcptrace was originally written and continues to be maintained by
28 * Shawn Ostermann with the help of a group of devoted students and
29 * users (see the file 'THANKS'). The work on tcptrace has been made
30 * possible over the years through the generous support of NASA GRC,
31 * the National Science Foundation, and Sun Microsystems.
32 *
33 * Tcptrace is free software; you can redistribute it and/or modify it
34 * under the terms of the GNU General Public License as published by
35 * the Free Software Foundation; either version 2 of the License, or
36 * (at your option) any later version.
37 *
38 * Tcptrace is distributed in the hope that it will be useful, but
39 * WITHOUT ANY WARRANTY; without even the implied warranty of
40 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
41 * General Public License for more details.
42 *
43 * You should have received a copy of the GNU General Public License
44 * along with Tcptrace (in the file 'COPYING'); if not, write to the
45 * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
46 * MA 02111-1307 USA
47 *
48 * Author: Ramani Yellapragada
49 * School of Electrical Engineering and Computer Science
50 * Ohio University
51 * Athens, OH
52 * http://www.tcptrace.org/
53 */
54
55 #include "tcptrace.h"
56 static char const GCC_UNUSED copyright[] =
57 "@(#)Copyright (c) 2004 -- Ohio University.\n";
58 static char const GCC_UNUSED rcsid[] =
59 "@(#)$Header$";
60
61
62 /* Local routines for handling AVL tree balancing after inserting a node */
63
64 static void SnapRotLeft(ptp_snap **n);
65 static void SnapRotRight(ptp_snap **n);
66 static enum AVLRES SnapLeftGrown(ptp_snap **n);
67 static enum AVLRES SnapRightGrown(ptp_snap **n);
68
69 /* Local routines for handling AVL tree balancing after removing a node */
70
71 static enum AVLRES SnapLeftShrunk(ptp_snap **n);
72 static enum AVLRES SnapRightShrunk(ptp_snap **n);
73 static int SnapFindHighest(ptp_snap *target, ptp_snap **n, enum AVLRES *res);
74 static int SnapFindLowest(ptp_snap *target, ptp_snap **n, enum AVLRES *res);
75
76 /*
77 * SnapRotLeft - perform counter clockwise rotation
78 */
79
80 static void
SnapRotLeft(ptp_snap ** n)81 SnapRotLeft(
82 ptp_snap **n)
83 {
84 ptp_snap *tmp = *n;
85
86 if (debug > 4)
87 printf("SnapRotLeft(): Rotating the AVL tree counter clockwise\n");
88
89 *n = (*n)->right;
90 tmp->right = (*n)->left;
91 (*n)->left = tmp;
92 }
93
94 /*
95 * SnapRotRight - perform clockwise rotation
96 */
97
98 static void
SnapRotRight(ptp_snap ** n)99 SnapRotRight(
100 ptp_snap **n)
101 {
102 ptp_snap *tmp = *n;
103
104 if (debug > 4)
105 printf("SnapRotRight(): Rotating the AVL tree clockwise\n");
106
107 *n = (*n)->left;
108 tmp->left = (*n)->right;
109 (*n)->right = tmp;
110 }
111
112 /* SnapLeftGrown - For balancing an AVL tree after insertion
113 * Input is the address of a node. The node's left subtree has grown
114 * due to insertion.
115 */
116
117 static enum AVLRES
SnapLeftGrown(ptp_snap ** n)118 SnapLeftGrown(
119 ptp_snap **n)
120 {
121 if (debug > 4)
122 printf("SnapLeftGrown(): Balancing the AVL tree because left subtree\
123 has grown after insertion\n");
124
125 switch ((*n)->skew) {
126 case LEFT:
127 if ((*n)->left->skew == LEFT) {
128 (*n)->skew = (*n)->left->skew = EQUAL1;
129 SnapRotRight(n);
130 }
131 else {
132 switch ((*n)->left->right->skew) {
133 case LEFT:
134 (*n)->skew = RIGHT;
135 (*n)->left->skew = EQUAL1;
136 break;
137 case RIGHT:
138 (*n)->skew = EQUAL1;
139 (*n)->left->skew = LEFT;
140 break;
141 default:
142 (*n)->skew = EQUAL1;
143 (*n)->left->skew = EQUAL1;
144 }
145
146 (*n)->left->right->skew = EQUAL1;
147 SnapRotLeft(&(*n)->left);
148 SnapRotRight(n);
149 }
150 return OK;
151
152 case RIGHT:
153 (*n)->skew = EQUAL1;
154 return OK;
155
156 default:
157 (*n)->skew = LEFT;
158 return BALANCE;
159 }
160 }
161
162 /* SnapRightGrown - For balancing an AVL tree after insertion
163 * Input is the address of a node. The node's right subtree has grown
164 * due to insertion.
165 */
166
167 static enum AVLRES
SnapRightGrown(ptp_snap ** n)168 SnapRightGrown(
169 ptp_snap **n)
170 {
171 if (debug > 4)
172 printf("SnapRightGrown(): Balancing the AVL tree because right subtree\
173 has grown after insertion\n");
174
175 switch ((*n)->skew) {
176 case LEFT:
177 (*n)->skew = EQUAL1;
178 return OK;
179
180 case RIGHT:
181 if ((*n)->right->skew == RIGHT) {
182 (*n)->skew = (*n)->right->skew = EQUAL1;
183 SnapRotLeft(n);
184 }
185 else {
186 switch ((*n)->right->left->skew) {
187 case RIGHT:
188 (*n)->skew = LEFT;
189 (*n)->right->skew = EQUAL1;
190 break;
191
192 case LEFT:
193 (*n)->skew = EQUAL1;
194 (*n)->right->skew = RIGHT;
195 break;
196
197 default:
198 (*n)->skew = EQUAL1;
199 (*n)->right->skew = EQUAL1;
200 }
201
202 (*n)->right->left->skew = EQUAL1;
203 SnapRotRight(&(*n)->right);
204 SnapRotLeft(n);
205 }
206 return OK;
207
208 default:
209 (*n)->skew = RIGHT;
210 return BALANCE;
211 }
212 }
213
214 /*
215 * SnapInsert - insert a node into the AVL tree
216 * and balance the AVL tree
217 */
218
219 enum AVLRES
SnapInsert(ptp_snap ** root,ptp_snap * new_node)220 SnapInsert(
221 ptp_snap **root,
222 ptp_snap *new_node)
223 {
224 enum AVLRES tmp;
225
226 if (debug > 4)
227 printf("SnapInsert(): Inserting a node in the AVL tree\n");
228
229 if (!(*root)) {
230 *root = new_node;
231 (*root)->left = (*root)->right = NULL;
232 (*root)->skew = EQUAL1;
233 return BALANCE;
234 }
235
236 else if (AVL_WhichDir(&new_node->addr_pair, &((*root)->addr_pair)) == LT) {
237 if ((tmp = SnapInsert(&(*root)->left, new_node)) == BALANCE) {
238 return SnapLeftGrown(root);
239 }
240 return tmp;
241 }
242
243 else if (AVL_WhichDir(&new_node->addr_pair, &((*root)->addr_pair)) == RT) {
244 if ((tmp = SnapInsert(&(*root)->right, new_node)) == BALANCE) {
245 return SnapRightGrown(root);
246 }
247 return tmp;
248 }
249 return 0;
250 }
251
252 /*
253 * SnapLeftShrunk - For balancing an AVL tree after removing a node
254 * Input is the address of a node. The node's left subtree has shrunk
255 * due to removal and might have made the tree unbalanced.
256 */
257
258 static enum AVLRES
SnapLeftShrunk(ptp_snap ** n)259 SnapLeftShrunk(
260 ptp_snap **n)
261 {
262 if (debug > 4)
263 printf("SnapLeftshrunk(): Balancing the AVL tree because left subtree\
264 has shrunk after removal\n");
265
266 switch ((*n)->skew) {
267 case LEFT:
268 (*n)->skew = EQUAL1;
269 return BALANCE;
270
271 case RIGHT:
272 if ((*n)->right->skew == RIGHT) {
273 (*n)->skew = (*n)->right->skew = EQUAL1;
274 SnapRotLeft(n);
275 return BALANCE;
276 }
277
278 else if ((*n)->right->skew == EQUAL1) {
279 (*n)->skew = RIGHT;
280 (*n)->right->skew = LEFT;
281 SnapRotLeft(n);
282 return OK;
283 }
284
285 else {
286 switch ((*n)->right->left->skew) {
287 case LEFT:
288 (*n)->skew = EQUAL1;
289 (*n)->right->skew = RIGHT;
290 break;
291
292 case RIGHT:
293 (*n)->skew = LEFT;
294 (*n)->right->skew = EQUAL1;
295 break;
296
297 default:
298 (*n)->skew = EQUAL1;
299 (*n)->right->skew = EQUAL1;
300 }
301
302 (*n)->right->left->skew = EQUAL1;
303 SnapRotRight(& (*n)->right);
304 SnapRotLeft(n);
305 return BALANCE;
306 }
307
308 default:
309 (*n)->skew = RIGHT;
310 return OK;
311 }
312 }
313
314 /*
315 * SnapRightShrunk - For balancing an AVL tree after removing a node
316 * Input is the address of a node. The node's right subtree has shrunk
317 * due to removal and might have made the tree unbalanced.
318 */
319
320 static enum AVLRES
SnapRightShrunk(ptp_snap ** n)321 SnapRightShrunk(
322 ptp_snap **n)
323 {
324 if (debug > 4)
325 printf("SnapRightShrunk(): Balancing the AVL tree because right subtree\
326 has shrunk after removal\n");
327
328 switch ((*n)->skew) {
329 case RIGHT:
330 (*n)->skew = EQUAL1;
331 return BALANCE;
332
333 case LEFT:
334 if ((*n)->left->skew == LEFT) {
335 (*n)->skew = (*n)->left->skew = EQUAL1;
336 SnapRotRight(n);
337 return BALANCE;
338 }
339 else if ((*n)->left->skew == EQUAL1) {
340 (*n)->skew = LEFT;
341 (*n)->left->skew = RIGHT;
342 SnapRotRight(n);
343 return OK;
344 }
345
346 else {
347 switch ((*n)->left->right->skew) {
348 case LEFT:
349 (*n)->skew = RIGHT;
350 (*n)->left->skew = EQUAL1;
351 break;
352
353 case RIGHT:
354 (*n)->skew = EQUAL1;
355 (*n)->left->skew = LEFT;
356 break;
357
358 default:
359 (*n)->skew = EQUAL1;
360 (*n)->left->skew = EQUAL1;
361 }
362
363 (*n)->left->right->skew = EQUAL1;
364 SnapRotLeft(& (*n)->left);
365 SnapRotRight(n);
366 return BALANCE;
367 }
368
369 default:
370 (*n)->skew = LEFT;
371 return OK;
372 }
373 }
374
375 /*
376 * SnapFindHighest - replace a node with a subtree's highest-ranking item
377 */
378
379 static int
SnapFindHighest(ptp_snap * target,ptp_snap ** n,enum AVLRES * res)380 SnapFindHighest(
381 ptp_snap *target,
382 ptp_snap **n,
383 enum AVLRES *res)
384 {
385 ptp_snap *tmp;
386
387 if (debug > 4)
388 printf("SnapFindHighest(): Replacing a node with a subtree's\
389 highest ranking item \n");
390
391 *res = BALANCE;
392 if (! (*n)) {
393 return 0;
394 }
395
396 if ((*n)->right) {
397 if (!SnapFindHighest(target, & (*n)->right, res)) {
398 return 0;
399 }
400
401 if (*res == BALANCE) {
402 *res = SnapRightShrunk(n);
403 }
404
405 return 1;
406 }
407
408 target->addr_pair = (*n)->addr_pair;
409 target->ptp = (*n)->ptp;
410 tmp = *n;
411 (*n) = (*n)->left;
412 return 1;
413 }
414
415 /*
416 * SnapFindLowest - replace a node with a subtree's lowest-ranking item
417 */
418
419 static int
SnapFindLowest(ptp_snap * target,ptp_snap ** n,enum AVLRES * res)420 SnapFindLowest(
421 ptp_snap *target,
422 ptp_snap **n,
423 enum AVLRES *res)
424 {
425 ptp_snap *tmp;
426
427 if (debug > 4)
428 printf("SnapFindLowest(): Replacing a node with a subtree's\
429 lowest ranking item \n");
430
431 *res = BALANCE;
432 if (!(*n)) {
433 return 0;
434 }
435
436 if ((*n)->left) {
437 if (!SnapFindLowest(target, & (*n)->left, res)) {
438 return 0;
439 }
440
441 if (*res == BALANCE) {
442 *res = SnapLeftShrunk(n);
443 }
444
445 return 1;
446 }
447
448 target->addr_pair = (*n)->addr_pair;
449 target->ptp = (*n)->ptp;
450 tmp = *n;
451 *n = (*n)->right;
452 return 1;
453 }
454
455 /*
456 * SnapRemove - remove a node from the AVL tree
457 * and balance the AVL tree
458 */
459
460 enum AVLRES
SnapRemove(ptp_snap ** root,tcp_pair_addrblock addr)461 SnapRemove(
462 ptp_snap **root,
463 tcp_pair_addrblock addr)
464 {
465 enum AVLRES tmp = BALANCE;
466
467 if (debug > 4)
468 printf("SnapRemove(): Removing a node from the AVL tree\n");
469
470 if (!(*root)) {
471 return 0;
472 }
473
474 if (AVL_WhichDir(&addr, &((*root)->addr_pair)) == LT) {
475 if ((tmp = SnapRemove(&(*root)->left, addr)) == BALANCE) {
476 return SnapLeftShrunk(root);
477 }
478
479 return tmp;
480 }
481
482 if (AVL_WhichDir(&addr, &((*root)->addr_pair)) == RT) {
483 if ((tmp = SnapRemove(&(*root)->right, addr)) == BALANCE) {
484 return SnapRightShrunk(root);
485 }
486
487 return tmp;
488 }
489
490 if ((*root)->left) {
491 if (SnapFindHighest(*root, &((*root)->left), &tmp)) {
492 if (tmp == BALANCE) {
493 tmp = SnapLeftShrunk(root);
494 }
495 return tmp;
496 }
497 }
498
499 if ((*root)->right) {
500 if (SnapFindLowest(*root, &((*root)->right), &tmp)) {
501 if (tmp == BALANCE) {
502 tmp = SnapRightShrunk(root);
503 }
504 return tmp;
505 }
506 }
507
508 *root = NULL;
509 return BALANCE;
510 }
511