1/* 2 * Copyright (c) 2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20/* 21 PointerHash.cpp 22 Pointer Hash Set for TLC. 23 Copyright (c) 2008-2011 Apple Inc. All rights reserved. 24 */ 25 26#include "PointerHash.h" 27#include "Configuration.h" 28#include <assert.h> 29 30namespace Auto { 31 32 inline uintptr_t PointerHash::hash(void *pointer) const { 33 return uintptr_t(pointer) >> allocate_quantum_small_log2; 34 } 35 36 void PointerHash::add(void *pointer, uint32_t flags) { 37 insert(pointer, flags); 38 // don't let table fill to capacity - if we did then a rehash would never find a slot with 0 39 if (_count*3 > _capacity*2) { 40 grow(_capacity * 2); // double when at 2/3 capacity 41 } else if ((_count + _removed + 8) >= _capacity) { 42 // rare. removes are not being eaten up by adds. 43 rehash(0x0); // if deletions are filling the table better rehash (and preserve any flags) 44 } 45 } 46 47 void PointerHash::insert(void *pointer, uint32_t flags) { 48 uintptr_t h = hash(pointer); 49 uint32_t index = h & _capacityMask; // <rdar://problem/6544627> don't use integer divide. 50 uint32_t run_length = 0; 51 vm_address_t probe; 52 while (validPointer(probe = _pointers[index])) { 53 if (pointerValue(probe) == pointer) return; // already inserted. should the flags be updated? they weren't before. 54 index++; 55 run_length++; 56 if (index == _capacity) 57 index = 0; 58 } 59 if (probe == (vm_address_t)RemovedEntry) 60 --_removed; 61 _pointers[index] = (vm_address_t)pointer | flags; 62 _count++; 63 if (index < _firstOccupiedSlot) 64 _firstOccupiedSlot = index; 65 if (index > _lastOccupiedSlot) 66 _lastOccupiedSlot = index; 67 if (run_length > _maxRunLength) 68 _maxRunLength = run_length; 69 } 70 71 int32_t PointerHash::slotIndex(void *pointer) const 72 { 73 if (_count > 0) { 74 uintptr_t h = hash(pointer); 75 const uint32_t kCapacityMask = _capacityMask, kMaxRunLength = _maxRunLength; 76 uint32_t i = h & kCapacityMask; 77 uint32_t run = 0; 78 while (vm_address_t probe = _pointers[i]) { 79 if (pointerValue(probe) == pointer) 80 return i; 81 if (run >= kMaxRunLength) 82 break; 83 run++; 84 i = (i + 1) & kCapacityMask; 85 } 86 } 87 return -1; 88 } 89 90 void PointerHash::remove(uint32_t slot) 91 { 92 if (slot < _capacity) { 93 uint32_t index = slot; 94 if (_maxRunLength == 0 || _pointers[(index + 1) & _capacityMask] == 0) { 95 // if there are no misaligned pointers or the next slot is NULL then we can just set this slot to NULL 96 // we can also clean up the table by NULL-ing slots that contain a now unneeded RemovedEntry value (to improve searching) 97 ++_removed; 98 do { 99 --_removed; 100 _pointers[index] = NULL; 101 index = (index == 0 ? _capacity - 1 : index - 1); 102 } while (_pointers[index] == (vm_address_t)RemovedEntry); 103 } else { 104 // there is an entry immediately after this one, so have to mark the slot as previously occupied 105 _pointers[slot] = (vm_address_t)RemovedEntry; 106 ++_removed; 107 } 108 _count--; 109 } 110 } 111 112 void PointerHash::remove(void *pointer) 113 { 114 int32_t index = slotIndex(pointer); 115 if (index != -1) { 116 remove(index); 117 } 118 } 119 120 void PointerHash::grow(uint32_t newCapacity, uint32_t flagMask) 121 { 122 vm_address_t mask = ~(FlagsMask & flagMask); 123 vm_address_t *old_pointers = _pointers; 124 uint32_t old_capacity = _capacity; 125 uint32_t old_count = _count; 126 uint32_t i = _firstOccupiedSlot; 127 128 if (newCapacity > 0 && newCapacity < MinCapacity) 129 newCapacity = MinCapacity; 130 131 if (_capacity != newCapacity) { 132 _capacity = newCapacity; 133 assert(is_power_of_2(_capacity)); 134 _capacityMask = _capacity - 1; // _capacity is ALWAYS a power of two. 135 _count = 0; 136 _removed = 0; 137 _firstOccupiedSlot = _capacity; 138 _lastOccupiedSlot = 0; 139 _maxRunLength = 0; 140 _pointers = NULL; 141 142 if (newCapacity > 0) { 143 _pointers = (vm_address_t *)aux_calloc(_capacity, sizeof(void *)); 144 if (old_count > 0) { 145 uint32_t rehashed = 0; 146 while (i<old_capacity && rehashed < old_count) { 147 if (validPointer(old_pointers[i])) { 148 insert(pointerValue(old_pointers[i]), flagsValue(old_pointers[i]) & mask); 149 rehashed++; 150 } 151 i++; 152 } 153 } 154 } 155 if (old_pointers) 156 aux_free(old_pointers); 157 } 158 } 159 160 161 void PointerHash::rehash(uint32_t flagMask) 162 { 163 vm_address_t mask = ~(FlagsMask & flagMask); 164 if (_maxRunLength > 0 || flagMask) { 165 if (_count > 0) { 166 // Must start in gap. 167 // Imagine a run that overlaps end, each of which wants to move down one 168 // (e.g. item at 0 wants to be at end, item at end wants to be at end-1) 169 // item at 0 can't initially move, yet item at end does, leaving item 0 170 // in wrong place 171 uint32_t start = _capacity; 172 for (uint32_t i = 0; i < _capacity; i++) { 173 if (_pointers[i] == 0) { 174 start = i; 175 break; 176 } 177 } 178 179 if (start == _capacity) { 180 // didn't find any gaps, can't rehash in-place safely. 181 grow(_capacity * 2, flagMask); 182 return; 183 } 184 185 _count = 0; 186 _removed = 0; 187 _firstOccupiedSlot = _capacity; 188 _lastOccupiedSlot = 0; 189 _maxRunLength = 0; 190 191 // assert start < _capacity 192 for (uint32_t i = start; i < _capacity; i++) { 193 vm_address_t pointer = _pointers[i]; 194 _pointers[i] = 0; 195 if (validPointer(pointer)) 196 insert(pointerValue(pointer), flagsValue(pointer) & mask); 197 } 198 for (uint32_t i = 0; i < start; i++) { 199 vm_address_t pointer = _pointers[i]; 200 _pointers[i] = 0; 201 if (validPointer(pointer)) 202 insert(pointerValue(pointer), flagsValue(pointer) & mask); 203 } 204 } else { 205 bzero(_pointers, _capacity * sizeof(void *)); 206 } 207 } 208 } 209 210 void PointerHash::compact(uint32_t flagMask) { 211 // If _count < PreferredCapacity / 3, then shrink the table to that size. 212 if (_capacity > PreferredCapacity && (_count * 3) < PreferredCapacity) 213 grow(PreferredCapacity, flagMask); 214 else 215 rehash(flagMask); 216 } 217 218 void PointerHash::clearFlags() { 219 for (uint32_t i = _firstOccupiedSlot; i <= _lastOccupiedSlot; ++i) { 220 _pointers[i] &= ~FlagsMask; 221 } 222 } 223} 224