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 #pragma once
10
11 #include "Vector.hh"
12 #include "Error.hh"
13 #include "ObjectId.hh"
14
15 namespace sta {
16
17 template <class OBJECT>
18 class TableBlock;
19
20 // Object tables allocate objects in blocks and use 32 bit IDs to
21 // reference an object. Paging performance is improved by allocating
22 // blocks instead of individual objects, and object sizes are reduced
23 // by using 32 bit references instead of 64 bit pointers.
24 //
25 // Class TYPE must define member functions
26 // ObjectIdx objectIdx() const
27 // void setObjectIdx(ObjectIdx idx)
28 // to get/set the index of the object in a block, which can be a bit
29 // field ObjectTable::idx_bits (7 bits) wide.
30
31 template <class TYPE>
32 class ObjectTable
33 {
34 public:
35 ObjectTable();
36 ~ObjectTable();
37 TYPE *make();
38 void destroy(TYPE *object);
39 TYPE *pointer(ObjectId id) const;
40 TYPE &ref(ObjectId id) const;
41 ObjectId objectId(const TYPE *object);
size() const42 size_t size() const { return size_; }
43 void clear();
44
45 // Objects are allocated in blocks of 128.
46 static constexpr int idx_bits = 7;
47 static constexpr int block_object_count = (1 << idx_bits);
48 static constexpr int block_id_max = 1 << (object_id_bits - idx_bits);
49
50 private:
51 void makeBlock();
52 void freePush(TYPE *object,
53 ObjectId id);
54
55 size_t size_;
56 // Object ID of next free object.
57 ObjectId free_;
58 Vector<TableBlock<TYPE>*> blocks_;
59 static constexpr ObjectId idx_mask_ = block_object_count - 1;
60 };
61
62 template <class TYPE>
ObjectTable()63 ObjectTable<TYPE>::ObjectTable() :
64 size_(0),
65 free_(object_id_null)
66 {
67 }
68
69 template <class TYPE>
~ObjectTable()70 ObjectTable<TYPE>::~ObjectTable()
71 {
72 blocks_.deleteContents();
73 }
74
75 template <class TYPE>
76 TYPE *
make()77 ObjectTable<TYPE>::make()
78 {
79 if (free_ == object_id_null)
80 makeBlock();
81 TYPE *object = pointer(free_);
82 ObjectIdx idx = free_ & idx_mask_;
83 object->setObjectIdx(idx);
84 ObjectId *free_next = reinterpret_cast<ObjectId*>(object);
85 free_ = *free_next;
86 size_++;
87 return object;
88 }
89
90 template <class TYPE>
91 void
freePush(TYPE * object,ObjectId id)92 ObjectTable<TYPE>::freePush(TYPE *object,
93 ObjectId id)
94 {
95 // Link free objects into a list linked by Object ID.
96 ObjectId *free_next = reinterpret_cast<ObjectId*>(object);
97 *free_next = free_;
98 free_ = id;
99 }
100
101 template <class TYPE>
102 void
makeBlock()103 ObjectTable<TYPE>::makeBlock()
104 {
105 BlockIdx block_index = blocks_.size();
106 TableBlock<TYPE> *block = new TableBlock<TYPE>(block_index, this);
107 blocks_.push_back(block);
108 if (blocks_.size() >= block_id_max)
109 criticalError(224, "max object table block count exceeded.");
110 // ObjectId zero is reserved for object_id_null.
111 int last = (block_index > 0) ? 0 : 1;
112 for (int i = block_object_count - 1; i >= last; i--) {
113 TYPE *obj = block->pointer(i);
114 ObjectId id = (block_index << idx_bits) + i;
115 freePush(obj, id);
116 }
117 }
118
119 template <class TYPE>
120 TYPE *
pointer(ObjectId id) const121 ObjectTable<TYPE>::pointer(ObjectId id) const
122 {
123 if (id == object_id_null)
124 return nullptr;
125 else {
126 BlockIdx blk_idx = id >> idx_bits;
127 ObjectIdx obj_idx = id & idx_mask_;
128 return blocks_[blk_idx]->pointer(obj_idx);
129 }
130 }
131
132 template <class TYPE>
133 TYPE &
ref(ObjectId id) const134 ObjectTable<TYPE>::ref(ObjectId id) const
135 {
136 if (id == object_id_null)
137 criticalError(225, "null ObjectId reference is undefined.");
138 else {
139 BlockIdx blk_idx = id >> idx_bits;
140 ObjectIdx obj_idx = id & idx_mask_;
141 return blocks_[blk_idx]->ptr(obj_idx);
142 }
143 }
144
145 template <class TYPE>
146 ObjectId
objectId(const TYPE * object)147 ObjectTable<TYPE>::objectId(const TYPE *object)
148 {
149 ObjectIdx idx = object->objectIdx();
150 const TableBlock<TYPE> *blk =
151 reinterpret_cast<const TableBlock<TYPE>*>(object - idx);
152 return (blk->index() << idx_bits) + idx;
153 }
154
155 template <class TYPE>
156 void
destroy(TYPE * object)157 ObjectTable<TYPE>::destroy(TYPE *object)
158 {
159 ObjectId object_id = objectId(object);
160 object->~TYPE();
161 size_--;
162 freePush(object, object_id);
163 }
164
165 template <class TYPE>
166 void
clear()167 ObjectTable<TYPE>::clear()
168 {
169 blocks_.deleteContentsClear();
170 size_ = 0;
171 }
172
173 ////////////////////////////////////////////////////////////////
174
175 template <class TYPE>
176 class TableBlock
177 {
178 public:
179 TableBlock(BlockIdx block_idx,
180 ObjectTable<TYPE> *table);
index() const181 BlockIdx index() const { return block_idx_; }
ref(ObjectIdx idx)182 TYPE &ref(ObjectIdx idx) { return objects_[idx]; }
pointer(ObjectIdx idx)183 TYPE *pointer(ObjectIdx idx) { return &objects_[idx]; }
184
185 private:
186 TYPE objects_[ObjectTable<TYPE>::block_object_count];
187 BlockIdx block_idx_;
188 ObjectTable<TYPE> *table_;
189 };
190
191 template <class TYPE>
TableBlock(BlockIdx block_idx,ObjectTable<TYPE> * table)192 TableBlock<TYPE>::TableBlock(BlockIdx block_idx,
193 ObjectTable<TYPE> *table) :
194 block_idx_(block_idx),
195 table_(table)
196 {
197 }
198
199 } // Namespace
200