15d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com/* 25d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com * Copyright 2013 Google Inc. 35d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com * 45d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com * Use of this source code is governed by a BSD-style license that can be 55d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com * found in the LICENSE file. 65d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com */ 75d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com 85d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com#ifndef SkTDynamicHash_DEFINED 95d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com#define SkTDynamicHash_DEFINED 105d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com 11f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org#include "SkMath.h" 125b8bde5db24f581d69b7efce72cf42110b80eaf5commit-bot@chromium.org#include "SkTemplates.h" 135b8bde5db24f581d69b7efce72cf42110b80eaf5commit-bot@chromium.org#include "SkTypes.h" 145d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com 1555bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org// Traits requires: 1655bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org// static const Key& GetKey(const T&) { ... } 1755bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org// static uint32_t Hash(const Key&) { ... } 1855bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org// We'll look on T for these by default, or you can pass a custom Traits type. 19b14ecdaeea96c8c210c7835058889c6b9a756833reed@google.comtemplate <typename T, 20f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org typename Key, 2155bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org typename Traits = T, 227a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org int kGrowPercent = 75> // Larger -> more memory efficient, but slower. 235d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.comclass SkTDynamicHash { 245d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.compublic: 257a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { 26c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com SkASSERT(this->validate()); 27c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 28f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 295d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com ~SkTDynamicHash() { 30f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org sk_free(fArray); 315d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 32956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 331f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org class Iter { 341f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org public: 351f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) { 361f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org SkASSERT(hash); 371f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org ++(*this); 381f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org } 391f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org bool done() const { 401f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org SkASSERT(fCurrentIndex <= fHash->fCapacity); 411f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org return fCurrentIndex == fHash->fCapacity; 421f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org } 431f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org T& operator*() const { 441f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org SkASSERT(!this->done()); 451f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org return *this->current(); 461f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org } 471f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org void operator++() { 481f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org do { 491f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org fCurrentIndex++; 501f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org } while (!this->done() && (this->current() == Empty() || this->current() == Deleted())); 511f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org } 521f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org 531f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org private: 541f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org T* current() const { return fHash->fArray[fCurrentIndex]; } 551f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org 561f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org SkTDynamicHash* fHash; 571f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org int fCurrentIndex; 581f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org }; 591f6cf695b30d2a7a4e7f046f04868a6e430b05b0commit-bot@chromium.org 603d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips class ConstIter { 613d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips public: 623d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) { 633d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips SkASSERT(hash); 643d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips ++(*this); 653d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 663d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips bool done() const { 673d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips SkASSERT(fCurrentIndex <= fHash->fCapacity); 683d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips return fCurrentIndex == fHash->fCapacity; 693d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 703d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips const T& operator*() const { 713d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips SkASSERT(!this->done()); 723d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips return *this->current(); 733d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 743d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips void operator++() { 753d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips do { 763d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fCurrentIndex++; 773d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } while (!this->done() && (this->current() == Empty() || this->current() == Deleted())); 783d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 793d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips 803d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips private: 813d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips const T* current() const { return fHash->fArray[fCurrentIndex]; } 823d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips 833d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips const SkTDynamicHash* fHash; 843d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips int fCurrentIndex; 853d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips }; 863d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips 87f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int count() const { return fCount; } 88956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 89f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // Return the entry with this key if we have it, otherwise NULL. 90f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org T* find(const Key& key) const { 91f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int index = this->firstIndex(key); 92f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org for (int round = 0; round < fCapacity; round++) { 932e09d18f78f5772d2d9506ff8024ca8542654358mtklein SkASSERT(index >= 0 && index < fCapacity); 945d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com T* candidate = fArray[index]; 95c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com if (Empty() == candidate) { 965d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com return NULL; 975d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 98158f64626f8dae7e8437744184860d0110b88609commit-bot@chromium.org if (Deleted() != candidate && GetKey(*candidate) == key) { 995d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com return candidate; 1005d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 101f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org index = this->nextIndex(index, round); 102f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org } 1037a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org SkASSERT(fCapacity == 0); 1045d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com return NULL; 1055d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 106956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 107c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com // Add an entry with this key. We require that no entry with newEntry's key is already present. 108f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org void add(T* newEntry) { 109c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com SkASSERT(NULL == this->find(GetKey(*newEntry))); 110f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org this->maybeGrow(); 111c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com this->innerAdd(newEntry); 112c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com SkASSERT(this->validate()); 113f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org } 114f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 1153d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips // Remove the entry with this key. We require that an entry with this key is present. 116f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org void remove(const Key& key) { 11749f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(this->find(key)); 118f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org this->innerRemove(key); 119c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com SkASSERT(this->validate()); 1205d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 121956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 1223d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips void rewind() { 12349f085dddff10473b6ebf832a974288300224e60bsalomon if (fArray) { 1243d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips sk_bzero(fArray, sizeof(T*)* fCapacity); 1253d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 1263d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fCount = 0; 1273d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fDeleted = 0; 1283d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 1293d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips 1303d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips void reset() { 1313d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fCount = 0; 1323d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fDeleted = 0; 1333d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fCapacity = 0; 1343d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips sk_free(fArray); 1353d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips fArray = NULL; 1363d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips } 1373d533ac917eaadf2fb3561f57d7266d8c0e665fdrobertphillips 138f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.orgprotected: 139f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // These methods are used by tests only. 140956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 141f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int capacity() const { return fCapacity; } 142f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 143f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // How many collisions do we go through before finding where this entry should be inserted? 144f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int countCollisions(const Key& key) const { 145f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int index = this->firstIndex(key); 146f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org for (int round = 0; round < fCapacity; round++) { 1472e09d18f78f5772d2d9506ff8024ca8542654358mtklein SkASSERT(index >= 0 && index < fCapacity); 1485d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com const T* candidate = fArray[index]; 149158f64626f8dae7e8437744184860d0110b88609commit-bot@chromium.org if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) { 150f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org return round; 1515d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 152f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org index = this->nextIndex(index, round); 1535d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 1547a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org SkASSERT(fCapacity == 0); 1557a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org return 0; 1565d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 157956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 1585d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.comprivate: 159f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // We have two special values to indicate an empty or deleted entry. 160c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL 161c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer. 162f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 163c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com bool validate() const { 16400ed9a909c06a139af54c1eded2e67c8354c6098dongseong.hwang #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false 165cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org static const int kLarge = 50; // Arbitrary, tweak to suit your patience. 166c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com 167cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org // O(1) checks, always done. 168c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com // Is capacity sane? 169ba0ca99b83d3e084811fd1764d227d850fab4d43mtklein@google.com SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); 170c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com 171cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org // O(N) checks, skipped when very large. 172cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org if (fCount < kLarge * kLarge) { 173cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org // Are fCount and fDeleted correct, and are all elements findable? 174cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org int count = 0, deleted = 0; 175cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org for (int i = 0; i < fCapacity; i++) { 176cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org if (Deleted() == fArray[i]) { 177cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org deleted++; 178cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org } else if (Empty() != fArray[i]) { 179cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org count++; 18049f085dddff10473b6ebf832a974288300224e60bsalomon SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i]))); 181cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org } 182c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 183cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org SKTDYNAMICHASH_CHECK(count == fCount); 184cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org SKTDYNAMICHASH_CHECK(deleted == fDeleted); 185c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 186c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com 187cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org // O(N^2) checks, skipped when large. 188cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org if (fCount < kLarge) { 189cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org // Are all entries unique? 190cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org for (int i = 0; i < fCapacity; i++) { 191cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org if (Empty() == fArray[i] || Deleted() == fArray[i]) { 192c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com continue; 193c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 194cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org for (int j = i+1; j < fCapacity; j++) { 195cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org if (Empty() == fArray[j] || Deleted() == fArray[j]) { 196cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org continue; 197cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org } 198cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); 199158f64626f8dae7e8437744184860d0110b88609commit-bot@chromium.org SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j]))); 200cd0bf0adaa7adc24f79834e1b36884b72e64dbcccommit-bot@chromium.org } 201c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 202c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 203ba0ca99b83d3e084811fd1764d227d850fab4d43mtklein@google.com #undef SKTDYNAMICHASH_CHECK 204c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com return true; 205c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 206c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com 207c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com void innerAdd(T* newEntry) { 208c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com const Key& key = GetKey(*newEntry); 209f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int index = this->firstIndex(key); 210f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org for (int round = 0; round < fCapacity; round++) { 2112e09d18f78f5772d2d9506ff8024ca8542654358mtklein SkASSERT(index >= 0 && index < fCapacity); 212b8d17fef261eb70305105dddc4089aa744accfcereed@google.com const T* candidate = fArray[index]; 213c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com if (Empty() == candidate || Deleted() == candidate) { 214c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com if (Deleted() == candidate) { 215c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com fDeleted--; 216c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 217c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com fCount++; 218c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com fArray[index] = newEntry; 219f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org return; 220b8d17fef261eb70305105dddc4089aa744accfcereed@google.com } 221c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com index = this->nextIndex(index, round); 222c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 2237a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org SkASSERT(fCapacity == 0); 224c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 225c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com 226c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com void innerRemove(const Key& key) { 227c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com const int firstIndex = this->firstIndex(key); 228c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com int index = firstIndex; 229c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com for (int round = 0; round < fCapacity; round++) { 2302e09d18f78f5772d2d9506ff8024ca8542654358mtklein SkASSERT(index >= 0 && index < fCapacity); 231c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com const T* candidate = fArray[index]; 232158f64626f8dae7e8437744184860d0110b88609commit-bot@chromium.org if (Deleted() != candidate && GetKey(*candidate) == key) { 233c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com fDeleted++; 234f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org fCount--; 235c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com fArray[index] = Deleted(); 236f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org return; 237f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org } 238f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org index = this->nextIndex(index, round); 239b8d17fef261eb70305105dddc4089aa744accfcereed@google.com } 2407a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org SkASSERT(fCapacity == 0); 241b8d17fef261eb70305105dddc4089aa744accfcereed@google.com } 242b8d17fef261eb70305105dddc4089aa744accfcereed@google.com 243f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org void maybeGrow() { 2447a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) { 2457a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org this->resize(fCapacity > 0 ? fCapacity * 2 : 4); 246b8d17fef261eb70305105dddc4089aa744accfcereed@google.com } 247c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com } 248f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 249c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com void resize(int newCapacity) { 250f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org SkDEBUGCODE(int oldCount = fCount;) 2515d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com int oldCapacity = fCapacity; 2527a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org SkAutoTMalloc<T*> oldArray(fArray); 253956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 2547a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org fCount = fDeleted = 0; 2557a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org fCapacity = newCapacity; 2567a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity); 257956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 258f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org for (int i = 0; i < oldCapacity; i++) { 259f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org T* entry = oldArray[i]; 260c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com if (Empty() != entry && Deleted() != entry) { 2617a4b9fab286c3c02cca433c2ca36ebd35377de46commit-bot@chromium.org this->innerAdd(entry); 2625d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 2635d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 264f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org SkASSERT(oldCount == fCount); 2655d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com } 266956b310f13c7412c035406c658ff16ca85eac656skia.committer@gmail.com 267f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash. 268f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org uint32_t hashMask() const { return fCapacity - 1; } 269f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 270f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int firstIndex(const Key& key) const { 271f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org return Hash(key) & this->hashMask(); 272f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org } 273f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 274f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // Given index at round N, what is the index to check at N+1? round should start at 0. 275f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int nextIndex(int index, int round) const { 276f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org // This will search a power-of-two array fully without repeating an index. 277f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org return (index + round + 1) & this->hashMask(); 278f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org } 279f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org 28055bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org static const Key& GetKey(const T& t) { return Traits::GetKey(t); } 28155bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org static uint32_t Hash(const Key& key) { return Traits::Hash(key); } 28255bd940446506f8409f38271f2e4969e9b4f3991commit-bot@chromium.org 283c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com int fCount; // Number of non Empty(), non Deleted() entries in fArray. 284c9ab2b7dd8411f8a78654b237c69a5886567dfecmtklein@google.com int fDeleted; // Number of Deleted() entries in fArray. 285f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org int fCapacity; // Number of entries in fArray. Always a power of 2. 286f916f9e7cf4403846c413acf8fec403e38cd8451commit-bot@chromium.org T** fArray; 2875d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com}; 2885d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com 2895d1e5589fe446a59372debd8c7221170e21ec2b8reed@google.com#endif 290