/home/andy/git/oilshell/oil/mycpp/gc_dict.h
Line | Count | Source (jump to first uncovered line) |
1 | | #ifndef MYCPP_GC_DICT_H |
2 | | #define MYCPP_GC_DICT_H |
3 | | |
4 | | #include "mycpp/comparators.h" |
5 | | #include "mycpp/gc_list.h" |
6 | | |
7 | | // Non-negative entries in entry_ are array indices into keys_ and values_. |
8 | | // There are two special negative entries. |
9 | | |
10 | | // index that means this Dict item was deleted (a tombstone). |
11 | | const int kDeletedEntry = -1; |
12 | | |
13 | | // index that means this Dict entry is free. Because we have Dict[int, int], |
14 | | // we can't use a sentinel entry in keys_. It has to be a sentinel entry in |
15 | | // entry_. |
16 | | const int kEmptyEntry = -2; |
17 | | |
18 | | // Helper for keys() and values() |
19 | | template <typename T> |
20 | 14 | List<T>* ListFromDictSlab(Slab<int>* index, Slab<T>* slab, int n) { |
21 | | // TODO: Reserve the right amount of space |
22 | 14 | List<T>* result = nullptr; |
23 | 14 | result = Alloc<List<T>>(); |
24 | | |
25 | 46 | for (int i = 0; i < n; ++i) { |
26 | 44 | int special = index->items_[i]; |
27 | 44 | if (special == kDeletedEntry) { |
28 | 0 | continue; |
29 | 0 | } |
30 | 44 | if (special == kEmptyEntry) { |
31 | 12 | break; |
32 | 12 | } |
33 | 32 | result->append(slab->items_[i]); |
34 | 32 | } |
35 | 14 | return result; |
36 | 14 | } _Z16ListFromDictSlabIP3StrEP4ListIT_EP4SlabIiEPS6_IS3_Ei Line | Count | Source | 20 | 12 | List<T>* ListFromDictSlab(Slab<int>* index, Slab<T>* slab, int n) { | 21 | | // TODO: Reserve the right amount of space | 22 | 12 | List<T>* result = nullptr; | 23 | 12 | result = Alloc<List<T>>(); | 24 | | | 25 | 38 | for (int i = 0; i < n; ++i) { | 26 | 36 | int special = index->items_[i]; | 27 | 36 | if (special == kDeletedEntry) { | 28 | 0 | continue; | 29 | 0 | } | 30 | 36 | if (special == kEmptyEntry) { | 31 | 10 | break; | 32 | 10 | } | 33 | 26 | result->append(slab->items_[i]); | 34 | 26 | } | 35 | 12 | return result; | 36 | 12 | } |
_Z16ListFromDictSlabIiEP4ListIT_EP4SlabIiEPS4_IS1_Ei Line | Count | Source | 20 | 2 | List<T>* ListFromDictSlab(Slab<int>* index, Slab<T>* slab, int n) { | 21 | | // TODO: Reserve the right amount of space | 22 | 2 | List<T>* result = nullptr; | 23 | 2 | result = Alloc<List<T>>(); | 24 | | | 25 | 8 | for (int i = 0; i < n; ++i) { | 26 | 8 | int special = index->items_[i]; | 27 | 8 | if (special == kDeletedEntry) { | 28 | 0 | continue; | 29 | 0 | } | 30 | 8 | if (special == kEmptyEntry) { | 31 | 2 | break; | 32 | 2 | } | 33 | 6 | result->append(slab->items_[i]); | 34 | 6 | } | 35 | 2 | return result; | 36 | 2 | } |
|
37 | | |
38 | | template <class K, class V> |
39 | | class Dict { |
40 | | // Relates to minimum slab size. This is good for Dict<K*, V*>, Dict<K*, |
41 | | // int>, Dict<int, V*>, but possibly suboptimal for Dict<int, int>. But that |
42 | | // case is rare. |
43 | | static const int kMinItems = 4; |
44 | | |
45 | | public: |
46 | | Dict() |
47 | | : header_(obj_header()), |
48 | | len_(0), |
49 | | capacity_(0), |
50 | | entry_(nullptr), |
51 | | keys_(nullptr), |
52 | 53 | values_(nullptr) { |
53 | 53 | } Line | Count | Source | 52 | 9 | values_(nullptr) { | 53 | 9 | } |
Line | Count | Source | 52 | 17 | values_(nullptr) { | 53 | 17 | } |
Line | Count | Source | 52 | 8 | values_(nullptr) { | 53 | 8 | } |
Line | Count | Source | 52 | 6 | values_(nullptr) { | 53 | 6 | } |
_ZN4DictIP6Tuple2IiiEiEC2Ev Line | Count | Source | 52 | 2 | values_(nullptr) { | 53 | 2 | } |
_ZN4DictIP6Tuple2IP3StriEiEC2Ev Line | Count | Source | 52 | 2 | values_(nullptr) { | 53 | 2 | } |
_ZN4DictIP3StrPN4args7_ActionEEC2Ev Line | Count | Source | 52 | 6 | values_(nullptr) { | 53 | 6 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEEC2Ev Line | Count | Source | 52 | 3 | values_(nullptr) { | 53 | 3 | } |
|
54 | | |
55 | | Dict(std::initializer_list<K> keys, std::initializer_list<V> values) |
56 | | : header_(obj_header()), |
57 | | len_(0), |
58 | | capacity_(0), |
59 | | entry_(nullptr), |
60 | | keys_(nullptr), |
61 | | values_(nullptr) { |
62 | | } |
63 | | |
64 | | // This relies on the fact that containers of 4-byte ints are reduced by 2 |
65 | | // items, which is greater than (or equal to) the reduction of any other |
66 | | // type |
67 | | static const int kCapacityAdjust = kSlabHeaderSize / sizeof(int); |
68 | | static_assert(kSlabHeaderSize % sizeof(int) == 0, |
69 | | "Slab header size should be multiple of key size"); |
70 | | |
71 | | void reserve(int n); |
72 | | |
73 | | // d[key] in Python: raises KeyError if not found |
74 | | V index_(K key); |
75 | | |
76 | | // Get a key. |
77 | | // Returns nullptr if not found (Can't use this for non-pointer types?) |
78 | | V get(K key); |
79 | | |
80 | | // Get a key, but return a default if not found. |
81 | | // expr_parse.py uses this with OTHER_BALANCE |
82 | | V get(K key, V default_val); |
83 | | |
84 | | // Implements d[k] = v. May resize the dictionary. |
85 | | void set(K key, V val); |
86 | | |
87 | | void update(List<Tuple2<K, V>*>* kvs); |
88 | | |
89 | | List<K>* keys(); |
90 | | |
91 | | // For AssocArray transformations |
92 | | List<V>* values(); |
93 | | |
94 | | void clear(); |
95 | | |
96 | | // Returns the position in the array. Used by dict_contains(), index(), |
97 | | // get(), and set(). |
98 | | // |
99 | | // For now this does a linear search. |
100 | | // TODO: |
101 | | // - hash functions, and linear probing. |
102 | | // - resizing based on load factor |
103 | | // - which requires rehashing (re-insert all items) |
104 | | // - Special case to intern Str* when it's hashed? How? |
105 | | // - Should we have wrappers like: |
106 | | // - V GetAndIntern<V>(D, &string_key) |
107 | | // - SetAndIntern<V>(D, &string_key, value) |
108 | | // This will enable duplicate copies of the string to be garbage collected |
109 | | int position_of_key(K key); |
110 | | |
111 | 53 | static constexpr ObjHeader obj_header() { |
112 | 53 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); |
113 | 53 | } _ZN4DictIP3StrS1_E10obj_headerEv Line | Count | Source | 111 | 9 | static constexpr ObjHeader obj_header() { | 112 | 9 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 9 | } |
_ZN4DictIP3StriE10obj_headerEv Line | Count | Source | 111 | 17 | static constexpr ObjHeader obj_header() { | 112 | 17 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 17 | } |
_ZN4DictIiP3StrE10obj_headerEv Line | Count | Source | 111 | 8 | static constexpr ObjHeader obj_header() { | 112 | 8 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 8 | } |
_ZN4DictIiiE10obj_headerEv Line | Count | Source | 111 | 6 | static constexpr ObjHeader obj_header() { | 112 | 6 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 6 | } |
_ZN4DictIP6Tuple2IiiEiE10obj_headerEv Line | Count | Source | 111 | 2 | static constexpr ObjHeader obj_header() { | 112 | 2 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 2 | } |
_ZN4DictIP6Tuple2IP3StriEiE10obj_headerEv Line | Count | Source | 111 | 2 | static constexpr ObjHeader obj_header() { | 112 | 2 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 2 | } |
_ZN4DictIP3StrPN4args7_ActionEE10obj_headerEv Line | Count | Source | 111 | 6 | static constexpr ObjHeader obj_header() { | 112 | 6 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 6 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEE10obj_headerEv Line | Count | Source | 111 | 3 | static constexpr ObjHeader obj_header() { | 112 | 3 | return ObjHeader::ClassFixed(field_mask(), sizeof(Dict)); | 113 | 3 | } |
|
114 | | |
115 | | GC_OBJ(header_); |
116 | | int len_; // number of entries (keys and values, almost dense) |
117 | | int capacity_; // number of entries before resizing |
118 | | |
119 | | // These 3 slabs are resized at the same time. |
120 | | Slab<int>* entry_; // NOW: kEmptyEntry, kDeletedEntry, or 0. |
121 | | // LATER: indices which are themselves indexed by // hash |
122 | | // value % capacity_ |
123 | | Slab<K>* keys_; // Dict<int, V> |
124 | | Slab<V>* values_; // Dict<K, int> |
125 | | |
126 | | // A dict has 3 pointers the GC needs to follow. |
127 | 55 | static constexpr uint16_t field_mask() { |
128 | 55 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | |
129 | 55 | maskbit(offsetof(Dict, values_)); |
130 | 55 | } _ZN4DictIP3StrS1_E10field_maskEv Line | Count | Source | 127 | 9 | static constexpr uint16_t field_mask() { | 128 | 9 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 9 | maskbit(offsetof(Dict, values_)); | 130 | 9 | } |
_ZN4DictIP3StriE10field_maskEv Line | Count | Source | 127 | 17 | static constexpr uint16_t field_mask() { | 128 | 17 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 17 | maskbit(offsetof(Dict, values_)); | 130 | 17 | } |
_ZN4DictIiP3StrE10field_maskEv Line | Count | Source | 127 | 8 | static constexpr uint16_t field_mask() { | 128 | 8 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 8 | maskbit(offsetof(Dict, values_)); | 130 | 8 | } |
_ZN4DictIiiE10field_maskEv Line | Count | Source | 127 | 8 | static constexpr uint16_t field_mask() { | 128 | 8 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 8 | maskbit(offsetof(Dict, values_)); | 130 | 8 | } |
_ZN4DictIP6Tuple2IiiEiE10field_maskEv Line | Count | Source | 127 | 2 | static constexpr uint16_t field_mask() { | 128 | 2 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 2 | maskbit(offsetof(Dict, values_)); | 130 | 2 | } |
_ZN4DictIP6Tuple2IP3StriEiE10field_maskEv Line | Count | Source | 127 | 2 | static constexpr uint16_t field_mask() { | 128 | 2 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 2 | maskbit(offsetof(Dict, values_)); | 130 | 2 | } |
_ZN4DictIP3StrPN4args7_ActionEE10field_maskEv Line | Count | Source | 127 | 6 | static constexpr uint16_t field_mask() { | 128 | 6 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 6 | maskbit(offsetof(Dict, values_)); | 130 | 6 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEE10field_maskEv Line | Count | Source | 127 | 3 | static constexpr uint16_t field_mask() { | 128 | 3 | return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) | | 129 | 3 | maskbit(offsetof(Dict, values_)); | 130 | 3 | } |
|
131 | | |
132 | | DISALLOW_COPY_AND_ASSIGN(Dict) |
133 | | |
134 | | private: |
135 | 82 | int RoundCapacity(int n) { |
136 | 82 | if (n < kMinItems) { |
137 | 44 | return kMinItems; |
138 | 44 | } |
139 | 38 | return RoundUp(n); |
140 | 82 | } _ZN4DictIP3StrS1_E13RoundCapacityEi Line | Count | Source | 135 | 10 | int RoundCapacity(int n) { | 136 | 10 | if (n < kMinItems) { | 137 | 6 | return kMinItems; | 138 | 6 | } | 139 | 4 | return RoundUp(n); | 140 | 10 | } |
_ZN4DictIP3StriE13RoundCapacityEi Line | Count | Source | 135 | 31 | int RoundCapacity(int n) { | 136 | 31 | if (n < kMinItems) { | 137 | 17 | return kMinItems; | 138 | 17 | } | 139 | 14 | return RoundUp(n); | 140 | 31 | } |
_ZN4DictIiP3StrE13RoundCapacityEi Line | Count | Source | 135 | 8 | int RoundCapacity(int n) { | 136 | 8 | if (n < kMinItems) { | 137 | 8 | return kMinItems; | 138 | 8 | } | 139 | 0 | return RoundUp(n); | 140 | 8 | } |
_ZN4DictIiiE13RoundCapacityEi Line | Count | Source | 135 | 14 | int RoundCapacity(int n) { | 136 | 14 | if (n < kMinItems) { | 137 | 4 | return kMinItems; | 138 | 4 | } | 139 | 10 | return RoundUp(n); | 140 | 14 | } |
_ZN4DictIP6Tuple2IiiEiE13RoundCapacityEi Line | Count | Source | 135 | 2 | int RoundCapacity(int n) { | 136 | 2 | if (n < kMinItems) { | 137 | 2 | return kMinItems; | 138 | 2 | } | 139 | 0 | return RoundUp(n); | 140 | 2 | } |
_ZN4DictIP6Tuple2IP3StriEiE13RoundCapacityEi Line | Count | Source | 135 | 2 | int RoundCapacity(int n) { | 136 | 2 | if (n < kMinItems) { | 137 | 2 | return kMinItems; | 138 | 2 | } | 139 | 0 | return RoundUp(n); | 140 | 2 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEE13RoundCapacityEi Line | Count | Source | 135 | 9 | int RoundCapacity(int n) { | 136 | 9 | if (n < kMinItems) { | 137 | 3 | return kMinItems; | 138 | 3 | } | 139 | 6 | return RoundUp(n); | 140 | 9 | } |
_ZN4DictIP3StrPN4args7_ActionEE13RoundCapacityEi Line | Count | Source | 135 | 6 | int RoundCapacity(int n) { | 136 | 6 | if (n < kMinItems) { | 137 | 2 | return kMinItems; | 138 | 2 | } | 139 | 4 | return RoundUp(n); | 140 | 6 | } |
|
141 | | }; |
142 | | |
143 | | template <typename K, typename V> |
144 | 8 | inline bool dict_contains(Dict<K, V>* haystack, K needle) { |
145 | 8 | return haystack->position_of_key(needle) != -1; |
146 | 8 | } _Z13dict_containsIiP3StrEbP4DictIT_T0_ES3_ Line | Count | Source | 144 | 4 | inline bool dict_contains(Dict<K, V>* haystack, K needle) { | 145 | 4 | return haystack->position_of_key(needle) != -1; | 146 | 4 | } |
_Z13dict_containsIP3StriEbP4DictIT_T0_ES3_ Line | Count | Source | 144 | 4 | inline bool dict_contains(Dict<K, V>* haystack, K needle) { | 145 | 4 | return haystack->position_of_key(needle) != -1; | 146 | 4 | } |
Unexecuted instantiation: _Z13dict_containsIP3StrPN4args7_ActionEEbP4DictIT_T0_ES6_ |
147 | | |
148 | | // TODO: Remove one of these styles using mycpp code gen |
149 | | template <typename K, typename V> |
150 | 29 | Dict<K, V>* NewDict() { |
151 | 29 | return Alloc<Dict<K, V>>(); |
152 | 29 | } _Z7NewDictIP3StriEP4DictIT_T0_Ev Line | Count | Source | 150 | 7 | Dict<K, V>* NewDict() { | 151 | 7 | return Alloc<Dict<K, V>>(); | 152 | 7 | } |
_Z7NewDictIiP3StrEP4DictIT_T0_Ev Line | Count | Source | 150 | 4 | Dict<K, V>* NewDict() { | 151 | 4 | return Alloc<Dict<K, V>>(); | 152 | 4 | } |
_Z7NewDictIP3StrS1_EP4DictIT_T0_Ev Line | Count | Source | 150 | 5 | Dict<K, V>* NewDict() { | 151 | 5 | return Alloc<Dict<K, V>>(); | 152 | 5 | } |
_Z7NewDictIiiEP4DictIT_T0_Ev Line | Count | Source | 150 | 4 | Dict<K, V>* NewDict() { | 151 | 4 | return Alloc<Dict<K, V>>(); | 152 | 4 | } |
_Z7NewDictIP3StrPN4args7_ActionEEP4DictIT_T0_Ev Line | Count | Source | 150 | 6 | Dict<K, V>* NewDict() { | 151 | 6 | return Alloc<Dict<K, V>>(); | 152 | 6 | } |
_Z7NewDictIP3StrPN12runtime_asdl7value_tEEP4DictIT_T0_Ev Line | Count | Source | 150 | 3 | Dict<K, V>* NewDict() { | 151 | 3 | return Alloc<Dict<K, V>>(); | 152 | 3 | } |
|
153 | | |
154 | | template <typename K, typename V> |
155 | | Dict<K, V>* NewDict(std::initializer_list<K> keys, |
156 | 2 | std::initializer_list<V> values) { |
157 | 2 | assert(keys.size() == values.size()); |
158 | 0 | auto self = Alloc<Dict<K, V>>(); |
159 | 2 | auto v = values.begin(); // This simulates a "zip" loop |
160 | 2 | for (auto key : keys) { |
161 | 2 | self->set(key, *v); |
162 | 2 | ++v; |
163 | 2 | } |
164 | | |
165 | 2 | return self; |
166 | 2 | } |
167 | | |
168 | | template <typename K, typename V> |
169 | 291 | void Dict<K, V>::reserve(int n) { |
170 | 291 | Slab<int>* new_i = nullptr; |
171 | 291 | Slab<K>* new_k = nullptr; |
172 | 291 | Slab<V>* new_v = nullptr; |
173 | | // log("--- reserve %d", capacity_); |
174 | | // |
175 | 291 | if (capacity_ < n) { // TODO: use load factor, not exact fit |
176 | | // calculate the number of keys and values we should have |
177 | 82 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; |
178 | | |
179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent |
180 | | // load factor? |
181 | 82 | int index_len = capacity_; |
182 | 82 | new_i = NewSlab<int>(index_len); |
183 | | |
184 | | // For the linear search to work |
185 | 774 | for (int i = 0; i < index_len; ++i) { |
186 | 692 | new_i->items_[i] = kEmptyEntry; |
187 | 692 | } |
188 | | |
189 | | // These are DENSE. |
190 | 82 | new_k = NewSlab<K>(capacity_); |
191 | 82 | new_v = NewSlab<V>(capacity_); |
192 | | |
193 | 82 | if (keys_ != nullptr) { |
194 | | // Right now the index is the same size as keys and values. |
195 | 36 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); |
196 | | |
197 | 36 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); |
198 | 36 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); |
199 | 36 | } |
200 | | |
201 | 82 | entry_ = new_i; |
202 | 82 | keys_ = new_k; |
203 | 82 | values_ = new_v; |
204 | 82 | } |
205 | 291 | } _ZN4DictIP3StrS1_E7reserveEi Line | Count | Source | 169 | 67 | void Dict<K, V>::reserve(int n) { | 170 | 67 | Slab<int>* new_i = nullptr; | 171 | 67 | Slab<K>* new_k = nullptr; | 172 | 67 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 67 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 10 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 10 | int index_len = capacity_; | 182 | 10 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 134 | for (int i = 0; i < index_len; ++i) { | 186 | 124 | new_i->items_[i] = kEmptyEntry; | 187 | 124 | } | 188 | | | 189 | | // These are DENSE. | 190 | 10 | new_k = NewSlab<K>(capacity_); | 191 | 10 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 10 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 4 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | | | 197 | 4 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 4 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 4 | } | 200 | | | 201 | 10 | entry_ = new_i; | 202 | 10 | keys_ = new_k; | 203 | 10 | values_ = new_v; | 204 | 10 | } | 205 | 67 | } |
_ZN4DictIP3StriE7reserveEi Line | Count | Source | 169 | 109 | void Dict<K, V>::reserve(int n) { | 170 | 109 | Slab<int>* new_i = nullptr; | 171 | 109 | Slab<K>* new_k = nullptr; | 172 | 109 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 109 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 31 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 31 | int index_len = capacity_; | 182 | 31 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 325 | for (int i = 0; i < index_len; ++i) { | 186 | 294 | new_i->items_[i] = kEmptyEntry; | 187 | 294 | } | 188 | | | 189 | | // These are DENSE. | 190 | 31 | new_k = NewSlab<K>(capacity_); | 191 | 31 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 31 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 14 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | | | 197 | 14 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 14 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 14 | } | 200 | | | 201 | 31 | entry_ = new_i; | 202 | 31 | keys_ = new_k; | 203 | 31 | values_ = new_v; | 204 | 31 | } | 205 | 109 | } |
_ZN4DictIiP3StrE7reserveEi Line | Count | Source | 169 | 8 | void Dict<K, V>::reserve(int n) { | 170 | 8 | Slab<int>* new_i = nullptr; | 171 | 8 | Slab<K>* new_k = nullptr; | 172 | 8 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 8 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 8 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 8 | int index_len = capacity_; | 182 | 8 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 24 | for (int i = 0; i < index_len; ++i) { | 186 | 16 | new_i->items_[i] = kEmptyEntry; | 187 | 16 | } | 188 | | | 189 | | // These are DENSE. | 190 | 8 | new_k = NewSlab<K>(capacity_); | 191 | 8 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 8 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 0 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | |
| 197 | 0 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 0 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 0 | } | 200 | | | 201 | 8 | entry_ = new_i; | 202 | 8 | keys_ = new_k; | 203 | 8 | values_ = new_v; | 204 | 8 | } | 205 | 8 | } |
Line | Count | Source | 169 | 44 | void Dict<K, V>::reserve(int n) { | 170 | 44 | Slab<int>* new_i = nullptr; | 171 | 44 | Slab<K>* new_k = nullptr; | 172 | 44 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 44 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 14 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 14 | int index_len = capacity_; | 182 | 14 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 138 | for (int i = 0; i < index_len; ++i) { | 186 | 124 | new_i->items_[i] = kEmptyEntry; | 187 | 124 | } | 188 | | | 189 | | // These are DENSE. | 190 | 14 | new_k = NewSlab<K>(capacity_); | 191 | 14 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 14 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 8 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | | | 197 | 8 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 8 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 8 | } | 200 | | | 201 | 14 | entry_ = new_i; | 202 | 14 | keys_ = new_k; | 203 | 14 | values_ = new_v; | 204 | 14 | } | 205 | 44 | } |
_ZN4DictIP6Tuple2IiiEiE7reserveEi Line | Count | Source | 169 | 4 | void Dict<K, V>::reserve(int n) { | 170 | 4 | Slab<int>* new_i = nullptr; | 171 | 4 | Slab<K>* new_k = nullptr; | 172 | 4 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 4 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 2 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 2 | int index_len = capacity_; | 182 | 2 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 6 | for (int i = 0; i < index_len; ++i) { | 186 | 4 | new_i->items_[i] = kEmptyEntry; | 187 | 4 | } | 188 | | | 189 | | // These are DENSE. | 190 | 2 | new_k = NewSlab<K>(capacity_); | 191 | 2 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 2 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 0 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | |
| 197 | 0 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 0 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 0 | } | 200 | | | 201 | 2 | entry_ = new_i; | 202 | 2 | keys_ = new_k; | 203 | 2 | values_ = new_v; | 204 | 2 | } | 205 | 4 | } |
_ZN4DictIP6Tuple2IP3StriEiE7reserveEi Line | Count | Source | 169 | 4 | void Dict<K, V>::reserve(int n) { | 170 | 4 | Slab<int>* new_i = nullptr; | 171 | 4 | Slab<K>* new_k = nullptr; | 172 | 4 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 4 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 2 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 2 | int index_len = capacity_; | 182 | 2 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 6 | for (int i = 0; i < index_len; ++i) { | 186 | 4 | new_i->items_[i] = kEmptyEntry; | 187 | 4 | } | 188 | | | 189 | | // These are DENSE. | 190 | 2 | new_k = NewSlab<K>(capacity_); | 191 | 2 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 2 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 0 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | |
| 197 | 0 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 0 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 0 | } | 200 | | | 201 | 2 | entry_ = new_i; | 202 | 2 | keys_ = new_k; | 203 | 2 | values_ = new_v; | 204 | 2 | } | 205 | 4 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEE7reserveEi Line | Count | Source | 169 | 29 | void Dict<K, V>::reserve(int n) { | 170 | 29 | Slab<int>* new_i = nullptr; | 171 | 29 | Slab<K>* new_k = nullptr; | 172 | 29 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 29 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 9 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 9 | int index_len = capacity_; | 182 | 9 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 91 | for (int i = 0; i < index_len; ++i) { | 186 | 82 | new_i->items_[i] = kEmptyEntry; | 187 | 82 | } | 188 | | | 189 | | // These are DENSE. | 190 | 9 | new_k = NewSlab<K>(capacity_); | 191 | 9 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 9 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 6 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | | | 197 | 6 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 6 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 6 | } | 200 | | | 201 | 9 | entry_ = new_i; | 202 | 9 | keys_ = new_k; | 203 | 9 | values_ = new_v; | 204 | 9 | } | 205 | 29 | } |
_ZN4DictIP3StrPN4args7_ActionEE7reserveEi Line | Count | Source | 169 | 26 | void Dict<K, V>::reserve(int n) { | 170 | 26 | Slab<int>* new_i = nullptr; | 171 | 26 | Slab<K>* new_k = nullptr; | 172 | 26 | Slab<V>* new_v = nullptr; | 173 | | // log("--- reserve %d", capacity_); | 174 | | // | 175 | 26 | if (capacity_ < n) { // TODO: use load factor, not exact fit | 176 | | // calculate the number of keys and values we should have | 177 | 6 | capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust; | 178 | | | 179 | | // TODO: This is SPARSE. How to compute a size that ensures a decent | 180 | | // load factor? | 181 | 6 | int index_len = capacity_; | 182 | 6 | new_i = NewSlab<int>(index_len); | 183 | | | 184 | | // For the linear search to work | 185 | 50 | for (int i = 0; i < index_len; ++i) { | 186 | 44 | new_i->items_[i] = kEmptyEntry; | 187 | 44 | } | 188 | | | 189 | | // These are DENSE. | 190 | 6 | new_k = NewSlab<K>(capacity_); | 191 | 6 | new_v = NewSlab<V>(capacity_); | 192 | | | 193 | 6 | if (keys_ != nullptr) { | 194 | | // Right now the index is the same size as keys and values. | 195 | 4 | memcpy(new_i->items_, entry_->items_, len_ * sizeof(int)); | 196 | | | 197 | 4 | memcpy(new_k->items_, keys_->items_, len_ * sizeof(K)); | 198 | 4 | memcpy(new_v->items_, values_->items_, len_ * sizeof(V)); | 199 | 4 | } | 200 | | | 201 | 6 | entry_ = new_i; | 202 | 6 | keys_ = new_k; | 203 | 6 | values_ = new_v; | 204 | 6 | } | 205 | 26 | } |
|
206 | | |
207 | | // d[key] in Python: raises KeyError if not found |
208 | | template <typename K, typename V> |
209 | 78 | V Dict<K, V>::index_(K key) { |
210 | 78 | int pos = position_of_key(key); |
211 | 78 | if (pos == -1) { |
212 | 0 | throw Alloc<KeyError>(); |
213 | 78 | } else { |
214 | 78 | return values_->items_[pos]; |
215 | 78 | } |
216 | 78 | } _ZN4DictIP3StrS1_E6index_ES1_ Line | Count | Source | 209 | 3 | V Dict<K, V>::index_(K key) { | 210 | 3 | int pos = position_of_key(key); | 211 | 3 | if (pos == -1) { | 212 | 0 | throw Alloc<KeyError>(); | 213 | 3 | } else { | 214 | 3 | return values_->items_[pos]; | 215 | 3 | } | 216 | 3 | } |
_ZN4DictIP3StriE6index_ES1_ Line | Count | Source | 209 | 13 | V Dict<K, V>::index_(K key) { | 210 | 13 | int pos = position_of_key(key); | 211 | 13 | if (pos == -1) { | 212 | 0 | throw Alloc<KeyError>(); | 213 | 13 | } else { | 214 | 13 | return values_->items_[pos]; | 215 | 13 | } | 216 | 13 | } |
_ZN4DictIiP3StrE6index_Ei Line | Count | Source | 209 | 6 | V Dict<K, V>::index_(K key) { | 210 | 6 | int pos = position_of_key(key); | 211 | 6 | if (pos == -1) { | 212 | 0 | throw Alloc<KeyError>(); | 213 | 6 | } else { | 214 | 6 | return values_->items_[pos]; | 215 | 6 | } | 216 | 6 | } |
Line | Count | Source | 209 | 48 | V Dict<K, V>::index_(K key) { | 210 | 48 | int pos = position_of_key(key); | 211 | 48 | if (pos == -1) { | 212 | 0 | throw Alloc<KeyError>(); | 213 | 48 | } else { | 214 | 48 | return values_->items_[pos]; | 215 | 48 | } | 216 | 48 | } |
_ZN4DictIP6Tuple2IiiEiE6index_ES2_ Line | Count | Source | 209 | 4 | V Dict<K, V>::index_(K key) { | 210 | 4 | int pos = position_of_key(key); | 211 | 4 | if (pos == -1) { | 212 | 0 | throw Alloc<KeyError>(); | 213 | 4 | } else { | 214 | 4 | return values_->items_[pos]; | 215 | 4 | } | 216 | 4 | } |
_ZN4DictIP6Tuple2IP3StriEiE6index_ES4_ Line | Count | Source | 209 | 4 | V Dict<K, V>::index_(K key) { | 210 | 4 | int pos = position_of_key(key); | 211 | 4 | if (pos == -1) { | 212 | 0 | throw Alloc<KeyError>(); | 213 | 4 | } else { | 214 | 4 | return values_->items_[pos]; | 215 | 4 | } | 216 | 4 | } |
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEE6index_ES1_ Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE6index_ES1_ |
217 | | |
218 | | // Get a key. |
219 | | // Returns nullptr if not found (Can't use this for non-pointer types?) |
220 | | template <typename K, typename V> |
221 | 7 | V Dict<K, V>::get(K key) { |
222 | 7 | int pos = position_of_key(key); |
223 | 7 | if (pos == -1) { |
224 | 4 | return nullptr; |
225 | 4 | } else { |
226 | 3 | return values_->items_[pos]; |
227 | 3 | } |
228 | 7 | } Line | Count | Source | 221 | 4 | V Dict<K, V>::get(K key) { | 222 | 4 | int pos = position_of_key(key); | 223 | 4 | if (pos == -1) { | 224 | 2 | return nullptr; | 225 | 2 | } else { | 226 | 2 | return values_->items_[pos]; | 227 | 2 | } | 228 | 4 | } |
_ZN4DictIP3StrS1_E3getES1_ Line | Count | Source | 221 | 3 | V Dict<K, V>::get(K key) { | 222 | 3 | int pos = position_of_key(key); | 223 | 3 | if (pos == -1) { | 224 | 2 | return nullptr; | 225 | 2 | } else { | 226 | 1 | return values_->items_[pos]; | 227 | 1 | } | 228 | 3 | } |
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE3getES1_ |
229 | | |
230 | | // Get a key, but return a default if not found. |
231 | | // expr_parse.py uses this with OTHER_BALANCE |
232 | | template <typename K, typename V> |
233 | 2 | V Dict<K, V>::get(K key, V default_val) { |
234 | 2 | int pos = position_of_key(key); |
235 | 2 | if (pos == -1) { |
236 | 2 | return default_val; |
237 | 2 | } else { |
238 | 0 | return values_->items_[pos]; |
239 | 0 | } |
240 | 2 | } _ZN4DictIP3StrS1_E3getES1_S1_ Line | Count | Source | 233 | 2 | V Dict<K, V>::get(K key, V default_val) { | 234 | 2 | int pos = position_of_key(key); | 235 | 2 | if (pos == -1) { | 236 | 2 | return default_val; | 237 | 2 | } else { | 238 | 0 | return values_->items_[pos]; | 239 | 0 | } | 240 | 2 | } |
Unexecuted instantiation: _ZN4DictIiP3StrE3getEiS1_ Unexecuted instantiation: _ZN4DictIP3StriE3getES1_i |
241 | | |
242 | | template <typename K, typename V> |
243 | 10 | List<K>* Dict<K, V>::keys() { |
244 | 10 | return ListFromDictSlab<K>(entry_, keys_, capacity_); |
245 | 10 | } Line | Count | Source | 243 | 8 | List<K>* Dict<K, V>::keys() { | 244 | 8 | return ListFromDictSlab<K>(entry_, keys_, capacity_); | 245 | 8 | } |
_ZN4DictIP3StrS1_E4keysEv Line | Count | Source | 243 | 2 | List<K>* Dict<K, V>::keys() { | 244 | 2 | return ListFromDictSlab<K>(entry_, keys_, capacity_); | 245 | 2 | } |
|
246 | | |
247 | | // For AssocArray transformations |
248 | | template <typename K, typename V> |
249 | 4 | List<V>* Dict<K, V>::values() { |
250 | 4 | return ListFromDictSlab<V>(entry_, values_, capacity_); |
251 | 4 | } _ZN4DictIP3StriE6valuesEv Line | Count | Source | 249 | 2 | List<V>* Dict<K, V>::values() { | 250 | 2 | return ListFromDictSlab<V>(entry_, values_, capacity_); | 251 | 2 | } |
_ZN4DictIP3StrS1_E6valuesEv Line | Count | Source | 249 | 2 | List<V>* Dict<K, V>::values() { | 250 | 2 | return ListFromDictSlab<V>(entry_, values_, capacity_); | 251 | 2 | } |
|
252 | | |
253 | | template <typename K, typename V> |
254 | 2 | void Dict<K, V>::clear() { |
255 | | // Maintain invariant |
256 | 14 | for (int i = 0; i < capacity_; ++i) { |
257 | 12 | entry_->items_[i] = kEmptyEntry; |
258 | 12 | } |
259 | | |
260 | 2 | memset(keys_->items_, 0, len_ * sizeof(K)); // zero for GC scan |
261 | 2 | memset(values_->items_, 0, len_ * sizeof(V)); // zero for GC scan |
262 | 2 | len_ = 0; |
263 | 2 | } |
264 | | |
265 | | // Returns the position in the array. Used by dict_contains(), index(), |
266 | | // get(), and set(). |
267 | | // |
268 | | // For now this does a linear search. |
269 | | // TODO: |
270 | | // - hash functions, and linear probing. |
271 | | // - resizing based on load factor |
272 | | // - which requires rehashing (re-insert all items) |
273 | | // - Special case to intern Str* when it's hashed? How? |
274 | | // - Should we have wrappers like: |
275 | | // - V GetAndIntern<V>(D, &string_key) |
276 | | // - SetAndIntern<V>(D, &string_key, value) |
277 | | // This will enable duplicate copies of the string to be garbage collected |
278 | | template <typename K, typename V> |
279 | 393 | int Dict<K, V>::position_of_key(K key) { |
280 | 4.56k | for (int i = 0; i < capacity_; ++i) { |
281 | 4.48k | int special = entry_->items_[i]; // NOT an index now |
282 | 4.48k | if (special == kDeletedEntry) { |
283 | 2 | continue; // keep searching |
284 | 2 | } |
285 | 4.48k | if (special == kEmptyEntry) { |
286 | 215 | return -1; // not found |
287 | 215 | } |
288 | 4.26k | if (keys_equal(keys_->items_[i], key)) { |
289 | 94 | return i; |
290 | 94 | } |
291 | 4.26k | } |
292 | 84 | return -1; // table is completely full? Does this happen? |
293 | 393 | } _ZN4DictIP3StrS1_E15position_of_keyES1_ Line | Count | Source | 279 | 77 | int Dict<K, V>::position_of_key(K key) { | 280 | 2.02k | for (int i = 0; i < capacity_; ++i) { | 281 | 2.00k | int special = entry_->items_[i]; // NOT an index now | 282 | 2.00k | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 2.00k | if (special == kEmptyEntry) { | 286 | 57 | return -1; // not found | 287 | 57 | } | 288 | 1.95k | if (keys_equal(keys_->items_[i], key)) { | 289 | 6 | return i; | 290 | 6 | } | 291 | 1.95k | } | 292 | 14 | return -1; // table is completely full? Does this happen? | 293 | 77 | } |
_ZN4DictIP3StriE15position_of_keyES1_ Line | Count | Source | 279 | 129 | int Dict<K, V>::position_of_key(K key) { | 280 | 1.73k | for (int i = 0; i < capacity_; ++i) { | 281 | 1.70k | int special = entry_->items_[i]; // NOT an index now | 282 | 1.70k | if (special == kDeletedEntry) { | 283 | 2 | continue; // keep searching | 284 | 2 | } | 285 | 1.69k | if (special == kEmptyEntry) { | 286 | 80 | return -1; // not found | 287 | 80 | } | 288 | 1.61k | if (keys_equal(keys_->items_[i], key)) { | 289 | 18 | return i; | 290 | 18 | } | 291 | 1.61k | } | 292 | 31 | return -1; // table is completely full? Does this happen? | 293 | 129 | } |
_ZN4DictIiP3StrE15position_of_keyEi Line | Count | Source | 279 | 22 | int Dict<K, V>::position_of_key(K key) { | 280 | 26 | for (int i = 0; i < capacity_; ++i) { | 281 | 18 | int special = entry_->items_[i]; // NOT an index now | 282 | 18 | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 18 | if (special == kEmptyEntry) { | 286 | 4 | return -1; // not found | 287 | 4 | } | 288 | 14 | if (keys_equal(keys_->items_[i], key)) { | 289 | 10 | return i; | 290 | 10 | } | 291 | 14 | } | 292 | 8 | return -1; // table is completely full? Does this happen? | 293 | 22 | } |
_ZN4DictIiiE15position_of_keyEi Line | Count | Source | 279 | 94 | int Dict<K, V>::position_of_key(K key) { | 280 | 384 | for (int i = 0; i < capacity_; ++i) { | 281 | 372 | int special = entry_->items_[i]; // NOT an index now | 282 | 372 | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 372 | if (special == kEmptyEntry) { | 286 | 30 | return -1; // not found | 287 | 30 | } | 288 | 342 | if (keys_equal(keys_->items_[i], key)) { | 289 | 52 | return i; | 290 | 52 | } | 291 | 342 | } | 292 | 12 | return -1; // table is completely full? Does this happen? | 293 | 94 | } |
_ZN4DictIP6Tuple2IiiEiE15position_of_keyES2_ Line | Count | Source | 279 | 8 | int Dict<K, V>::position_of_key(K key) { | 280 | 12 | for (int i = 0; i < capacity_; ++i) { | 281 | 10 | int special = entry_->items_[i]; // NOT an index now | 282 | 10 | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 10 | if (special == kEmptyEntry) { | 286 | 2 | return -1; // not found | 287 | 2 | } | 288 | 8 | if (keys_equal(keys_->items_[i], key)) { | 289 | 4 | return i; | 290 | 4 | } | 291 | 8 | } | 292 | 2 | return -1; // table is completely full? Does this happen? | 293 | 8 | } |
_ZN4DictIP6Tuple2IP3StriEiE15position_of_keyES4_ Line | Count | Source | 279 | 8 | int Dict<K, V>::position_of_key(K key) { | 280 | 12 | for (int i = 0; i < capacity_; ++i) { | 281 | 10 | int special = entry_->items_[i]; // NOT an index now | 282 | 10 | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 10 | if (special == kEmptyEntry) { | 286 | 2 | return -1; // not found | 287 | 2 | } | 288 | 8 | if (keys_equal(keys_->items_[i], key)) { | 289 | 4 | return i; | 290 | 4 | } | 291 | 8 | } | 292 | 2 | return -1; // table is completely full? Does this happen? | 293 | 8 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEE15position_of_keyES1_ Line | Count | Source | 279 | 29 | int Dict<K, V>::position_of_key(K key) { | 280 | 197 | for (int i = 0; i < capacity_; ++i) { | 281 | 188 | int special = entry_->items_[i]; // NOT an index now | 282 | 188 | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 188 | if (special == kEmptyEntry) { | 286 | 20 | return -1; // not found | 287 | 20 | } | 288 | 168 | if (keys_equal(keys_->items_[i], key)) { | 289 | 0 | return i; | 290 | 0 | } | 291 | 168 | } | 292 | 9 | return -1; // table is completely full? Does this happen? | 293 | 29 | } |
_ZN4DictIP3StrPN4args7_ActionEE15position_of_keyES1_ Line | Count | Source | 279 | 26 | int Dict<K, V>::position_of_key(K key) { | 280 | 182 | for (int i = 0; i < capacity_; ++i) { | 281 | 176 | int special = entry_->items_[i]; // NOT an index now | 282 | 176 | if (special == kDeletedEntry) { | 283 | 0 | continue; // keep searching | 284 | 0 | } | 285 | 176 | if (special == kEmptyEntry) { | 286 | 20 | return -1; // not found | 287 | 20 | } | 288 | 156 | if (keys_equal(keys_->items_[i], key)) { | 289 | 0 | return i; | 290 | 0 | } | 291 | 156 | } | 292 | 6 | return -1; // table is completely full? Does this happen? | 293 | 26 | } |
|
294 | | |
295 | | template <typename K, typename V> |
296 | 294 | void Dict<K, V>::set(K key, V val) { |
297 | 294 | int pos = position_of_key(key); |
298 | 294 | if (pos == -1) { // new pair |
299 | 289 | reserve(len_ + 1); |
300 | 289 | keys_->items_[len_] = key; |
301 | 289 | values_->items_[len_] = val; |
302 | | |
303 | 289 | entry_->items_[len_] = 0; // new special value |
304 | | |
305 | 289 | ++len_; |
306 | 289 | } else { |
307 | 5 | values_->items_[pos] = val; |
308 | 5 | } |
309 | 294 | } _ZN4DictIP3StrS1_E3setES1_S1_ Line | Count | Source | 296 | 67 | void Dict<K, V>::set(K key, V val) { | 297 | 67 | int pos = position_of_key(key); | 298 | 67 | if (pos == -1) { // new pair | 299 | 67 | reserve(len_ + 1); | 300 | 67 | keys_->items_[len_] = key; | 301 | 67 | values_->items_[len_] = val; | 302 | | | 303 | 67 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 67 | ++len_; | 306 | 67 | } else { | 307 | 0 | values_->items_[pos] = val; | 308 | 0 | } | 309 | 67 | } |
_ZN4DictIP3StriE3setES1_i Line | Count | Source | 296 | 110 | void Dict<K, V>::set(K key, V val) { | 297 | 110 | int pos = position_of_key(key); | 298 | 110 | if (pos == -1) { // new pair | 299 | 109 | reserve(len_ + 1); | 300 | 109 | keys_->items_[len_] = key; | 301 | 109 | values_->items_[len_] = val; | 302 | | | 303 | 109 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 109 | ++len_; | 306 | 109 | } else { | 307 | 1 | values_->items_[pos] = val; | 308 | 1 | } | 309 | 110 | } |
_ZN4DictIiP3StrE3setEiS1_ Line | Count | Source | 296 | 8 | void Dict<K, V>::set(K key, V val) { | 297 | 8 | int pos = position_of_key(key); | 298 | 8 | if (pos == -1) { // new pair | 299 | 8 | reserve(len_ + 1); | 300 | 8 | keys_->items_[len_] = key; | 301 | 8 | values_->items_[len_] = val; | 302 | | | 303 | 8 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 8 | ++len_; | 306 | 8 | } else { | 307 | 0 | values_->items_[pos] = val; | 308 | 0 | } | 309 | 8 | } |
Line | Count | Source | 296 | 46 | void Dict<K, V>::set(K key, V val) { | 297 | 46 | int pos = position_of_key(key); | 298 | 46 | if (pos == -1) { // new pair | 299 | 42 | reserve(len_ + 1); | 300 | 42 | keys_->items_[len_] = key; | 301 | 42 | values_->items_[len_] = val; | 302 | | | 303 | 42 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 42 | ++len_; | 306 | 42 | } else { | 307 | 4 | values_->items_[pos] = val; | 308 | 4 | } | 309 | 46 | } |
_ZN4DictIP6Tuple2IiiEiE3setES2_i Line | Count | Source | 296 | 4 | void Dict<K, V>::set(K key, V val) { | 297 | 4 | int pos = position_of_key(key); | 298 | 4 | if (pos == -1) { // new pair | 299 | 4 | reserve(len_ + 1); | 300 | 4 | keys_->items_[len_] = key; | 301 | 4 | values_->items_[len_] = val; | 302 | | | 303 | 4 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 4 | ++len_; | 306 | 4 | } else { | 307 | 0 | values_->items_[pos] = val; | 308 | 0 | } | 309 | 4 | } |
_ZN4DictIP6Tuple2IP3StriEiE3setES4_i Line | Count | Source | 296 | 4 | void Dict<K, V>::set(K key, V val) { | 297 | 4 | int pos = position_of_key(key); | 298 | 4 | if (pos == -1) { // new pair | 299 | 4 | reserve(len_ + 1); | 300 | 4 | keys_->items_[len_] = key; | 301 | 4 | values_->items_[len_] = val; | 302 | | | 303 | 4 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 4 | ++len_; | 306 | 4 | } else { | 307 | 0 | values_->items_[pos] = val; | 308 | 0 | } | 309 | 4 | } |
_ZN4DictIP3StrPN12runtime_asdl7value_tEE3setES1_S4_ Line | Count | Source | 296 | 29 | void Dict<K, V>::set(K key, V val) { | 297 | 29 | int pos = position_of_key(key); | 298 | 29 | if (pos == -1) { // new pair | 299 | 29 | reserve(len_ + 1); | 300 | 29 | keys_->items_[len_] = key; | 301 | 29 | values_->items_[len_] = val; | 302 | | | 303 | 29 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 29 | ++len_; | 306 | 29 | } else { | 307 | 0 | values_->items_[pos] = val; | 308 | 0 | } | 309 | 29 | } |
_ZN4DictIP3StrPN4args7_ActionEE3setES1_S4_ Line | Count | Source | 296 | 26 | void Dict<K, V>::set(K key, V val) { | 297 | 26 | int pos = position_of_key(key); | 298 | 26 | if (pos == -1) { // new pair | 299 | 26 | reserve(len_ + 1); | 300 | 26 | keys_->items_[len_] = key; | 301 | 26 | values_->items_[len_] = val; | 302 | | | 303 | 26 | entry_->items_[len_] = 0; // new special value | 304 | | | 305 | 26 | ++len_; | 306 | 26 | } else { | 307 | 0 | values_->items_[pos] = val; | 308 | 0 | } | 309 | 26 | } |
|
310 | | |
311 | | template <class K, class V> |
312 | 2 | void Dict<K, V>::update(List<Tuple2<K, V>*>* kvs) { |
313 | 6 | for (ListIter<Tuple2<K, V>*> it(kvs); !it.Done(); it.Next()) { |
314 | 4 | set(it.Value()->at0(), it.Value()->at1()); |
315 | 4 | } |
316 | 2 | } |
317 | | |
318 | | template <typename K, typename V> |
319 | 35 | inline int len(const Dict<K, V>* d) { |
320 | 35 | return d->len_; |
321 | 35 | } _Z3lenIP3StrS1_EiPK4DictIT_T0_E Line | Count | Source | 319 | 9 | inline int len(const Dict<K, V>* d) { | 320 | 9 | return d->len_; | 321 | 9 | } |
_Z3lenIP3StriEiPK4DictIT_T0_E Line | Count | Source | 319 | 18 | inline int len(const Dict<K, V>* d) { | 320 | 18 | return d->len_; | 321 | 18 | } |
_Z3lenIiiEiPK4DictIT_T0_E Line | Count | Source | 319 | 8 | inline int len(const Dict<K, V>* d) { | 320 | 8 | return d->len_; | 321 | 8 | } |
Unexecuted instantiation: _Z3lenIiP3StrEiPK4DictIT_T0_E Unexecuted instantiation: _Z3lenIP3StrPN4args7_ActionEEiPK4DictIT_T0_E |
322 | | |
323 | | template <class K, class V> |
324 | | class DictIter { |
325 | | public: |
326 | 11 | explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) { |
327 | 11 | } _ZN8DictIterIP3StriEC2EP4DictIS1_iE Line | Count | Source | 326 | 9 | explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) { | 327 | 9 | } |
_ZN8DictIterIP3StrS1_EC2EP4DictIS1_S1_E Line | Count | Source | 326 | 2 | explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) { | 327 | 2 | } |
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEEC2EP4DictIS1_S4_E Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEEC2EP4DictIS1_S4_E |
328 | 17 | void Next() { |
329 | 17 | pos_ = ValidPosAfter(pos_ + 1); |
330 | 17 | } _ZN8DictIterIP3StriE4NextEv Line | Count | Source | 328 | 17 | void Next() { | 329 | 17 | pos_ = ValidPosAfter(pos_ + 1); | 330 | 17 | } |
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E4NextEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE4NextEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE4NextEv |
331 | 28 | bool Done() { |
332 | 28 | return pos_ == -1; |
333 | 28 | } _ZN8DictIterIP3StriE4DoneEv Line | Count | Source | 331 | 26 | bool Done() { | 332 | 26 | return pos_ == -1; | 333 | 26 | } |
_ZN8DictIterIP3StrS1_E4DoneEv Line | Count | Source | 331 | 2 | bool Done() { | 332 | 2 | return pos_ == -1; | 333 | 2 | } |
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE4DoneEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE4DoneEv |
334 | 17 | K Key() { |
335 | 17 | return D_->keys_->items_[pos_]; |
336 | 17 | } _ZN8DictIterIP3StriE3KeyEv Line | Count | Source | 334 | 17 | K Key() { | 335 | 17 | return D_->keys_->items_[pos_]; | 336 | 17 | } |
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E3KeyEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE3KeyEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE3KeyEv |
337 | 10 | V Value() { |
338 | 10 | return D_->values_->items_[pos_]; |
339 | 10 | } _ZN8DictIterIP3StriE5ValueEv Line | Count | Source | 337 | 10 | V Value() { | 338 | 10 | return D_->values_->items_[pos_]; | 339 | 10 | } |
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E5ValueEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE5ValueEv Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE5ValueEv |
340 | | |
341 | | private: |
342 | 28 | int ValidPosAfter(int pos) { |
343 | | // Returns the position of a valid entry at or after index i_. Or -1 if |
344 | | // there isn't one. Advances i_ too. |
345 | 32 | while (true) { |
346 | 32 | if (pos >= D_->capacity_) { |
347 | 2 | return -1; |
348 | 2 | } |
349 | 30 | int index = D_->entry_->items_[pos]; |
350 | 30 | if (index == kDeletedEntry) { |
351 | 4 | ++pos; |
352 | 4 | continue; // increment again |
353 | 4 | } |
354 | 26 | if (index == kEmptyEntry) { |
355 | 9 | return -1; |
356 | 9 | } |
357 | 17 | break; |
358 | 26 | } |
359 | 17 | return pos; |
360 | 28 | } _ZN8DictIterIP3StriE13ValidPosAfterEi Line | Count | Source | 342 | 26 | int ValidPosAfter(int pos) { | 343 | | // Returns the position of a valid entry at or after index i_. Or -1 if | 344 | | // there isn't one. Advances i_ too. | 345 | 28 | while (true) { | 346 | 28 | if (pos >= D_->capacity_) { | 347 | 2 | return -1; | 348 | 2 | } | 349 | 26 | int index = D_->entry_->items_[pos]; | 350 | 26 | if (index == kDeletedEntry) { | 351 | 2 | ++pos; | 352 | 2 | continue; // increment again | 353 | 2 | } | 354 | 24 | if (index == kEmptyEntry) { | 355 | 7 | return -1; | 356 | 7 | } | 357 | 17 | break; | 358 | 24 | } | 359 | 17 | return pos; | 360 | 26 | } |
_ZN8DictIterIP3StrS1_E13ValidPosAfterEi Line | Count | Source | 342 | 2 | int ValidPosAfter(int pos) { | 343 | | // Returns the position of a valid entry at or after index i_. Or -1 if | 344 | | // there isn't one. Advances i_ too. | 345 | 4 | while (true) { | 346 | 4 | if (pos >= D_->capacity_) { | 347 | 0 | return -1; | 348 | 0 | } | 349 | 4 | int index = D_->entry_->items_[pos]; | 350 | 4 | if (index == kDeletedEntry) { | 351 | 2 | ++pos; | 352 | 2 | continue; // increment again | 353 | 2 | } | 354 | 2 | if (index == kEmptyEntry) { | 355 | 2 | return -1; | 356 | 2 | } | 357 | 0 | break; | 358 | 2 | } | 359 | 0 | return pos; | 360 | 2 | } |
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE13ValidPosAfterEi Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE13ValidPosAfterEi |
361 | | |
362 | | Dict<K, V>* D_; |
363 | | int pos_; |
364 | | }; |
365 | | |
366 | | // dict(l) converts a list of (k, v) tuples into a dict |
367 | | template <typename K, typename V> |
368 | 2 | Dict<K, V>* dict(List<Tuple2<K, V>*>* l) { |
369 | 2 | auto ret = NewDict<K, V>(); |
370 | 2 | ret->reserve(len(l)); |
371 | 6 | for (ListIter<Tuple2<K, V>*> it(l); !it.Done(); it.Next()) { |
372 | 4 | ret->set(it.Value()->at0(), it.Value()->at1()); |
373 | 4 | } |
374 | 2 | return ret; |
375 | 2 | } |
376 | | |
377 | | #endif // MYCPP_GC_DICT_H |