1 // Parallax Static Timing Analyzer
2 // Copyright (c) 2019, Parallax Software, Inc.
3 // All rights reserved.
4 //
5 // No part of this document may be copied, transmitted or
6 // disclosed in any form or fashion without the express
7 // written consent of Parallax Software, Inc.
8
9 #ifndef STA_ARRAY_TABLE_H
10 #define STA_ARRAY_TABLE_H
11
12 #include <string.h> // memcpy
13
14 #include "ObjectId.hh"
15 #include "Error.hh"
16
17 namespace sta {
18
19 template <class TYPE>
20 class ArrayBlock;
21
22 // Array tables allocate arrays of objects in blocks and use 32 bit IDs to
23 // reference the array. Paging performance is improved by allocating
24 // blocks instead of individual arrays, and object sizes are reduced
25 // by using 32 bit references instead of 64 bit pointers.
26 // They are similar to ObjectTables but do not support delete/destroy or
27 // reclaiming deleted arrays.
28
29 template <class TYPE>
30 class ArrayTable
31 {
32 public:
33 ArrayTable();
34 ~ArrayTable();
35 void make(uint32_t count,
36 TYPE *&array,
37 ObjectId &id);
38 // Grow as necessary and return pointer for id.
39 TYPE *ensureId(ObjectId id);
40 TYPE *pointer(ObjectId id) const;
41 TYPE &ref(ObjectId id) const;
size() const42 size_t size() const { return size_; }
43 void clear();
44
45 static constexpr int idx_bits = 7;
46 static constexpr int block_size = (1 << idx_bits);
47 static constexpr int block_id_max = 1 << (object_id_bits - idx_bits);
48
49 private:
50 ArrayBlock<TYPE> *makeBlock(uint32_t size);
51 void pushBlock(ArrayBlock<TYPE> *block);
52 void deleteBlocks();
53
54 size_t size_;
55 // Block index of free block (blocks_[size - 1]).
56 BlockIdx free_block_idx_;
57 // Index of next free object in free_block_idx_.
58 ObjectIdx free_idx_;
59 // Don't use std::vector so growing blocks_ can be thread safe.
60 size_t blocks_size_;
61 size_t blocks_capacity_;
62 ArrayBlock<TYPE>* *blocks_;
63 ArrayBlock<TYPE>* *prev_blocks_;
64 static constexpr ObjectId idx_mask_ = block_size - 1;
65 };
66
67 template <class TYPE>
ArrayTable()68 ArrayTable<TYPE>::ArrayTable() :
69 size_(0),
70 free_block_idx_(block_idx_null),
71 free_idx_(object_idx_null),
72 blocks_size_(0),
73 blocks_capacity_(1024),
74 blocks_(new ArrayBlock<TYPE>*[blocks_capacity_]),
75 prev_blocks_(nullptr)
76 {
77 }
78
79 template <class TYPE>
~ArrayTable()80 ArrayTable<TYPE>::~ArrayTable()
81 {
82 deleteBlocks();
83 delete [] blocks_;
84 delete [] prev_blocks_;
85 }
86
87 template <class TYPE>
88 void
deleteBlocks()89 ArrayTable<TYPE>::deleteBlocks()
90 {
91 for (size_t i = 0; i < blocks_size_; i++)
92 delete blocks_[i];
93 }
94
95 template <class TYPE>
96 void
make(uint32_t count,TYPE * & array,ObjectId & id)97 ArrayTable<TYPE>::make(uint32_t count,
98 TYPE *&array,
99 ObjectId &id)
100 {
101 ArrayBlock<TYPE> *block = blocks_size_ ? blocks_[free_block_idx_] : nullptr;
102 if ((free_idx_ == object_idx_null
103 && free_block_idx_ == block_idx_null)
104 || free_idx_ + count >= block->size()) {
105 uint32_t size = (count > block_size) ? count : block_size;
106 block = makeBlock(size);
107 }
108 // makeId(free_block_idx_, idx_bits)
109 id = (free_block_idx_ << idx_bits) + free_idx_;
110 array = block->pointer(free_idx_);
111 free_idx_ += count;
112 size_ += count;
113 }
114
115 template <class TYPE>
116 ArrayBlock<TYPE> *
makeBlock(uint32_t size)117 ArrayTable<TYPE>::makeBlock(uint32_t size)
118 {
119 BlockIdx block_idx = blocks_size_;
120 ArrayBlock<TYPE> *block = new ArrayBlock<TYPE>(size);
121 pushBlock(block);
122 free_block_idx_ = block_idx;
123 // ObjectId zero is reserved for object_id_null.
124 free_idx_ = (block_idx > 0) ? 0 : 1;
125 return block;
126 }
127
128 template <class TYPE>
129 void
pushBlock(ArrayBlock<TYPE> * block)130 ArrayTable<TYPE>::pushBlock(ArrayBlock<TYPE> *block)
131 {
132 blocks_[blocks_size_++] = block;
133 if (blocks_size_ >= block_id_max)
134 criticalError(223, "max array table block count exceeded.");
135 if (blocks_size_ == blocks_capacity_) {
136 size_t new_capacity = blocks_capacity_ * 1.5;
137 ArrayBlock<TYPE>** new_blocks = new ArrayBlock<TYPE>*[new_capacity];
138 memcpy(new_blocks, blocks_, blocks_capacity_ * sizeof(ArrayBlock<TYPE>*));
139 if (prev_blocks_)
140 delete [] prev_blocks_;
141 // Preserve block array for other threads to reference.
142 prev_blocks_ = blocks_;
143 blocks_ = new_blocks;
144 blocks_capacity_ = new_capacity;
145 }
146 }
147
148 template <class TYPE>
149 TYPE *
pointer(ObjectId id) const150 ArrayTable<TYPE>::pointer(ObjectId id) const
151 {
152 if (id == object_id_null)
153 return nullptr;
154 else {
155 BlockIdx blk_idx = id >> idx_bits;
156 ObjectIdx obj_idx = id & idx_mask_;
157 return blocks_[blk_idx]->pointer(obj_idx);
158 }
159 }
160
161 template <class TYPE>
162 TYPE *
ensureId(ObjectId id)163 ArrayTable<TYPE>::ensureId(ObjectId id)
164 {
165 BlockIdx blk_idx = id >> idx_bits;
166 ObjectIdx obj_idx = id & idx_mask_;
167 // Make enough blocks for blk_idx to be valid.
168 for (BlockIdx i = blocks_size_; i <= blk_idx; i++) {
169 ArrayBlock<TYPE> *block = new ArrayBlock<TYPE>(block_size);
170 pushBlock(block);
171 }
172 return blocks_[blk_idx]->pointer(obj_idx);
173 }
174
175 template <class TYPE>
176 TYPE &
ref(ObjectId id) const177 ArrayTable<TYPE>::ref(ObjectId id) const
178 {
179 if (id == object_id_null)
180 criticalError(222, "null ObjectId reference is undefined.");
181
182 BlockIdx blk_idx = id >> idx_bits;
183 ObjectIdx obj_idx = id & idx_mask_;
184 return blocks_[blk_idx]->ref(obj_idx);
185 }
186
187 template <class TYPE>
188 void
clear()189 ArrayTable<TYPE>::clear()
190 {
191 deleteBlocks();
192 blocks_size_ = 0;
193 size_ = 0;
194 free_block_idx_ = block_idx_null;
195 free_idx_ = object_idx_null;
196 }
197
198 ////////////////////////////////////////////////////////////////
199
200 template <class TYPE>
201 class ArrayBlock
202 {
203 public:
204 ArrayBlock(uint32_t size);
205 ~ArrayBlock();
size() const206 uint32_t size() const { return size_; }
ref(ObjectIdx idx)207 TYPE &ref(ObjectIdx idx) { return objects_[idx]; }
pointer(ObjectIdx idx)208 TYPE *pointer(ObjectIdx idx) { return &objects_[idx]; }
209
210 private:
211 uint32_t size_;
212 TYPE *objects_;
213 };
214
215 template <class TYPE>
ArrayBlock(uint32_t size)216 ArrayBlock<TYPE>::ArrayBlock(uint32_t size) :
217 size_(size),
218 objects_(new TYPE[size])
219 {
220 }
221
222 template <class TYPE>
~ArrayBlock()223 ArrayBlock<TYPE>::~ArrayBlock()
224 {
225 delete [] objects_;
226 }
227
228 } // Namespace
229 #endif
230