Annotation of libwww/Library/src/HTBTree.c, revision 1.1
1.1 ! timbl 1: /* Binary Tree for sorting things
! 2: ** ==============================
! 3: ** Author: Arthur Secret
! 4: */
! 5:
! 6:
! 7: #include "HTUtils.h"
! 8: #include "HTBTree.h"
! 9: #include <stdlib.h>
! 10: #include <string.h>
! 11:
! 12: #define MAX(a,b) ((a)>(b)?(a):(b))
! 13:
! 14:
! 15:
! 16:
! 17:
! 18: PUBLIC HTBTree * HTBTree_new ARGS1(HTComparer, comp)
! 19: /*********************************************************
! 20: ** This function returns an HTBTree with memory allocated
! 21: ** for it when given a mean to compare things
! 22: */
! 23: {
! 24: HTBTree * tree = (HTBTree *)malloc(sizeof(HTBTree));
! 25: if (tree==NULL) outofmem(__FILE__, "HTBTree_new");
! 26:
! 27: tree->compare = comp;
! 28: tree->top = NULL;
! 29:
! 30: return tree;
! 31: }
! 32:
! 33:
! 34:
! 35:
! 36:
! 37: PUBLIC void HTBTree_free ARGS1(HTBTree*, tree)
! 38: /**************************************************************
! 39: ** This void will free the memory allocated for the whole tree
! 40: */
! 41: {
! 42: HTBTElement * wagazou;
! 43:
! 44: wagazou = HTBTree_next(tree,NULL);
! 45: while (wagazou != NULL)
! 46: {
! 47: free (wagazou);
! 48: wagazou = HTBTree_next(tree,wagazou);
! 49: }
! 50: free(tree);
! 51: }
! 52:
! 53:
! 54:
! 55:
! 56:
! 57: PUBLIC void HTBTree_add ARGS2(
! 58: HTBTree*, tree,
! 59: void*, object)
! 60: /**********************************************************************
! 61: ** This void is the core of HTBTree.c . It will
! 62: ** 1/ add a new element to the tree at the right place
! 63: ** so that the tree remains sorted
! 64: ** 2/ balance the tree to be as fast as possible when reading it
! 65: */
! 66: {
! 67: HTBTElement * leopard;
! 68: HTBTElement * leopard_son;
! 69: HTBTElement * leopard_father;
! 70: HTBTElement * leo_brother;
! 71: BOOL bouboule,bouboule2,first_correction;
! 72: int depth,depth2;
! 73: /* leopard is a pointer to the structure that is the father of the new
! 74: ** object "object".
! 75: ** leopard_son is a pointer to the structure that contains or will contain
! 76: ** the new object "object".
! 77: ** leopard_father and leo_brother are pointers that are used to modify the
! 78: ** depths of upper elements, when needed.
! 79: **
! 80: ** bouboule indicates by a value NO when the future father of "object" is
! 81: ** found.
! 82: ** bouboule2 indicates by a value NO when, in case of a difference of depths
! 83: ** < 2, the top of the tree is encountered and forbids any further try to
! 84: ** balance the tree.
! 85: ** first_correction is a boolean used to avoid infinite loops in cases
! 86: ** such as:
! 87: **
! 88: ** 3 3
! 89: ** 4 4
! 90: ** 5 5
! 91: **
! 92: ** 3 is used here to show that it need not be the top of the tree.
! 93: */
! 94:
! 95: /*
! 96: ** 1/ Adding of the element to the binary tree
! 97: */
! 98:
! 99: if (tree->top == NULL)
! 100: {
! 101: tree->top = (HTBTElement *)malloc(sizeof(HTBTElement));
! 102: if (tree->top == NULL) outofmem(__FILE__, "HTBTree_add");
! 103: tree->top->up = NULL;
! 104: tree->top->object = object;
! 105: tree->top->left = NULL;
! 106: tree->top->left_depth = 0;
! 107: tree->top->right = NULL;
! 108: tree->top->right_depth = 0;
! 109: }
! 110: else
! 111: {
! 112: bouboule = YES;
! 113: leopard = tree->top;
! 114: leopard_son = NULL;
! 115: leopard_father = NULL;
! 116: leo_brother = NULL;
! 117: while (bouboule)
! 118: {
! 119: if (tree->compare(object,leopard->object)<0)
! 120: {
! 121: if (leopard->left != NULL) leopard = leopard->left;
! 122: else
! 123: {
! 124: bouboule = NO;
! 125: leopard->left = (HTBTElement *)malloc(sizeof(HTBTElement));
! 126: if (leopard->left==NULL) outofmem(__FILE__, "HTBTree_add");
! 127: leopard_son = leopard->left;
! 128: leopard_son->up = leopard;
! 129: leopard_son->object = object;
! 130: leopard_son->left = NULL;
! 131: leopard_son->left_depth = 0;
! 132: leopard_son->right = NULL;
! 133: leopard_son->right_depth = 0;
! 134: }
! 135: }
! 136: if (tree->compare(object,leopard->object)>0)
! 137: {
! 138: if (leopard->right != NULL) leopard = leopard->right;
! 139: else
! 140: {
! 141: bouboule = NO;
! 142: leopard->right = (HTBTElement *)malloc(sizeof(HTBTElement));
! 143: if (leopard->right==NULL) outofmem(__FILE__, "HTBTree_add");
! 144: leopard_son = leopard->right;
! 145: leopard_son->up = leopard;
! 146: leopard_son->object = object;
! 147: leopard_son->left = NULL;
! 148: leopard_son->left_depth = 0;
! 149: leopard_son->right = NULL;
! 150: leopard_son->right_depth = 0;
! 151: }
! 152: }
! 153: }
! 154: /*
! 155: ** Changing of all depths that need to be changed
! 156: */
! 157: leopard_father = leopard;
! 158: leo_brother = leopard_son;
! 159: do
! 160: {
! 161: if (leopard_father->left == leo_brother)
! 162: {
! 163: depth = leopard_father->left_depth;
! 164: leopard_father->left_depth = 1
! 165: + MAX(leo_brother->right_depth,leo_brother->left_depth);
! 166: depth2 = leopard_father->left_depth;
! 167: }
! 168: else
! 169: {
! 170: depth = leopard_father->right_depth;
! 171: leopard_father->right_depth = 1
! 172: + MAX(leo_brother->right_depth,leo_brother->left_depth);
! 173: depth2 = leopard_father->right_depth;
! 174: }
! 175: leo_brother = leopard_father;
! 176: leopard_father = leopard_father->up;
! 177: } while ((depth != depth2) && (leopard_father != NULL));
! 178:
! 179:
! 180: /*
! 181: ** 2/ Balancing the binary tree, if necessary
! 182: */
! 183: bouboule2 = YES;
! 184: first_correction = YES;
! 185: while ((bouboule2) && (first_correction))
! 186: {
! 187: if ((abs(leopard->left_depth - leopard->right_depth)) < 2)
! 188: {
! 189: if (leopard->up != NULL) leopard = leopard->up;
! 190: else bouboule2 = NO;
! 191: }
! 192: else
! 193: { /* We start the process of balancing */
! 194:
! 195: first_correction = NO;
! 196: /*
! 197: ** first_correction is a boolean used to avoid infinite
! 198: ** loops in cases such as:
! 199: **
! 200: ** 3 3
! 201: ** 4 4
! 202: ** 5 5
! 203: **
! 204: ** 3 is used to show that it need not be the top of the tree
! 205: */
! 206:
! 207:
! 208: if (leopard->left_depth > leopard->right_depth)
! 209: {
! 210: leopard_son = leopard->left;
! 211: leopard->left_depth = leopard_son->right_depth;
! 212: leopard_son->right_depth = 1
! 213: + MAX(leopard->right_depth,leopard->left_depth);
! 214: if (leopard->up != NULL)
! 215: {
! 216: leopard_father = leopard->up;
! 217: leo_brother = leopard_son;
! 218: do
! 219: {
! 220: if (leopard_father->left == leo_brother->up)
! 221: {
! 222: depth = leopard_father->left_depth;
! 223: leopard_father->left_depth = 1
! 224: + MAX(leo_brother->left_depth,
! 225: leo_brother->right_depth);
! 226: depth2 = leopard_father->left_depth;
! 227: }
! 228: else
! 229: {
! 230: depth = leopard_father->right_depth;
! 231: leopard_father->right_depth = 1
! 232: + MAX(leo_brother->left_depth,
! 233: leo_brother->right_depth);
! 234: depth2 = leopard_father->right_depth;
! 235: }
! 236: leo_brother = leopard_father;
! 237: leopard_father = leopard_father->up;
! 238: } while ((depth != depth2) && (leopard_father != NULL));
! 239: leopard_father = leopard->up;
! 240: if (leopard_father->left == leopard)
! 241: {
! 242: /*
! 243: ** 3 3
! 244: ** 4 5
! 245: ** When tree 5 6 becomes 7 4
! 246: ** 7 8 8 6
! 247: **
! 248: ** 3 is used to show that it may not be the top of the
! 249: ** tree.
! 250: */
! 251: leopard_father->left = leopard_son;
! 252: leopard->left = leopard_son->right;
! 253: leopard_son->right = leopard;
! 254: }
! 255: if (leopard_father->right == leopard)
! 256: {
! 257: /*
! 258: ** 3 3
! 259: ** 4 5
! 260: ** When tree 5 6 becomes 7 4
! 261: ** 7 8 8 6
! 262: **
! 263: ** 3 is used to show that it may not be the top of the
! 264: ** tree
! 265: */
! 266: leopard_father->right = leopard_son;
! 267: leopard->left = leopard_son->right;
! 268: leopard_son->right = leopard;
! 269: }
! 270: leopard_son->up = leopard_father;
! 271: }
! 272: else
! 273: {
! 274: /*
! 275: **
! 276: ** 1 2
! 277: ** When tree 2 3 becomes 4 1
! 278: ** 4 5 5 3
! 279: **
! 280: ** 1 is used to show that it is the top of the tree
! 281: */
! 282: leopard_son->up = NULL;
! 283: leopard->left = leopard_son->right;
! 284: leopard_son->right = leopard;
! 285: }
! 286: leopard->up = leopard_son;
! 287: if (leopard->left != NULL)
! 288: leopard->left->up = leopard;
! 289: }
! 290: else
! 291: {
! 292: leopard_son = leopard->right;
! 293: leopard->right_depth = leopard_son->left_depth;
! 294: leopard_son->left_depth = 1 +
! 295: MAX(leopard->right_depth,leopard->left_depth);
! 296: if (leopard->up != NULL)
! 297: {
! 298: leopard_father = leopard->up;
! 299: leo_brother = leopard_son;
! 300: do
! 301: {
! 302: if (leopard_father->left == leopard)
! 303: {
! 304: depth = leopard_father->left_depth;
! 305: leopard_father->left_depth = 1
! 306: + MAX(leopard_son->left_depth,
! 307: leopard_son->right_depth);
! 308: depth2 = leopard_father->left_depth;
! 309: }
! 310: else
! 311: {
! 312: depth = leopard_father->right_depth;
! 313: leopard_father->right_depth = 1
! 314: + MAX(leopard_son->left_depth,
! 315: leopard_son->right_depth);
! 316: depth2 = leopard_father->right_depth;
! 317: }
! 318: leopard_father = leopard_father->up;
! 319: leo_brother = leopard_father;
! 320: } while ((depth != depth2) && (leopard_father != NULL));;
! 321: leopard_father = leopard->up;
! 322: if (leopard_father->left == leopard)
! 323: {
! 324: /*
! 325: ** 3 3
! 326: ** 4 6
! 327: ** When tree 5 6 becomes 4 8
! 328: ** 7 8 5 7
! 329: **
! 330: ** 3 is used to show that it may not be the top of the
! 331: ** tree.
! 332: */
! 333: leopard_father->left = leopard_son;
! 334: leopard->right = leopard_son->left;
! 335: leopard_son->left = leopard;
! 336: }
! 337: if (leopard_father->right == leopard)
! 338: {
! 339: /*
! 340: ** 3 3
! 341: ** 4 6
! 342: ** When tree 5 6 becomes 4 8
! 343: ** 7 8 5 7
! 344: **
! 345: ** 3 is used to show that it may not be the top of the
! 346: ** tree
! 347: */
! 348: leopard_father->right = leopard_son;
! 349: leopard->right = leopard_son->left;
! 350: leopard_son->left = leopard;
! 351: }
! 352: leopard_son->up = leopard_father;
! 353: }
! 354: else
! 355: {
! 356: /*
! 357: **
! 358: ** 1 3
! 359: ** When tree 2 3 becomes 1 5
! 360: ** 4 5 2 4
! 361: **
! 362: ** 1 is used to show that it is the top of the tree.
! 363: */
! 364: leopard_son->up = NULL;
! 365: leopard->right = leopard_son->left;
! 366: leopard_son->left = leopard;
! 367: }
! 368: leopard->up = leopard_son;
! 369: leopard->right->up = leopard;
! 370: }
! 371: }
! 372: }
! 373: while (leopard->up != NULL)
! 374: {
! 375: leopard = leopard->up;
! 376: }
! 377: tree->top = leopard;
! 378: }
! 379: }
! 380:
! 381:
! 382:
! 383: PUBLIC HTBTElement * HTBTree_next ARGS2(
! 384: HTBTree*, tree,
! 385: HTBTElement*, ele)
! 386: /**************************************************************************
! 387: ** this function returns a pointer to the leftmost element if ele is NULL,
! 388: ** and to the next object to the right otherways.
! 389: ** If no elements left, returns a pointer to NULL.
! 390: */
! 391: {
! 392: HTBTElement * leopard;
! 393: HTBTElement * leopard_father;
! 394:
! 395: if (ele == NULL)
! 396: {
! 397: leopard = tree->top;
! 398: if (leopard != NULL)
! 399: while (leopard->left != NULL)
! 400: leopard = leopard->left;
! 401: }
! 402: else
! 403: {
! 404: leopard = ele;
! 405: if (leopard->right != NULL)
! 406: {
! 407: leopard = leopard->right;
! 408: while (leopard->left != NULL)
! 409: leopard = leopard->left;
! 410: }
! 411: else
! 412: {
! 413: leopard_father = leopard->up;
! 414: while (leopard_father->right == leopard)
! 415: {
! 416: leopard = leopard_father;
! 417: leopard_father = leopard->up;
! 418: }
! 419: leopard = leopard_father;
! 420: }
! 421: }
! 422: return leopard;
! 423: }
! 424:
! 425:
! 426: #ifdef TEST
! 427: main ()
! 428: /******************************************************
! 429: ** This is just a test to show how to handle HTBTree.c
! 430: */
! 431: {
! 432: HTBTree * tree;
! 433: HTBTElement * wagazou;
! 434:
! 435: tree = HTBTree_new(strcasecmp);
! 436: HTBTree_add(tree,"zoo");
! 437: HTBTree_add(tree,"carot");
! 438: HTBTree_add(tree,"elephant\t");
! 439: HTBTree_add(tree,"coat");
! 440: HTBTree_add(tree,"snake");
! 441: HTBTree_add(tree,"Peter");
! 442: HTBTree_add(tree,"Harrison");
! 443: HTBTree_add(tree,"WWW");
! 444: wagazou = HTBTree_next(tree,NULL);
! 445: while (wagazou != NULL)
! 446: {
! 447: printf("The next element is %s\n",wagazou->object);
! 448: wagazou = HTBTree_next(tree,wagazou);
! 449: }
! 450: HTBTree_free (tree);
! 451: }
! 452:
! 453:
! 454: #endif
Webmaster
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to HTBTree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Public] / libwww / Library / src