dyld3/Map.h

   1 /*
   2  * Copyright (c) 2017 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 #ifndef Map_h
  25 #define Map_h
  26
  27 #include "Array.h"
  28
  29 namespace dyld3 {
  30
  31
  32
  33 template<typename T>
  34 struct Hash {
  35     static size_t hash(const T&);
  36 };
  37
  38 template<typename T>
  39 struct Equal {
  40     static bool equal(const T&a, const T& b);
  41 };
  42
  43 template<typename KeyT, typename ValueT, class GetHash = Hash<KeyT>, class IsEqual = Equal<KeyT>>
  44 class Map {
  45     typedef std::pair<KeyT, ValueT>     NodeT;
  46     typedef NodeT*                      iterator;
  47     typedef const NodeT*                const_iterator;
  48
  49     enum : size_t {
  50         SentinelHash = (size_t)-1
  51     };
  52
  53 public:
  54     Map() {
  55         // Keep the hash buffer about 75% full
  56         nextHashBufferGrowth = 768;
  57         hashBufferUseCount = 0;
  58         hashBuffer.reserve(1024);
  59         for (size_t i = 0; i != 1024; ++i) {
  60             hashBuffer.push_back(SentinelHash);
  61         }
  62         nodeBuffer.reserve(1024);
  63     }
  64
  65     iterator find(const KeyT& key) {
  66         // Find the index to look up in the hash buffer
  67         size_t hashIndex = GetHash::hash(key) & (hashBuffer.count() - 1);
  68
  69         // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
  70         size_t probeAmount = 1;
  71         while (true) {
  72             size_t nodeBufferIndex = hashBuffer[hashIndex];
  73
  74             if (nodeBufferIndex == SentinelHash) {
  75                 // This node is unused, so we don't have this element
  76                 return end();
  77             }
  78
  79             // If that hash is in use, then check if that node is actually the one we are trying to find
  80             if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, key)) {
  81                 // Keys match so we found this element
  82                 return &nodeBuffer[nodeBufferIndex];
  83             }
  84
  85             // We didn't find this node, so try with a later one
  86             hashIndex += probeAmount;
  87             hashIndex &= (hashBuffer.count() - 1);
  88             ++probeAmount;
  89         }
  90
  91         assert(0 && "unreachable");
  92     }
  93
  94     const_iterator find(const KeyT& key) const {
  95         // Find the index to look up in the hash buffer
  96         size_t hashIndex = GetHash::hash(key) & (hashBuffer.count() - 1);
  97
  98         // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
  99         size_t probeAmount = 1;
 100         while (true) {
 101             size_t nodeBufferIndex = hashBuffer[hashIndex];
 102
 103             if (nodeBufferIndex == SentinelHash) {
 104                 // This node is unused, so we don't have this element
 105                 return end();
 106             }
 107
 108             // If that hash is in use, then check if that node is actually the one we are trying to find
 109             if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, key)) {
 110                 // Keys match so we found this element
 111                 return &nodeBuffer[nodeBufferIndex];
 112             }
 113
 114             // We didn't find this node, so try with a later one
 115             hashIndex += probeAmount;
 116             hashIndex &= (hashBuffer.count() - 1);
 117             ++probeAmount;
 118         }
 119
 120         assert(0 && "unreachable");
 121     }
 122
 123     iterator begin() {
 124         return nodeBuffer.begin();
 125     }
 126
 127     iterator end() {
 128         return nodeBuffer.end();
 129     }
 130
 131     const_iterator begin() const {
 132         return nodeBuffer.begin();
 133     }
 134
 135     const_iterator end() const {
 136         return nodeBuffer.end();
 137     }
 138
 139     const Array<NodeT>& array() const {
 140         return nodeBuffer;
 141     }
 142
 143     std::pair<iterator, bool> insert(NodeT&& v) {
 144         // First see if we have enough space.  We don't want the hash buffer to get too full.
 145         if (hashBufferUseCount == nextHashBufferGrowth) {
 146             // Grow and rehash everything.
 147             size_t newHashTableSize = hashBuffer.count() * 2;
 148             nextHashBufferGrowth *= 2;
 149
 150             dyld3::OverflowSafeArray<size_t> newHashBuffer;
 151             newHashBuffer.reserve(newHashTableSize);
 152             for (size_t i = 0; i != newHashTableSize; ++i) {
 153                 newHashBuffer.push_back(SentinelHash);
 154             }
 155
 156             // Walk the existing nodes trying to populate the new hash buffer and looking for collisions
 157             for (size_t i = 0; i != nodeBuffer.count(); ++i) {
 158                 const KeyT& key = nodeBuffer[i].first;
 159                 size_t newHashIndex = GetHash::hash(key) & (newHashBuffer.count() - 1);
 160
 161                 // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
 162                 size_t probeAmount = 1;
 163                 while (true) {
 164                     size_t newNodeBufferIndex = newHashBuffer[newHashIndex];
 165
 166                     if (newNodeBufferIndex == SentinelHash) {
 167                         // This node is unused, so we don't have this element.  Lets add it
 168                         newHashBuffer[newHashIndex] = i;
 169                         break;
 170                     }
 171
 172                     // Don't bother checking for matching keys here.  We know we are adding elements with different keys
 173                     // Just probe to find the next sentinel
 174
 175                     // We didn't find this node, so try with a later one
 176                     newHashIndex += probeAmount;
 177                     newHashIndex &= (newHashBuffer.count() - 1);
 178                     ++probeAmount;
 179                 }
 180             }
 181
 182             // Use the new buffer
 183             hashBuffer = std::move(newHashBuffer);
 184         }
 185
 186         // Find the index to look up in the hash buffer
 187         size_t hashIndex = GetHash::hash(v.first) & (hashBuffer.count() - 1);
 188
 189         // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
 190         size_t probeAmount = 1;
 191         while (true) {
 192             size_t nodeBufferIndex = hashBuffer[hashIndex];
 193
 194             if (nodeBufferIndex == SentinelHash) {
 195                 // This node is unused, so we don't have this element.  Lets add it
 196                 hashBuffer[hashIndex] = nodeBuffer.count();
 197                 ++hashBufferUseCount;
 198                 nodeBuffer.push_back(v);
 199                 return { &nodeBuffer.back(), true };
 200             }
 201
 202             // If that hash is in use, then check if that node is actually the one we are trying to insert
 203             if (IsEqual::equal(nodeBuffer[nodeBufferIndex].first, v.first)) {
 204                 // Keys match.  We already have this element
 205                 return { &nodeBuffer[nodeBufferIndex], false };
 206             }
 207
 208             // We didn't find this node, so try with a later one
 209             hashIndex += probeAmount;
 210             hashIndex &= (hashBuffer.count() - 1);
 211             ++probeAmount;
 212         }
 213
 214         assert(0 && "unreachable");
 215     }
 216
 217
 218     ValueT& operator[](KeyT idx) {
 219         auto itAndInserted = insert({ idx, ValueT() });
 220         return itAndInserted.first->second;
 221     }
 222
 223 private:
 224     size_t                              nextHashBufferGrowth;
 225     size_t                              hashBufferUseCount;
 226     dyld3::OverflowSafeArray<size_t>    hashBuffer;
 227     dyld3::OverflowSafeArray<NodeT>     nodeBuffer;
 228 };
 229
 230 template<typename KeyT, typename ValueT, class GetHash = Hash<KeyT>, class IsEqual = Equal<KeyT>>
 231 class MultiMap {
 232
 233     struct NextNode {
 234         size_t isDuplicateHead  : 1;
 235         size_t isDuplicateEntry : 1;
 236         size_t isDuplicateTail  : 1;
 237         size_t nextIndex        : 29;
 238
 239         bool hasAnyDuplicates() const {
 240             return isDuplicateHead || isDuplicateEntry || isDuplicateTail;
 241         }
 242
 243         bool hasMoreDuplicates() const {
 244             return isDuplicateHead || isDuplicateEntry;
 245         }
 246
 247         static NextNode makeNoDuplicates() {
 248             return { 0, 0, 0, 0 };
 249         }
 250
 251         static NextNode makeDuplicateTailNode() {
 252             return { 0, 0, 1, 0 };
 253         }
 254     };
 255     static_assert(sizeof(NextNode) == sizeof(size_t), "Invalid size");
 256
 257     typedef std::pair<KeyT, ValueT>             NodeT;
 258     typedef std::tuple<KeyT, ValueT, NextNode>  NodeEntryT;
 259     typedef NodeT*                              iterator;
 260     typedef const NodeT*                        const_iterator;
 261
 262     enum : size_t {
 263         SentinelHash        = (size_t)-1
 264     };
 265
 266 public:
 267     MultiMap() {
 268         // Keep the hash buffer about 75% full
 269         nextHashBufferGrowth = 768;
 270         hashBufferUseCount = 0;
 271         hashBuffer.reserve(1024);
 272         for (size_t i = 0; i != 1024; ++i) {
 273             hashBuffer.push_back(SentinelHash);
 274         }
 275         nodeBuffer.reserve(1024);
 276     }
 277
 278     void forEachEntry(void (^handler)(const KeyT& key, const ValueT** values, uint64_t valuesCount)) const {
 279         // Walk the top level nodes, skipping dupes
 280         for (const NodeEntryT& headNode : nodeBuffer) {
 281             NextNode nextNode = std::get<2>(headNode);
 282             if (!nextNode.hasAnyDuplicates()) {
 283                 const ValueT* value[1] = { &std::get<1>(headNode) };
 284                 handler(std::get<0>(headNode), value, 1);
 285                 continue;
 286             }
 287
 288             if (!nextNode.isDuplicateHead)
 289                 continue;
 290
 291             // This is the head of a list.  Work out how long the list is
 292             uint64_t valuesCount = 1;
 293             while (std::get<2>(nodeBuffer[nextNode.nextIndex]).hasMoreDuplicates()) {
 294                 nextNode = std::get<2>(nodeBuffer[nextNode.nextIndex]);
 295                 ++valuesCount;
 296             }
 297
 298             // Add one more for the last node
 299             ++valuesCount;
 300
 301             // Now make an array with that many value for the callback
 302             const ValueT* values[valuesCount];
 303             // Copy in the head
 304             values[0] = &std::get<1>(headNode);
 305
 306             // And copy the remainder
 307             nextNode = std::get<2>(headNode);
 308             valuesCount = 1;
 309             while (std::get<2>(nodeBuffer[nextNode.nextIndex]).hasMoreDuplicates()) {
 310                 values[valuesCount] = &std::get<1>(nodeBuffer[nextNode.nextIndex]);
 311                 nextNode = std::get<2>(nodeBuffer[nextNode.nextIndex]);
 312                 ++valuesCount;
 313             }
 314
 315             // Add in the last node
 316             values[valuesCount] = &std::get<1>(nodeBuffer[nextNode.nextIndex]);
 317             ++valuesCount;
 318
 319             // Finally call the handler with a whole array of values.
 320             handler(std::get<0>(headNode), values, valuesCount);
 321         }
 322     }
 323
 324     void insert(NodeT&& v) {
 325         // First see if we have enough space.  We don't want the hash buffer to get too full.
 326         if (hashBufferUseCount == nextHashBufferGrowth) {
 327             // Grow and rehash everything.
 328             size_t newHashTableSize = hashBuffer.count() * 2;
 329             nextHashBufferGrowth *= 2;
 330
 331             dyld3::OverflowSafeArray<size_t> newHashBuffer;
 332             newHashBuffer.reserve(newHashTableSize);
 333             for (size_t i = 0; i != newHashTableSize; ++i) {
 334                 newHashBuffer.push_back(SentinelHash);
 335             }
 336
 337             // Walk the existing nodes trying to populate the new hash buffer and looking for collisions
 338             for (size_t i = 0; i != nodeBuffer.count(); ++i) {
 339                 // Skip nodes which are not the head of the list
 340                 // They aren't moving the buffer anyway
 341                 NextNode nextNode = std::get<2>(nodeBuffer[i]);
 342                 if (nextNode.isDuplicateEntry || nextNode.isDuplicateTail)
 343                     continue;
 344                 const KeyT& key = std::get<0>(nodeBuffer[i]);
 345                 size_t newHashIndex = GetHash::hash(key) & (newHashBuffer.count() - 1);
 346
 347                 // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
 348                 size_t probeAmount = 1;
 349                 while (true) {
 350                     size_t newNodeBufferIndex = newHashBuffer[newHashIndex];
 351
 352                     if (newNodeBufferIndex == SentinelHash) {
 353                         // This node is unused, so we don't have this element.  Lets add it
 354                         newHashBuffer[newHashIndex] = i;
 355                         break;
 356                     }
 357
 358                     // Don't bother checking for matching keys here.  We know we are adding elements with different keys
 359                     // Just probe to find the next sentinel
 360
 361                     // We didn't find this node, so try with a later one
 362                     newHashIndex += probeAmount;
 363                     newHashIndex &= (newHashBuffer.count() - 1);
 364                     ++probeAmount;
 365                 }
 366             }
 367
 368             // Use the new buffer
 369             hashBuffer = std::move(newHashBuffer);
 370         }
 371
 372         // Find the index to look up in the hash buffer
 373         size_t hashIndex = GetHash::hash(v.first) & (hashBuffer.count() - 1);
 374
 375         // Note we'll use a quadratic probe to look past identical hashes until we find our node or a sentinel
 376         size_t probeAmount = 1;
 377         while (true) {
 378             size_t nodeBufferIndex = hashBuffer[hashIndex];
 379
 380             if (nodeBufferIndex == SentinelHash) {
 381                 // This node is unused, so we don't have this element.  Lets add it
 382                 hashBuffer[hashIndex] = nodeBuffer.count();
 383                 ++hashBufferUseCount;
 384                 nodeBuffer.push_back({ v.first, v.second, NextNode::makeNoDuplicates() } );
 385                 return;
 386             }
 387
 388             // If that hash is in use, then check if that node is actually the one we are trying to insert
 389             if (IsEqual::equal(std::get<0>(nodeBuffer[nodeBufferIndex]), v.first)) {
 390                 // Keys match.  We already have this element
 391                 // But this is a multimap so add the new element too
 392                 // Walk from this node to find the end of the chain
 393                 while (std::get<2>(nodeBuffer[nodeBufferIndex]).hasMoreDuplicates()) {
 394                     nodeBufferIndex = std::get<2>(nodeBuffer[nodeBufferIndex]).nextIndex;
 395                 }
 396                 NextNode& tailNode = std::get<2>(nodeBuffer[nodeBufferIndex]);
 397                 if (!tailNode.hasAnyDuplicates()) {
 398                     // If the previous node has no duplicates then its now the new head of a list
 399                     tailNode.isDuplicateHead = 1;
 400                     tailNode.nextIndex = nodeBuffer.count();
 401                 } else {
 402                     // This must be a tail node.  Update it to be an entry node
 403                     assert(tailNode.isDuplicateTail);
 404                     tailNode.isDuplicateTail = 0;
 405                     tailNode.isDuplicateEntry = 1;
 406                     tailNode.nextIndex = nodeBuffer.count();
 407                 }
 408                 //.nextIndex = nodeBuffer.count();
 409                 nodeBuffer.push_back({ v.first, v.second, NextNode::makeDuplicateTailNode() } );
 410                 return;
 411             }
 412
 413             // We didn't find this node, so try with a later one
 414             hashIndex += probeAmount;
 415             hashIndex &= (hashBuffer.count() - 1);
 416             ++probeAmount;
 417         }
 418
 419         assert(0 && "unreachable");
 420     }
 421
 422 private:
 423     size_t                                  nextHashBufferGrowth;
 424     size_t                                  hashBufferUseCount;
 425     dyld3::OverflowSafeArray<size_t>        hashBuffer;
 426     dyld3::OverflowSafeArray<NodeEntryT>    nodeBuffer;
 427 };
 428
 429 } // namespace dyld3
 430
 431 #endif /* Map_h */