diff options
Diffstat (limited to 'debian/uncrustify-trinity/uncrustify-trinity-0.75.0/tests/expected/d/40000-HashMap.d')
| -rw-r--r-- | debian/uncrustify-trinity/uncrustify-trinity-0.75.0/tests/expected/d/40000-HashMap.d | 1106 |
1 files changed, 0 insertions, 1106 deletions
diff --git a/debian/uncrustify-trinity/uncrustify-trinity-0.75.0/tests/expected/d/40000-HashMap.d b/debian/uncrustify-trinity/uncrustify-trinity-0.75.0/tests/expected/d/40000-HashMap.d deleted file mode 100644 index 80b26e1d..00000000 --- a/debian/uncrustify-trinity/uncrustify-trinity-0.75.0/tests/expected/d/40000-HashMap.d +++ /dev/null @@ -1,1106 +0,0 @@ -/******************************************************************************* - - @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. bob_jenkins@burtleburtle.net. 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; - } - } -} |