PandA-2024.02
tree.c
Go to the documentation of this file.
1 #include <assert.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4 
5 #define MAX_NUMBER_OF_NODES 255
6 extern void __builtin_bambu_time_start();
7 extern void __builtin_bambu_time_stop();
8 
9 /* stack data structure */
10 struct stack
11 {
12  void* data;
13  struct stack* next;
14 };
15 
16 typedef struct stack node_stack;
17 
18 /* Auxiliary memory stack allocation utilities */
21 
23 {
24  new_node->data = 0;
25  new_node->next = *head;
26  *head = new_node;
27 }
29 {
30  node_stack* retval = 0;
31  node_stack* next_node = NULL;
32 
33  if(*head == NULL)
34  return NULL;
35 
36  next_node = (*head)->next;
37  retval = *head;
38  *head = next_node;
39 
40  return retval;
41 }
43 {
44  int index;
45  for(index = 0; index < MAX_NUMBER_OF_NODES; ++index)
46  push_stack_free_list(&head_stack_free_list, &StaticPoolStack[index]);
47 }
48 
49 /* Stack related functions */
50 void push(node_stack** head, void* t)
51 {
52  node_stack* temp = pop_stack_free_list(&head_stack_free_list);
53  assert(temp);
54  temp->data = t;
55  temp->next = (*head);
56  *head = temp;
57 }
58 _Bool isEmpty(node_stack* head)
59 {
60  return (head == NULL) ? 1 : 0;
61 }
62 void* pop(node_stack** head)
63 {
64  void* res;
65  node_stack* top;
66 
67  assert(!isEmpty(*head));
68  top = *head;
69  res = top->data;
70  *head = top->next;
71  push_stack_free_list(&head_stack_free_list, top);
72  return res;
73 }
74 
75 void* top(node_stack* head)
76 {
77  return head->data;
78 }
79 
80 /* binary tree data structure */
81 struct bin_tree
82 {
83  int data;
84  struct bin_tree *right, *left;
85 };
86 typedef struct bin_tree node_tree;
87 
88 /* Auxiliary memory tree allocation utilities */
91 
92 void push_tree_free_list(node_tree** head, node_tree* new_node)
93 {
94  new_node->data = 0;
95  new_node->left = *head;
96  new_node->right = 0;
97  *head = new_node;
98 }
100 {
101  node_tree* retval = 0;
102  node_tree* next_node = NULL;
103 
104  if(*head == NULL)
105  return NULL;
106 
107  next_node = (*head)->left;
108  retval = *head;
109  *head = next_node;
110 
111  return retval;
112 }
114 {
115  int index;
116  for(index = 0; index < MAX_NUMBER_OF_NODES; ++index)
117  push_tree_free_list(&head_tree_free_list, &StaticPoolTree[index]);
118 }
119 
120 /* binary tree functions */
121 void insert(node_tree** tree, int val)
122 {
123  node_tree* temp = NULL;
124  if(!(*tree))
125  {
126  temp = pop_tree_free_list(&head_tree_free_list);
127  assert(temp);
128  temp->left = temp->right = NULL;
129  temp->data = val;
130  *tree = temp;
131  return;
132  }
133  if(val < (*tree)->data)
134  {
135  insert(&(*tree)->left, val);
136  }
137  else if(val > (*tree)->data)
138  {
139  insert(&(*tree)->right, val);
140  }
141 }
142 
144 {
145  if(root)
146  {
147  node_tree* current;
148  node_stack* s = NULL;
149  push(&s, root);
150 
151  while(!isEmpty(s))
152  {
153  current = pop(&s);
154  printf("%d\n", current->data);
155 
156  if(current->right)
157  push(&s, current->right);
158  if(current->left)
159  push(&s, current->left);
160  }
161  }
162 }
163 
164 /* Iterative function for inorder binary tree print */
166 {
167  node_tree* current = root;
168  node_stack* s = NULL;
169  _Bool done = 0;
170 
171  while(!done)
172  {
173  if(current != NULL)
174  {
175  push(&s, current);
176  current = current->left;
177  }
178  else
179  {
180  if(!isEmpty(s))
181  {
182  current = pop(&s);
183  printf("%d\n", current->data);
184  current = current->right;
185  }
186  else
187  done = 1;
188  }
189  }
190 }
191 
193 {
194  if(root)
195  {
196  node_tree* prev = NULL;
197  node_stack* s = NULL;
198  push(&s, root);
199 
200  while(!isEmpty(s))
201  {
202  node_tree* curr = top(s);
203  if(!prev || prev->left == curr || prev->right == curr)
204  {
205  if(curr->left)
206  push(&s, curr->left);
207  else if(curr->right)
208  push(&s, curr->right);
209  }
210  else if(curr->left == prev)
211  {
212  if(curr->right)
213  push(&s, curr->right);
214  }
215  else
216  {
217  printf("%d\n", curr->data);
218  pop(&s);
219  }
220  prev = curr;
221  }
222  }
223 }
224 
225 void deltree(node_tree* root)
226 {
227  if(root)
228  {
229  node_tree* prev = NULL;
230  node_stack* s = NULL;
231  push(&s, root);
232 
233  while(!isEmpty(s))
234  {
235  node_tree* curr = top(s);
236  if(!prev || prev->left == curr || prev->right == curr)
237  {
238  if(curr->left)
239  push(&s, curr->left);
240  else if(curr->right)
241  push(&s, curr->right);
242  }
243  else if(curr->left == prev)
244  {
245  if(curr->right)
246  push(&s, curr->right);
247  }
248  else
249  {
250  push_tree_free_list(&head_tree_free_list, curr);
251  pop(&s);
252  }
253  prev = curr;
254  }
255  }
256 }
257 
258 node_tree* __attribute__((noinline)) search(node_tree* tree, int val)
259 {
260  if(tree == NULL || tree->data == val)
261  return tree;
262 
263  if(tree->data < val)
264  return search(tree->right, val);
265  else
266  return search(tree->left, val);
267 }
268 
269 int main()
270 {
271  node_tree* root;
272  node_tree* tmp;
273  // int i;
276 
277  root = NULL;
278  /* Inserting nodes into tree */
279  insert(&root, 9);
280  insert(&root, 4);
281  insert(&root, 15);
282  insert(&root, 6);
283  insert(&root, 12);
284  insert(&root, 17);
285  insert(&root, 2);
286 
287  /* Printing nodes of tree */
288  printf("Pre Order Display\n");
289  print_preorder(root);
290 
291  printf("In Order Display\n");
292  print_inorder(root);
293 
294  printf("Post Order Display\n");
295  print_postorder(root);
296 
297  /* Search node into tree */
298  tmp = search(root, 4);
299  if(tmp)
300  {
301  printf("Searched node=%d\n", tmp->data);
302  }
303  else
304  {
305  printf("Data Not found in tree.\n");
306  }
307 
308  /* Search node into tree */
309  tmp = search(root, 6);
310  if(tmp)
311  {
312  printf("Second searched node=%d\n", tmp->data);
313  }
314  else
315  {
316  printf("Data Not found in tree.\n");
317  }
318 
319  /* Deleting all nodes of tree */
320  deltree(root);
321  return 0;
322 }
void push(node_stack **head, void *t)
Definition: tree.c:50
#define NULL
int data
Definition: tree.c:83
void * top(node_stack *head)
Definition: tree.c:75
_Bool isEmpty(node_stack *head)
Definition: tree.c:58
node_tree * pop_tree_free_list(node_tree **head)
Definition: tree.c:99
void print_preorder(node_tree *root)
Definition: tree.c:143
void __builtin_bambu_time_start()
void init_tree_free_list()
Definition: tree.c:113
void init_stack_free_list()
Definition: tree.c:42
void insert(node_tree **tree, int val)
Definition: tree.c:121
static node_stack StaticPoolStack[MAX_NUMBER_OF_NODES]
Definition: tree.c:19
struct stack * next
Definition: tree.c:13
struct bin_tree * left
Definition: tree.c:84
struct bin_tree * right
Definition: tree.c:84
static node_stack * head_stack_free_list
Definition: tree.c:20
Definition: tree.c:81
void push_stack_free_list(node_stack **head, node_stack *new_node)
Definition: tree.c:22
#define index(x, y)
Definition: Keccak.c:74
node_tree * __attribute__((noinline))
Definition: tree.c:258
void print_inorder(node_tree *root)
Definition: tree.c:165
void * data
Definition: tree.c:12
void push_tree_free_list(node_tree **head, node_tree *new_node)
Definition: tree.c:92
Definition: tree.c:10
static node_tree StaticPoolTree[MAX_NUMBER_OF_NODES]
Definition: tree.c:89
void * pop(node_stack **head)
Definition: tree.c:62
void print_postorder(node_tree *root)
Definition: tree.c:192
node_stack * pop_stack_free_list(node_stack **head)
Definition: tree.c:28
void deltree(node_tree *root)
Definition: tree.c:225
static node_tree * head_tree_free_list
Definition: tree.c:90
void __builtin_bambu_time_stop()
#define MAX_NUMBER_OF_NODES
Definition: tree.c:5
int main()
Definition: tree.c:269

Generated on Mon Feb 12 2024 13:02:47 for PandA-2024.02 by doxygen 1.8.13