00001 /* 00002 * Licensed to the Apache Software Foundation (ASF) under one 00003 * or more contributor license agreements. See the NOTICE file 00004 * distributed with this work for additional information 00005 * regarding copyright ownership. The ASF licenses this file 00006 * to you under the Apache License, Version 2.0 (the "License"); 00007 * you may not use this file except in compliance with the License. 00008 * You may obtain a copy of the License at 00009 * 00010 * http://www.apache.org/licenses/LICENSE-2.0 00011 * 00012 * Unless required by applicable law or agreed to in writing, software 00013 * distributed under the License is distributed on an "AS IS" BASIS, 00014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00015 * See the License for the specific language governing permissions and 00016 * limitations under the License. 00017 */ 00018 00019 #if !defined(XALANMAP_HEADER_GUARD_1357924680) 00020 #define XALANMAP_HEADER_GUARD_1357924680 00021 00022 00023 // Base include file. Must be first. 00024 #include <xalanc/Include/PlatformDefinitions.hpp> 00025 00026 00027 00028 #include <cstddef> 00029 #include <algorithm> 00030 #include <functional> 00031 #include <utility> 00032 00033 00034 #include <xalanc/Include/XalanVector.hpp> 00035 #include <xalanc/Include/XalanList.hpp> 00036 00037 00038 00039 XALAN_CPP_NAMESPACE_BEGIN 00040 00041 #if defined(_MSC_VER) 00042 #pragma warning(push) 00043 #pragma warning(disable: 4189) 00044 #endif 00045 00046 typedef size_t size_type; 00047 00048 template <class Key> 00049 class XalanHasher : public XALAN_STD_QUALIFIER unary_function<Key, size_type> 00050 { 00051 public: 00052 size_type operator()(const Key& key) const 00053 { 00054 const char *byteArray = reinterpret_cast<const char*>(&key); 00055 00056 size_type result = 0; 00057 00058 for (size_type i = 0; i < sizeof(Key); ++i) 00059 { 00060 result = (result << 1) ^ byteArray[i]; 00061 } 00062 00063 return result; 00064 } 00065 }; 00066 00067 template <class Key> 00068 struct XalanMapKeyTraits 00069 { 00070 typedef XalanHasher<Key> Hasher; 00071 typedef XALAN_STD_QUALIFIER equal_to<Key> Comparator; 00072 }; 00073 00074 00075 template <class Key> 00076 struct XalanHashMemberPointer 00077 { 00078 00079 size_type operator() (const Key * key) const 00080 { 00081 assert (key != 0); 00082 return key->hash(); 00083 } 00084 }; 00085 00086 template <class Key> 00087 struct XalanHashMemberReference 00088 { 00089 00090 size_type operator() (const Key& key) const 00091 { 00092 return key.hash(); 00093 } 00094 }; 00095 00096 00097 00098 template <class Value> 00099 struct XalanMapIteratorTraits 00100 { 00101 typedef Value value_type; 00102 typedef Value& reference; 00103 typedef Value* pointer; 00104 }; 00105 00106 template <class Value> 00107 struct XalanMapConstIteratorTraits 00108 { 00109 typedef Value value_type; 00110 typedef const Value& reference; 00111 typedef const Value* pointer; 00112 }; 00113 00114 template <class XalanMapTraits, class BaseIterator> 00115 struct XalanMapIterator 00116 { 00117 typedef typename XalanMapTraits::value_type value_type; 00118 typedef typename XalanMapTraits::reference reference; 00119 typedef typename XalanMapTraits::pointer pointer; 00120 00121 typedef ptrdiff_t difference_type; 00122 typedef XALAN_STD_QUALIFIER bidirectional_iterator_tag iterator_category; 00123 00124 typedef XalanMapIterator< 00125 XalanMapIteratorTraits<value_type>, 00126 BaseIterator> Iterator; 00127 00128 XalanMapIterator(const Iterator & theRhs) : 00129 baseIterator(theRhs.baseIterator) 00130 { 00131 } 00132 00133 XalanMapIterator(const BaseIterator & theRhs) : 00134 baseIterator(theRhs) 00135 { 00136 } 00137 00138 XalanMapIterator operator++(int) 00139 { 00140 XalanMapIterator temp(*this); 00141 ++baseIterator; 00142 return temp; 00143 } 00144 00145 XalanMapIterator& operator++() 00146 { 00147 ++baseIterator; 00148 return *this; 00149 } 00150 00151 reference operator*() const 00152 { 00153 return *baseIterator->value; 00154 } 00155 00156 pointer operator->() const 00157 { 00158 return baseIterator->value; 00159 } 00160 00161 bool operator==(const XalanMapIterator& theRhs) const 00162 { 00163 return theRhs.baseIterator == baseIterator; 00164 } 00165 00166 bool operator!=(const XalanMapIterator& theRhs) const 00167 { 00168 return !(theRhs == *this); 00169 } 00170 00171 BaseIterator baseIterator; 00172 }; 00173 00174 00175 00176 /** 00177 * Xalan implementation of a hashtable. 00178 * 00179 */ 00180 template < 00181 class Key, 00182 class Value, 00183 class KeyTraits = XalanMapKeyTraits<Key>, 00184 class KeyConstructionTraits = MemoryManagedConstructionTraits<Key>, 00185 class ValueConstructionTraits = MemoryManagedConstructionTraits<Value> > 00186 class XalanMap 00187 { 00188 public: 00189 /** 00190 * Each map entry is stored in a linked list where an entry 00191 * consists of a pointer to the key/value pair and a flag to indicate 00192 * whether the entry has been erased. 00193 * The hash buckets are a vector of pointers into the entry list. 00194 * Deleted entries are spliced into another list and marked 'erased'. 00195 */ 00196 00197 typedef Key key_type; 00198 typedef Value data_type; 00199 typedef size_t size_type; 00200 00201 typedef XALAN_STD_QUALIFIER pair<const key_type, data_type> value_type; 00202 00203 struct Entry 00204 { 00205 value_type* value; 00206 bool erased; 00207 00208 Entry(value_type* theValue) : 00209 value(theValue), 00210 erased(false) 00211 { 00212 } 00213 }; 00214 00215 typedef XalanList<Entry> EntryListType; 00216 00217 typedef XalanVector<typename EntryListType::iterator> BucketType; 00218 typedef XalanVector<BucketType, ConstructWithMemoryManagerTraits<BucketType> > BucketTableType; 00219 00220 typedef typename EntryListType::iterator EntryListIterator; 00221 typedef typename BucketTableType::iterator TableIterator; 00222 typedef typename BucketType::iterator BucketIterator; 00223 00224 typedef XalanMapIterator< 00225 XalanMapIteratorTraits<value_type>, 00226 typename EntryListType::iterator> iterator; 00227 typedef XalanMapIterator< 00228 XalanMapConstIteratorTraits<value_type>, 00229 typename EntryListType::iterator> const_iterator; 00230 00231 typedef typename KeyConstructionTraits::Constructor FirstConstructor; 00232 typedef typename ValueConstructionTraits::Constructor SecondConstructor; 00233 00234 enum 00235 { 00236 eDefaultMinBuckets = 29u, 00237 eDefaultEraseThreshold = 50u, 00238 eMinimumBucketSize = 5u 00239 }; 00240 00241 00242 XalanMap( 00243 MemoryManager& theMemoryManager, 00244 double loadFactor = 0.75, 00245 size_type minBuckets = eDefaultMinBuckets, 00246 size_type eraseThreshold = eDefaultEraseThreshold) : 00247 m_memoryManager(&theMemoryManager), 00248 m_loadFactor(loadFactor), 00249 m_minBuckets(minBuckets), 00250 m_size(0), 00251 m_entries(theMemoryManager), 00252 m_freeEntries(theMemoryManager), 00253 m_buckets(theMemoryManager), 00254 m_eraseCount(0), 00255 m_eraseThreshold(eraseThreshold) 00256 { 00257 } 00258 00259 XalanMap( 00260 const XalanMap& theRhs, 00261 MemoryManager& theMemoryManager) : 00262 m_memoryManager(&theMemoryManager), 00263 m_loadFactor(theRhs.m_loadFactor), 00264 m_minBuckets(theRhs.m_minBuckets), 00265 m_size(0), 00266 m_entries(theMemoryManager), 00267 m_freeEntries(theMemoryManager), 00268 m_buckets( 00269 size_type(m_loadFactor * theRhs.size()) + 1, 00270 BucketType(*m_memoryManager), 00271 theMemoryManager), 00272 m_eraseCount(0), 00273 m_eraseThreshold(theRhs.m_eraseThreshold) 00274 { 00275 const_iterator entry = theRhs.begin(); 00276 00277 while(entry != theRhs.end()) 00278 { 00279 insert(*entry); 00280 ++entry; 00281 } 00282 00283 assert(m_size == theRhs.m_size); 00284 } 00285 00286 MemoryManager& 00287 getMemoryManager() 00288 { 00289 assert (m_memoryManager != 0); 00290 00291 return *m_memoryManager; 00292 } 00293 00294 ~XalanMap() 00295 { 00296 doRemoveEntries(); 00297 00298 if (!m_buckets.empty()) 00299 { 00300 EntryListIterator toRemove = m_freeEntries.begin(); 00301 00302 while(toRemove != m_freeEntries.end()) 00303 { 00304 deallocate(toRemove->value); 00305 ++toRemove; 00306 } 00307 } 00308 } 00309 00310 XalanMap& 00311 operator=(const XalanMap& theRhs) 00312 { 00313 XalanMap theTemp(theRhs, *m_memoryManager); 00314 00315 swap(theTemp); 00316 00317 return *this; 00318 } 00319 00320 size_type size() const 00321 { 00322 return m_size; 00323 } 00324 00325 bool empty() const 00326 { 00327 return m_size == 0; 00328 } 00329 00330 iterator begin() 00331 { 00332 return m_entries.begin(); 00333 } 00334 00335 const_iterator begin() const 00336 { 00337 return const_cast<XalanMap*>(this)->begin(); 00338 } 00339 00340 iterator end() 00341 { 00342 return m_entries.end(); 00343 } 00344 00345 const_iterator end() const 00346 { 00347 return const_cast<XalanMap*>(this)->end(); 00348 } 00349 00350 iterator find(const key_type& key) 00351 { 00352 if (m_size != 0) 00353 { 00354 assert(m_buckets.empty() == false); 00355 00356 const size_type index = doHash(key); 00357 assert(index < m_buckets.size()); 00358 00359 BucketType& bucket = m_buckets[index]; 00360 BucketIterator pos = bucket.begin(); 00361 00362 while (pos != bucket.end()) 00363 { 00364 if (!(*pos)->erased && m_equals(key, (*pos)->value->first)) 00365 { 00366 return iterator(*pos); 00367 } 00368 ++pos; 00369 } 00370 } 00371 00372 return end(); 00373 } 00374 00375 const_iterator find(const key_type& key) const 00376 { 00377 return const_cast<XalanMap *>(this)->find(key); 00378 } 00379 00380 data_type & operator[](const key_type& key) 00381 { 00382 iterator pos = find(key); 00383 00384 if (pos == end()) 00385 { 00386 pos = doCreateEntry(key); 00387 } 00388 00389 return (*pos).second; 00390 } 00391 00392 void 00393 insert(const value_type& value) 00394 { 00395 insert(value.first, value.second); 00396 } 00397 00398 void insert(const key_type& key, const data_type& data) 00399 { 00400 const const_iterator pos = find(key); 00401 00402 if (pos == end()) 00403 { 00404 doCreateEntry(key, &data); 00405 } 00406 } 00407 00408 void erase(iterator pos) 00409 { 00410 if (pos != end()) 00411 { 00412 doErase(pos); 00413 } 00414 } 00415 00416 size_type erase(const key_type& key) 00417 { 00418 const iterator pos = find(key); 00419 00420 if (pos != end()) 00421 { 00422 doErase(pos); 00423 00424 return 1; 00425 } 00426 else 00427 { 00428 return 0; 00429 } 00430 } 00431 00432 void clear() 00433 { 00434 doRemoveEntries(); 00435 00436 TableIterator bucketPos = m_buckets.begin(); 00437 00438 while (bucketPos != m_buckets.end()) 00439 { 00440 bucketPos->clear(); 00441 ++bucketPos; 00442 } 00443 00444 m_eraseCount = 0; 00445 00446 assert(0 == m_size); 00447 assert(m_entries.empty()); 00448 } 00449 00450 void swap(XalanMap& theRhs) 00451 { 00452 const size_type tempSize = m_size; 00453 m_size = theRhs.m_size; 00454 theRhs.m_size = tempSize; 00455 00456 MemoryManager* const tempMemoryManager = m_memoryManager; 00457 m_memoryManager = theRhs.m_memoryManager; 00458 theRhs.m_memoryManager = tempMemoryManager; 00459 00460 const size_type tempEraseCount = m_eraseCount; 00461 m_eraseCount = theRhs.m_eraseCount; 00462 theRhs.m_eraseCount = tempEraseCount; 00463 00464 const size_type tempEraseTheshold = m_eraseThreshold; 00465 m_eraseThreshold = theRhs.m_eraseThreshold; 00466 theRhs.m_eraseThreshold = tempEraseTheshold; 00467 00468 m_entries.swap(theRhs.m_entries); 00469 m_freeEntries.swap(theRhs.m_freeEntries); 00470 m_buckets.swap(theRhs.m_buckets); 00471 } 00472 00473 protected: 00474 00475 iterator doCreateEntry(const key_type & key, const data_type* data = 0) 00476 { 00477 // if there are no buckets, create initial minimum set of buckets 00478 if (m_buckets.empty()) 00479 { 00480 m_buckets.insert( 00481 m_buckets.begin(), 00482 m_minBuckets, 00483 BucketType(*m_memoryManager)); 00484 } 00485 00486 // if the load factor has been reached, rehash 00487 if (size_type(m_loadFactor * size()) > m_buckets.size()) 00488 { 00489 rehash(); 00490 } 00491 00492 const size_type index = doHash(key); 00493 00494 if (m_freeEntries.empty()) 00495 { 00496 m_freeEntries.push_back(Entry(allocate(1))); 00497 } 00498 00499 // insert a new entry as the first position in the bucket 00500 Entry& newEntry = m_freeEntries.back(); 00501 newEntry.erased = false; 00502 00503 FirstConstructor::construct( 00504 const_cast<key_type*>(&newEntry.value->first), 00505 key, 00506 *m_memoryManager); 00507 00508 if (data != 0) 00509 { 00510 SecondConstructor::construct( 00511 &newEntry.value->second, 00512 *data, 00513 *m_memoryManager); 00514 } 00515 else 00516 { 00517 SecondConstructor::construct( 00518 &newEntry.value->second, 00519 *m_memoryManager); 00520 } 00521 00522 m_entries.splice(m_entries.end(), m_freeEntries, --m_freeEntries.end()); 00523 00524 m_buckets[index].push_back(--m_entries.end()); 00525 00526 ++m_size; 00527 00528 return iterator(--m_entries.end()); 00529 } 00530 00531 void doRemoveEntry(const iterator & toRemovePos) 00532 { 00533 value_type& toRemove = *toRemovePos; 00534 #if defined(_MSC_VER) && _MSC_VER <= 1300 00535 toRemove.value_type::~value_type(); 00536 #else 00537 toRemove.~value_type(); 00538 #endif 00539 m_freeEntries.splice( 00540 m_freeEntries.end(), 00541 m_entries, 00542 toRemovePos.baseIterator); 00543 00544 toRemovePos.baseIterator->erased = true; 00545 00546 --m_size; 00547 } 00548 00549 void 00550 doRemoveEntries() 00551 { 00552 while(size() > 0) 00553 { 00554 doRemoveEntry(begin()); 00555 } 00556 } 00557 00558 void 00559 doErase(iterator pos) 00560 { 00561 assert(pos != end()); 00562 00563 doRemoveEntry(pos); 00564 00565 ++m_eraseCount; 00566 00567 if (m_eraseCount == m_eraseThreshold) 00568 { 00569 compactBuckets(); 00570 00571 m_eraseCount = 0; 00572 } 00573 } 00574 00575 size_type 00576 doHash( 00577 const Key& key, 00578 size_type modulus) const 00579 { 00580 assert(modulus != 0); 00581 00582 return m_hash(key) % modulus; 00583 } 00584 00585 size_type doHash(const Key & key) const 00586 { 00587 return doHash(key, m_buckets.size()); 00588 } 00589 00590 void rehash() 00591 { 00592 // grow the number of buckets by 60% 00593 const size_type theNewSize = size_type(1.6 * size()); 00594 assert(theNewSize != 0); 00595 00596 BucketTableType temp( 00597 theNewSize, 00598 BucketType(*m_memoryManager), 00599 *m_memoryManager); 00600 00601 // rehash each entry assign to bucket and insert into list 00602 EntryListIterator entryPos = m_entries.begin(); 00603 00604 while (entryPos != m_entries.end()) 00605 { 00606 const size_type index = 00607 doHash( 00608 entryPos->value->first, 00609 theNewSize); 00610 00611 temp[index].push_back(entryPos); 00612 00613 ++entryPos; 00614 } 00615 00616 // Now that we've rebuilt the buckets, swap the rebuilt 00617 // buckets with our existing buckets. 00618 m_buckets.swap(temp); 00619 } 00620 00621 value_type* 00622 allocate(size_type size) 00623 { 00624 const size_type theBytesNeeded = size * sizeof(value_type); 00625 00626 assert(m_memoryManager != 0); 00627 00628 void* pointer = m_memoryManager->allocate(theBytesNeeded); 00629 00630 assert(pointer != 0); 00631 00632 return reinterpret_cast<value_type*>(pointer); 00633 } 00634 00635 void 00636 deallocate(value_type* pointer) 00637 { 00638 assert(m_memoryManager != 0); 00639 00640 m_memoryManager->deallocate(pointer); 00641 } 00642 00643 static size_type 00644 calculateNewBucketCapacity( 00645 size_type theCurrentSize, 00646 size_type theExtraCapacity) 00647 { 00648 assert(theExtraCapacity > theCurrentSize); 00649 00650 // We'll use the current extra capacity a convenient number. 00651 // Perhaps a better choice would be to determine how much 00652 // of the extra capacity to keep, but we really need to 00653 // figure out how to keep the buckets compacted during 00654 // removal of an item. 00655 return theCurrentSize == 0 ? 00656 eMinimumBucketSize : 00657 theExtraCapacity; 00658 } 00659 00660 void 00661 compactBuckets() 00662 { 00663 for(TableIterator i = m_buckets.begin(); 00664 i != m_buckets.end(); 00665 ++i) 00666 { 00667 BucketType& theCurrentBucket = *i; 00668 00669 BucketIterator j = theCurrentBucket.begin(); 00670 00671 while(j != theCurrentBucket.end()) 00672 { 00673 if ((*j)->erased == true) 00674 { 00675 j = theCurrentBucket.erase(j); 00676 } 00677 else 00678 { 00679 ++j; 00680 } 00681 } 00682 00683 // Now we should do something if the 00684 // bucket has a much greater capacity 00685 // than the number of items in it. 00686 const size_type theCurrentSize = 00687 theCurrentBucket.size(); 00688 00689 const size_type theExtraCapacity = 00690 theCurrentBucket.capacity() - theCurrentSize; 00691 00692 if (theExtraCapacity > theCurrentSize) 00693 { 00694 const size_type theNewCapacity = 00695 calculateNewBucketCapacity( 00696 theCurrentSize, 00697 theExtraCapacity); 00698 00699 // Create a copy of the bucket, and 00700 // give it the new capacity of the extra 00701 // capacity. 00702 BucketType theTempBucket( 00703 theCurrentBucket, 00704 *m_memoryManager, 00705 theNewCapacity); 00706 00707 theCurrentBucket.swap(theTempBucket); 00708 } 00709 } 00710 } 00711 00712 // Data members... 00713 typename KeyTraits::Hasher m_hash; 00714 00715 typename KeyTraits::Comparator m_equals; 00716 00717 MemoryManager* m_memoryManager; 00718 00719 double m_loadFactor; 00720 00721 const size_type m_minBuckets; 00722 00723 size_type m_size; 00724 00725 EntryListType m_entries; 00726 00727 EntryListType m_freeEntries; 00728 00729 BucketTableType m_buckets; 00730 00731 size_type m_eraseCount; 00732 00733 size_type m_eraseThreshold; 00734 00735 private: 00736 00737 // These are not implemented. 00738 XalanMap(); 00739 00740 XalanMap(const XalanMap&); 00741 }; 00742 00743 00744 00745 #if defined(_MSC_VER) 00746 #pragma warning(pop) 00747 #endif 00748 00749 00750 00751 XALAN_CPP_NAMESPACE_END 00752 00753 00754 00755 #endif // XALANMAP_HEADER_GUARD_1357924680 00756
Doxygen and GraphViz are used to generate this API documentation from the Xalan-C header files.
Xalan-C++ XSLT Processor Version 1.11 |
|