COVISE Core
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros
dmgr_mem_avltrees.h
Go to the documentation of this file.
1 /* This file is part of COVISE.
2 
3  You can use it under the terms of the GNU Lesser General Public License
4  version 2.1 or later, see lgpl-2.1.txt.
5 
6  * License: LGPL 2+ */
7 
8 #ifndef DMGR_AVL_TREE_H
9 #define DMGR_AVL_TREE_H
10 
11 #include <shm/covise_shm.h>
12 
13 //*****************************************************************//
14 // search for a special value in a binary tree. return value is
15 // if search==-2: the biggest node with value < data,
16 // if search==+2: the smallest node with value > data,
17 // if search==-1: the biggest node with value <= data,
18 // if search==+1: the smallest node with value >= data,
19 // if search== 0: the node with value == data,
20 // or NULL, if the condition cannot be satisfied.
21 //*****************************************************************//
22 
23 /*
24 const int GREATER_THAN = 2;
25 const int GT_EQUAL = 1;
26 const int EQUAL = 0;
27 const int LS_EQUAL = -1;
28 const int LESS_THAN = -2;
29 */
30 
31 #ifndef GREATER_THAN
32 #define GREATER_THAN 2
33 #endif
34 #ifndef GT_EQUAL
35 #define GT_EQUAL 1
36 #endif
37 #ifndef EQUAL
38 #define EQUAL 0
39 #endif
40 #ifndef LS_EQUAL
41 #define LS_EQUAL -1
42 #endif
43 #ifndef LESS_THAN
44 #define LESS_THAN -2
45 #endif
46 
47 namespace covise
48 {
49 
50 class CO_MemAddAVLTree;
51 
52 const int NO_OF_TREES = 256;
53 const int NO_OF_MEMCHUNKS = 1000;
54 
56 {
57  friend class AddressOrderedTree;
58  friend class CO_MemSizeAVLNode;
59  friend class CO_MemAddAVLTree;
60  friend class CO_MemSizeAVLTree;
61  int seq_no;
63  char *address;
64 
65 public:
66  class MemChunk *next;
68  : seq_no(0)
69  , size(0)
70  , address(0L)
71  , next(0L){};
72  MemChunk(int no, void *add, shmSizeType s)
73  : seq_no(no)
74  , size(s)
75  , address((char *)add)
76  , next(0L){};
77  ~MemChunk(){};
79  {
80  MemChunk *new_node = new MemChunk(seq_no, address, s);
81  size = size - s;
82  address = address + s;
83  return new_node;
84  };
86  {
88  coShmPtr *ptr = new coShmPtr(seq_no, address - (char *)shm->get_pointer(seq_no));
89  return ptr;
90  };
92  {
93  return address;
94  };
96  {
97  return size;
98  };
100  {
101  size += incr;
102  };
103  void print();
104  void set(int no, void *add, shmSizeType s)
105  {
106  seq_no = no;
107  size = s;
108  address = (char *)add;
109  };
110 };
111 
112 AVL_EXTERN MemChunk *new_memchunk();
113 AVL_EXTERN MemChunk *new_memchunk(int no, void *add, shmSizeType s);
114 AVL_EXTERN void delete_memchunk(MemChunk *);
115 
116 class DMGREXPORT CO_MemAVLNode /* structure for AVL-trees */
117 {
118 public:
119  CO_MemAVLNode *left; /* pointer to left subtree */
120  CO_MemAVLNode *right; /* pointer to right subtree */
121  CO_MemAVLNode *up; /* pointer to father node */
122  int balance; /* balance of subtrees =h(R)-h(L), normally -1..1 */
123  MemChunk *data; /* data the tree is sorted by */
125  {
126  data = d;
127  left = 0L;
128  right = 0L;
129  up = 0L;
130  balance = 0;
131  };
132  CO_MemAVLNode() // does not delete data!!
133  {
134  data = 0L;
135  delete left;
136  delete right;
137  };
138  void print()
139  {
140  if (left)
141  left->print();
142  // if(data) data->print();
143  if (right)
144  right->print();
145  };
146  void remove_nod(int dispo_chunk)
147  {
148  if (left)
149  {
150  left->remove_nod(dispo_chunk);
151  delete left;
152  }
153  if (right)
154  {
155  right->remove_nod(dispo_chunk);
156  delete right;
157  }
158  if (dispo_chunk && data)
160  };
161 };
162 
164 {
165  friend class CO_MemAddAVLTree;
166  friend class CO_MemSizeAVLTree;
167  int m_reb_active; //rebalance of the tree active - default true
168 public:
169  CO_MemAVLTree() // standard initialization
170  {
171  m_reb_active = 1;
172  };
174 
175  void activate_reb(void)
176  {
177  m_reb_active = 1;
178  };
179  void deactivate_reb(void)
180  {
181  m_reb_active = 0;
182  };
183  int is_reb_active(void)
184  {
185  return m_reb_active;
186  };
187 
188  void show_tree(CO_MemAVLNode *curr_node);
189 };
190 
192 {
194  CO_MemAVLNode *best_node; /* after a search the found node can be found here */
195 public:
197  : root(0L){};
199  void rebalance_tree(CO_MemAVLNode *tree_node, int add_balance,
200  int grow_shrink);
201  MemChunk *search_node(MemChunk *data, int search);
202  MemChunk *search_and_remove_node(MemChunk *data, int search);
203  int insert_node(MemChunk *data);
204  MemChunk *remove_node(MemChunk *data);
205  void empty_tree(int dispo_chunk)
206  {
207  if (root)
208  {
209  root->remove_nod(dispo_chunk);
210  delete root;
211  root = NULL;
212  }
213  };
214 };
215 
217 {
218 private:
220 
221 public:
225  {
226  return trees[(long)data->address & 0xff00 >> 8].search_node(data, search);
227  };
229  {
230  return trees[(long)data->address & 0xff00 >> 8].insert_node(data);
231  };
233  {
234  return trees[(long)data->address & 0xff00 >> 8].search_and_remove_node(data, EQUAL);
235  };
236  void empty_trees(int dispo_chunk)
237  {
238  for (int i = 0; i < NO_OF_TREES; i++)
239  trees[i].empty_tree(dispo_chunk);
240  };
241 };
242 
243 class DMGREXPORT CO_MemSizeAVLNode /* structure for AVL-trees */
244 {
245 public:
246  CO_MemSizeAVLNode *left; /* pointer to left subtree */
247  CO_MemSizeAVLNode *right; /* pointer to right subtree */
248  CO_MemSizeAVLNode *up; /* pointer to father node */
249  int balance; /* balance of subtrees =h(R)-h(L), normally -1..1 */
250  shmSizeType size; /* data the tree is sorted by */
254  : left(0L)
255  , right(0L)
256  , up(0)
257  , balance(0)
258  , number_of_chunks(1)
259  {
260  d->next = 0L;
261  node_list = d;
262  size = d->size;
263  };
265  {
266  while (node_list)
267  {
268  fprintf(stderr, "Fehler!!!\n");
269  MemChunk *tmp = node_list->next;
270  delete_memchunk(node_list);
271  node_list = tmp;
272  }
273  // Uwe delete left;
274  // delete right;
275  }; // does not delete data!!
277  {
278  d->next = node_list;
279  node_list = d;
280  number_of_chunks++;
281  };
283  {
284  MemChunk *tmpptr = node_list;
285  node_list = node_list->next;
286  number_of_chunks--;
287  return tmpptr;
288  };
290  {
291  MemChunk *tmpptr = node_list;
292  if (tmpptr == data)
293  {
294  node_list = node_list->next;
295  number_of_chunks--;
296  return tmpptr;
297  }
298  while (tmpptr->next)
299  {
300  if (tmpptr->next == data)
301  {
302  tmpptr->next = data->next;
303  number_of_chunks--;
304  return data;
305  }
306  else
307  tmpptr = tmpptr->next;
308  }
309  return 0L;
310  };
311  void print()
312  {
313  if (left)
314  left->print();
315  // if(data) data->print();
316  if (right)
317  right->print();
318  };
319  void remove_nod(void)
320  {
321  if (left)
322  {
323  left->remove_nod();
324  delete left;
325  }
326  if (right)
327  {
328  right->remove_nod();
329  delete right;
330  }
331  while (node_list)
332  {
333  MemChunk *tmp = node_list->next;
334  delete_memchunk(node_list);
335  node_list = tmp;
336  }
337  };
338 };
339 
341 {
343  CO_MemSizeAVLNode *best_node; /* after a search the found node can be found here */
344 public:
346  : root(0L){};
348  void rebalance_tree(CO_MemSizeAVLNode *tree_node, int add_balance,
349  int grow_shrink);
350  MemChunk *search_and_remove_node(shmSizeType size, int search);
351  MemChunk *remove_node(MemChunk *data);
352  int insert_node(MemChunk *data);
353  void empty_tree(void)
354  {
355  if (root)
356  {
357  root->remove_nod();
358  delete root;
359  root = NULL;
360  }
361  };
362 };
363 
365 {
366 private:
368 
369 public:
373  {
374  return tree.search_and_remove_node(size_wanted, GT_EQUAL);
375  };
377  {
378  return tree.remove_node(data);
379  };
381  {
382  return tree.insert_node(data);
383  };
384  void empty_tree(void)
385  {
386  tree.empty_tree();
387  };
388 };
389 }
390 #endif
Definition: dmgr_mem_avltrees.h:163
MemChunk(int no, void *add, shmSizeType s)
Definition: dmgr_mem_avltrees.h:72
void * get_pointer(int no)
Definition: covise_shm.h:246
Definition: dmgr_mem_avltrees.h:191
void set(int no, void *add, shmSizeType s)
Definition: dmgr_mem_avltrees.h:104
void empty_tree(void)
Definition: dmgr_mem_avltrees.h:384
shmSizeType size
Definition: dmgr_mem_avltrees.h:250
void empty_tree(int dispo_chunk)
Definition: dmgr_mem_avltrees.h:205
~CO_MemAVLTree()
Definition: dmgr_mem_avltrees.h:173
char * address
Definition: dmgr_mem_avltrees.h:63
CO_MemSizeAVLNode(MemChunk *d)
Definition: dmgr_mem_avltrees.h:253
~AddressOrderedTree()
Definition: dmgr_mem_avltrees.h:223
CO_MemAVLNode * root
Definition: dmgr_mem_avltrees.h:193
void activate_reb(void)
Definition: dmgr_mem_avltrees.h:175
int number_of_chunks
Definition: dmgr_mem_avltrees.h:251
CO_MemAVLNode * best_node
Definition: dmgr_mem_avltrees.h:194
int insert_chunk(MemChunk *data)
Definition: dmgr_mem_avltrees.h:228
coShmPtr * getAddress()
Definition: dmgr_mem_avltrees.h:85
int m_reb_active
Definition: dmgr_mem_avltrees.h:167
#define GT_EQUAL
Definition: dmgr_mem_avltrees.h:35
char * get_plain_address()
Definition: dmgr_mem_avltrees.h:91
CO_MemAVLNode(MemChunk *d)
Definition: dmgr_mem_avltrees.h:124
void empty_tree(void)
Definition: dmgr_mem_avltrees.h:353
#define DMGREXPORT
Definition: coExport.h:301
Definition: dmgr_mem_avltrees.h:116
MemChunk()
Definition: dmgr_mem_avltrees.h:67
void delete_memchunk(MemChunk *chunk_ptr)
Definition: dmgr_mem_avltrees.cpp:113
CO_MemAVLNode * left
Definition: dmgr_mem_avltrees.h:119
GLdouble s
Definition: khronos-glext.h:6441
CO_MemAVLNode()
Definition: dmgr_mem_avltrees.h:132
int is_reb_active(void)
Definition: dmgr_mem_avltrees.h:183
CO_MemSizeAVLTree tree
Definition: dmgr_mem_avltrees.h:367
#define EQUAL
Definition: dmgr_mem_avltrees.h:38
GLint left
Definition: khronos-glext.h:8444
#define NULL
Definition: covise_list.h:22
void deactivate_reb(void)
Definition: dmgr_mem_avltrees.h:179
~CO_MemSizeAVLTree()
Definition: dmgr_mem_avltrees.h:347
CO_MemSizeAVLNode * left
Definition: dmgr_mem_avltrees.h:246
~MemChunk()
Definition: dmgr_mem_avltrees.h:77
MemChunk * data
Definition: dmgr_mem_avltrees.h:123
~SizeOrderedTree()
Definition: dmgr_mem_avltrees.h:371
int balance
Definition: dmgr_mem_avltrees.h:249
#define AVL_EXTERN
Definition: dmgr_mem_avltrees.cpp:9
~CO_MemSizeAVLNode()
Definition: dmgr_mem_avltrees.h:264
CO_MemSizeAVLNode * root
Definition: dmgr_mem_avltrees.h:342
void empty_trees(int dispo_chunk)
Definition: dmgr_mem_avltrees.h:236
GLsizeiptr size
Definition: khronos-glext.h:6610
Definition: dmgr_mem_avltrees.h:340
void increase_size(shmSizeType incr)
Definition: dmgr_mem_avltrees.h:99
int balance
Definition: dmgr_mem_avltrees.h:122
void remove_nod(int dispo_chunk)
Definition: dmgr_mem_avltrees.h:146
shmSizeType get_plain_size()
Definition: dmgr_mem_avltrees.h:95
void print()
Definition: dmgr_mem_avltrees.h:311
void add_chunk(MemChunk *d)
Definition: dmgr_mem_avltrees.h:276
MemChunk * search_chunk(MemChunk *data, int search)
Definition: dmgr_mem_avltrees.h:224
class MemChunk * next
Definition: dmgr_mem_avltrees.h:66
const int NO_OF_TREES
Definition: dmgr_mem_avltrees.h:52
MemChunk * remove_chunk(MemChunk *data)
Definition: dmgr_mem_avltrees.h:376
Definition: dmgr_mem_avltrees.h:364
MemChunk * remove_chunk(MemChunk *data)
Definition: dmgr_mem_avltrees.h:289
MemChunk * split(shmSizeType s)
Definition: dmgr_mem_avltrees.h:78
CO_MemAVLNode * up
Definition: dmgr_mem_avltrees.h:121
CO_MemSizeAVLTree()
Definition: dmgr_mem_avltrees.h:345
Definition: covise_shm.h:379
void remove_nod(void)
Definition: dmgr_mem_avltrees.h:319
const int NO_OF_MEMCHUNKS
Definition: dmgr_mem_avltrees.h:53
shmSizeType size
Definition: dmgr_mem_avltrees.h:62
SizeOrderedTree()
Definition: dmgr_mem_avltrees.h:370
Definition: dmgr_mem_avltrees.h:243
int insert_chunk(MemChunk *data)
Definition: dmgr_mem_avltrees.h:380
GLuint address
Definition: khronos-glext.h:10368
Definition: dmgr_mem_avltrees.h:55
~CO_MemAddAVLTree()
Definition: dmgr_mem_avltrees.h:198
CO_MemAVLNode * right
Definition: dmgr_mem_avltrees.h:120
AddressOrderedTree()
Definition: dmgr_mem_avltrees.h:222
MemChunk * new_memchunk()
Definition: dmgr_mem_avltrees.cpp:89
int seq_no
Definition: dmgr_mem_avltrees.h:61
MemChunk * remove_chunk(MemChunk *data)
Definition: dmgr_mem_avltrees.h:232
GLdouble GLdouble right
Definition: khronos-glext.h:12128
void print()
Definition: dmgr_mem_avltrees.h:138
CO_MemAddAVLTree()
Definition: dmgr_mem_avltrees.h:196
SHMEXPORT SharedMemory * get_shared_memory()
Definition: covise_shm.cpp:88
CO_MemAVLTree()
Definition: dmgr_mem_avltrees.h:169
MemChunk * get_chunk(shmSizeType size_wanted)
Definition: dmgr_mem_avltrees.h:372
CO_MemSizeAVLNode * up
Definition: dmgr_mem_avltrees.h:248
Definition: dmgr_mem_avltrees.h:216
MemChunk * remove_chunk()
Definition: dmgr_mem_avltrees.h:282
CO_MemSizeAVLNode * best_node
Definition: dmgr_mem_avltrees.h:343
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: khronos-glext.h:6354
Definition: covise_shm.h:208
CO_MemSizeAVLNode * right
Definition: dmgr_mem_avltrees.h:247
unsigned int shmSizeType
Definition: covise_shm.h:202
MemChunk * node_list
Definition: dmgr_mem_avltrees.h:252