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