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.h 22 Pointer Hash Set for TLC. 23 Copyright (c) 2008-2011 Apple Inc. All rights reserved. 24 */ 25 26#ifndef __AUTO_POINTER_HASH__ 27#define __AUTO_POINTER_HASH__ 28 29#include <stdint.h> 30#include <stddef.h> 31#include "auto_impl_utilities.h" 32 33namespace Auto { 34 35 class PointerHash { 36 protected: 37 enum { 38 FlagsMask = 0x7, 39 RemovedEntry = ~FlagsMask, 40 MaxRunLength = 16, 41 MinCapacity = MaxRunLength * 2, 42 PreferredCapacity = 512, // arbitrarily chosen such that this many 64 bit pointers fit in a single page 43 }; 44 45 vm_address_t *_pointers; 46 uint32_t _capacity; 47 uint32_t _capacityMask; 48 uint32_t _count; 49 uint32_t _removed; 50 uint32_t _firstOccupiedSlot; 51 uint32_t _lastOccupiedSlot; 52 uint32_t _maxRunLength; 53 54 inline uint32_t flagsValue(vm_address_t storedValue) const { return storedValue & FlagsMask; } 55 inline void *pointerValue(vm_address_t storedValue) const { return (void *)(storedValue & ~FlagsMask); } 56 inline bool validPointer(vm_address_t value) const { return value != 0 && value != (vm_address_t)RemovedEntry; } 57 58 public: 59 PointerHash(uint32_t initialCapacity) : _pointers(NULL), _capacity(0), _capacityMask(0), _count(0), _removed(0), _firstOccupiedSlot(0), _lastOccupiedSlot(0), _maxRunLength(0) { if (initialCapacity > 0) grow(initialCapacity * 4); }; 60 ~PointerHash() { if (_pointers) aux_free(_pointers); } 61 62 int32_t slotIndex(void *pointer) const; // returns the index of the slot containing pointer, or -1 if pointer is not in the set 63 64 void add(void *pointer, uint32_t flags = 0); 65 void remove(uint32_t slot); 66 void remove(void *pointer); 67 inline bool contains(void *pointer) const { return slotIndex(pointer) != -1; } 68 69 void rehash(uint32_t flagMask = 0); // bits which are set in flagMask will be cleared in all entries 70 void grow(uint32_t newCapacity = PreferredCapacity, uint32_t flagMask = 0); // bits which are set in flagMask will be cleared in all entries 71 void compact(uint32_t flagMask = 0); 72 void clearFlags(); 73 74 inline uint32_t capacity() const { return _capacity; } 75 inline uint32_t count() const { return _count; } 76 inline uint32_t firstOccupiedSlot() const { return _firstOccupiedSlot; } 77 inline uint32_t lastOccupiedSlot() const { return _lastOccupiedSlot; } 78 79 inline bool validPointerAtIndex(uint32_t index) const { return validPointer(_pointers[index]); } 80 81 inline void *operator[](uint32_t index) const { return validPointerAtIndex(index) ? pointerValue(_pointers[index]) : NULL; } 82 83 inline void setFlag(uint32_t index, uint32_t flag) { _pointers[index] |= flag; } 84 inline void clearFlag(uint32_t index, uint32_t flag) { if (_pointers[index] != (vm_address_t)RemovedEntry) _pointers[index] &= ~flag; } 85 inline bool flagSet(uint32_t index, uint32_t flag) { return (_pointers[index] & flag) != 0; } 86 87 private: 88 uintptr_t hash(void *pointer) const; 89 void insert(void *pointer, uint32_t flags); 90 }; 91 92}; 93 94#endif // __AUTO_POINTER_HASH__ 95