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