00001 /* 00002 * Copyright 1999-2004 The Apache Software Foundation. 00003 * 00004 * Licensed under the Apache License, Version 2.0 (the "License"); 00005 * you may not use this file except in compliance with the License. 00006 * You may obtain a copy of the License at 00007 * 00008 * http://www.apache.org/licenses/LICENSE-2.0 00009 * 00010 * Unless required by applicable law or agreed to in writing, software 00011 * distributed under the License is distributed on an "AS IS" BASIS, 00012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00013 * See the License for the specific language governing permissions and 00014 * limitations under the License. 00015 */ 00016 00017 #if !defined(XALANMAP_HEADER_GUARD_1357924680) 00018 #define XALANMAP_HEADER_GUARD_1357924680 00019 00020 00021 // Base include file. Must be first. 00022 #include <xalanc/Include/PlatformDefinitions.hpp> 00023 00024 00025 00026 #include <cstddef> 00027 #include <algorithm> 00028 #include <functional> 00029 #include <utility> 00030 00031 00032 #include <xalanc/Include/XalanVector.hpp> 00033 #include <xalanc/Include/XalanList.hpp> 00034 00035 00036 00037 XALAN_CPP_NAMESPACE_BEGIN 00038 00039 #if defined(_MSC_VER) 00040 #pragma warning(push) 00041 #pragma warning(disable: 4189) 00042 #endif 00043 00044 typedef size_t size_type; 00045 00046 template <class Key> 00047 class XalanHasher : public XALAN_STD_QUALIFIER unary_function<Key, size_type> 00048 { 00049 public: 00050 size_type operator()(const Key& key) const 00051 { 00052 const char *byteArray = reinterpret_cast<const char*>(&key); 00053 00054 size_type result = 0; 00055 00056 for (size_type i = 0; i < sizeof(Key); ++i) 00057 { 00058 result = (result << 1) ^ byteArray[i]; 00059 } 00060 00061 return result; 00062 } 00063 }; 00064 00065 template <class Key> 00066 struct XalanMapKeyTraits 00067 { 00068 typedef XalanHasher<Key> Hasher; 00069 typedef XALAN_STD_QUALIFIER equal_to<Key> Comparator; 00070 }; 00071 00072 00073 template <class Key> 00074 struct XalanHashMemberPointer 00075 { 00076 00077 size_type operator() (const Key * key) const 00078 { 00079 assert (key != 0); 00080 return key->hash(); 00081 } 00082 }; 00083 00084 template <class Key> 00085 struct XalanHashMemberReference 00086 { 00087 00088 size_type operator() (const Key& key) const 00089 { 00090 return key.hash(); 00091 } 00092 }; 00093 00094 00095 00096 template <class Value> 00097 struct XalanMapIteratorTraits 00098 { 00099 typedef Value value_type; 00100 typedef Value& reference; 00101 typedef Value* pointer; 00102 }; 00103 00104 template <class Value> 00105 struct XalanMapConstIteratorTraits 00106 { 00107 typedef Value value_type; 00108 typedef const Value& reference; 00109 typedef const Value* pointer; 00110 }; 00111 00112 template <class XalanMapTraits, class BaseIterator> 00113 struct XalanMapIterator 00114 { 00115 typedef typename XalanMapTraits::value_type value_type; 00116 typedef typename XalanMapTraits::reference reference; 00117 typedef typename XalanMapTraits::pointer pointer; 00118 00119 typedef ptrdiff_t difference_type; 00120 typedef XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category; 00121 00122 typedef XalanMapIterator< 00123 XalanMapIteratorTraits<value_type>, 00124 BaseIterator> Iterator; 00125 00126 XalanMapIterator(const Iterator & theRhs) : 00127 baseIterator(theRhs.baseIterator) 00128 { 00129 } 00130 00131 XalanMapIterator(const BaseIterator & theRhs) : 00132 baseIterator(theRhs) 00133 { 00134 } 00135 00136 XalanMapIterator operator++(int) 00137 { 00138 XalanMapIterator temp(*this); 00139 ++baseIterator; 00140 return temp; 00141 } 00142 00143 XalanMapIterator& operator++() 00144 { 00145 ++baseIterator; 00146 return *this; 00147 } 00148 00149 reference operator*() const 00150 { 00151 return *baseIterator->value; 00152 } 00153 00154 pointer operator->() const 00155 { 00156 return baseIterator->value; 00157 } 00158 00159 bool operator==(const XalanMapIterator& theRhs) const 00160 { 00161 return theRhs.baseIterator == baseIterator; 00162 } 00163 00164 bool operator!=(const XalanMapIterator& theRhs) const 00165 { 00166 return !(theRhs == *this); 00167 } 00168 00169 BaseIterator baseIterator; 00170 }; 00171 00172 00173 00178 template < 00179 class Key, 00180 class Value, 00181 class KeyTraits = XalanMapKeyTraits<Key> > 00182 class XalanMap 00183 { 00184 public: 00193 typedef Key key_type; 00194 typedef Value data_type; 00195 typedef size_t size_type; 00196 00197 typedef XALAN_STD_QUALIFIER pair<const key_type, data_type> value_type; 00198 00199 struct Entry 00200 { 00201 value_type* value; 00202 bool erased; 00203 00204 Entry(value_type* theValue) : 00205 value(theValue), 00206 erased(false) 00207 { 00208 } 00209 }; 00210 00211 typedef XalanList<Entry> EntryListType; 00212 00213 typedef XalanVector<typename EntryListType::iterator> BucketType; 00214 typedef XalanVector<BucketType, ConstructWithMemoryManagerTraits<BucketType> > BucketTableType; 00215 00216 typedef XalanMapIterator< 00217 XalanMapIteratorTraits<value_type>, 00218 typename EntryListType::iterator> iterator; 00219 typedef XalanMapIterator< 00220 XalanMapConstIteratorTraits<value_type>, 00221 typename EntryListType::iterator> const_iterator; 00222 00223 typedef typename MemoryManagedConstructionTraits<key_type>::Constructor FirstConstructor; 00224 typedef typename MemoryManagedConstructionTraits<data_type>::Constructor SecondConstructor; 00225 00226 XalanMap( 00227 MemoryManagerType& theMemoryManager, 00228 float loadFactor = 0.75, 00229 size_type minBuckets = 10) : 00230 m_memoryManager(&theMemoryManager), 00231 m_loadFactor(loadFactor), 00232 m_minBuckets(minBuckets), 00233 m_size(0), 00234 m_entries(theMemoryManager), 00235 m_freeEntries(theMemoryManager), 00236 m_buckets(theMemoryManager) 00237 { 00238 } 00239 00240 XalanMap( 00241 const XalanMap &theRhs, 00242 MemoryManagerType& theMemoryManager) : 00243 m_memoryManager(&theMemoryManager), 00244 m_loadFactor(theRhs.m_loadFactor), 00245 m_minBuckets(10), 00246 m_size(0), 00247 m_entries(theMemoryManager), 00248 m_freeEntries(theMemoryManager), 00249 m_buckets(size_type(m_loadFactor * theRhs.size())+ 1, BucketType(*m_memoryManager), theMemoryManager) 00250 { 00251 const_iterator entry = theRhs.begin(); 00252 while(entry != theRhs.end()) 00253 { 00254 insert(*entry); 00255 ++entry; 00256 } 00257 00258 assert(m_size == theRhs.m_size); 00259 } 00260 00261 MemoryManagerType& 00262 getMemoryManager() 00263 { 00264 assert (m_memoryManager != 0); 00265 00266 return *m_memoryManager; 00267 } 00268 00269 ~XalanMap() 00270 { 00271 doRemoveEntries(); 00272 00273 if (!m_buckets.empty()) 00274 { 00275 typename EntryListType::iterator toRemove = m_freeEntries.begin(); 00276 while(toRemove != m_freeEntries.end()) 00277 { 00278 deallocate(toRemove->value); 00279 ++toRemove; 00280 } 00281 } 00282 } 00283 00284 XalanMap & operator=(const XalanMap& theRhs) 00285 { 00286 XalanMap theTemp(theRhs, *m_memoryManager); 00287 swap(theTemp); 00288 return *this; 00289 } 00290 00291 size_type size() const 00292 { 00293 return m_size; 00294 } 00295 00296 bool empty() const 00297 { 00298 return m_size == 0; 00299 } 00300 00301 iterator begin() 00302 { 00303 return m_entries.begin(); 00304 } 00305 00306 const_iterator begin() const 00307 { 00308 return const_cast<XalanMap*>(this)->begin(); 00309 } 00310 00311 iterator end() 00312 { 00313 return m_entries.end(); 00314 } 00315 00316 const_iterator end() const 00317 { 00318 return const_cast<XalanMap*>(this)->end(); 00319 } 00320 00321 iterator find(const key_type& key) 00322 { 00323 if (!m_buckets.empty()) 00324 { 00325 const size_type index = doHash(key); 00326 assert(index < m_buckets.size()); 00327 00328 BucketType & bucket = m_buckets[index]; 00329 typename BucketType::iterator pos = bucket.begin(); 00330 00331 while (pos != bucket.end()) 00332 { 00333 if (!(*pos)->erased && m_equals(key, (*pos)->value->first)) 00334 { 00335 return iterator(*pos); 00336 } 00337 ++pos; 00338 } 00339 } 00340 00341 return end(); 00342 } 00343 00344 const_iterator find(const key_type& key) const 00345 { 00346 return const_cast<XalanMap *>(this)->find(key); 00347 } 00348 00349 data_type & operator[](const key_type& key) 00350 { 00351 iterator pos = find(key); 00352 00353 if (pos == end()) 00354 { 00355 pos = doCreateEntry(key); 00356 } 00357 00358 return (*pos).second; 00359 } 00360 00361 void insert(const value_type& value) 00362 { 00363 const key_type& key = value.first; 00364 const data_type& data = value.second; 00365 00366 insert(key, data); 00367 } 00368 00369 void insert(const key_type& key, const data_type& data) 00370 { 00371 const const_iterator pos = find(key); 00372 00373 if (pos == end()) 00374 { 00375 doCreateEntry(key, &data); 00376 } 00377 } 00378 00379 void erase(iterator pos) 00380 { 00381 if (pos != end()) 00382 { 00383 doRemoveEntry(pos); 00384 } 00385 } 00386 00387 size_type erase(const key_type& key) 00388 { 00389 const iterator pos = find(key); 00390 00391 if (pos != end()) 00392 { 00393 erase(pos); 00394 return 1; 00395 } 00396 else 00397 { 00398 return 0; 00399 } 00400 } 00401 00402 void clear() 00403 { 00404 doRemoveEntries(); 00405 00406 typename BucketTableType::iterator bucketPos = m_buckets.begin(); 00407 while (bucketPos != m_buckets.end()) 00408 { 00409 bucketPos->clear(); 00410 ++bucketPos; 00411 } 00412 00413 assert(0 == m_size); 00414 assert(m_entries.empty()); 00415 } 00416 00417 void swap(XalanMap& theRhs) 00418 { 00419 size_type tempSize = m_size; 00420 m_size = theRhs.m_size; 00421 theRhs.m_size = tempSize; 00422 00423 MemoryManagerType* tempMemoryManager = m_memoryManager; 00424 m_memoryManager = theRhs.m_memoryManager; 00425 theRhs.m_memoryManager = tempMemoryManager; 00426 00427 m_entries.swap(theRhs.m_entries); 00428 m_freeEntries.swap(theRhs.m_freeEntries); 00429 m_buckets.swap(theRhs.m_buckets); 00430 } 00431 00432 protected: 00433 00434 iterator doCreateEntry(const key_type & key, const data_type* data = 0) 00435 { 00436 // if there are no buckets, create initial minimum set of buckets 00437 if (m_buckets.empty()) 00438 { 00439 m_buckets.insert(m_buckets.begin(), m_minBuckets, BucketType(*m_memoryManager)); 00440 } 00441 00442 // if the load factor has been reached, rehash 00443 if (size_type(m_loadFactor * size()) > m_buckets.size()) 00444 { 00445 rehash(); 00446 } 00447 00448 size_type index = doHash(key); 00449 00450 00451 if (m_freeEntries.empty()) 00452 { 00453 m_freeEntries.push_back(Entry(allocate(1))); 00454 } 00455 00456 // insert a new entry as the first position in the bucket 00457 Entry& newEntry = m_freeEntries.back(); 00458 newEntry.erased = false; 00459 00460 FirstConstructor::construct(const_cast<key_type*>(&newEntry.value->first), key, *m_memoryManager); 00461 if (data != 0) 00462 { 00463 SecondConstructor::construct(&newEntry.value->second, *data, *m_memoryManager); 00464 } 00465 else 00466 { 00467 SecondConstructor::construct(&newEntry.value->second, *m_memoryManager); 00468 } 00469 00470 00471 m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end()); 00472 00473 m_buckets[index].push_back(--m_entries.end()); 00474 00475 ++m_size; 00476 00477 return iterator(--m_entries.end()); 00478 } 00479 00480 void doRemoveEntry(const iterator & toRemovePos) 00481 { 00482 value_type& toRemove = *toRemovePos; 00483 #if defined(_MSC_VER) && _MSC_VER <= 1300 00484 toRemove.value_type::~value_type(); 00485 #else 00486 toRemove.~value_type(); 00487 #endif 00488 m_freeEntries.splice( 00489 m_freeEntries.end(), 00490 m_entries, 00491 toRemovePos.baseIterator); 00492 00493 toRemovePos.baseIterator->erased = true; 00494 00495 --m_size; 00496 } 00497 00498 void 00499 doRemoveEntries() 00500 { 00501 while(size() > 0) 00502 { 00503 doRemoveEntry(begin()); 00504 } 00505 } 00506 00507 size_type doHash(const Key & key) const 00508 { 00509 return m_hash(key) % m_buckets.size(); 00510 } 00511 00512 void rehash() 00513 { 00514 // grow the number of buckets by 60% 00515 BucketTableType temp(size_type(1.6 * size()), BucketType(*m_memoryManager), *m_memoryManager); 00516 m_buckets.swap(temp); 00517 00518 // rehash each entry assign to bucket and insert into list 00519 typename EntryListType::iterator entryPos = m_entries.begin(); 00520 while (entryPos != m_entries.end()) 00521 { 00522 size_type index = doHash(entryPos->value->first); 00523 m_buckets[index].push_back(entryPos); 00524 ++entryPos; 00525 } 00526 } 00527 00528 value_type* 00529 allocate(size_type size) 00530 { 00531 const size_type theBytesNeeded = size * sizeof(value_type); 00532 00533 assert( m_memoryManager != 0 ); 00534 00535 void* pointer = m_memoryManager->allocate(theBytesNeeded); 00536 00537 assert(pointer != 0); 00538 00539 return (value_type*) pointer; 00540 } 00541 00542 void 00543 deallocate(value_type* pointer) 00544 { 00545 if (m_memoryManager == 0) 00546 { 00547 ::operator delete(pointer); 00548 } 00549 else 00550 { 00551 m_memoryManager->deallocate(pointer); 00552 } 00553 } 00554 00555 // Data members... 00556 typename KeyTraits::Hasher m_hash; 00557 00558 typename KeyTraits::Comparator m_equals; 00559 00560 MemoryManagerType* m_memoryManager; 00561 00562 float m_loadFactor; 00563 00564 size_type m_minBuckets; 00565 00566 size_type m_size; 00567 00568 EntryListType m_entries; 00569 00570 EntryListType m_freeEntries; 00571 00572 BucketTableType m_buckets; 00573 00574 private: 00575 // not defined 00576 XalanMap(); 00577 XalanMap(const XalanMap&); 00578 }; 00579 00580 00581 00582 #if defined(_MSC_VER) 00583 #pragma warning(pop) 00584 #endif 00585 00586 00587 00588 XALAN_CPP_NAMESPACE_END 00589 00590 00591 00592 #endif // XALANMAP_HEADER_GUARD_1357924680 00593
Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.
![]() |
Xalan-C++ XSLT Processor Version 1.9 |
|