]> git.saurik.com Git - wxWidgets.git/blame - utils/HelpGen/src/wxstlac.h
projects / wxWidgets.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
attempts to fix recursive mutex initialized detection under RedHat 7.1 (new glibc)
[wxWidgets.git] / utils / HelpGen / src / wxstlac.h
CommitLineData
cecfc5e7
VZ		 1/////////////////////////////////////////////////////////////////////////////
2// Name: No names yet.
3// Purpose: Contrib. demo
4// Author: Aleksandras Gluchovas
5// Modified by:
6// Created: 27/09/98
7// RCS-ID: $Id$
8// Copyright: (c) Aleskandars Gluchovas
9// Licence: wxWindows licence
10/////////////////////////////////////////////////////////////////////////////
11
12#ifndef __WXSTLAC_G__
13#define __WXSTLAC_G__
14
3d05544e
JS		 15#ifdef new
16#undef new
17#endif
18
cecfc5e7
VZ		 19#include <stddef.h>
20#include <sys/types.h>
21#include <memory.h>
22#include <limits.h>
23#include <new.h>
24
cecfc5e7
VZ		 25// the below macro used internally (see actual interface after this macro)
26
27// arguments:
28//
29// ARG_IS_UNIQUE
30// ASSOC_CONT_CLASS_NAME
31//
32// ARG_VALUE_TYPE
33// ARG_KEY_TYPE
34// ARG_ACTUAL_VALUE_TYPE
35//
36// _KEY_NAME
37// _VALUE_NAME
38//
39// _X_KEY_NAME
40// _X_VALUE_NAME
41//
42// _INSERT_METHOD_DEFINITION
43
44#define __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE, \
45FUNCTOR,\
46ASSOC_CONT_CLASS_NAME, \
47ARG_VALUE_TYPE, \
48ARG_KEY_TYPE, \
49ARG_ACTUAL_VALUE_TYPE, \
50_KEY_NAME, \
51_VALUE_NAME, \
52_X_KEY_NAME, \
53_X_VALUE_NAME, \
54_INSERT_METHOD_DEFINITION \
55) class \
56ASSOC_CONT_CLASS_NAME\
57{\
58protected:\
59\
60public:\
61 typedef ARG_VALUE_TYPE value_type;\
62 typedef ARG_KEY_TYPE key_type;\
63 typedef ARG_ACTUAL_VALUE_TYPE actual_value_type;\
64\
65 typedef value_type* pointer;\
66 typedef value_type& reference;\
67\
68 typedef const value_type& const_reference;\
69\
70 typedef FUNCTOR key_compare;\
71 typedef key_compare Compare;\
72\
73protected:\
74\
75 struct tree_node \
76 {\
77 tree_node* mpParent;\
78 tree_node* mpLeft;\
79 tree_node* mpRight;\
80\
81 value_type mData;\
82 };\
83\
84 typedef tree_node* node_ref_type;\
85\
86 node_ref_type mpRoot;\
87 node_ref_type mpLeftMost;\
88 node_ref_type mpRightMost;\
89\
90 node_ref_type mpFreeListHead;\
91 int mKeyIsUnique;\
92\
93 key_compare mCmpFunctorObj;\
94\
95public:\
96\
97 static inline node_ref_type next( node_ref_type pNode )\
98 {\
99 if ( pNode->mpRight ) \
100 {\
101 pNode = pNode->mpRight;\
102\
103 while ( pNode->mpLeft ) pNode = pNode->mpLeft;\
104\
105 return pNode;\
106 }\
107 else\
108 if ( pNode->mpParent )\
109 {\
110 if ( pNode == pNode->mpParent->mpLeft )\
111\
112 return pNode->mpParent;\
113\
114 pNode = pNode->mpParent;\
115\
116 node_ref_type prevNode = pNode;\
117 pNode = pNode->mpParent;\
118\
119 while(pNode)\
120 {\
121 if ( pNode->mpRight &&\
122 pNode->mpRight != prevNode\
123 ) return pNode;\
124\
125 prevNode = pNode;\
126 pNode= pNode->mpParent;\
127 }\
128\
129 return 0;\
130 }\
131 else\
132 return 0;\
133 }\
134\
135 static inline node_ref_type prev( node_ref_type pNode )\
136 {\
137 if ( pNode->mpLeft ) \
138 {\
139 pNode = pNode->mpLeft;\
140\
141 while ( pNode->mpRight ) pNode = pNode->mpRight;\
142\
143 return pNode;\
144 }\
145 else\
146 if ( pNode->mpParent )\
147 {\
148 if ( pNode == pNode->mpParent->mpRight )\
149 return pNode->mpParent;\
150\
151 pNode = pNode->mpParent;\
152\
153 node_ref_type prevNode = pNode;\
154 pNode = pNode->mpParent;\
155\
156 while(pNode)\
157 {\
158 if ( pNode->mpLeft &&\
159 pNode->mpLeft != prevNode\
160 ) return pNode;\
161\
162 prevNode = pNode;\
163 pNode= pNode->mpParent;\
164 }\
165\
166 return 0;\
167 }\
168 else \
169 return 0;\
170 }\
171\
172protected:\
173\
174 inline int are_equel( const key_type& x, const key_type& y )\
175 {\
176 return ( !mCmpFunctorObj(x,y) && !mCmpFunctorObj(y,x) );\
177 }\
178\
179 inline int is_less( const key_type& x, const key_type& y )\
180 {\
181 return mCmpFunctorObj(x,y);\
182 }\
183\
184 static inline const actual_value_type& value( node_ref_type pNode )\
185 {\
186 return pNode->_VALUE_NAME;\
187 }\
188\
189 static inline const key_type& key( node_ref_type pNode )\
190 {\
191 return pNode->_KEY_NAME;\
192 }\
193\
194 inline node_ref_type AllocNode() \
195 { \
196 if ( mpFreeListHead ) \
197 {\
198 node_ref_type pFreeNode = mpFreeListHead;\
199 mpFreeListHead = mpFreeListHead->mpLeft;\
200\
201 return pFreeNode;\
202 }\
203 else\
204 {\
205 char* pHeapBlock = new char[sizeof(tree_node)];\
206\
207 return (node_ref_type)pHeapBlock;\
208 }\
209 }\
210\
211 inline void DestroyFreeList()\
212 {\
213 while ( mpFreeListHead )\
214 {\
215 node_ref_type tmp = mpFreeListHead;\
216 mpFreeListHead = mpFreeListHead->mpLeft;\
217\
218 delete [](char*)tmp;\
219 }\
220 }\
221\
222 inline void RecycleNode( node_ref_type pNode ) \
223 {\
224 pNode->mpLeft = mpFreeListHead;\
225 mpFreeListHead = pNode;\
226 }\
227\
228 inline node_ref_type do_insert(const value_type& x = value_type() )\
229 {\
230 node_ref_type pNewNode = AllocNode();\
231\
232 pNewNode->mpParent = \
233 pNewNode->mpLeft =\
234 pNewNode->mpRight = 0;\
235\
236 node_ref_type pCurrent = mpRoot;\
237 node_ref_type pParent = 0;\
238 \
239 while (pCurrent) \
240 {\
241 if ( mKeyIsUnique && are_equel( _X_KEY_NAME, value(pCurrent) ) )\
242 {\
243 RecycleNode(pNewNode);\
244 return 0;\
245 }\
246\
247 pParent = pCurrent;\
248\
249 pCurrent = is_less( _X_KEY_NAME, value(pCurrent) ) \
250 ? pCurrent->mpLeft \
251 : pCurrent->mpRight;\
252 }\
253 \
254 pNewNode->mpParent = pParent;\
255\
256 if(pParent)\
257\
258 if( is_less(_X_KEY_NAME, value(pParent) ) )\
259 \
260 pParent->mpLeft = pNewNode;\
261 else\
262 pParent->mpRight = pNewNode;\
263 else\
264 mpRoot = pNewNode;\
265\
266 new ( &pNewNode->_KEY_NAME ) key_type(_X_KEY_NAME);\
267 new ( &pNewNode->_VALUE_NAME ) actual_value_type(_X_VALUE_NAME);\
268\
269 if ( prev(pNewNode) == 0 ) mpLeftMost = pNewNode;\
270 if ( next(pNewNode) == 0 ) mpRightMost = pNewNode;\
271\
272 return pNewNode;\
273 }\
274\
275 friend class iterator;\
276\
277public:\
278\
279 class iterator;\
280 class const_iterator;\
281\
282 class iterator \
283 {\
284 public:\
285 node_ref_type mpNode;\
286 friend class CONT_CLASS_NAME;\
287 friend class const_iterator;\
288 friend class const_reverse_iterator;\
289\
290 inline iterator( node_ref_type pNode )\
291 {\
292 mpNode = pNode;\
293 }\
294 \
295 public:\
296 inline iterator() {}\
297 inline int operator==( const iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
298 inline int operator!=( const iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
299\
300 inline iterator( const iterator& other )\
301 {\
302 mpNode = other.mpNode;\
303 }\
304\
305 inline const iterator& operator=( const iterator& other )\
306 {\
307 mpNode = other.mpNode;\
308 return *this;\
309 }\
310\
311 inline const iterator& operator--() \
312 {\
313 mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
314 return *this;\
315 }\
316\
317 inline iterator operator--(int)\
318 {\
319 iterator tmp = *this;\
320 mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
321 return tmp;\
322 }\
323\
324 inline const iterator& operator++() \
325 {\
326 mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
327 return *this;\
328 }\
329\
330 inline iterator operator++(int)\
331 {\
332 iterator tmp = *this;\
333 mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
334 return tmp;\
335 }\
336\
337 inline reference operator*() const { return mpNode->mData; }\
338 };\
339\
340\
341 class const_iterator \
342 {\
343 public:\
344 node_ref_type mpNode;\
345 friend class CONT_CLASS_NAME;\
346 friend class const_reverse_iterator;\
347\
348 inline const_iterator( node_ref_type pNode )\
349 {\
350 mpNode = pNode;\
351 }\
352 \
353 public:\
354 inline const_iterator() {}\
355\
356 inline int operator==( const const_iterator& rhs ) const { return (mpNode == rhs.mpNode); }\
357 inline int operator!=( const const_iterator& rhs ) const { return (mpNode != rhs.mpNode); }\
358\
359 inline const_iterator( const iterator& other )\
360 {\
361 mpNode = other.mpNode;\
362 }\
363\
364 inline const_iterator( const const_iterator& other )\
365 {\
366 mpNode = other.mpNode;\
367 }\
368\
369 inline const const_iterator& operator=( const const_iterator& other )\
370 {\
371 mpNode = other.mpNode;\
372 return *this;\
373 }\
374\
375 inline const const_iterator& operator--() \
376 {\
377 mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
378 return *this;\
379 }\
380\
381 inline const_iterator operator--(int)\
382 {\
383 const_iterator tmp = *this;\
384 mpNode = ASSOC_CONT_CLASS_NAME::prev(mpNode);\
385 return tmp;\
386 }\
387\
388 inline const const_iterator& operator++() \
389 {\
390 mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
391 return *this;\
392 }\
393\
394 inline const_iterator operator++(int)\
395 {\
396 const_iterator tmp = *this;\
397 mpNode = ASSOC_CONT_CLASS_NAME::next(mpNode);\
398 return tmp;\
399 }\
400\
401 inline const_reference operator*() const { return mpNode->mData; }\
402 };\
403\
404public:\
405\
406 inline ASSOC_CONT_CLASS_NAME( key_compare cmpFunctorObj = key_compare(),\
407 int keyIsUnique = ARG_IS_UNIQUE )\
408 : mpFreeListHead( 0 ),\
409 mKeyIsUnique( keyIsUnique ),\
410 mCmpFunctorObj( cmpFunctorObj )\
411 {\
412 mpLeftMost = 0;\
413 mpRightMost = 0;\
414 mpRoot = 0;\
415 }\
416\
417 inline ~ASSOC_CONT_CLASS_NAME() \
418 { \
419 erase( begin(), end() ); \
420\
421 DestroyFreeList();\
422 }\
423\
424 inline iterator begin() { return mpLeftMost; }\
425 inline iterator end() { return 0; }\
426\
427 inline const_iterator begin() const { return mpLeftMost; }\
428 inline const_iterator end() const { return 0; }\
429\
430 inline iterator lower_bound( const key_type& x )\
431 { \
432 node_ref_type pCurrent = mpRoot;\
433 \
434 while( pCurrent )\
435 {\
436 node_ref_type pParent = pCurrent;\
437\
438 if( are_equel( x, key(pCurrent) ) )\
439 \
440 return (pCurrent);\
441 else\
442 pCurrent = is_less( x, key(pCurrent) ) \
443 ? pCurrent->mpLeft \
444 : pCurrent->mpRight;\
445\
446 if ( !pCurrent ) return (pParent);\
447 }\
448\
449 return begin();\
450 }\
451\
452 inline const_iterator lower_bound( const key_type& x ) const\
453\
454 { return const_iterator( lower_bound(x).mpNode ); }\
455\
456 inline iterator upper_bound( const key_type& x )\
457 {\
458 node_ref_type pCurrent = mpRoot;\
459 \
460 while( pCurrent )\
461 {\
462 node_ref_type pParent = pCurrent;\
463\
464 if( are_equel( x, key(pCurrent) ) )\
465 \
466 return (pCurrent);\
467 else\
468 pCurrent = is_less( x, key(pCurrent) ) \
469 ? pCurrent->mpLeft \
470 : pCurrent->mpRight;\
471\
472 if ( !pCurrent ) return next(pParent);\
473 }\
474\
475 return end();\
476 }\
477\
478 inline const_iterator upper_bound( const key_type& x ) const\
479\
480 { return const_iterator( upper_bound(x).mpNode ); }\
481\
482 inline iterator find( const key_type& x )\
483 {\
484 node_ref_type pCurrent = mpRoot;\
485 \
486 while( pCurrent )\
487 {\
488 if( are_equel( x, key(pCurrent) ) )\
489 \
490 return (pCurrent);\
491 else\
492 pCurrent = is_less( x, key(pCurrent) ) \
493 ? pCurrent->mpLeft \
494 : pCurrent->mpRight;\
495 }\
496\
497 return end();\
498 }\
499\
500 inline const_iterator find( const key_type& x ) const\
501\
502 { return const_iterator( find(x).mpNode ); }\
503\
504 inline void erase(iterator first, iterator last)\
505 {\
506 if ( first.mpNode == 0 ) return;\
507\
508 while( first != last ) \
509 {\
510 iterator next = first;\
511 ++next;\
512 erase( first );\
513 first = next;\
514 }\
515 }\
516\
517 inline void erase(iterator position)\
518 {\
519 if ( position.mpNode == 0 ) return;\
520\
521 node_ref_type pZ = position.mpNode;\
522 node_ref_type pX, pY;\
523\
524 if ( pZ == mpLeftMost ) mpLeftMost = next(pZ);\
525 if ( pZ == mpRightMost ) mpRightMost = prev( pZ );\
526\
527 if ( !pZ->mpLeft || !pZ->mpRight )\
528 \
529 pY = pZ;\
530 else \
531 {\
532 pY = pZ->mpRight;\
533 \
534 while (pY->mpLeft) \
535 \
536 pY = pY->mpLeft;\
537 }\
538 \
539 if ( pY->mpLeft)\
540 \
541 pX = pY->mpLeft;\
542 else\
543 pX = pY->mpRight;\
544 \
545 if ( pX ) pX->mpParent = pY->mpParent;\
546 \
547 if (pY->mpParent)\
548 \
549 if (pY == pY->mpParent->mpLeft )\
550 \
551 pY->mpParent->mpLeft = pX;\
552 else\
553 pY->mpParent->mpRight = pX;\
554 else\
555 mpRoot = pX;\
556 \
557 node_ref_type toRemove = 0;\
558 \
559 if (pY != pZ) {\
560 \
561 pY->mpLeft = pZ->mpLeft;\
562 \
563 if (pY->mpLeft) pY->mpLeft->mpParent = pY;\
564 \
565 pY->mpRight = pZ->mpRight;\
566 \
567 if ( pY->mpRight ) \
568 \
569 pY->mpRight->mpParent = pY;\
570 \
571 pY->mpParent = pZ->mpParent;\
572 \
573 if (pZ->mpParent)\
574 \
575 if (pZ == pZ->mpParent->mpLeft)\
576 \
577 pZ->mpParent->mpLeft = pY;\
578 else\
579 pZ->mpParent->mpRight = pY;\
580 else\
581 mpRoot = pY;\
582 \
583 toRemove = pZ;\
584 } \
585 else \
586 toRemove = pY;\
587 \
588 value(toRemove).~actual_value_type();\
589 key(toRemove).~actual_value_type();\
590\
591 RecycleNode( toRemove );\
592 }\
593\
594 _INSERT_METHOD_DEFINITION\
595}
596
597// do not undefine ___WXSTL_COMMA, where associated containers are defined!
598// (it is used as workaround for constraints of C-Preprocessor's nested macros)
599
600#define ___WXSTL_COMMA ,
601
602#define __DEFINE_MAP(ARG_IS_UNIQUE, KEY_TYPE, VAL_TYPE, FUNCTOR ) __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
603FUNCTOR,\
604__WXSTLMAP_##KEY_TYPE##VAL_TYPE##ARG_IS_UNIQUE, \
605struct key_value_pair { KEY_TYPE first ; \
606 VAL_TYPE second;\
607 key_value_pair() {}\
608 key_value_pair( const KEY_TYPE& key ___WXSTL_COMMA const VAL_TYPE& value ) \
609 : first(key) ___WXSTL_COMMA second( value ) {} \
610 } , \
611KEY_TYPE,\
612VAL_TYPE,\
613mData.first, mData.second, x.first, x.second, \
614struct insert_result_iterator\
615{\
616 iterator first;\
617 int second;\
618};\
619inline insert_result_iterator insert( const value_type& x )\
620{\
621 insert_result_iterator result;\
622\
623 result.first = do_insert(x);\
624 result.second = ( result.first == end() ) ? 0 : 1;\
625\
626 return result;\
627} )
628
629#define __DEFINE_SET(ARG_IS_UNIQUE, KEY_TYPE, FUNCTOR ) __DEFINE_ASOC_CLASS( ARG_IS_UNIQUE,\
630FUNCTOR,\
631__WXSTLSET_##TYPE##ARG_IS_UNIQUE, \
632KEY_TYPE,\
633KEY_TYPE,\
634KEY_TYPE,\
635mData, mData, x, x, \
636struct insert_result_iterator\
637{\
638 iterator first;\
639 int second;\
640};\
641inline insert_result_iterator insert( const value_type& x )\
642{\
643 insert_result_iterator result;\
644\
645 result.first = do_insert(x);\
646 result.second = ( result.first == end() ) ? 0 : 1;\
647\
648 return result;\
649} )
650
651// helper macros to create functor objects for associative containers of the given type
652
653#define LESS_THEN_FUNCTOR(TYPE) struct \
654{ inline int operator()(const TYPE& x, const TYPE& y ) const { return x < y; } }
655
656#define GREATER_THEN_FUNCTOR(TYPE) struct \
657{ inline int operator()(const TYPE& x, const TYPE& y ) const { return x > y; } }
658
659// functor argument should be created using the two above macros
660// or passing own class with method "operator()(const TYPE&,cosnt TYPE&)" defined in it
661
662#define WXSTL_MAP( KEY_TYPE, VALUE_TYPE, FUNCTOR ) __DEFINE_MAP( 1 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
663#define WXSTL_MULTIMAP( KEY_TYPE, VALUE_TYPE, FUNCTOR ) __DEFINE_MAP( 0 ,KEY_TYPE, VALUE_TYPE, FUNCTOR)
664#define WXSTL_SET( KEY_TYPE, FUNCTOR ) __DEFINE_SET( 1 ,KEY_TYPE, FUNCTOR )
665#define WXSTL_MULTISET( KEY_TYPE, FUNCTOR ) __DEFINE_SET( 0 ,KEY_TYPE, FUNCTOR )
666
667#endif
wxWidgets (Impactor)