diff options
Diffstat (limited to 'debian/uncrustify-trinity/uncrustify-trinity-0.78.1/tests/input/d/HashMap.d')
| -rw-r--r-- | debian/uncrustify-trinity/uncrustify-trinity-0.78.1/tests/input/d/HashMap.d | 1059 |
1 files changed, 1059 insertions, 0 deletions
diff --git a/debian/uncrustify-trinity/uncrustify-trinity-0.78.1/tests/input/d/HashMap.d b/debian/uncrustify-trinity/uncrustify-trinity-0.78.1/tests/input/d/HashMap.d new file mode 100644 index 00000000..618b3e59 --- /dev/null +++ b/debian/uncrustify-trinity/uncrustify-trinity-0.78.1/tests/input/d/HashMap.d @@ -0,0 +1,1059 @@ +/******************************************************************************* + + @file HashMap.d + + This software is provided 'as-is', without any express or implied + warranty. In no event will the authors be held liable for damages + of any kind arising from the use of this software. + + Permission is hereby granted to anyone to use this software for any + purpose, including commercial applications, and to alter it and/or + redistribute it freely, subject to the following restrictions: + + 1. The origin of this software must not be misrepresented; you must + not claim that you wrote the original software. If you use this + software in a product, an acknowledgment within documentation of + said product would be appreciated but is not required. + + 2. Altered source versions must be plainly marked as such, and must + not be misrepresented as being the original software. + + 3. This notice may not be removed or altered from any distribution + of the source. + + 4. Derivative works are permitted, but they must carry this notice + in full and credit the original source. + + + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + + Written by Doug Lea with assistance from members of JCP JSR-166 + Expert Group and released to the public domain, as explained at + http://creativecommons.org/licenses/publicdomain + + @version Initial version, July 2004 + @author Doug Lea; ported/modified by Kris + +*******************************************************************************/ + +module mango.cache.HashMap; + +/****************************************************************************** + +******************************************************************************/ + +extern (C) +{ + int memcmp (char *, char *, uint); +} + + +/** + * A hash table supporting full concurrency of retrievals and + * adjustable expected concurrency for updates. This class obeys the + * same functional specification as {@link java.util.Hashtable}, and + * includes versions of methods corresponding to each method of + * <tt>Hashtable</tt>. However, even though all operations are + * thread-safe, retrieval operations do <em>not</em> entail locking, + * and there is <em>not</em> any support for locking the entire table + * in a way that prevents all access. This class is fully + * interoperable with <tt>Hashtable</tt> in programs that rely on its + * thread safety but not on its synchronization details. + * + * <p> Retrieval operations (including <tt>get</tt>) generally do not + * block, so may overlap with update operations (including + * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results + * of the most recently <em>completed</em> update operations holding + * upon their onset. For aggregate operations such as <tt>putAll</tt> + * and <tt>clear</tt>, concurrent retrievals may reflect insertion or + * removal of only some entries. Similarly, Iterators and + * Enumerations return elements reflecting the state of the hash table + * at some point at or since the creation of the iterator/enumeration. + * They do <em>not</em> throw + * {@link ConcurrentModificationException}. However, iterators are + * designed to be used by only one thread at a time. + * + * <p> The allowed concurrency among update operations is guided by + * the optional <tt>concurrencyLevel</tt> constructor argument + * (default 16), which is used as a hint for internal sizing. The + * table is internally partitioned to try to permit the indicated + * number of concurrent updates without contention. Because placement + * in hash tables is essentially random, the actual concurrency will + * vary. Ideally, you should choose a value to accommodate as many + * threads as will ever concurrently modify the table. Using a + * significantly higher value than you need can waste space and time, + * and a significantly lower value can lead to thread contention. But + * overestimates and underestimates within an order of magnitude do + * not usually have much noticeable impact. A value of one is + * appropriate when it is known that only one thread will modify and + * all others will only read. Also, resizing this or any other kind of + * hash table is a relatively slow operation, so, when possible, it is + * a good idea to provide estimates of expected table sizes in + * constructors. + * + * <p>This class and its views and iterators implement all of the + * <em>optional</em> methods of the {@link Map} and {@link Iterator} + * interfaces. + * + * <p> Like {@link java.util.Hashtable} but unlike {@link + * java.util.HashMap}, this class does NOT allow <tt>null</tt> to be + * used as a key or value. + * + * <p>This class is a member of the + * <a href="{@docRoot}/../guide/collections/index.html"> + * Java Collections Framework</a>. + * + * @since 1.5 + * @author Doug Lea + * @param <K> the type of keys maintained by this map + * @param <V> the type of mapped values + */ + +class HashMap +{ + alias void[] K; + alias Object V; + alias jhash hash; // jhash, fnv, or walter + + /* + * The basic strategy is to subdivide the table among Segments, + * each of which itself is a concurrently readable hash table. + */ + + /* ---------------- Constants -------------- */ + + /** + * The default initial number of table slots for this table. + * Used when not otherwise specified in constructor. + */ + private const uint DEFAULT_INITIAL_CAPACITY = 16; + + /** + * The maximum capacity, used if a higher value is implicitly + * specified by either of the constructors with arguments. MUST + * be a power of two <= 1<<30 to ensure that entries are indexible + * using ints. + */ + private const uint MAXIMUM_CAPACITY = 1 << 30; + + /** + * The default load factor for this table. Used when not + * otherwise specified in constructor. + */ + private const float DEFAULT_LOAD_FACTOR = 0.75f; + + /** + * The default number of concurrency control segments. + **/ + private const uint DEFAULT_SEGMENTS = 16; + + /** + * The maximum number of segments to allow; used to bound + * constructor arguments. + */ + private const uint MAX_SEGMENTS = 1 << 16; // slightly conservative + + + /* ---------------- Fields -------------- */ + + /** + * Mask value for indexing into segments. The upper bits of a + * key's hash code are used to choose the segment. + **/ + private final int segmentMask; + + /** + * Shift value for indexing within segments. + **/ + private final int segmentShift; + + /** + * The segments, each of which is a specialized hash table + */ + private final Segment[] segments; + + + /* ---------------- Small Utilities -------------- */ + + /** + * Returns a hash code for non-null Object x. + * Uses the same hash code spreader as most other java.util hash tables. + * @param x the object serving as a key + * @return the hash code + */ + private static final uint walter(K x) + { + uint h = typeid(char[]).getHash (&x); + h += ~(h << 9); + h ^= (h >>> 14); + h += (h << 4); + h ^= (h >>> 10); + return h; + } + + /** + * Returns a hash code for non-null Object x. + * uses the FNV hash function + * @param x the object serving as a key + * @return the hash code + */ + private static final uint fnv(K x) + { + uint hash = 2_166_136_261; + + foreach (ubyte c; cast(ubyte[]) x) + { + hash ^= c; + hash *= 16_777_619; + } + return hash; + } + + + + /** + * hash() -- hash a variable-length key into a 32-bit value + * k : the key (the unaligned variable-length array of bytes) + * len : the length of the key, counting by bytes + * level : can be any 4-byte value + * Returns a 32-bit value. Every bit of the key affects every bit of + * the return value. Every 1-bit and 2-bit delta achieves avalanche. + * About 36+6len instructions. + * + * The best hash table sizes are powers of 2. There is no need to do + * mod a prime (mod is sooo slow!). If you need less than 32 bits, + * use a bitmask. For example, if you need only 10 bits, do + * h = (h & hashmask(10)); + * In which case, the hash table should have hashsize(10) elements. + * + * If you are hashing n strings (ub1 **)k, do it like this: + * for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); + * + * By Bob Jenkins, 1996. [email protected]. You may use this + * code any way you wish, private, educational, or commercial. It's free. + * + * See http://burlteburtle.net/bob/hash/evahash.html + * Use for hash table lookup, or anything where one collision in 2^32 is + * acceptable. Do NOT use for cryptographic purposes. + */ + + static final uint jhash (K x) + { + ubyte* k; + uint a, + b, + c, + len; + + len = x.length; + k = cast(ubyte *) x; + a = b = 0x9e3779b9; + + // the previous hash value + c = 0; + + // handle most of the key + while (len >= 12) + { + a += *cast(uint *)(k+0); + b += *cast(uint *)(k+4); + c += *cast(uint *)(k+8); + + a -= b; a -= c; a ^= (c>>13); + b -= c; b -= a; b ^= (a<<8); + c -= a; c -= b; c ^= (b>>13); + a -= b; a -= c; a ^= (c>>12); + b -= c; b -= a; b ^= (a<<16); + c -= a; c -= b; c ^= (b>>5); + a -= b; a -= c; a ^= (c>>3); + b -= c; b -= a; b ^= (a<<10); + c -= a; c -= b; c ^= (b>>15); + k += 12; len -= 12; + } + + // handle the last 11 bytes + c += x.length; + switch (len) + { + case 11: c+=(cast(uint)k[10]<<24); + case 10: c+=(cast(uint)k[9]<<16); + case 9 : c+=(cast(uint)k[8]<<8); + case 8 : b+=(cast(uint)k[7]<<24); + case 7 : b+=(cast(uint)k[6]<<16); + case 6 : b+=(cast(uint)k[5]<<8); + case 5 : b+=k[4]; + case 4 : a+=(cast(uint)k[3]<<24); + case 3 : a+=(cast(uint)k[2]<<16); + case 2 : a+=(cast(uint)k[1]<<8); + case 1 : a+=k[0]; + default: + } + + a -= b; a -= c; a ^= (c>>13); + b -= c; b -= a; b ^= (a<<8); + c -= a; c -= b; c ^= (b>>13); + a -= b; a -= c; a ^= (c>>12); + b -= c; b -= a; b ^= (a<<16); + c -= a; c -= b; c ^= (b>>5); + a -= b; a -= c; a ^= (c>>3); + b -= c; b -= a; b ^= (a<<10); + c -= a; c -= b; c ^= (b>>15); + + return c; + } + + + /** + * Returns the segment that should be used for key with given hash + * @param hash the hash code for the key + * @return the segment + */ + private final Segment segmentFor(uint hash) + { + return segments[(hash >>> segmentShift) & segmentMask]; + } + + /* ---------------- Inner Classes -------------- */ + + /** + * ConcurrentHashMap list entry. Note that this is never exported + * out as a user-visible Map.Entry. + * + * Because the value field is volatile, not final, it is legal wrt + * the Java Memory Model for an unsynchronized reader to see null + * instead of initial value when read via a data race. Although a + * reordering leading to this is not likely to ever actually + * occur, the Segment.readValueUnderLock method is used as a + * backup in case a null (pre-initialized) value is ever seen in + * an unsynchronized access method. + */ + private static class HashEntry + { + final K key; + final uint hash; + final V value; + final HashEntry next; + + this (K key, uint hash, HashEntry next, V value) + { + this.key = key; + this.hash = hash; + this.next = next; + this.value = value; + } + } + + /** + * Segments are specialized versions of hash tables. This + * subclasses from ReentrantLock opportunistically, just to + * simplify some locking and avoid separate construction. + **/ + static class Segment + { + /* + * Segments maintain a table of entry lists that are ALWAYS + * kept in a consistent state, so can be read without locking. + * Next fields of nodes are immutable (final). All list + * additions are performed at the front of each bin. This + * makes it easy to check changes, and also fast to traverse. + * When nodes would otherwise be changed, new nodes are + * created to replace them. This works well for hash tables + * since the bin lists tend to be short. (The average length + * is less than two for the default load factor threshold.) + * + * Read operations can thus proceed without locking, but rely + * on selected uses of volatiles to ensure that completed + * write operations performed by other threads are + * noticed. For most purposes, the "count" field, tracking the + * number of elements, serves as that volatile variable + * ensuring visibility. This is convenient because this field + * needs to be read in many read operations anyway: + * + * - All (unsynchronized) read operations must first read the + * "count" field, and should not look at table entries if + * it is 0. + * + * - All (synchronized) write operations should write to + * the "count" field after structurally changing any bin. + * The operations must not take any action that could even + * momentarily cause a concurrent read operation to see + * inconsistent data. This is made easier by the nature of + * the read operations in Map. For example, no operation + * can reveal that the table has grown but the threshold + * has not yet been updated, so there are no atomicity + * requirements for this with respect to reads. + * + * As a guide, all critical volatile reads and writes to the + * count field are marked in code comments. + */ + + /** + * The number of elements in this segment's region. + **/ + int count; + + /** + * The table is rehashed when its size exceeds this threshold. + * (The value of this field is always (int)(capacity * + * loadFactor).) + */ + int threshold; + + /** + * The per-segment table. Declared as a raw type, casted + * to HashEntry<K,V> on each use. + */ + HashEntry[] table; + + /** + * The load factor for the hash table. Even though this value + * is same for all segments, it is replicated to avoid needing + * links to outer object. + * @serial + */ + final float loadFactor; + + this (int initialCapacity, float lf) + { + loadFactor = lf; + setTable (new HashEntry[initialCapacity]); + } + + /** + * Set table to new HashEntry array. + * Call only while holding lock or in constructor. + **/ + private final void setTable (HashEntry[] newTable) + { + threshold = cast(int) (newTable.length * loadFactor); + volatile table = newTable; + } + + /** + * Return properly casted first entry of bin for given hash + */ + private final HashEntry getFirst (uint hash) + { + HashEntry[] tab; + + volatile tab = table; + return tab [hash & (tab.length - 1)]; + } + + /** + * Return true if the two keys match + */ + private static final bool matchKey (K a, K b) + { + if (a.length == b.length) + return cast(bool) (memcmp (cast(char*) a, cast(char*) b, a.length) == 0); + return false; + } + + /* Specialized implementations of map methods */ + + final V get (K key, uint hash) + { + int c; + + // read-volatile + volatile c = count; + if (c) + { + HashEntry e = getFirst (hash); + while (e) + { + if (hash == e.hash && matchKey (key, e.key)) + { + V v; + volatile v = e.value; + if (v) + return v; + + synchronized (this) + return e.value; + } + e = e.next; + } + } + return null; + } + + + final bool containsKey (K key, uint hash) + { + int c; + + // read-volatile + volatile c = count; + if (c) + { + HashEntry e = getFirst (hash); + while (e) + { + if (e.hash == hash && matchKey (key, e.key)) + return true; + e = e.next; + } + } + return false; + } + + + + final synchronized V replace (K key, uint hash, V newValue) + { + HashEntry e = getFirst(hash); + while (e && (e.hash != hash || !matchKey (key, e.key))) + e = e.next; + + V oldValue = null; + if (e) + volatile + { + oldValue = e.value; + e.value = newValue; + } + return oldValue; + } + + + final synchronized V put (K key, uint hash, V value, bool onlyIfAbsent) + { + int c; + + volatile c = count; + if (c++ > threshold) + rehash(); + + HashEntry[] tab; + volatile tab = table; + uint index = hash & (tab.length - 1); + HashEntry first = tab[index]; + HashEntry e = first; + + while (e && (e.hash != hash || !matchKey (key, e.key))) + e = e.next; + + V oldValue; + if (e) + { + volatile oldValue = e.value; + if (!onlyIfAbsent) + volatile e.value = value; + } + else + { + oldValue = null; + tab[index] = new HashEntry (key, hash, first, value); + + // write-volatile + volatile count = c; + } + return oldValue; + } + + + private final void rehash () + { + HashEntry[] oldTable; + + volatile oldTable = table; + int oldCapacity = oldTable.length; + if (oldCapacity >= MAXIMUM_CAPACITY) + return; + + /* + * Reclassify nodes in each list to new Map. Because we are + * using power-of-two expansion, the elements from each bin + * must either stay at same index, or move with a power of two + * offset. We eliminate unnecessary node creation by catching + * cases where old nodes can be reused because their next + * fields won't change. Statistically, at the default + * threshold, only about one-sixth of them need cloning when + * a table doubles. The nodes they replace will be garbage + * collectable as soon as they are no longer referenced by any + * reader thread that may be in the midst of traversing table + * right now. + */ + + HashEntry[] newTable = new HashEntry[oldCapacity << 1]; + threshold = cast(int) (newTable.length * loadFactor); + int sizeMask = newTable.length - 1; + + for (int i = 0; i < oldCapacity ; ++i) + { + // We need to guarantee that any existing reads of old Map can + // proceed. So we cannot yet null out each bin. + HashEntry e = oldTable[i]; + + if (e) + { + HashEntry next = e.next; + uint idx = e.hash & sizeMask; + + // Single node on list + if (next is null) + newTable[idx] = e; + else + { + // Reuse trailing consecutive sequence at same slot + HashEntry lastRun = e; + int lastIdx = idx; + for (HashEntry last=next; last; last = last.next) + { + uint k = last.hash & sizeMask; + if (k != lastIdx) + { + lastIdx = k; + lastRun = last; + } + } + newTable[lastIdx] = lastRun; + + // Clone all remaining nodes + for (HashEntry p = e; p !is lastRun; p = p.next) + { + uint k = p.hash & sizeMask; + HashEntry n = newTable[k]; + newTable[k] = new HashEntry(p.key, p.hash, n, p.value); + } + } + } + } + volatile table = newTable; + } + + /** + * Remove; match on key only if value null, else match both. + */ + final synchronized V remove (K key, uint hash, V value) + { + int c; + HashEntry[] tab; + + volatile c = count - 1; + volatile tab = table; + + uint index = hash & (tab.length - 1); + HashEntry first = tab[index]; + HashEntry e = first; + + while (e && (e.hash != hash || !matchKey (key, e.key))) + e = e.next; + + V oldValue = null; + if (e) + { + V v; + volatile v = e.value; + if (value is null || value == v) + { + oldValue = v; + + // All entries following removed node can stay + // in list, but all preceding ones need to be + // cloned. + HashEntry newFirst = e.next; + for (HashEntry p = first; p !is e; p = p.next) + newFirst = new HashEntry (p.key, p.hash, newFirst, p.value); + tab[index] = newFirst; + + // write-volatile + volatile count = c; + } + } + return oldValue; + } + + + final synchronized void clear() + { + if (count) + { + HashEntry[] tab; + volatile tab = table; + + for (int i = 0; i < tab.length ; i++) + tab[i] = null; + + // write-volatile + volatile count = 0; + } + } + } + + + + /* ---------------- Public operations -------------- */ + + /** + * Creates a new, empty map with the specified initial + * capacity and the specified load factor. + * + * @param initialCapacity the initial capacity. The implementation + * performs internal sizing to accommodate this many elements. + * @param loadFactor the load factor threshold, used to control resizing. + * @param concurrencyLevel the estimated number of concurrently + * updating threads. The implementation performs internal sizing + * to try to accommodate this many threads. + * @throws IllegalArgumentException if the initial capacity is + * negative or the load factor or concurrencyLevel are + * nonpositive. + */ + public this (uint initialCapacity, float loadFactor, uint concurrencyLevel) + { + assert (loadFactor > 0); + + if (concurrencyLevel > MAX_SEGMENTS) + concurrencyLevel = MAX_SEGMENTS; + + // Find power-of-two sizes best matching arguments + int sshift = 0; + int ssize = 1; + while (ssize < concurrencyLevel) + { + ++sshift; + ssize <<= 1; + } + + segmentShift = 32 - sshift; + segmentMask = ssize - 1; + this.segments = new Segment[ssize]; + + if (initialCapacity > MAXIMUM_CAPACITY) + initialCapacity = MAXIMUM_CAPACITY; + + int c = initialCapacity / ssize; + if (c * ssize < initialCapacity) + ++c; + + int cap = 1; + while (cap < c) + cap <<= 1; + + for (int i = 0; i < this.segments.length; ++i) + this.segments[i] = new Segment (cap, loadFactor); + } + + /** + * Creates a new, empty map with the specified initial + * capacity, and with default load factor and concurrencyLevel. + * + * @param initialCapacity The implementation performs internal + * sizing to accommodate this many elements. + * @throws IllegalArgumentException if the initial capacity of + * elements is negative. + */ + public this (uint initialCapacity) + { + this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS); + } + + /** + * Creates a new, empty map with a default initial capacity, + * load factor, and concurrencyLevel. + */ + public this () + { + this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS); + } + + /** + * Returns the value to which the specified key is mapped in this table. + * + * @param key a key in the table. + * @return the value to which the key is mapped in this table; + * <tt>null</tt> if the key is not mapped to any value in + * this table. + * @throws NullPointerException if the key is + * <tt>null</tt>. + */ + public V get (K key) + { + uint hash = hash(key); // throws NullPointerException if key null + return segmentFor(hash).get(key, hash); + } + + /** + * Tests if the specified object is a key in this table. + * + * @param key possible key. + * @return <tt>true</tt> if and only if the specified object + * is a key in this table, as determined by the + * <tt>equals</tt> method; <tt>false</tt> otherwise. + * @throws NullPointerException if the key is + * <tt>null</tt>. + */ + public bool containsKey (K key) + { + uint hash = hash(key); // throws NullPointerException if key null + return segmentFor(hash).containsKey(key, hash); + } + + /** + * Maps the specified <tt>key</tt> to the specified + * <tt>value</tt> in this table. Neither the key nor the + * value can be <tt>null</tt>. + * + * <p> The value can be retrieved by calling the <tt>get</tt> method + * with a key that is equal to the original key. + * + * @param key the table key. + * @param value the value. + * @return the previous value of the specified key in this table, + * or <tt>null</tt> if it did not have one. + * @throws NullPointerException if the key or value is + * <tt>null</tt>. + */ + public V put (K key, V value) + { + assert (value); + + uint hash = hash(key); + return segmentFor(hash).put(key, hash, value, false); + } + + /** + * If the specified key is not already associated + * with a value, associate it with the given value. + * This is equivalent to + * <pre> + * if (!map.containsKey(key)) + * return map.put(key, value); + * else + * return map.get(key); + * </pre> + * Except that the action is performed atomically. + * @param key key with which the specified value is to be associated. + * @param value value to be associated with the specified key. + * @return previous value associated with specified key, or <tt>null</tt> + * if there was no mapping for key. + * @throws NullPointerException if the specified key or value is + * <tt>null</tt>. + */ + public V putIfAbsent (K key, V value) + { + assert (value); + + uint hash = hash(key); + return segmentFor(hash).put(key, hash, value, true); + } + + + /** + * Removes the key (and its corresponding value) from this + * table. This method does nothing if the key is not in the table. + * + * @param key the key that needs to be removed. + * @return the value to which the key had been mapped in this table, + * or <tt>null</tt> if the key did not have a mapping. + * @throws NullPointerException if the key is + * <tt>null</tt>. + */ + public V remove (K key) + { + uint hash = hash(key); + return segmentFor(hash).remove(key, hash, null); + } + + /** + * Remove entry for key only if currently mapped to given value. + * Acts as + * <pre> + * if (map.get(key).equals(value)) { + * map.remove(key); + * return true; + * } else return false; + * </pre> + * except that the action is performed atomically. + * @param key key with which the specified value is associated. + * @param value value associated with the specified key. + * @return true if the value was removed + * @throws NullPointerException if the specified key is + * <tt>null</tt>. + */ + public bool remove (K key, V value) + { + uint hash = hash(key); + return cast(bool) (segmentFor(hash).remove(key, hash, value) !is null); + } + + + /** + * Replace entry for key only if currently mapped to some value. + * Acts as + * <pre> + * if ((map.containsKey(key)) { + * return map.put(key, value); + * } else return null; + * </pre> + * except that the action is performed atomically. + * @param key key with which the specified value is associated. + * @param value value to be associated with the specified key. + * @return previous value associated with specified key, or <tt>null</tt> + * if there was no mapping for key. + * @throws NullPointerException if the specified key or value is + * <tt>null</tt>. + */ + public V replace (K key, V value) + { + assert (value); + + uint hash = hash(key); + return segmentFor(hash).replace(key, hash, value); + } + + + /** + * Removes all mappings from this map. + */ + public void clear () + { + for (int i = 0; i < segments.length; ++i) + segments[i].clear(); + } + + + /** + * Returns an enumeration of the keys in this table. + * + * @return an enumeration of the keys in this table. + * @see #keySet + */ + public KeyIterator keys () + { + return new KeyIterator (this); + } + + /** + * Returns an enumeration of the values in this table. + * + * @return an enumeration of the values in this table. + * @see #values + */ + public ValueIterator elements () + { + return new ValueIterator (this); + } + + /********************************************************************** + + Iterate over all keys in hashmap + + **********************************************************************/ + + int opApply (int delegate(inout char[]) dg) + { + int result = 0; + KeyIterator iterator = keys (); + + while (iterator.hasNext) + { + char[] ca = cast(char[]) iterator.next; + if ((result = dg (ca)) != 0) + break; + } + return result; + } + + /********************************************************************** + + Iterate over all keys in hashmap + + **********************************************************************/ + + int opApply (int delegate(inout char[], inout Object) dg) + { + int result = 0; + KeyIterator iterator = keys (); + + while (iterator.hasNext) + { + HashEntry he = iterator.nextElement; + char[] ca = cast(char[]) he.key; + if ((result = dg (ca, he.value)) != 0) + break; + } + return result; + } + + + /* ---------------- Iterator Support -------------- */ + + abstract static class HashIterator + { + int nextSegmentIndex; + int nextTableIndex; + HashEntry[] currentTable; + HashEntry nextEntry; + HashEntry lastReturned; + HashMap map; + + this (HashMap map) + { + this.map = map; + nextSegmentIndex = map.segments.length - 1; + nextTableIndex = -1; + advance(); + } + + final void advance () + { + if (nextEntry !is null && (nextEntry = nextEntry.next) !is null) + return; + + while (nextTableIndex >= 0) + { + if ( (nextEntry = currentTable[nextTableIndex--]) !is null) + return; + } + + while (nextSegmentIndex >= 0) + { + Segment seg = map.segments[nextSegmentIndex--]; + volatile if (seg.count) + { + currentTable = seg.table; + for (int j = currentTable.length - 1; j >= 0; --j) + { + if ((nextEntry = currentTable[j]) !is null) + { + nextTableIndex = j - 1; + return; + } + } + } + } + } + + public bool hasNext () + { + return cast(bool) (nextEntry !is null); + } + + HashEntry nextElement () + { + if (nextEntry is null) + throw new Exception ("no such element in HashMap"); + + lastReturned = nextEntry; + advance (); + return lastReturned; + } + } + + static class KeyIterator : HashIterator + { + this (HashMap map) {super (map);} + public K next() { return super.nextElement().key; } + } + + static class ValueIterator : HashIterator + { + this (HashMap map) {super (map);} + public V next() { volatile return super.nextElement().value; } + } + +} |