Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qmap.h

Source at commit 1406 created 12 years 10 months ago.
By meklort, Revert drivers.c so that kexts are only loaded when OSBundleRequired is set and that value is not safe mode. Added some comments about it too.
1/****************************************************************************␊
2** ␊
3**␊
4** Definition of QMap class␊
5**␊
6** Created : 990406␊
7**␊
8** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.␊
9**␊
10** This file is part of the tools module of the Qt GUI Toolkit.␊
11**␊
12** This file may be distributed under the terms of the Q Public License␊
13** as defined by Trolltech AS of Norway and appearing in the file␊
14** LICENSE.QPL included in the packaging of this file.␊
15**␊
16** This file may be distributed and/or modified under the terms of the␊
17** GNU General Public License version 2 as published by the Free Software␊
18** Foundation and appearing in the file LICENSE.GPL included in the␊
19** packaging of this file.␊
20**␊
21** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition␊
22** licenses may use this file in accordance with the Qt Commercial License␊
23** Agreement provided with the Software.␊
24**␊
25** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE␊
26** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.␊
27**␊
28** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for␊
29** information about Qt Commercial License Agreements.␊
30** See http://www.trolltech.com/qpl/ for QPL licensing information.␊
31** See http://www.trolltech.com/gpl/ for GPL licensing information.␊
32**␊
33** Contact info@trolltech.com if any conditions of this licensing are␊
34** not clear to you.␊
35**␊
36**********************************************************************/␊
37␊
38#ifndef QMAP_H␊
39#define QMAP_H␊
40␊
41#ifndef QT_H␊
42#include "qshared.h"␊
43#include "qdatastream.h"␊
44#endif // QT_H␊
45␊
46␊
47struct QMapNodeBase␊
48{␊
49 enum Color { Red, Black };␊
50␊
51 QMapNodeBase* left;␊
52 QMapNodeBase* right;␊
53 QMapNodeBase* parent;␊
54␊
55 Color color;␊
56␊
57 QMapNodeBase* minimum() {␊
58␉QMapNodeBase* x = this;␊
59␉while ( x->left )␊
60␉ x = x->left;␊
61␉return x;␊
62 }␊
63␊
64 QMapNodeBase* maximum() {␊
65␉QMapNodeBase* x = this;␊
66␉while ( x->right )␊
67␉ x = x->right;␊
68␉return x;␊
69 }␊
70};␊
71␊
72␊
73template <class K, class T>␊
74struct QMapNode : public QMapNodeBase␊
75{␊
76 QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }␊
77 QMapNode( const K& _key )␉ { key = _key; }␊
78 QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }␊
79 QMapNode() { }␊
80 T data;␊
81 K key;␊
82};␊
83␊
84␊
85template<class K, class T>␊
86class Q_EXPORT QMapIterator␊
87{␊
88 public:␊
89 /**␊
90 * Typedefs␊
91 */␊
92 typedef QMapNode< K, T >* NodePtr;␊
93␊
94 /**␊
95 * Variables␊
96 */␊
97 QMapNode<K,T>* node;␊
98␊
99 /**␊
100 * Functions␊
101 */␊
102 QMapIterator() : node( 0 ) {}␊
103 QMapIterator( QMapNode<K,T>* p ) : node( p ) {}␊
104 QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}␊
105␊
106 bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }␊
107 bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }␊
108 T& operator*() { return node->data; }␊
109 const T& operator*() const { return node->data; }␊
110␊
111 // Cannot have this - some compilers are too stupid␊
112 //T* operator->() const { return &(node->data); }␊
113␊
114 const K& key() const { return node->key; }␊
115 T& data() { return node->data; }␊
116 const T& data() const { return node->data; }␊
117␊
118private:␊
119 int inc() {␊
120␉QMapNodeBase* tmp = node;␊
121␉if ( tmp->right ) {␊
122␉ tmp = tmp->right;␊
123␉ while ( tmp->left )␊
124␉␉tmp = tmp->left;␊
125␉} else {␊
126␉ QMapNodeBase* y = tmp->parent;␊
127␉ while (tmp == y->right) {␊
128␉␉tmp = y;␊
129␉␉y = y->parent;␊
130␉ }␊
131␉ if (tmp->right != y)␊
132␉␉tmp = y;␊
133␉}␊
134␉node = (NodePtr)tmp;␊
135␉return 0;␊
136 }␊
137␊
138 int dec() {␊
139␉QMapNodeBase* tmp = node;␊
140␉if (tmp->color == QMapNodeBase::Red &&␊
141␉ tmp->parent->parent == tmp ) {␊
142␉ tmp = tmp->right;␊
143␉} else if (tmp->left != 0) {␊
144␉ QMapNodeBase* y = tmp->left;␊
145␉ while ( y->right )␊
146␉␉y = y->right;␊
147␉ tmp = y;␊
148␉} else {␊
149␉ QMapNodeBase* y = tmp->parent;␊
150␉ while (tmp == y->left) {␊
151␉␉tmp = y;␊
152␉␉y = y->parent;␊
153␉ }␊
154␉ tmp = y;␊
155␉}␊
156␉node = (NodePtr)tmp;␊
157␉return 0;␊
158 }␊
159␊
160public:␊
161 QMapIterator<K,T>& operator++() {␊
162␉inc();␊
163␉return *this;␊
164 }␊
165␊
166 QMapIterator<K,T> operator++(int) {␊
167␉QMapIterator<K,T> tmp = *this;␊
168␉inc();␊
169␉return tmp;␊
170 }␊
171␊
172 QMapIterator<K,T>& operator--() {␊
173␉dec();␊
174␉return *this;␊
175 }␊
176␊
177 QMapIterator<K,T> operator--(int) {␊
178␉QMapIterator<K,T> tmp = *this;␊
179␉dec();␊
180␉return tmp;␊
181 }␊
182};␊
183␊
184template<class K, class T>␊
185class Q_EXPORT QMapConstIterator␊
186{␊
187 public:␊
188 /**␊
189 * Typedefs␊
190 */␊
191 typedef QMapNode< K, T >* NodePtr;␊
192␊
193 /**␊
194 * Variables␊
195 */␊
196 QMapNode<K,T>* node;␊
197␊
198 /**␊
199 * Functions␊
200 */␊
201 QMapConstIterator() : node( 0 ) {}␊
202 QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}␊
203 QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}␊
204 QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}␊
205␊
206 bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }␊
207 bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }␊
208 const T& operator*() const { return node->data; }␊
209␊
210 // Cannot have this - some compilers are too stupid␊
211 //const T* operator->() const { return &(node->data); }␊
212␊
213 const K& key() const { return node->key; }␊
214 const T& data() const { return node->data; }␊
215␊
216private:␊
217 int inc() {␊
218 QMapNodeBase* tmp = node;␊
219␉if ( tmp->right ) {␊
220␉ tmp = tmp->right;␊
221␉ while ( tmp->left )␊
222␉␉tmp = tmp->left;␊
223␉} else {␊
224␉ QMapNodeBase* y = tmp->parent;␊
225␉ while (tmp == y->right) {␊
226␉␉tmp = y;␊
227␉␉y = y->parent;␊
228␉ }␊
229␉ if (tmp->right != y)␊
230␉␉tmp = y;␊
231␉}␊
232␉node = (NodePtr)tmp;␊
233␉return 0;␊
234 }␊
235␊
236 int dec() {␊
237␉QMapNodeBase* tmp = node;␊
238␉if (tmp->color == QMapNodeBase::Red &&␊
239␉ tmp->parent->parent == tmp ) {␊
240␉ tmp = tmp->right;␊
241␉} else if (tmp->left != 0) {␊
242␉ QMapNodeBase* y = tmp->left;␊
243␉ while ( y->right )␊
244␉␉y = y->right;␊
245␉ tmp = y;␊
246␉} else {␊
247␉ QMapNodeBase* y = tmp->parent;␊
248␉ while (tmp == y->left) {␊
249␉␉tmp = y;␊
250␉␉y = y->parent;␊
251␉ }␊
252␉ tmp = y;␊
253␉}␊
254␉node = (NodePtr)tmp;␊
255␉return 0;␊
256 }␊
257␊
258public:␊
259 QMapConstIterator<K,T>& operator++() {␊
260␉inc();␊
261␉return *this;␊
262 }␊
263␊
264 QMapConstIterator<K,T> operator++(int) {␊
265␉QMapConstIterator<K,T> tmp = *this;␊
266␉inc();␊
267␉return tmp;␊
268 }␊
269␊
270 QMapConstIterator<K,T>& operator--() {␊
271␉dec();␊
272␉return *this;␊
273 }␊
274␊
275 QMapConstIterator<K,T> operator--(int) {␊
276␉QMapConstIterator<K,T> tmp = *this;␊
277␉dec();␊
278␉return tmp;␊
279 }␊
280};␊
281␊
282␊
283class Q_EXPORT QMapPrivateBase : public QShared␊
284{␊
285public:␊
286 QMapPrivateBase() {␊
287␉node_count = 0;␊
288 }␊
289 QMapPrivateBase( const QMapPrivateBase* _map) {␊
290␉node_count = _map->node_count;␊
291 }␊
292␊
293 /**␊
294 * Implementations of basic tree algorithms␊
295 */␊
296 void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);␊
297 void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );␊
298 void rebalance( QMapNodeBase* x, QMapNodeBase*& root );␊
299 QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,␊
300␉␉␉␉ QMapNodeBase*& leftmost,␊
301␉␉␉␉ QMapNodeBase*& rightmost );␊
302␊
303 /**␊
304 * Variables␊
305 */␊
306 int node_count;␊
307};␊
308␊
309␊
310template <class Key, class T>␊
311class QMapPrivate : public QMapPrivateBase␊
312{␊
313public:␊
314 /**␊
315 * Typedefs␊
316 */␊
317 typedef QMapIterator< Key, T > Iterator;␊
318 typedef QMapConstIterator< Key, T > ConstIterator;␊
319 typedef QMapNode< Key, T > Node;␊
320 typedef QMapNode< Key, T >* NodePtr;␊
321␊
322 /**␊
323 * Functions␊
324 */␊
325 QMapPrivate() {␊
326␉header = new Node;␊
327␉header->color = QMapNodeBase::Red; // Mark the header␊
328␉header->parent = 0;␊
329␉header->left = header->right = header;␊
330 }␊
331 QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {␊
332␉header = new Node;␊
333␉header->color = QMapNodeBase::Red; // Mark the header␊
334␉if ( _map->header->parent == 0 ) {␊
335␉ header->parent = 0;␊
336␉ header->left = header->right = header;␊
337␉} else {␊
338␉ header->parent = copy( (NodePtr)(_map->header->parent) );␊
339␉ header->parent->parent = header;␊
340␉ header->left = header->parent->minimum();␊
341␉ header->right = header->parent->maximum();␊
342␉}␊
343 }␊
344 ~QMapPrivate() { clear(); delete header; }␊
345␊
346 NodePtr copy( NodePtr p ) {␊
347␉if ( !p )␊
348␉ return 0;␊
349␉NodePtr n = new Node( *p );␊
350␉n->color = p->color;␊
351␉if ( p->left ) {␊
352␉ n->left = copy( (NodePtr)(p->left) );␊
353␉ n->left->parent = n;␊
354␉} else {␊
355␉ n->left = 0;␊
356␉}␊
357␉if ( p->right ) {␊
358␉ n->right = copy( (NodePtr)(p->right) );␊
359␉ n->right->parent = n;␊
360␉} else {␊
361␉ n->right = 0;␊
362␉}␊
363␉return n;␊
364 }␊
365␊
366 void clear() {␊
367␉clear( (NodePtr)(header->parent) );␊
368␉header->color = QMapNodeBase::Red;␊
369␉header->parent = 0;␊
370␉header->left = header->right = header;␊
371␉node_count = 0;␊
372 }␊
373␊
374 void clear( NodePtr p ) {␊
375␉while ( p != 0 ) {␊
376␉ clear( (NodePtr)p->right );␊
377␉ NodePtr y = (NodePtr)p->left;␊
378␉ delete p;␊
379␉ p = y;␊
380␉}␊
381 }␊
382␊
383 Iterator begin()␉{ return Iterator( (NodePtr)(header->left ) ); }␊
384 Iterator end()␉{ return Iterator( header ); }␊
385 ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }␊
386 ConstIterator end() const { return ConstIterator( header ); }␊
387␊
388 ConstIterator find(const Key& k) const {␊
389␉QMapNodeBase* y = header; // Last node␊
390␉QMapNodeBase* x = header->parent; // Root node.␊
391␊
392␉while ( x != 0 ) {␊
393␉ // If as k <= key(x) go left␊
394␉ if ( !( key(x) < k ) ) {␊
395␉␉y = x;␊
396␉␉x = x->left;␊
397␉ } else {␊
398␉␉x = x->right;␊
399␉ }␊
400␉}␊
401␊
402␉// Was k bigger/smaller then the biggest/smallest␊
403␉// element of the tree ? Return end()␊
404␉if ( y == header || k < key(y) )␊
405␉ return ConstIterator( header );␊
406␉return ConstIterator( (NodePtr)y );␊
407 }␊
408␊
409 void remove( Iterator it ) {␊
410␉NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->right );␊
411␉delete del;␊
412␉--node_count;␊
413 }␊
414␊
415#ifdef QT_QMAP_DEBUG␊
416 void inorder( QMapNodeBase* x = 0, int level = 0 ){␊
417␉if ( !x )␊
418␉ x = header->parent;␊
419␉if ( x->left )␊
420␉ inorder( x->left, level + 1 );␊
421 //cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;␊
422␉if ( x->right )␊
423␉ inorder( x->right, level + 1 );␊
424 }␊
425#endif␊
426␊
427 Iterator insertMulti(const Key& v){␊
428␉QMapNodeBase* y = header;␊
429␉QMapNodeBase* x = header->parent;␊
430␉while (x != 0){␊
431␉ y = x;␊
432␉ x = ( v < key(x) ) ? x->left : x->right;␊
433␉}␊
434␉return insert(x, y, v);␊
435 }␊
436␊
437 Iterator insertSingle( const Key& k ) {␊
438␉// Search correct position in the tree␊
439␉QMapNodeBase* y = header;␊
440␉QMapNodeBase* x = header->parent;␊
441␉bool result = TRUE;␊
442␉while ( x != 0 ) {␊
443␉ result = ( k < key(x) );␊
444␉ y = x;␊
445␉ x = result ? x->left : x->right;␊
446␉}␊
447␉// Get iterator on the last not empty one␊
448␉Iterator j( (NodePtr)y );␊
449␉if ( result ) {␊
450␉ // Smaller then the leftmost one ?␊
451␉ if ( j == begin() ) {␊
452␉␉return insert(x, y, k );␊
453␉ } else {␊
454␉␉// Perhaps daddy is the right one ?␊
455␉␉--j;␊
456␉ }␊
457␉}␊
458␉// Really bigger ?␊
459␉if ( (j.node->key) < k )␊
460␉ return insert(x, y, k );␊
461␉// We are going to replace a node␊
462␉return j;␊
463 }␊
464␊
465 Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k ) {␊
466␉NodePtr z = new Node( k );␊
467␉if (y == header || x != 0 || k < key(y) ) {␊
468␉ y->left = z; // also makes leftmost = z when y == header␊
469␉ if ( y == header ) {␊
470␉␉header->parent = z;␊
471␉␉header->right = z;␊
472␉ } else if ( y == header->left )␊
473␉␉header->left = z; // maintain leftmost pointing to min node␊
474␉} else {␊
475␉ y->right = z;␊
476␉ if ( y == header->right )␊
477␉␉header->right = z; // maintain rightmost pointing to max node␊
478␉}␊
479␉z->parent = y;␊
480␉z->left = 0;␊
481␉z->right = 0;␊
482␉rebalance( z, header->parent );␊
483␉++node_count;␊
484␉return Iterator(z);␊
485 }␊
486␊
487protected:␊
488 /**␊
489 * Helpers␊
490 */␊
491 const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }␊
492␊
493 /**␊
494 * Variables␊
495 */␊
496 NodePtr header;␊
497};␊
498␊
499␊
500template<class Key, class T>␊
501class Q_EXPORT QMap␊
502{␊
503public:␊
504 /**␊
505 * Typedefs␊
506 */␊
507 typedef QMapIterator< Key, T > Iterator;␊
508 typedef QMapConstIterator< Key, T > ConstIterator;␊
509 typedef T ValueType;␊
510 typedef QMapPrivate< Key, T > Priv;␊
511␊
512 /**␊
513 * API␊
514 */␊
515 QMap() { sh = new QMapPrivate< Key, T >; }␊
516 QMap( const QMap<Key,T>& m ) { sh = m.sh; sh->ref(); }␊
517 ~QMap() { if ( sh->deref() ) delete sh; }␊
518␊
519 QMap<Key,T>& operator= ( const QMap<Key,T>& m )␊
520 { m.sh->ref(); if ( sh->deref() ) delete sh; sh = m.sh; return *this; }␊
521␊
522 Iterator begin() { detach(); return sh->begin(); }␊
523 Iterator end() { detach(); return sh->end(); }␊
524 ConstIterator begin() const { return ((const Priv*)sh)->begin(); }␊
525 ConstIterator end() const { return ((const Priv*)sh)->end(); }␊
526␊
527 Iterator find ( const Key& k )␊
528␉{ detach(); return Iterator( sh->find( k ).node ); }␊
529 ConstIterator find ( const Key& k ) const␊
530␉{ return sh->find( k ); }␊
531 T& operator[] ( const Key& k ) {␊
532␉detach(); QMapNode<Key,T>* p = sh->find( k ).node;␊
533␉if ( p != sh->end().node ) return p->data;␊
534␉return insert( k, T() ).data(); }␊
535 const T& operator[] ( const Key& k ) const␊
536␉{ return sh->find( k ).data(); }␊
537 bool contains ( const Key& k ) const␊
538␉{ return find( k ) != end(); }␊
539␉//{ return sh->find( k ) != ((const Priv*)sh)->end(); }␊
540␊
541 uint count() const { return sh->node_count; }␊
542␊
543 bool isEmpty() const { return sh->node_count == 0; }␊
544␊
545 Iterator insert( const Key& key, const T& value ) {␊
546 detach();␊
547 Iterator it = sh->insertSingle( key );␊
548 it.data() = value;␊
549 return it;␊
550 }␊
551␊
552 void remove( Iterator it ) { detach(); sh->remove( it ); }␊
553 void remove( const Key& k ) {␊
554 detach();␊
555 Iterator it( sh->find( k ).node );␊
556 if ( it != end() )␊
557 sh->remove( it );␊
558 }␊
559␊
560 Iterator replace( const Key& k, const T& v ) {␊
561␉remove( k );␊
562␉return insert( k, v );␊
563 }␊
564␊
565 void clear() { if ( sh->count == 1 ) sh->clear(); else { sh->deref(); sh = new QMapPrivate<Key,T>; } }␊
566␊
567#if defined(Q_FULL_TEMPLATE_INSTANTIATION)␊
568 bool operator==( const QMap<Key,T>& ) const { return FALSE; }␊
569#endif␊
570␊
571protected:␊
572 /**␊
573 * Helpers␊
574 */␊
575 void detach() { if ( sh->count > 1 ) { sh->deref(); sh = new QMapPrivate<Key,T>( sh ); } }␊
576␊
577 Priv* sh;␊
578};␊
579␊
580␊
581#ifndef QT_NO_DATASTREAM␊
582template<class Key, class T>␊
583inline QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {␊
584 m.clear();␊
585 Q_UINT32 c;␊
586 s >> c;␊
587 for( Q_UINT32 i = 0; i < c; ++i ) {␊
588␉Key k; T t;␊
589␉s >> k >> t;␊
590␉m.insert( k, t );␊
591 }␊
592 return s;␊
593}␊
594␊
595␊
596template<class Key, class T>␊
597inline QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {␊
598 s << (Q_UINT32)m.count();␊
599 QMapConstIterator<Key,T> it = m.begin();␊
600 for( ; it != m.end(); ++it )␊
601␉s << it.key() << it.data();␊
602 return s;␊
603}␊
604#endif␊
605␊
606#endif // QMAP_H␊
607

Archive Download this file

Revision: 1406