Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Side by Side Diff: src/core/SkTDynamicHash.h

Issue 1316233002: Style Change: NULL->nullptr (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: 2015-08-27 (Thursday) 10:25:06 EDT Created 5 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/core/SkTDPQueue.h ('k') | src/core/SkTLList.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2013 Google Inc. 2 * Copyright 2013 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 7
8 #ifndef SkTDynamicHash_DEFINED 8 #ifndef SkTDynamicHash_DEFINED
9 #define SkTDynamicHash_DEFINED 9 #define SkTDynamicHash_DEFINED
10 10
11 #include "SkMath.h" 11 #include "SkMath.h"
12 #include "SkTemplates.h" 12 #include "SkTemplates.h"
13 #include "SkTypes.h" 13 #include "SkTypes.h"
14 14
15 // Traits requires: 15 // Traits requires:
16 // static const Key& GetKey(const T&) { ... } 16 // static const Key& GetKey(const T&) { ... }
17 // static uint32_t Hash(const Key&) { ... } 17 // static uint32_t Hash(const Key&) { ... }
18 // We'll look on T for these by default, or you can pass a custom Traits type. 18 // We'll look on T for these by default, or you can pass a custom Traits type.
19 template <typename T, 19 template <typename T,
20 typename Key, 20 typename Key,
21 typename Traits = T, 21 typename Traits = T,
22 int kGrowPercent = 75> // Larger -> more memory efficient, but slower . 22 int kGrowPercent = 75> // Larger -> more memory efficient, but slower .
23 class SkTDynamicHash { 23 class SkTDynamicHash {
24 public: 24 public:
25 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { 25 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) {
26 SkASSERT(this->validate()); 26 SkASSERT(this->validate());
27 } 27 }
28 28
29 ~SkTDynamicHash() { 29 ~SkTDynamicHash() {
30 sk_free(fArray); 30 sk_free(fArray);
31 } 31 }
32 32
33 class Iter { 33 class Iter {
34 public: 34 public:
35 explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) { 35 explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after
79 79
80 private: 80 private:
81 const T* current() const { return fHash->fArray[fCurrentIndex]; } 81 const T* current() const { return fHash->fArray[fCurrentIndex]; }
82 82
83 const SkTDynamicHash* fHash; 83 const SkTDynamicHash* fHash;
84 int fCurrentIndex; 84 int fCurrentIndex;
85 }; 85 };
86 86
87 int count() const { return fCount; } 87 int count() const { return fCount; }
88 88
89 // Return the entry with this key if we have it, otherwise NULL. 89 // Return the entry with this key if we have it, otherwise nullptr.
90 T* find(const Key& key) const { 90 T* find(const Key& key) const {
91 int index = this->firstIndex(key); 91 int index = this->firstIndex(key);
92 for (int round = 0; round < fCapacity; round++) { 92 for (int round = 0; round < fCapacity; round++) {
93 SkASSERT(index >= 0 && index < fCapacity); 93 SkASSERT(index >= 0 && index < fCapacity);
94 T* candidate = fArray[index]; 94 T* candidate = fArray[index];
95 if (Empty() == candidate) { 95 if (Empty() == candidate) {
96 return NULL; 96 return nullptr;
97 } 97 }
98 if (Deleted() != candidate && GetKey(*candidate) == key) { 98 if (Deleted() != candidate && GetKey(*candidate) == key) {
99 return candidate; 99 return candidate;
100 } 100 }
101 index = this->nextIndex(index, round); 101 index = this->nextIndex(index, round);
102 } 102 }
103 SkASSERT(fCapacity == 0); 103 SkASSERT(fCapacity == 0);
104 return NULL; 104 return nullptr;
105 } 105 }
106 106
107 // Add an entry with this key. We require that no entry with newEntry's key is already present. 107 // Add an entry with this key. We require that no entry with newEntry's key is already present.
108 void add(T* newEntry) { 108 void add(T* newEntry) {
109 SkASSERT(NULL == this->find(GetKey(*newEntry))); 109 SkASSERT(nullptr == this->find(GetKey(*newEntry)));
110 this->maybeGrow(); 110 this->maybeGrow();
111 this->innerAdd(newEntry); 111 this->innerAdd(newEntry);
112 SkASSERT(this->validate()); 112 SkASSERT(this->validate());
113 } 113 }
114 114
115 // Remove the entry with this key. We require that an entry with this key i s present. 115 // Remove the entry with this key. We require that an entry with this key i s present.
116 void remove(const Key& key) { 116 void remove(const Key& key) {
117 SkASSERT(this->find(key)); 117 SkASSERT(this->find(key));
118 this->innerRemove(key); 118 this->innerRemove(key);
119 SkASSERT(this->validate()); 119 SkASSERT(this->validate());
120 } 120 }
121 121
122 void rewind() { 122 void rewind() {
123 if (fArray) { 123 if (fArray) {
124 sk_bzero(fArray, sizeof(T*)* fCapacity); 124 sk_bzero(fArray, sizeof(T*)* fCapacity);
125 } 125 }
126 fCount = 0; 126 fCount = 0;
127 fDeleted = 0; 127 fDeleted = 0;
128 } 128 }
129 129
130 void reset() { 130 void reset() {
131 fCount = 0; 131 fCount = 0;
132 fDeleted = 0; 132 fDeleted = 0;
133 fCapacity = 0; 133 fCapacity = 0;
134 sk_free(fArray); 134 sk_free(fArray);
135 fArray = NULL; 135 fArray = nullptr;
136 } 136 }
137 137
138 protected: 138 protected:
139 // These methods are used by tests only. 139 // These methods are used by tests only.
140 140
141 int capacity() const { return fCapacity; } 141 int capacity() const { return fCapacity; }
142 142
143 // How many collisions do we go through before finding where this entry shou ld be inserted? 143 // How many collisions do we go through before finding where this entry shou ld be inserted?
144 int countCollisions(const Key& key) const { 144 int countCollisions(const Key& key) const {
145 int index = this->firstIndex(key); 145 int index = this->firstIndex(key);
146 for (int round = 0; round < fCapacity; round++) { 146 for (int round = 0; round < fCapacity; round++) {
147 SkASSERT(index >= 0 && index < fCapacity); 147 SkASSERT(index >= 0 && index < fCapacity);
148 const T* candidate = fArray[index]; 148 const T* candidate = fArray[index];
149 if (Empty() == candidate || Deleted() == candidate || GetKey(*candid ate) == key) { 149 if (Empty() == candidate || Deleted() == candidate || GetKey(*candid ate) == key) {
150 return round; 150 return round;
151 } 151 }
152 index = this->nextIndex(index, round); 152 index = this->nextIndex(index, round);
153 } 153 }
154 SkASSERT(fCapacity == 0); 154 SkASSERT(fCapacity == 0);
155 return 0; 155 return 0;
156 } 156 }
157 157
158 private: 158 private:
159 // We have two special values to indicate an empty or deleted entry. 159 // We have two special values to indicate an empty or deleted entry.
160 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL 160 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. nullptr
161 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer. 161 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer.
162 162
163 bool validate() const { 163 bool validate() const {
164 #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false 164 #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false
165 static const int kLarge = 50; // Arbitrary, tweak to suit your patience . 165 static const int kLarge = 50; // Arbitrary, tweak to suit your patience .
166 166
167 // O(1) checks, always done. 167 // O(1) checks, always done.
168 // Is capacity sane? 168 // Is capacity sane?
169 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); 169 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
170 170
(...skipping 109 matching lines...) Expand 10 before | Expand all | Expand 10 after
280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } 280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } 281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
282 282
283 int fCount; // Number of non Empty(), non Deleted() entries in fArray. 283 int fCount; // Number of non Empty(), non Deleted() entries in fArray.
284 int fDeleted; // Number of Deleted() entries in fArray. 284 int fDeleted; // Number of Deleted() entries in fArray.
285 int fCapacity; // Number of entries in fArray. Always a power of 2. 285 int fCapacity; // Number of entries in fArray. Always a power of 2.
286 T** fArray; 286 T** fArray;
287 }; 287 };
288 288
289 #endif 289 #endif
OLDNEW
« no previous file with comments | « src/core/SkTDPQueue.h ('k') | src/core/SkTLList.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698