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

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