15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2005, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Sanjay Ghemawat 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A fast map from addresses to values. Assumes that addresses are 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// clustered. The main use is intended to be for heap-profiling. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// May be too memory-hungry for other uses. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We use a user-defined allocator/de-allocator so that we can use 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this data structure during heap-profiling. 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// IMPLEMENTATION DETAIL: 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Some default definitions/parameters: 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Block -- aligned 128-byte region of the address space 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Cluster -- aligned 1-MB region of the address space 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Block-ID -- block-number within a cluster 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Cluster-ID -- Starting address of cluster divided by cluster size 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We use a three-level map to represent the state: 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1. A hash-table maps from a cluster-ID to the data for that cluster. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 2. For each non-empty cluster we keep an array indexed by 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// block-ID tht points to the first entry in the linked-list 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for the block. 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 3. At the bottom, we keep a singly-linked list of all 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// entries in a block (for non-empty blocks). 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// hash table 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// +-------------+ 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | id->cluster |---> ... 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | ... | 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | id->cluster |---> Cluster 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// +-------------+ +-------+ Data for one block 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | nil | +------------------------------------+ 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | ----+---|->[addr/value]-->[addr/value]-->... | 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | nil | +------------------------------------+ 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | ----+--> ... 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | nil | 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// | ... | 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// +-------+ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note that we require zero-bytes of overhead for completely empty 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// clusters. The minimum space requirement for a cluster is the size 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// of the hash-table entry plus a pointer value for each block in 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the cluster. Empty blocks impose no extra space requirement. 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The cost of a lookup is: 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a. A hash-table lookup to find the cluster 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// b. An array access in the cluster structure 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// c. A traversal over the linked-list for a block 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef BASE_ADDRESSMAP_INL_H_ 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define BASE_ADDRESSMAP_INL_H_ 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config.h" 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stddef.h> 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h> 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined HAVE_STDINT_H 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdint.h> // to get uint16_t (ISO naming madness) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#elif defined HAVE_INTTYPES_H 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <inttypes.h> // another place uint16_t might be defined 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <sys/types.h> // our last best hope 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class is thread-unsafe -- that is, instances of this class can 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// not be accessed concurrently by multiple threads -- because the 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// callback function for Iterate() may mutate contained values. If the 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// callback functions you pass do not mutate their Value* argument, 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// AddressMap can be treated as thread-compatible -- that is, it's 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// safe for multiple threads to call "const" methods on this class, 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but not safe for one thread to call const methods on this class 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// while another thread is calling non-const methods on the class. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class AddressMap { 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef void* (*Allocator)(size_t size); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef void (*DeAllocator)(void* ptr); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef const void* Key; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create an AddressMap that uses the specified allocator/deallocator. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The allocator/deallocator should behave like malloc/free. 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For instance, the allocator does not need to return initialized memory. 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddressMap(Allocator alloc, DeAllocator dealloc); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~AddressMap(); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the map contains an entry for "key", return it. Else return NULL. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline const Value* Find(Key key) const; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline Value* FindMutable(Key key); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Insert <key,value> into the map. Any old value associated 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // with key is forgotten. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Insert(Key key, Value value); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove any entry for key in the map. If an entry was found 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and removed, stores the associated value in "*removed_value" 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and returns true. Else returns false. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool FindAndRemove(Key key, Value* removed_value); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Similar to Find but we assume that keys are addresses of non-overlapping 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // memory ranges whose sizes are given by size_func. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the map contains a range into which "key" points 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (at its start or inside of it, but not at the end), 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // return the address of the associated value 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and store its key in "*res_key". 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Else return NULL. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // max_size specifies largest range size possibly in existence now. 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef size_t (*ValueSizeFunc)(const Value& v); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Value* FindInside(ValueSizeFunc size_func, size_t max_size, 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Key key, Key* res_key); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterate over the address map calling 'callback' 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for all stored key-value pairs and passing 'arg' to it. 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We don't use full Closure/Callback machinery not to add 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // unnecessary dependencies to this class with low-level uses. 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template<class Type> 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void Iterate(void (*callback)(Key, Value*, Type), Type arg) const; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef uintptr_t Number; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The implementation assumes that addresses inserted into the map 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will be clustered. We take advantage of this fact by splitting 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // up the address-space into blocks and using a linked-list entry 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for each block. 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Size of each block. There is one linked-list for each block, so 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // do not make the block-size too big. Oterwise, a lot of time 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will be spent traversing linked lists. 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kBlockBits = 7; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kBlockSize = 1 << kBlockBits; 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Entry kept in per-block linked-list 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Entry { 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Entry* next; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Key key; 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value value; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We further group a sequence of consecutive blocks into a cluster. 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The data for a cluster is represented as a dense array of 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // linked-lists, one list per contained block. 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kClusterBits = 13; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const Number kClusterSize = 1 << (kBlockBits + kClusterBits); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kClusterBlocks = 1 << kClusterBits; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We use a simple chaining hash-table to represent the clusters. 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Cluster { 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cluster* next; // Next cluster in hash table chain 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Number id; // Cluster ID 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Entry* blocks[kClusterBlocks]; // Per-block linked-lists 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Number of hash-table entries. With the block-size/cluster-size 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // defined above, each cluster covers 1 MB, so an 4K entry 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // hash-table will give an average hash-chain length of 1 for 4GB of 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // in-use memory. 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kHashBits = 12; 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kHashSize = 1 << 12; 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Number of entry objects allocated at a time 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int ALLOC_COUNT = 64; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cluster** hashtable_; // The hash-table 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Entry* free_; // Free list of unused Entry objects 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Multiplicative hash function: 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The value "kHashMultiplier" is the bottom 32 bits of 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // int((sqrt(5)-1)/2 * 2^32) 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is a good multiplier as suggested in CLR, Knuth. The hash 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // value is taken to be the top "k" bits of the bottom 32 bits 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of the muliplied value. 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint32_t kHashMultiplier = 2654435769u; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int HashInt(Number x) { 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Multiply by a constant and take the top bits of the result. 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint32_t m = static_cast<uint32_t>(x) * kHashMultiplier; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return static_cast<int>(m >> (32 - kHashBits)); 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find cluster object for specified address. If not found 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and "create" is true, create the object. If not found 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and "create" is false, return NULL. 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This method is bitwise-const if create is false. 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cluster* FindCluster(Number address, bool create) { 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Look in hashtable 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number cluster_id = address >> (kBlockBits + kClusterBits); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int h = HashInt(cluster_id); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Cluster* c = hashtable_[h]; c != NULL; c = c->next) { 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (c->id == cluster_id) { 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return c; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create cluster if necessary 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (create) { 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cluster* c = New<Cluster>(1); 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) c->id = cluster_id; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) c->next = hashtable_[h]; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hashtable_[h] = c; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return c; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the block ID for an address within its cluster 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int BlockID(Number address) { 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (address >> kBlockBits) & (kClusterBlocks - 1); 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //-------------------------------------------------------------- 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Memory management -- we keep all objects we allocate linked 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // together in a singly linked list so we can get rid of them 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when we are all done. Furthermore, we allow the client to 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // pass in custom memory allocator/deallocator routines. 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //-------------------------------------------------------------- 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Object { 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Object* next; 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The real data starts here 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Allocator alloc_; // The allocator 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeAllocator dealloc_; // The deallocator 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Object* allocated_; // List of allocated objects 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocates a zeroed array of T with length "num". Also inserts 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the allocated block into a linked list so it can be deallocated 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when we are all done. 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template <class T> T* New(int num) { 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* ptr = (*alloc_)(sizeof(Object) + num*sizeof(T)); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(ptr, 0, sizeof(Object) + num*sizeof(T)); 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Object* obj = reinterpret_cast<Object*>(ptr); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) obj->next = allocated_; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) allocated_ = obj; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reinterpret_cast<T*>(reinterpret_cast<Object*>(ptr) + 1); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// More implementation details follow: 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)AddressMap<Value>::AddressMap(Allocator alloc, DeAllocator dealloc) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : free_(NULL), 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc_(alloc), 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dealloc_(dealloc), 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) allocated_(NULL) { 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hashtable_ = New<Cluster*>(kHashSize); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)AddressMap<Value>::~AddressMap() { 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // De-allocate all of the objects we allocated 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Object* obj = allocated_; obj != NULL; /**/) { 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Object* next = obj->next; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (*dealloc_)(obj); 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) obj = next; 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline const Value* AddressMap<Value>::Find(Key key) const { 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return const_cast<AddressMap*>(this)->FindMutable(key); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline Value* AddressMap<Value>::FindMutable(Key key) { 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number num = reinterpret_cast<Number>(key); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cluster* const c = FindCluster(num, false/*do not create*/); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (c != NULL) { 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Entry* e = c->blocks[BlockID(num)]; e != NULL; e = e->next) { 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (e->key == key) { 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &e->value; 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void AddressMap<Value>::Insert(Key key, Value value) { 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number num = reinterpret_cast<Number>(key); 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cluster* const c = FindCluster(num, true/*create*/); 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Look in linked-list for this block 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int block = BlockID(num); 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Entry* e = c->blocks[block]; e != NULL; e = e->next) { 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (e->key == key) { 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->value = value; 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create entry 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (free_ == NULL) { 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate a new batch of entries and add to free-list 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Entry* array = New<Entry>(ALLOC_COUNT); 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < ALLOC_COUNT-1; i++) { 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array[i].next = &array[i+1]; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array[ALLOC_COUNT-1].next = free_; 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free_ = &array[0]; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Entry* e = free_; 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free_ = e->next; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->key = key; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->value = value; 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->next = c->blocks[block]; 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) c->blocks[block] = e; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool AddressMap<Value>::FindAndRemove(Key key, Value* removed_value) { 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number num = reinterpret_cast<Number>(key); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cluster* const c = FindCluster(num, false/*do not create*/); 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (c != NULL) { 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Entry** p = &c->blocks[BlockID(num)]; *p != NULL; p = &(*p)->next) { 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Entry* e = *p; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (e->key == key) { 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *removed_value = e->value; 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *p = e->next; // Remove e from linked-list 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->next = free_; // Add e to free-list 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) free_ = e; 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const Value* AddressMap<Value>::FindInside(ValueSizeFunc size_func, 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t max_size, 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Key key, 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Key* res_key) { 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number key_num = reinterpret_cast<Number>(key); 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Number num = key_num; // we'll move this to move back through the clusters 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (1) { 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cluster* c = FindCluster(num, false/*do not create*/); 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (c != NULL) { 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (1) { 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int block = BlockID(num); 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool had_smaller_key = false; 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (const Entry* e = c->blocks[block]; e != NULL; e = e->next) { 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number e_num = reinterpret_cast<Number>(e->key); 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (e_num <= key_num) { 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (e_num == key_num || // to handle 0-sized ranges 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_num < e_num + (*size_func)(e->value)) { 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *res_key = e->key; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &e->value; 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) had_smaller_key = true; 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (had_smaller_key) return NULL; // got a range before 'key' 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and it did not contain 'key' 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (block == 0) break; 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // try address-wise previous block 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num |= kBlockSize - 1; // start at the last addr of prev block 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num -= kBlockSize; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_num - num > max_size) return NULL; 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (num < kClusterSize) return NULL; // first cluster 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // go to address-wise previous cluster to try 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num |= kClusterSize - 1; // start at the last block of previous cluster 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num -= kClusterSize; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_num - num > max_size) return NULL; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Having max_size to limit the search is crucial: else 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we have to traverse a lot of empty clusters (or blocks). 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We can avoid needing max_size if we put clusters into 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a search tree, but performance suffers considerably 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if we use this approach by using stl::set. 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Value> 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class Type> 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void AddressMap<Value>::Iterate(void (*callback)(Key, Value*, Type), 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Type arg) const { 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We could optimize this by traversing only non-empty clusters and/or blocks 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // but it does not speed up heap-checker noticeably. 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int h = 0; h < kHashSize; ++h) { 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (const Cluster* c = hashtable_[h]; c != NULL; c = c->next) { 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int b = 0; b < kClusterBlocks; ++b) { 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Entry* e = c->blocks[b]; e != NULL; e = e->next) { 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) callback(e->key, &e->value, arg); 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // BASE_ADDRESSMAP_INL_H_ 422