diff options
Diffstat (limited to 'src/3rdparty/v8/src/hashmap.h')
-rw-r--r-- | src/3rdparty/v8/src/hashmap.h | 121 |
1 files changed, 121 insertions, 0 deletions
diff --git a/src/3rdparty/v8/src/hashmap.h b/src/3rdparty/v8/src/hashmap.h new file mode 100644 index 0000000..bb3e3ce --- /dev/null +++ b/src/3rdparty/v8/src/hashmap.h @@ -0,0 +1,121 @@ +// Copyright 2008 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_HASHMAP_H_ +#define V8_HASHMAP_H_ + +namespace v8 { +namespace internal { + + +// Allocator defines the memory allocator interface +// used by HashMap and implements a default allocator. +class Allocator BASE_EMBEDDED { + public: + virtual ~Allocator() {} + virtual void* New(size_t size) { return Malloced::New(size); } + virtual void Delete(void* p) { Malloced::Delete(p); } +}; + + +class HashMap { + public: + static Allocator DefaultAllocator; + + typedef bool (*MatchFun) (void* key1, void* key2); + + // Dummy constructor. This constructor doesn't set up the hash + // map properly so don't use it unless you have good reason (e.g., + // you know that the HashMap will never be used). + HashMap(); + + // initial_capacity is the size of the initial hash map; + // it must be a power of 2 (and thus must not be 0). + explicit HashMap(MatchFun match, + Allocator* allocator = &DefaultAllocator, + uint32_t initial_capacity = 8); + + ~HashMap(); + + // HashMap entries are (key, value, hash) triplets. + // Some clients may not need to use the value slot + // (e.g. implementers of sets, where the key is the value). + struct Entry { + void* key; + void* value; + uint32_t hash; // the full hash value for key + }; + + // If an entry with matching key is found, Lookup() + // returns that entry. If no matching entry is found, + // but insert is set, a new entry is inserted with + // corresponding key, key hash, and NULL value. + // Otherwise, NULL is returned. + Entry* Lookup(void* key, uint32_t hash, bool insert); + + // Removes the entry with matching key. + void Remove(void* key, uint32_t hash); + + // Empties the hash map (occupancy() == 0). + void Clear(); + + // The number of (non-empty) entries in the table. + uint32_t occupancy() const { return occupancy_; } + + // The capacity of the table. The implementation + // makes sure that occupancy is at most 80% of + // the table capacity. + uint32_t capacity() const { return capacity_; } + + // Iteration + // + // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { + // ... + // } + // + // If entries are inserted during iteration, the effect of + // calling Next() is undefined. + Entry* Start() const; + Entry* Next(Entry* p) const; + + private: + Allocator* allocator_; + MatchFun match_; + Entry* map_; + uint32_t capacity_; + uint32_t occupancy_; + + Entry* map_end() const { return map_ + capacity_; } + Entry* Probe(void* key, uint32_t hash); + void Initialize(uint32_t capacity); + void Resize(); +}; + + +} } // namespace v8::internal + +#endif // V8_HASHMAP_H_ |