taskrambler  v0.1.8
Web server and task management solution.
insert.c File Reference
#include "tree.h"
+ Include dependency graph for insert.c:

Go to the source code of this file.

Functions

void treeRotateLeft (Tree *, Tree)
 
void treeRotateRight (Tree *, Tree)
 
void * treeInsert (Tree *this, const void *search, TreeComp comp)
 

Detailed Description

Author
Georg Hopp

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition in file insert.c.

Function Documentation

void* treeInsert ( Tree *  this,
const void *  search,
TreeComp  comp 
)

Definition at line 29 of file insert.c.

References comp(), rbBlack, rbRed, TREE_GRANDPARENT, TREE_LEFT, TREE_PARENT, TREE_RIGHT, TREE_UNCLE, treeRotateLeft(), and treeRotateRight().

Referenced by hashAdd(), and main().

30 {
31  Tree node = *this;
32  Tree new_node = NULL;
33 
34  /*
35  * insert the node or return the one in tree if comparison
36  * succeeds.
37  */
38  if (NULL == node) {
39  /*
40  * if the root is NULL we simple add the element and set
41  * node to it.
42  */
43  *this = node = new_node = new(Tree, search);
44  } else {
45  /*
46  * first search for it and if its found return the data
47  * and we are done...
48  */
49  int comparison;
50 
51  while (NULL != node) {
52  comparison = comp(node->data, search);
53 
54  if (0 < comparison) {
55  if (NULL != TREE_LEFT(node)) {
56  node = TREE_LEFT(node);
57  continue;
58  } else {
59  break;
60  }
61  }
62 
63  if (0 > comparison) {
64  if (NULL != TREE_RIGHT(node)) {
65  node = TREE_RIGHT(node);
66  continue;
67  } else {
68  break;
69  }
70  }
71 
72  if (0 == comparison) {
73  return node->data;
74  }
75  }
76 
77  /*
78  * as we have not found it now add a new element.
79  */
80  if (0 < comparison) {
81  node->left = new(Tree, search);
82  TREE_LEFT(node)->parent = node;
83  node = new_node = TREE_LEFT(node);
84  } else {
85  node->right = new(Tree, search);
86  TREE_RIGHT(node)->parent = node;
87  node = new_node = TREE_RIGHT(node);
88  }
89  }
90 
91  /*
92  * we expect node not to be NULL and pointing to our
93  * new node at this point...now rabalance the tree
94  */
95  while (1) {
96  // case 1
97  if (NULL == TREE_PARENT(node)) {
98  node->color = rbBlack;
99  break;
100  }
101 
102  // case 2
103  if (rbBlack == TREE_PARENT(node)->color) {
104  break;
105  }
106 
107  // case 3
108  if (NULL != TREE_UNCLE(node) && rbRed == TREE_UNCLE(node)->color) {
109  TREE_PARENT(node)->color = rbBlack;
110  TREE_UNCLE(node)->color = rbBlack;
111  TREE_GRANDPARENT(node)->color = rbRed;
112 
113  node = TREE_GRANDPARENT(node);
114  continue;
115  }
116 
117  // case 4
118  if (node == TREE_PARENT(node)->right
119  && TREE_PARENT(node) == TREE_GRANDPARENT(node)->left) {
120 
121  //TREE_ROTATE_LEFT(this, TREE_PARENT(node));
122  treeRotateLeft(this, TREE_PARENT(node));
123  node = TREE_LEFT(node);
124 
125  } else if (node == TREE_PARENT(node)->left
126  && TREE_PARENT(node) == TREE_GRANDPARENT(node)->right) {
127 
128  //TREE_ROTATE_RIGHT(this, TREE_PARENT(node));
129  treeRotateRight(this, TREE_PARENT(node));
130  node = TREE_RIGHT(node);
131 
132  }
133 
134  // case 5
135  TREE_PARENT(node)->color = rbBlack;
136  TREE_GRANDPARENT(node)->color = rbRed;
137 
138  if (node == TREE_PARENT(node)->left) {
139  //TREE_ROTATE_RIGHT(this, TREE_GRANDPARENT(node));
140  treeRotateRight(this, TREE_GRANDPARENT(node));
141  } else {
142  //TREE_ROTATE_LEFT(this, TREE_GRANDPARENT(node));
143  treeRotateLeft(this, TREE_GRANDPARENT(node));
144  }
145 
146  break;
147  }
148 
149  return new_node->data;
150 }
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_PARENT(node)
Definition: tree.h:30
static int comp(const void *_a, const void *_b)
Definition: interface.c:32
void treeRotateRight(Tree *, Tree)
Definition: rotateRight.c:26
void treeRotateLeft(Tree *, Tree)
Definition: rotateLeft.c:26
#define TREE_GRANDPARENT(node)
Definition: tree.h:48
Definition: tree.h:115
#define TREE_LEFT(node)
Definition: tree.h:29
#define TREE_UNCLE(node)
Definition: tree.h:51
Definition: tree.h:115

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void treeRotateLeft ( Tree *  ,
Tree   
)

Definition at line 26 of file rotateLeft.c.

References TREE_PARENT, TREE_RIGHT, and TREE_RIGHT_LEFT.

Referenced by treeInsert().

27 {
28  Tree rightChild = TREE_RIGHT(node);
29  Tree rcLeftSub = TREE_RIGHT_LEFT(node);
30 
31  rightChild->left = node;
32  rightChild->parent = TREE_PARENT(node);
33  node->right = rcLeftSub;
34  if (NULL != rcLeftSub) {
35  rcLeftSub->parent = node;
36  }
37 
38  if (NULL != TREE_PARENT(node)) {
39  if (TREE_PARENT(node)->left == node) {
40  TREE_PARENT(node)->left = rightChild;
41  } else {
42  TREE_PARENT(node)->right = rightChild;
43  }
44  } else {
45  *this = rightChild;
46  }
47 
48  node->parent = rightChild;
49 }
#define TREE_RIGHT(node)
Definition: tree.h:28
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_RIGHT_LEFT(node)
Definition: tree.h:35

+ Here is the caller graph for this function:

void treeRotateRight ( Tree *  ,
Tree   
)

Definition at line 26 of file rotateRight.c.

References TREE_LEFT, TREE_LEFT_RIGHT, and TREE_PARENT.

Referenced by treeInsert().

27 {
28  Tree leftChild = TREE_LEFT(node);
29  Tree lcRightSub = TREE_LEFT_RIGHT(node);
30 
31  leftChild->right = node;
32  leftChild->parent = TREE_PARENT(node);
33  node->left = lcRightSub;
34  if (NULL != lcRightSub) {
35  lcRightSub->parent = node;
36  }
37 
38  if (NULL != TREE_PARENT(node)) {
39  if (TREE_PARENT(node)->left == node) {
40  TREE_PARENT(node)->left = leftChild;
41  } else {
42  TREE_PARENT(node)->right = leftChild;
43  }
44  } else {
45  *this = leftChild;
46  }
47 
48  node->parent = leftChild;
49 }
#define TREE_PARENT(node)
Definition: tree.h:30
#define TREE_LEFT_RIGHT(node)
Definition: tree.h:38
#define TREE_LEFT(node)
Definition: tree.h:29

+ Here is the caller graph for this function: