activemq-cpp-3.9.5
HashMap.h
Go to the documentation of this file.
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18#ifndef _DECAF_UTIL_HASHMAP_H_
19#define _DECAF_UTIL_HASHMAP_H_
20
21#include <decaf/util/Config.h>
22
25#include <decaf/util/HashCode.h>
28#include <decaf/lang/Pointer.h>
30
31namespace decaf {
32namespace util {
33
94 template<typename K, typename V, typename HASHCODE = HashCode<K> >
95 class HashMap : public AbstractMap<K, V> {
96 protected:
97
98 class HashMapEntry : public MapEntry<K, V> {
99 private:
100
101 HashMapEntry(const HashMapEntry&);
102 HashMapEntry& operator= (const HashMapEntry&);
103
104 public:
105
107
108 HashMapEntry* next;
109
110 HashMapEntry(const K& key, const V& value, int hash) : MapEntry<K, V>(), origKeyHash(hash), next(NULL) {
111 this->setKey(key);
112 this->setValue(value);
113 this->origKeyHash = hash;
114 }
115
116 HashMapEntry(const K& key, const V& value) : MapEntry<K, V>(key, value), origKeyHash(0), next(NULL){
117 this->origKeyHash = HASHCODE()(key);
118 }
119
120 };
121
122 private:
123
124 class AbstractMapIterator {
125 protected:
126
127 mutable int position;
128 int expectedModCount;
129 HashMapEntry* futureEntry;
130 HashMapEntry* currentEntry;
131 HashMapEntry* prevEntry;
132
133 HashMap* associatedMap;
134
135 private:
136
137 AbstractMapIterator(const AbstractMapIterator&);
138 AbstractMapIterator& operator= (const AbstractMapIterator&);
139
140 public:
141
142 AbstractMapIterator(HashMap* parent) : position(0),
143 expectedModCount(parent->modCount),
144 futureEntry(NULL),
145 currentEntry(NULL),
146 prevEntry(NULL),
147 associatedMap(parent) {
148 }
149
150 virtual ~AbstractMapIterator() {}
151
152 virtual bool checkHasNext() const {
153 if (futureEntry != NULL) {
154 return true;
155 }
156 while (position < associatedMap->elementData.length()) {
157 if (associatedMap->elementData[position] == NULL) {
158 position++;
159 } else {
160 return true;
161 }
162 }
163 return false;
164 }
165
166 void checkConcurrentMod() const {
167 if (expectedModCount != associatedMap->modCount) {
168 throw ConcurrentModificationException(
169 __FILE__, __LINE__, "HashMap modified outside this iterator");
170 }
171 }
172
173 void makeNext() {
174 checkConcurrentMod();
175
176 if (!checkHasNext()) {
177 throw NoSuchElementException(__FILE__, __LINE__, "No next element");
178 }
179
180 if (futureEntry == NULL) {
181 currentEntry = associatedMap->elementData[position++];
182 futureEntry = currentEntry->next;
183 prevEntry = NULL;
184 } else {
185 if (currentEntry != NULL){
186 prevEntry = currentEntry;
187 }
188 currentEntry = futureEntry;
189 futureEntry = futureEntry->next;
190 }
191 }
192
193 virtual void doRemove() {
194
195 checkConcurrentMod();
196
197 if (currentEntry == NULL) {
198 throw decaf::lang::exceptions::IllegalStateException(
199 __FILE__, __LINE__, "Remove called before call to next()");
200 }
201
202 if (prevEntry == NULL){
203 int index = currentEntry->origKeyHash & (associatedMap->elementData.length() - 1);
204 associatedMap->elementData[index] = associatedMap->elementData[index]->next;
205 } else {
206 prevEntry->next = currentEntry->next;
207 }
208
209 delete currentEntry;
210 currentEntry = NULL;
211
212 expectedModCount++;
213 associatedMap->modCount++;
214 associatedMap->elementCount--;
215 }
216 };
217
218 class EntryIterator : public Iterator< MapEntry<K,V> >, public AbstractMapIterator {
219 private:
220
221 EntryIterator(const EntryIterator&);
222 EntryIterator& operator= (const EntryIterator&);
223
224 public:
225
226 EntryIterator(HashMap* parent) : AbstractMapIterator(parent) {
227 }
228
229 virtual ~EntryIterator() {}
230
231 virtual bool hasNext() const {
232 return this->checkHasNext();
233 }
234
235 virtual MapEntry<K, V> next() {
236 this->makeNext();
237 return *(this->currentEntry);
238 }
239
240 virtual void remove() {
241 this->doRemove();
242 }
243 };
244
245 class KeyIterator : public Iterator<K>, public AbstractMapIterator {
246 private:
247
248 KeyIterator(const KeyIterator&);
249 KeyIterator& operator= (const KeyIterator&);
250
251 public:
252
253 KeyIterator(HashMap* parent) : AbstractMapIterator(parent) {
254 }
255
256 virtual ~KeyIterator() {}
257
258 virtual bool hasNext() const {
259 return this->checkHasNext();
260 }
261
262 virtual K next() {
263 this->makeNext();
264 return this->currentEntry->getKey();
265 }
266
267 virtual void remove() {
268 this->doRemove();
269 }
270 };
271
272 class ValueIterator : public Iterator<V>, public AbstractMapIterator {
273 private:
274
275 ValueIterator(const ValueIterator&);
276 ValueIterator& operator= (const ValueIterator&);
277
278 public:
279
280 ValueIterator(HashMap* parent) : AbstractMapIterator(parent) {
281 }
282
283 virtual ~ValueIterator() {}
284
285 virtual bool hasNext() const {
286 return this->checkHasNext();
287 }
288
289 virtual V next() {
290 this->makeNext();
291 return this->currentEntry->getValue();
292 }
293
294 virtual void remove() {
295 this->doRemove();
296 }
297 };
298
299 private:
300
301 class ConstAbstractMapIterator {
302 protected:
303
304 mutable int position;
305 int expectedModCount;
306 const HashMapEntry* futureEntry;
307 const HashMapEntry* currentEntry;
308 const HashMapEntry* prevEntry;
309
310 const HashMap* associatedMap;
311
312 private:
313
314 ConstAbstractMapIterator(const ConstAbstractMapIterator&);
315 ConstAbstractMapIterator& operator= (const ConstAbstractMapIterator&);
316
317 public:
318
319 ConstAbstractMapIterator(const HashMap* parent) : position(0),
320 expectedModCount(parent->modCount),
321 futureEntry(NULL),
322 currentEntry(NULL),
323 prevEntry(NULL),
324 associatedMap(parent) {
325 }
326
327 virtual ~ConstAbstractMapIterator() {}
328
329 virtual bool checkHasNext() const {
330 if (futureEntry != NULL) {
331 return true;
332 }
333 while (position < associatedMap->elementData.length()) {
334 if (associatedMap->elementData[position] == NULL) {
335 position++;
336 } else {
337 return true;
338 }
339 }
340 return false;
341 }
342
343 void checkConcurrentMod() const {
344 if (expectedModCount != associatedMap->modCount) {
345 throw ConcurrentModificationException(
346 __FILE__, __LINE__, "HashMap modified outside this iterator");
347 }
348 }
349
350 void makeNext() {
351 checkConcurrentMod();
352
353 if (!checkHasNext()) {
354 throw NoSuchElementException(__FILE__, __LINE__, "No next element");
355 }
356
357 if (futureEntry == NULL) {
358 currentEntry = associatedMap->elementData[position++];
359 futureEntry = currentEntry->next;
360 prevEntry = NULL;
361 } else {
362 if (currentEntry != NULL){
363 prevEntry = currentEntry;
364 }
365 currentEntry = futureEntry;
366 futureEntry = futureEntry->next;
367 }
368 }
369 };
370
371 class ConstEntryIterator : public Iterator< MapEntry<K,V> >, public ConstAbstractMapIterator {
372 private:
373
374 ConstEntryIterator(const ConstEntryIterator&);
375 ConstEntryIterator& operator= (const ConstEntryIterator&);
376
377 public:
378
379 ConstEntryIterator(const HashMap* parent) : ConstAbstractMapIterator(parent) {
380 }
381
382 virtual ~ConstEntryIterator() {}
383
384 virtual bool hasNext() const {
385 return this->checkHasNext();
386 }
387
388 virtual MapEntry<K, V> next() {
389 this->makeNext();
390 return *(this->currentEntry);
391 }
392
393 virtual void remove() {
394 throw lang::exceptions::UnsupportedOperationException(
395 __FILE__, __LINE__, "Cannot write to a const Iterator.");
396 }
397 };
398
399 class ConstKeyIterator : public Iterator<K>, public ConstAbstractMapIterator {
400 private:
401
402 ConstKeyIterator(const ConstKeyIterator&);
403 ConstKeyIterator& operator= (const ConstKeyIterator&);
404
405 public:
406
407 ConstKeyIterator(const HashMap* parent) : ConstAbstractMapIterator(parent) {
408 }
409
410 virtual ~ConstKeyIterator() {}
411
412 virtual bool hasNext() const {
413 return this->checkHasNext();
414 }
415
416 virtual K next() {
417 this->makeNext();
418 return this->currentEntry->getKey();
419 }
420
421 virtual void remove() {
422 throw lang::exceptions::UnsupportedOperationException(
423 __FILE__, __LINE__, "Cannot write to a const Iterator.");
424 }
425 };
426
427 class ConstValueIterator : public Iterator<V>, public ConstAbstractMapIterator {
428 private:
429
430 ConstValueIterator(const ConstValueIterator&);
431 ConstValueIterator& operator= (const ConstValueIterator&);
432
433 public:
434
435 ConstValueIterator(const HashMap* parent) : ConstAbstractMapIterator(parent) {
436 }
437
438 virtual ~ConstValueIterator() {}
439
440 virtual bool hasNext() const {
441 return this->checkHasNext();
442 }
443
444 virtual V next() {
445 this->makeNext();
446 return this->currentEntry->getValue();
447 }
448
449 virtual void remove() {
450 throw lang::exceptions::UnsupportedOperationException(
451 __FILE__, __LINE__, "Cannot write to a const Iterator.");
452 }
453 };
454
455 protected:
456
457 // Special Set implementation that is backed by this HashMap
458 class HashMapEntrySet : public AbstractSet< MapEntry<K, V> > {
459 private:
460
461 HashMap* associatedMap;
462
463 private:
464
465 HashMapEntrySet(const HashMapEntrySet&);
466 HashMapEntrySet& operator= (const HashMapEntrySet&);
467
468 public:
469
470 HashMapEntrySet(HashMap* parent) : AbstractSet< MapEntry<K,V> >(), associatedMap(parent) {
471 }
472
473 virtual ~HashMapEntrySet() {}
474
475 virtual int size() const {
476 return associatedMap->elementCount;
477 }
478
479 virtual void clear() {
480 associatedMap->clear();
481 }
482
483 virtual bool remove(const MapEntry<K,V>& entry) {
484 HashMapEntry* result = associatedMap->getEntry(entry.getKey());
485 if (result != NULL && entry.getValue() == result->getValue()) {
486 associatedMap->removeEntry(result);
487 return true;
488 }
489
490 return false;
491 }
492
493 virtual bool contains(const MapEntry<K,V>& entry) const {
494 HashMapEntry* result = associatedMap->getEntry(entry.getKey());
495 if (result != NULL && entry.getValue() == result->getValue()) {
496 return true;
497 }
498 return false;
499 }
500
502 return new EntryIterator(associatedMap);
503 }
504
506 return new ConstEntryIterator(associatedMap);
507 }
508 };
509
510 // Special Set implementation that is backed by this HashMap
511 class ConstHashMapEntrySet : public AbstractSet< MapEntry<K, V> > {
512 private:
513
514 const HashMap* associatedMap;
515
516 private:
517
518 ConstHashMapEntrySet(const ConstHashMapEntrySet&);
519 ConstHashMapEntrySet& operator= (const ConstHashMapEntrySet&);
520
521 public:
522
523 ConstHashMapEntrySet(const HashMap* parent) : AbstractSet< MapEntry<K,V> >(), associatedMap(parent) {
524 }
525
527
528 virtual int size() const {
529 return associatedMap->elementCount;
530 }
531
532 virtual void clear() {
534 __FILE__, __LINE__, "Can't clear a const collection");
535 }
536
537 virtual bool remove(const MapEntry<K,V>& entry DECAF_UNUSED) {
539 __FILE__, __LINE__, "Can't remove from const collection");
540 }
541
542 virtual bool contains(const MapEntry<K,V>& entry) const {
543 HashMapEntry* result = associatedMap->getEntry(entry.getKey());
544 if (result != NULL && entry.getValue() == result->getValue()) {
545 return true;
546 }
547 return false;
548 }
549
552 __FILE__, __LINE__, "Can't return a non-const iterator for a const collection");
553 }
554
556 return new ConstEntryIterator(associatedMap);
557 }
558 };
559
560 protected:
561
562 class HashMapKeySet : public AbstractSet<K> {
563 private:
564
565 HashMap* associatedMap;
566
567 private:
568
569 HashMapKeySet(const HashMapKeySet&);
570 HashMapKeySet& operator= (const HashMapKeySet&);
571
572 public:
573
574 HashMapKeySet(HashMap* parent) : AbstractSet<K>(), associatedMap(parent) {
575 }
576
577 virtual ~HashMapKeySet() {}
578
579 virtual bool contains(const K& key) const {
580 return this->associatedMap->containsKey(key);
581 }
582
583 virtual int size() const {
584 return this->associatedMap->size();
585 }
586
587 virtual void clear() {
588 this->associatedMap->clear();
589 }
590
591 virtual bool remove(const K& key) {
592 HashMapEntry* entry = this->associatedMap->removeEntry(key);
593 if (entry != NULL) {
594 delete entry;
595 return true;
596 }
597 return false;
598 }
599
601 return new KeyIterator(this->associatedMap);
602 }
603
604 virtual Iterator<K>* iterator() const {
605 return new ConstKeyIterator(this->associatedMap);
606 }
607 };
608
609 class ConstHashMapKeySet : public AbstractSet<K> {
610 private:
611
612 const HashMap* associatedMap;
613
614 private:
615
616 ConstHashMapKeySet(const ConstHashMapKeySet&);
617 ConstHashMapKeySet& operator= (const ConstHashMapKeySet&);
618
619 public:
620
621 ConstHashMapKeySet(const HashMap* parent) : AbstractSet<K>(), associatedMap(parent) {
622 }
623
625
626 virtual bool contains(const K& key) const {
627 return this->associatedMap->containsKey(key);
628 }
629
630 virtual int size() const {
631 return this->associatedMap->size();
632 }
633
634 virtual void clear() {
636 __FILE__, __LINE__, "Can't modify a const collection");
637 }
638
639 virtual bool remove(const K& key DECAF_UNUSED) {
641 __FILE__, __LINE__, "Can't modify a const collection");
642 }
643
646 __FILE__, __LINE__, "Can't return a non-const iterator for a const collection");
647 }
648
649 virtual Iterator<K>* iterator() const {
650 return new ConstKeyIterator(this->associatedMap);
651 }
652 };
653
654 protected:
655
656 class HashMapValueCollection : public AbstractCollection<V> {
657 private:
658
659 HashMap* associatedMap;
660
661 private:
662
663 HashMapValueCollection(const HashMapValueCollection&);
664 HashMapValueCollection& operator= (const HashMapValueCollection&);
665
666 public:
667
668 HashMapValueCollection(HashMap* parent) : AbstractCollection<V>(), associatedMap(parent) {
669 }
670
672
673 virtual bool contains(const V& value) const {
674 return this->associatedMap->containsValue(value);
675 }
676
677 virtual int size() const {
678 return this->associatedMap->size();
679 }
680
681 virtual void clear() {
682 this->associatedMap->clear();
683 }
684
686 return new ValueIterator(this->associatedMap);
687 }
688
689 virtual Iterator<V>* iterator() const {
690 return new ConstValueIterator(this->associatedMap);
691 }
692 };
693
694 class ConstHashMapValueCollection : public AbstractCollection<V> {
695 private:
696
697 const HashMap* associatedMap;
698
699 private:
700
701 ConstHashMapValueCollection(const ConstHashMapValueCollection&);
702 ConstHashMapValueCollection& operator= (const ConstHashMapValueCollection&);
703
704 public:
705
706 ConstHashMapValueCollection(const HashMap* parent) : AbstractCollection<V>(), associatedMap(parent) {
707 }
708
710
711 virtual bool contains(const V& value) const {
712 return this->associatedMap->containsValue(value);
713 }
714
715 virtual int size() const {
716 return this->associatedMap->size();
717 }
718
719 virtual void clear() {
721 __FILE__, __LINE__, "Can't modify a const collection");
722 }
723
726 __FILE__, __LINE__, "Can't return a non-const iterator for a const collection");
727 }
728
729 virtual Iterator<V>* iterator() const {
730 return new ConstValueIterator(this->associatedMap);
731 }
732 };
733
734 protected:
735
739 HASHCODE hashFunc;
740
741 /*
742 * Actual count of entries
743 */
745
746 /*
747 * The internal data structure to hold Entries, Array of MapEntry pointers.
748 */
750
751 /*
752 * modification count, to keep track of structural modifications between the
753 * HashMap and the iterator
754 */
756
757 /*
758 * maximum ratio of (stored elements)/(storage size) which does not lead to rehash
759 */
761
762 /*
763 * maximum number of elements that can be put in this map before having to rehash
764 */
766
767 // Cached values that are only initialized once a request for them is made.
771
772 // Cached values that are only initialized once a request for them is made.
776
777 private:
778
779 void computeThreshold() {
780 threshold = (int) ((float) elementData.length() * loadFactor);
781 }
782
783 static int calculateCapacity(int x) {
784 if (x >= 1 << 30) {
785 return 1 << 30;
786 }
787
788 if (x == 0) {
789 return 16;
790 }
791 x = x - 1;
792 x |= x >> 1;
793 x |= x >> 2;
794 x |= x >> 4;
795 x |= x >> 8;
796 x |= x >> 16;
797 return x + 1;
798 }
799
800 public:
801
806 modCount(0), loadFactor(0.75), threshold(0),
809 int capacity = calculateCapacity(12);
810 elementCount = 0;
812 computeThreshold();
813 }
814
823 HashMap(int capacity) : AbstractMap<K,V>(), hashFunc(), elementCount(0),
824 elementData(), modCount(0), loadFactor(0.75), threshold(0),
827 if (capacity >= 0) {
828 capacity = calculateCapacity(capacity);
829 elementCount = 0;
831 computeThreshold();
832 } else {
834 __FILE__, __LINE__, "Invalid capacity configuration");
835 }
836 }
837
848 HashMap(int capacity, float loadFactor) : AbstractMap<K,V>(), hashFunc(), elementCount(0),
849 elementData(), modCount(0), loadFactor(0.75), threshold(0),
852 if (capacity >= 0 && loadFactor > 0) {
853 capacity = calculateCapacity(capacity);
854 elementCount = 0;
856 this->loadFactor = loadFactor;
857 computeThreshold();
858 } else {
860 __FILE__, __LINE__, "Invalid configuration");
861 }
862 }
863
872 modCount(0), loadFactor(0.75), threshold(0),
875 int capacity = calculateCapacity(map.size());
876 elementCount = 0;
878 computeThreshold();
879 putAll(map);
880 }
881
890 modCount(0), loadFactor(0.75), threshold(0),
893 int capacity = calculateCapacity(map.size());
894 elementCount = 0;
896 computeThreshold();
897 putAll(map);
898 }
899
900 virtual ~HashMap() {
901 for (int i = 0; i < elementData.length(); i++) {
902 HashMapEntry* entry = elementData[i];
903 while (entry != NULL) {
904 HashMapEntry* temp = entry;
905 entry = entry->next;
906 delete temp;
907 }
908 }
909 }
910
911 public:
912
914 this->copy(other);
915 return *this;
916 }
917
919 this->copy(other);
920 return *this;
921 }
922
923 bool operator==(const Map<K, V>& other) const {
924 return this->equals(other);
925 }
926
927 bool operator!=(const Map<K, V>& other) const {
928 return !this->equals(other);
929 }
930
931 public:
932
933 virtual void clear() {
934 if (elementCount > 0) {
935 elementCount = 0;
936 for (int i = 0; i < elementData.length(); ++i) {
937 HashMapEntry* entry = elementData[i];
938 elementData[i] = NULL;
939 while (entry != NULL) {
940 HashMapEntry* temp = entry;
941 entry = entry->next;
942 delete temp;
943 }
944 }
945 modCount++;
946 }
947 }
948
949 virtual bool isEmpty() const {
950 return elementCount == 0;
951 }
952
953 virtual int size() const {
954 return elementCount;
955 }
956
957 virtual bool containsKey(const K& key) const {
958 const HashMapEntry* entry = getEntry(key);
959 return entry != NULL;
960 }
961
962 virtual bool containsValue(const V& value) const {
963 for (int i = 0; i < elementData.length(); i++) {
964 const HashMapEntry* entry = elementData[i];
965 while (entry != NULL) {
966 if (value == entry->getValue()) {
967 return true;
968 }
969 entry = entry->next;
970 }
971 }
972 return false;
973 }
974
975 virtual V& get(const K& key) {
976 HashMapEntry* entry = getEntry(key);
977 if (entry != NULL) {
978 return entry->getValue();
979 }
980
982 __FILE__, __LINE__, "The specified key is not present in the Map");
983 }
984
985 virtual const V& get(const K& key) const {
986 const HashMapEntry* entry = getEntry(key);
987 if (entry != NULL) {
988 return entry->getValue();
989 }
990
992 __FILE__, __LINE__, "The specified key is not present in the Map");
993 }
994
995 virtual bool put(const K& key, const V& value) {
996 return this->putImpl(key, value);
997 }
998
999 virtual bool put(const K& key, const V& value, V& oldValue) {
1000 return this->putImpl(key, value, oldValue);
1001 }
1002
1003 virtual void putAll(const Map<K, V>& map) {
1004 if (!map.isEmpty()) {
1005 putAllImpl(map);
1006 }
1007 }
1008
1009 virtual V remove(const K& key) {
1010 HashMapEntry* entry = removeEntry(key);
1011 if (entry != NULL) {
1012 V oldValue = entry->getValue();
1013 delete entry;
1014 return oldValue;
1015 }
1016
1018 __FILE__, __LINE__, "Specified key not present in the Map.");
1019 }
1020
1022 if (this->cachedEntrySet == NULL) {
1023 this->cachedEntrySet.reset(new HashMapEntrySet(this));
1024 }
1025 return *(this->cachedEntrySet);
1026 }
1027
1028 virtual const Set< MapEntry<K,V> >& entrySet() const {
1029 if (this->cachedConstEntrySet == NULL) {
1030 this->cachedConstEntrySet.reset(new ConstHashMapEntrySet(this));
1031 }
1032 return *(this->cachedConstEntrySet);
1033 }
1034
1035 virtual Set<K>& keySet() {
1036 if (this->cachedKeySet == NULL) {
1037 this->cachedKeySet.reset(new HashMapKeySet(this));
1038 }
1039 return *(this->cachedKeySet);
1040 }
1041
1042 virtual const Set<K>& keySet() const {
1043 if (this->cachedConstKeySet == NULL) {
1044 this->cachedConstKeySet.reset(new ConstHashMapKeySet(this));
1045 }
1046 return *(this->cachedConstKeySet);
1047 }
1048
1050 if (this->cachedValueCollection == NULL) {
1051 this->cachedValueCollection.reset(new HashMapValueCollection(this));
1052 }
1053 return *(this->cachedValueCollection);
1054 }
1055
1056 virtual const Collection<V>& values() const {
1057 if (this->cachedConstValueCollection == NULL) {
1058 this->cachedConstValueCollection.reset(new ConstHashMapValueCollection(this));
1059 }
1060 return *(this->cachedConstValueCollection);
1061 }
1062
1063 virtual bool equals(const Map<K, V>& source) const {
1064
1065 if (this == &source) {
1066 return true;
1067 }
1068
1069 if (size() != source.size()) {
1070 return false;
1071 }
1072
1073 try {
1075 while (iter->hasNext() ) {
1076 MapEntry<K, V> entry = iter->next();
1077 K key = entry.getKey();
1078 V mine = entry.getValue();
1079
1080 if (!source.containsKey(key)) {
1081 return false;
1082 }
1083
1084 if (source.get(key) != mine) {
1085 return false;
1086 }
1087 }
1089 return false;
1091 return false;
1092 }
1093 return true;
1094 }
1095
1096 virtual void copy(const Map<K, V>& source) {
1097 int capacity = calculateCapacity(source.size());
1098 this->clear();
1099 if (capacity > elementData.length()) {
1101 }
1102 computeThreshold();
1103 putAll(source);
1104 }
1105
1106 virtual std::string toString() const {
1107 return "HashMap";
1108 }
1109
1110 protected:
1111
1112 virtual HashMapEntry* getEntry(const K& key) const {
1113 HashMapEntry* result = NULL;
1114
1115 int hash = hashFunc(key);
1116 int index = hash & (elementData.length() - 1);
1117 result = findKeyEntry(key, index, hash);
1118
1119 return result;
1120 }
1121
1122 virtual bool putImpl(const K& key, const V& value) {
1123 V oldValue;
1124 return putImpl(key, value, oldValue);
1125 }
1126
1127 virtual bool putImpl(const K& key, const V& value, V& oldValue) {
1128 bool replaced = true;
1129 HashMapEntry* entry = NULL;
1130
1131 int hash = hashFunc(key);
1132 int index = hash & (elementData.length() - 1);
1133
1134 entry = findKeyEntry(key, index, hash);
1135
1136 if (entry == NULL) {
1137 modCount++;
1138 entry = createHashedEntry(key, index, hash);
1139 if (++elementCount > threshold) {
1140 rehash();
1141 }
1142 replaced = false;
1143 } else {
1144 oldValue = entry->getValue();
1145 }
1146
1147 entry->setValue(value);
1148
1149 return replaced;
1150 }
1151
1152 virtual HashMapEntry* createEntry(const K& key, int index, const V& value) {
1153 HashMapEntry* entry = new HashMapEntry(key, value);
1154 entry->next = elementData[index];
1155 elementData[index] = entry;
1156 return entry;
1157 }
1158
1159 virtual HashMapEntry* createHashedEntry(const K& key, int index, int hash) {
1160 HashMapEntry* entry = new HashMapEntry(key, V(), hash);
1161 entry->next = elementData[index];
1162 elementData[index] = entry;
1163 return entry;
1164 }
1165
1166 protected:
1167
1168 void putAllImpl(const Map<K, V>& map) {
1169 int capacity = elementCount + map.size();
1170 if (capacity > threshold) {
1171 rehash(capacity);
1172 }
1173
1175 while (iterator->hasNext()) {
1176 MapEntry<K, V> entry = iterator->next();
1177 this->putImpl(entry.getKey(), entry.getValue());
1178 }
1179 }
1180
1181 HashMapEntry* findKeyEntry(const K& key, int index, int keyHash) const {
1182 HashMapEntry* entry = elementData[index];
1183 while (entry != NULL && (entry->origKeyHash != keyHash || !(key == entry->getKey()))) {
1184 entry = entry->next;
1185 }
1186 return entry;
1187 }
1188
1189 void rehash(int capacity) {
1190 int length = calculateCapacity((capacity == 0 ? 1 : capacity << 1));
1191
1193 for (int i = 0; i < elementData.length(); i++) {
1194 HashMapEntry* entry = elementData[i];
1195 elementData[i] = NULL;
1196 while (entry != NULL) {
1197 int index = entry->origKeyHash & (length - 1);
1198 HashMapEntry* next = entry->next;
1199 entry->next = newData[index];
1200 newData[index] = entry;
1201 entry = next;
1202 }
1203 }
1204 elementData = newData;
1205 computeThreshold();
1206 }
1207
1208 void rehash() {
1209 rehash(elementData.length());
1210 }
1211
1212 // Removes the given entry from the map and deletes it
1214 int index = entry->origKeyHash & (elementData.length() - 1);
1215 HashMapEntry* current = elementData[index];
1216 if (current == entry) {
1217 elementData[index] = entry->next;
1218 } else {
1219 while (current->next != entry) {
1220 current = current->next;
1221 }
1222 current->next = entry->next;
1223 }
1224 delete entry;
1225 modCount++;
1226 elementCount--;
1227 }
1228
1229 // Removes but doesn't delete the entry in the map with the given key.
1230 HashMapEntry* removeEntry(const K& key) {
1231
1232 int index = 0;
1233 HashMapEntry* current = NULL;
1234 HashMapEntry* last = NULL;
1235
1236 int hash = hashFunc(key);
1237 index = hash & (elementData.length() - 1);
1238 current = elementData[index];
1239 while (current != NULL && !(current->origKeyHash == hash && key == current->getKey())) {
1240 last = current;
1241 current = current->next;
1242 }
1243
1244 if (current == NULL) {
1245 return NULL;
1246 }
1247
1248 if (last == NULL) {
1249 elementData[index] = current->next;
1250 } else {
1251 last->next = current->next;
1252 }
1253
1254 modCount++;
1255 elementCount--;
1256 return current;
1257 }
1258
1259 };
1260
1261}}
1262
1263#endif /* _DECAF_UTIL_HASHMAP_H_ */
Decaf's implementation of a Smart Pointer that is a template on a Type and is Thread Safe if the defa...
Definition ArrayPointer.h:51
virtual decaf::util::Iterator< E > * iterator()=0
Decaf's implementation of a Smart Pointer that is a template on a Type and is Thread Safe if the defa...
Definition Pointer.h:53
void reset(T *value=NULL)
Resets the Pointer to hold the new value.
Definition Pointer.h:161
Definition ClassCastException.h:31
Definition IllegalArgumentException.h:31
Definition NullPointerException.h:32
Definition UnsupportedOperationException.h:32
AbstractCollection()
Definition AbstractCollection.h:65
AbstractMap()
Definition AbstractMap.h:66
AbstractSet()
Definition AbstractSet.h:50
The root interface in the collection hierarchy.
Definition Collection.h:69
Definition HashMap.h:511
virtual ~ConstHashMapEntrySet()
Definition HashMap.h:526
ConstHashMapEntrySet(const HashMap *parent)
Definition HashMap.h:523
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:532
virtual bool remove(const MapEntry< K, V > &entry DECAF_UNUSED)
Definition HashMap.h:537
virtual bool contains(const MapEntry< K, V > &entry) const
Returns true if this collection contains the specified element.
Definition HashMap.h:542
virtual Iterator< MapEntry< K, V > > * iterator()
Definition HashMap.h:550
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:528
virtual Iterator< MapEntry< K, V > > * iterator() const
Definition HashMap.h:555
virtual Iterator< K > * iterator()
Definition HashMap.h:644
ConstHashMapKeySet(const HashMap *parent)
Definition HashMap.h:621
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:630
virtual bool contains(const K &key) const
Returns true if this collection contains the specified element.
Definition HashMap.h:626
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:634
virtual bool remove(const K &key DECAF_UNUSED)
Definition HashMap.h:639
virtual ~ConstHashMapKeySet()
Definition HashMap.h:624
virtual Iterator< K > * iterator() const
Definition HashMap.h:649
virtual ~ConstHashMapValueCollection()
Definition HashMap.h:709
virtual bool contains(const V &value) const
Returns true if this collection contains the specified element.More formally, returns true if and onl...
Definition HashMap.h:711
virtual Iterator< V > * iterator() const
Definition HashMap.h:729
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:719
ConstHashMapValueCollection(const HashMap *parent)
Definition HashMap.h:706
virtual Iterator< V > * iterator()
Definition HashMap.h:724
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:715
Definition HashMap.h:98
HashMapEntry(const K &key, const V &value)
Definition HashMap.h:116
int origKeyHash
Definition HashMap.h:106
HashMapEntry(const K &key, const V &value, int hash)
Definition HashMap.h:110
HashMapEntry * next
Definition HashMap.h:108
Definition HashMap.h:458
virtual bool contains(const MapEntry< K, V > &entry) const
Returns true if this collection contains the specified element.
Definition HashMap.h:493
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:479
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:475
virtual Iterator< MapEntry< K, V > > * iterator()
Definition HashMap.h:501
virtual ~HashMapEntrySet()
Definition HashMap.h:473
virtual bool remove(const MapEntry< K, V > &entry)
Removes a single instance of the specified element from the collection.
Definition HashMap.h:483
HashMapEntrySet(HashMap *parent)
Definition HashMap.h:470
virtual Iterator< MapEntry< K, V > > * iterator() const
Definition HashMap.h:505
Definition HashMap.h:562
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:583
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:587
virtual bool contains(const K &key) const
Returns true if this collection contains the specified element.
Definition HashMap.h:579
virtual ~HashMapKeySet()
Definition HashMap.h:577
HashMapKeySet(HashMap *parent)
Definition HashMap.h:574
virtual Iterator< K > * iterator() const
Definition HashMap.h:604
virtual Iterator< K > * iterator()
Definition HashMap.h:600
virtual bool remove(const K &key)
Removes a single instance of the specified element from the collection.
Definition HashMap.h:591
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:677
HashMapValueCollection(HashMap *parent)
Definition HashMap.h:668
virtual Iterator< V > * iterator() const
Definition HashMap.h:689
virtual ~HashMapValueCollection()
Definition HashMap.h:671
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:681
virtual bool contains(const V &value) const
Returns true if this collection contains the specified element.More formally, returns true if and onl...
Definition HashMap.h:673
virtual Iterator< V > * iterator()
Definition HashMap.h:685
Hash table based implementation of the Map interface.
Definition HashMap.h:95
virtual ~HashMap()
Definition HashMap.h:900
HashMap(const HashMap< K, V > &map)
Creates a new HashMap with default configuration settings and fills it with the contents of the given...
Definition HashMap.h:871
decaf::lang::ArrayPointer< HashMapEntry * > elementData
Definition HashMap.h:749
virtual bool put(const K &key, const V &value)
Associates the specified value with the specified key in this map (optional operation).
Definition HashMap.h:995
decaf::lang::Pointer< HashMapKeySet > cachedKeySet
Definition HashMap.h:769
HashMapEntry * removeEntry(const K &key)
Definition HashMap.h:1230
virtual const V & get(const K &key) const
Gets the value mapped to the specified key in the Map.
Definition HashMap.h:985
bool operator==(const Map< K, V > &other) const
Definition HashMap.h:923
void rehash(int capacity)
Definition HashMap.h:1189
int threshold
Definition HashMap.h:765
virtual bool put(const K &key, const V &value, V &oldValue)
Associates the specified value with the specified key in this map (optional operation).
Definition HashMap.h:999
virtual bool putImpl(const K &key, const V &value, V &oldValue)
Definition HashMap.h:1127
HashMap< K, V > & operator=(const Map< K, V > &other)
Definition HashMap.h:913
virtual const Set< K > & keySet() const
Definition HashMap.h:1042
virtual bool equals(const Map< K, V > &source) const
Compares the specified object with this map for equality.
Definition HashMap.h:1063
virtual const Set< MapEntry< K, V > > & entrySet() const
Definition HashMap.h:1028
decaf::lang::Pointer< HashMapEntrySet > cachedEntrySet
Definition HashMap.h:768
void putAllImpl(const Map< K, V > &map)
Definition HashMap.h:1168
HashMap(int capacity, float loadFactor)
Constructs a new HashMap instance with the specified capacity.
Definition HashMap.h:848
virtual void clear()
Removes all of the mappings from this map (optional operation).
Definition HashMap.h:933
virtual bool isEmpty() const
Definition HashMap.h:949
virtual int size() const
Definition HashMap.h:953
void rehash()
Definition HashMap.h:1208
virtual Collection< V > & values()
Returns a Collection view of the values contained in this map.
Definition HashMap.h:1049
decaf::lang::Pointer< ConstHashMapKeySet > cachedConstKeySet
Definition HashMap.h:774
HASHCODE hashFunc
The Hash Code generator for this map's keys.
Definition HashMap.h:739
virtual const Collection< V > & values() const
Definition HashMap.h:1056
HashMapEntry * findKeyEntry(const K &key, int index, int keyHash) const
Definition HashMap.h:1181
virtual HashMapEntry * getEntry(const K &key) const
Definition HashMap.h:1112
virtual V & get(const K &key)
Gets the value mapped to the specified key in the Map.
Definition HashMap.h:975
virtual bool containsValue(const V &value) const
Returns true if this map maps one or more keys to the specified value.
Definition HashMap.h:962
decaf::lang::Pointer< HashMapValueCollection > cachedValueCollection
Definition HashMap.h:770
virtual Set< MapEntry< K, V > > & entrySet()
Returns a Set view of the mappings contained in this map.
Definition HashMap.h:1021
float loadFactor
Definition HashMap.h:760
bool operator!=(const Map< K, V > &other) const
Definition HashMap.h:927
virtual V remove(const K &key)
Removes the value (key/value pair) for the specified key from the map, returns a copy of the value th...
Definition HashMap.h:1009
HashMap(const Map< K, V > &map)
Creates a new HashMap with default configuration settings and fills it with the contents of the given...
Definition HashMap.h:889
virtual HashMapEntry * createHashedEntry(const K &key, int index, int hash)
Definition HashMap.h:1159
HashMap()
Creates a new empty HashMap with default configuration settings.
Definition HashMap.h:805
virtual std::string toString() const
Definition HashMap.h:1106
HashMap(int capacity)
Constructs a new HashMap instance with the specified capacity.
Definition HashMap.h:823
int elementCount
Definition HashMap.h:744
virtual Set< K > & keySet()
Returns a Set view of the keys contained in this map.
Definition HashMap.h:1035
void removeEntry(HashMapEntry *entry)
Definition HashMap.h:1213
decaf::lang::Pointer< ConstHashMapValueCollection > cachedConstValueCollection
Definition HashMap.h:775
int modCount
Definition HashMap.h:755
decaf::lang::Pointer< ConstHashMapEntrySet > cachedConstEntrySet
Definition HashMap.h:773
virtual bool containsKey(const K &key) const
Returns true if this map contains a mapping for the specified key.
Definition HashMap.h:957
virtual void putAll(const Map< K, V > &map)
Copies all of the mappings from the specified map to this map (optional operation).
Definition HashMap.h:1003
virtual void copy(const Map< K, V > &source)
Copies the content of the source map into this map.
Definition HashMap.h:1096
virtual bool putImpl(const K &key, const V &value)
Definition HashMap.h:1122
virtual HashMapEntry * createEntry(const K &key, int index, const V &value)
Definition HashMap.h:1152
Defines an object that can be used to iterate over the elements of a collection.
Definition Iterator.h:34
Definition MapEntry.h:27
virtual void setKey(K key)
Definition MapEntry.h:53
virtual void setValue(const V &value)
Definition MapEntry.h:65
MapEntry()
Definition MapEntry.h:35
virtual K & getKey()
Definition MapEntry.h:57
virtual V & getValue()
Definition MapEntry.h:69
An object that maps keys to values.
Definition Map.h:88
virtual V & get(const K &key)=0
Gets the value mapped to the specified key in the Map.
virtual bool isEmpty() const =0
virtual bool containsKey(const K &key) const =0
Returns true if this map contains a mapping for the specified key.
virtual int size() const =0
virtual Set< MapEntry< K, V > > & entrySet()=0
Returns a Set view of the mappings contained in this map.
Definition NoSuchElementException.h:31
A collection that contains no duplicate elements.
Definition Set.h:45
#define NULL
Definition Config.h:33
Definition AbstractCollection.h:33
Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements.
Definition AprPool.h:25