cpp

Coverage Report

Created: 2023-09-13 01:07

/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
// GlobalDict is layout-compatible with Dict (unit tests assert this), and it
39
// can be a true C global (incurs zero startup time)
40
41
template <typename K, typename V, int N>
42
class GlobalDict {
43
 public:
44
  int len_;
45
  int capacity_;
46
  GlobalSlab<int, N>* entry_;  // TODO: should be sized differently
47
  GlobalSlab<K, N>* keys_;
48
  GlobalSlab<V, N>* values_;
49
};
50
51
// TODO: when we implement entry_, it shouldn't be the zero slab
52
// We should probably update the runtime code to allow a nullptr?  For linear
53
// search?
54
55
#define GLOBAL_DICT(name, K, V, N, keys, vals)                                 \
56
  GcGlobal<GlobalSlab<int, N>> _entry_##name = {                               \
57
      ObjHeader::Global(TypeTag::Slab), {.items_ = {}}};                       \
58
  GcGlobal<GlobalSlab<K, N>> _keys_##name = {ObjHeader::Global(TypeTag::Slab), \
59
                                             {.items_ = keys}};                \
60
  GcGlobal<GlobalSlab<V, N>> _vals_##name = {ObjHeader::Global(TypeTag::Slab), \
61
                                             {.items_ = vals}};                \
62
  GcGlobal<GlobalDict<K, V, N>> _dict_##name = {                               \
63
      ObjHeader::Global(TypeTag::Dict),                                        \
64
      {.len_ = N,                                                              \
65
       .capacity_ = N,                                                         \
66
       .entry_ = &_entry_##name.obj,                                           \
67
       .keys_ = &_keys_##name.obj,                                             \
68
       .values_ = &_vals_##name.obj},                                          \
69
  };                                                                           \
70
  Dict<K, V>* name = reinterpret_cast<Dict<K, V>*>(&_dict_##name.obj);
71
72
template <class K, class V>
73
class Dict {
74
  // Relates to minimum slab size.  This is good for Dict<K*, V*>, Dict<K*,
75
  // int>, Dict<int, V*>, but possibly suboptimal for Dict<int, int>.  But that
76
  // case is rare.
77
  static const int kMinItems = 4;
78
79
 public:
80
  Dict()
81
      : len_(0),
82
        capacity_(0),
83
        entry_(nullptr),
84
        keys_(nullptr),
85
51
        values_(nullptr) {
86
51
  }
_ZN4DictIP3StrS1_EC2Ev
Line
Count
Source
85
9
        values_(nullptr) {
86
9
  }
_ZN4DictIP3StriEC2Ev
Line
Count
Source
85
17
        values_(nullptr) {
86
17
  }
_ZN4DictIiP3StrEC2Ev
Line
Count
Source
85
6
        values_(nullptr) {
86
6
  }
_ZN4DictIiiEC2Ev
Line
Count
Source
85
6
        values_(nullptr) {
86
6
  }
_ZN4DictIP6Tuple2IiiEiEC2Ev
Line
Count
Source
85
2
        values_(nullptr) {
86
2
  }
_ZN4DictIP6Tuple2IP3StriEiEC2Ev
Line
Count
Source
85
2
        values_(nullptr) {
86
2
  }
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEEC2Ev
_ZN4DictIP3StrPN4args7_ActionEEC2Ev
Line
Count
Source
85
6
        values_(nullptr) {
86
6
  }
_ZN4DictIP3StrPN12runtime_asdl7value_tEEC2Ev
Line
Count
Source
85
3
        values_(nullptr) {
86
3
  }
87
88
  Dict(std::initializer_list<K> keys, std::initializer_list<V> values)
89
      : len_(0),
90
        capacity_(0),
91
        entry_(nullptr),
92
        keys_(nullptr),
93
5
        values_(nullptr) {
94
5
    assert(keys.size() == values.size());
95
0
    auto v = values.begin();  // This simulates a "zip" loop
96
8
    for (auto key : keys) {
97
      // note: calls reserve(), and maybe allocate
98
8
      this->set(key, *v);
99
8
      ++v;
100
8
    }
101
5
  }
_ZN4DictIP3StriEC2ESt16initializer_listIS1_ES3_IiE
Line
Count
Source
93
3
        values_(nullptr) {
94
3
    assert(keys.size() == values.size());
95
0
    auto v = values.begin();  // This simulates a "zip" loop
96
6
    for (auto key : keys) {
97
      // note: calls reserve(), and maybe allocate
98
6
      this->set(key, *v);
99
6
      ++v;
100
6
    }
101
3
  }
_ZN4DictIiP3StrEC2ESt16initializer_listIiES3_IS1_E
Line
Count
Source
93
2
        values_(nullptr) {
94
2
    assert(keys.size() == values.size());
95
0
    auto v = values.begin();  // This simulates a "zip" loop
96
2
    for (auto key : keys) {
97
      // note: calls reserve(), and maybe allocate
98
2
      this->set(key, *v);
99
2
      ++v;
100
2
    }
101
2
  }
102
103
  // This relies on the fact that containers of 4-byte ints are reduced by 2
104
  // items, which is greater than (or equal to) the reduction of any other
105
  // type
106
  static const int kCapacityAdjust = kSlabHeaderSize / sizeof(int);
107
  static_assert(kSlabHeaderSize % sizeof(int) == 0,
108
                "Slab header size should be multiple of key size");
109
110
  void reserve(int n);
111
112
  // d[key] in Python: raises KeyError if not found
113
  V index_(K key);
114
115
  // Get a key.
116
  // Returns nullptr if not found (Can't use this for non-pointer types?)
117
  V get(K key);
118
119
  // Get a key, but return a default if not found.
120
  // expr_parse.py uses this with OTHER_BALANCE
121
  V get(K key, V default_val);
122
123
  // Implements d[k] = v.  May resize the dictionary.
124
  void set(K key, V val);
125
126
  void update(List<Tuple2<K, V>*>* kvs);
127
128
  List<K>* keys();
129
130
  // For AssocArray transformations
131
  List<V>* values();
132
133
  void clear();
134
135
  // Returns the position in the array.  Used by dict_contains(), index(),
136
  // get(), and set().
137
  //
138
  // For now this does a linear search.
139
  // TODO:
140
  // - hash functions, and linear probing.
141
  // - resizing based on load factor
142
  //   - which requires rehashing (re-insert all items)
143
  // - Special case to intern Str* when it's hashed?  How?
144
  //   - Should we have wrappers like:
145
  //   - V GetAndIntern<V>(D, &string_key)
146
  //   - SetAndIntern<V>(D, &string_key, value)
147
  //   This will enable duplicate copies of the string to be garbage collected
148
  int position_of_key(K key);
149
150
56
  static constexpr ObjHeader obj_header() {
151
56
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
56
  }
_ZN4DictIP3StrS1_E10obj_headerEv
Line
Count
Source
150
9
  static constexpr ObjHeader obj_header() {
151
9
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
9
  }
_ZN4DictIP3StriE10obj_headerEv
Line
Count
Source
150
20
  static constexpr ObjHeader obj_header() {
151
20
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
20
  }
_ZN4DictIiP3StrE10obj_headerEv
Line
Count
Source
150
8
  static constexpr ObjHeader obj_header() {
151
8
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
8
  }
_ZN4DictIiiE10obj_headerEv
Line
Count
Source
150
6
  static constexpr ObjHeader obj_header() {
151
6
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
6
  }
_ZN4DictIP6Tuple2IiiEiE10obj_headerEv
Line
Count
Source
150
2
  static constexpr ObjHeader obj_header() {
151
2
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
2
  }
_ZN4DictIP6Tuple2IP3StriEiE10obj_headerEv
Line
Count
Source
150
2
  static constexpr ObjHeader obj_header() {
151
2
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
2
  }
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEE10obj_headerEv
_ZN4DictIP3StrPN4args7_ActionEE10obj_headerEv
Line
Count
Source
150
6
  static constexpr ObjHeader obj_header() {
151
6
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
6
  }
_ZN4DictIP3StrPN12runtime_asdl7value_tEE10obj_headerEv
Line
Count
Source
150
3
  static constexpr ObjHeader obj_header() {
151
3
    return ObjHeader::ClassFixed(field_mask(), sizeof(Dict));
152
3
  }
153
154
  int len_;       // number of entries (keys and values, almost dense)
155
  int capacity_;  // number of entries before resizing
156
157
  // These 3 slabs are resized at the same time.
158
  Slab<int>* entry_;  // NOW: kEmptyEntry, kDeletedEntry, or 0.
159
                      // LATER: indices which are themselves indexed by // hash
160
                      // value % capacity_
161
  Slab<K>* keys_;     // Dict<int, V>
162
  Slab<V>* values_;   // Dict<K, int>
163
164
  // A dict has 3 pointers the GC needs to follow.
165
58
  static constexpr uint32_t field_mask() {
166
58
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
58
           maskbit(offsetof(Dict, values_));
168
58
  }
_ZN4DictIP3StrS1_E10field_maskEv
Line
Count
Source
165
9
  static constexpr uint32_t field_mask() {
166
9
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
9
           maskbit(offsetof(Dict, values_));
168
9
  }
_ZN4DictIP3StriE10field_maskEv
Line
Count
Source
165
20
  static constexpr uint32_t field_mask() {
166
20
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
20
           maskbit(offsetof(Dict, values_));
168
20
  }
_ZN4DictIiP3StrE10field_maskEv
Line
Count
Source
165
8
  static constexpr uint32_t field_mask() {
166
8
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
8
           maskbit(offsetof(Dict, values_));
168
8
  }
_ZN4DictIiiE10field_maskEv
Line
Count
Source
165
8
  static constexpr uint32_t field_mask() {
166
8
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
8
           maskbit(offsetof(Dict, values_));
168
8
  }
_ZN4DictIP6Tuple2IiiEiE10field_maskEv
Line
Count
Source
165
2
  static constexpr uint32_t field_mask() {
166
2
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
2
           maskbit(offsetof(Dict, values_));
168
2
  }
_ZN4DictIP6Tuple2IP3StriEiE10field_maskEv
Line
Count
Source
165
2
  static constexpr uint32_t field_mask() {
166
2
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
2
           maskbit(offsetof(Dict, values_));
168
2
  }
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEE10field_maskEv
_ZN4DictIP3StrPN4args7_ActionEE10field_maskEv
Line
Count
Source
165
6
  static constexpr uint32_t field_mask() {
166
6
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
6
           maskbit(offsetof(Dict, values_));
168
6
  }
_ZN4DictIP3StrPN12runtime_asdl7value_tEE10field_maskEv
Line
Count
Source
165
3
  static constexpr uint32_t field_mask() {
166
3
    return maskbit(offsetof(Dict, entry_)) | maskbit(offsetof(Dict, keys_)) |
167
3
           maskbit(offsetof(Dict, values_));
168
3
  }
169
170
  DISALLOW_COPY_AND_ASSIGN(Dict)
171
172
 private:
173
86
  int RoundCapacity(int n) {
174
86
    if (n < kMinItems) {
175
47
      return kMinItems;
176
47
    }
177
39
    return RoundUp(n);
178
86
  }
_ZN4DictIP3StrS1_E13RoundCapacityEi
Line
Count
Source
173
10
  int RoundCapacity(int n) {
174
10
    if (n < kMinItems) {
175
6
      return kMinItems;
176
6
    }
177
4
    return RoundUp(n);
178
10
  }
_ZN4DictIP3StriE13RoundCapacityEi
Line
Count
Source
173
34
  int RoundCapacity(int n) {
174
34
    if (n < kMinItems) {
175
20
      return kMinItems;
176
20
    }
177
14
    return RoundUp(n);
178
34
  }
_ZN4DictIiP3StrE13RoundCapacityEi
Line
Count
Source
173
8
  int RoundCapacity(int n) {
174
8
    if (n < kMinItems) {
175
8
      return kMinItems;
176
8
    }
177
0
    return RoundUp(n);
178
8
  }
_ZN4DictIiiE13RoundCapacityEi
Line
Count
Source
173
14
  int RoundCapacity(int n) {
174
14
    if (n < kMinItems) {
175
4
      return kMinItems;
176
4
    }
177
10
    return RoundUp(n);
178
14
  }
_ZN4DictIP6Tuple2IiiEiE13RoundCapacityEi
Line
Count
Source
173
2
  int RoundCapacity(int n) {
174
2
    if (n < kMinItems) {
175
2
      return kMinItems;
176
2
    }
177
0
    return RoundUp(n);
178
2
  }
_ZN4DictIP6Tuple2IP3StriEiE13RoundCapacityEi
Line
Count
Source
173
2
  int RoundCapacity(int n) {
174
2
    if (n < kMinItems) {
175
2
      return kMinItems;
176
2
    }
177
0
    return RoundUp(n);
178
2
  }
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEE13RoundCapacityEi
_ZN4DictIP3StrPN12runtime_asdl7value_tEE13RoundCapacityEi
Line
Count
Source
173
9
  int RoundCapacity(int n) {
174
9
    if (n < kMinItems) {
175
3
      return kMinItems;
176
3
    }
177
6
    return RoundUp(n);
178
9
  }
_ZN4DictIP3StrPN4args7_ActionEE13RoundCapacityEi
Line
Count
Source
173
7
  int RoundCapacity(int n) {
174
7
    if (n < kMinItems) {
175
2
      return kMinItems;
176
2
    }
177
5
    return RoundUp(n);
178
7
  }
179
};
180
181
template <typename K, typename V>
182
9
inline bool dict_contains(Dict<K, V>* haystack, K needle) {
183
9
  return haystack->position_of_key(needle) != -1;
184
9
}
_Z13dict_containsIP3StriEbP4DictIT_T0_ES3_
Line
Count
Source
182
5
inline bool dict_contains(Dict<K, V>* haystack, K needle) {
183
5
  return haystack->position_of_key(needle) != -1;
184
5
}
_Z13dict_containsIiP3StrEbP4DictIT_T0_ES3_
Line
Count
Source
182
4
inline bool dict_contains(Dict<K, V>* haystack, K needle) {
183
4
  return haystack->position_of_key(needle) != -1;
184
4
}
Unexecuted instantiation: _Z13dict_containsIP3StrPN4args7_ActionEEbP4DictIT_T0_ES6_
185
186
#if 0
187
// mylib.NewDict() translates to this
188
template <typename K, typename V>
189
Dict<K, V>* NewDict() {
190
  return Alloc<Dict<K, V>>();
191
}
192
193
template <typename K, typename V>
194
Dict<K, V>* NewDict(std::initializer_list<K> keys,
195
                    std::initializer_list<V> values) {
196
  assert(keys.size() == values.size());
197
  auto self = Alloc<Dict<K, V>>();
198
  auto v = values.begin();  // This simulates a "zip" loop
199
  for (auto key : keys) {
200
    // note: calls reserve(), and maybe allocate
201
    self->set(key, *v);
202
    ++v;
203
  }
204
205
  return self;
206
}
207
#endif
208
209
template <typename K, typename V>
210
276
void Dict<K, V>::reserve(int n) {
211
276
  Slab<int>* new_i = nullptr;
212
276
  Slab<K>* new_k = nullptr;
213
276
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
276
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
86
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
86
    int index_len = capacity_;
223
86
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
814
    for (int i = 0; i < index_len; ++i) {
227
728
      new_i->items_[i] = kEmptyEntry;
228
728
    }
229
230
    // These are DENSE.
231
86
    new_k = NewSlab<K>(capacity_);
232
86
    new_v = NewSlab<V>(capacity_);
233
234
86
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
37
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
37
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
37
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
37
    }
241
242
86
    entry_ = new_i;
243
86
    keys_ = new_k;
244
86
    values_ = new_v;
245
86
  }
246
276
}
_ZN4DictIP3StrS1_E7reserveEi
Line
Count
Source
210
38
void Dict<K, V>::reserve(int n) {
211
38
  Slab<int>* new_i = nullptr;
212
38
  Slab<K>* new_k = nullptr;
213
38
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
38
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
10
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
10
    int index_len = capacity_;
223
10
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
134
    for (int i = 0; i < index_len; ++i) {
227
124
      new_i->items_[i] = kEmptyEntry;
228
124
    }
229
230
    // These are DENSE.
231
10
    new_k = NewSlab<K>(capacity_);
232
10
    new_v = NewSlab<V>(capacity_);
233
234
10
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
4
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
4
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
4
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
4
    }
241
242
10
    entry_ = new_i;
243
10
    keys_ = new_k;
244
10
    values_ = new_v;
245
10
  }
246
38
}
_ZN4DictIP3StriE7reserveEi
Line
Count
Source
210
115
void Dict<K, V>::reserve(int n) {
211
115
  Slab<int>* new_i = nullptr;
212
115
  Slab<K>* new_k = nullptr;
213
115
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
115
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
34
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
34
    int index_len = capacity_;
223
34
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
334
    for (int i = 0; i < index_len; ++i) {
227
300
      new_i->items_[i] = kEmptyEntry;
228
300
    }
229
230
    // These are DENSE.
231
34
    new_k = NewSlab<K>(capacity_);
232
34
    new_v = NewSlab<V>(capacity_);
233
234
34
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
14
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
14
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
14
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
14
    }
241
242
34
    entry_ = new_i;
243
34
    keys_ = new_k;
244
34
    values_ = new_v;
245
34
  }
246
115
}
_ZN4DictIiP3StrE7reserveEi
Line
Count
Source
210
8
void Dict<K, V>::reserve(int n) {
211
8
  Slab<int>* new_i = nullptr;
212
8
  Slab<K>* new_k = nullptr;
213
8
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
8
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
8
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
8
    int index_len = capacity_;
223
8
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
24
    for (int i = 0; i < index_len; ++i) {
227
16
      new_i->items_[i] = kEmptyEntry;
228
16
    }
229
230
    // These are DENSE.
231
8
    new_k = NewSlab<K>(capacity_);
232
8
    new_v = NewSlab<V>(capacity_);
233
234
8
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
0
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
0
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
0
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
0
    }
241
242
8
    entry_ = new_i;
243
8
    keys_ = new_k;
244
8
    values_ = new_v;
245
8
  }
246
8
}
_ZN4DictIiiE7reserveEi
Line
Count
Source
210
44
void Dict<K, V>::reserve(int n) {
211
44
  Slab<int>* new_i = nullptr;
212
44
  Slab<K>* new_k = nullptr;
213
44
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
44
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
14
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
14
    int index_len = capacity_;
223
14
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
138
    for (int i = 0; i < index_len; ++i) {
227
124
      new_i->items_[i] = kEmptyEntry;
228
124
    }
229
230
    // These are DENSE.
231
14
    new_k = NewSlab<K>(capacity_);
232
14
    new_v = NewSlab<V>(capacity_);
233
234
14
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
8
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
8
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
8
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
8
    }
241
242
14
    entry_ = new_i;
243
14
    keys_ = new_k;
244
14
    values_ = new_v;
245
14
  }
246
44
}
_ZN4DictIP6Tuple2IiiEiE7reserveEi
Line
Count
Source
210
4
void Dict<K, V>::reserve(int n) {
211
4
  Slab<int>* new_i = nullptr;
212
4
  Slab<K>* new_k = nullptr;
213
4
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
4
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
2
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
2
    int index_len = capacity_;
223
2
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
6
    for (int i = 0; i < index_len; ++i) {
227
4
      new_i->items_[i] = kEmptyEntry;
228
4
    }
229
230
    // These are DENSE.
231
2
    new_k = NewSlab<K>(capacity_);
232
2
    new_v = NewSlab<V>(capacity_);
233
234
2
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
0
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
0
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
0
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
0
    }
241
242
2
    entry_ = new_i;
243
2
    keys_ = new_k;
244
2
    values_ = new_v;
245
2
  }
246
4
}
_ZN4DictIP6Tuple2IP3StriEiE7reserveEi
Line
Count
Source
210
4
void Dict<K, V>::reserve(int n) {
211
4
  Slab<int>* new_i = nullptr;
212
4
  Slab<K>* new_k = nullptr;
213
4
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
4
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
2
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
2
    int index_len = capacity_;
223
2
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
6
    for (int i = 0; i < index_len; ++i) {
227
4
      new_i->items_[i] = kEmptyEntry;
228
4
    }
229
230
    // These are DENSE.
231
2
    new_k = NewSlab<K>(capacity_);
232
2
    new_v = NewSlab<V>(capacity_);
233
234
2
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
0
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
0
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
0
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
0
    }
241
242
2
    entry_ = new_i;
243
2
    keys_ = new_k;
244
2
    values_ = new_v;
245
2
  }
246
4
}
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEE7reserveEi
_ZN4DictIP3StrPN12runtime_asdl7value_tEE7reserveEi
Line
Count
Source
210
33
void Dict<K, V>::reserve(int n) {
211
33
  Slab<int>* new_i = nullptr;
212
33
  Slab<K>* new_k = nullptr;
213
33
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
33
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
9
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
9
    int index_len = capacity_;
223
9
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
91
    for (int i = 0; i < index_len; ++i) {
227
82
      new_i->items_[i] = kEmptyEntry;
228
82
    }
229
230
    // These are DENSE.
231
9
    new_k = NewSlab<K>(capacity_);
232
9
    new_v = NewSlab<V>(capacity_);
233
234
9
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
6
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
6
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
6
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
6
    }
241
242
9
    entry_ = new_i;
243
9
    keys_ = new_k;
244
9
    values_ = new_v;
245
9
  }
246
33
}
_ZN4DictIP3StrPN4args7_ActionEE7reserveEi
Line
Count
Source
210
30
void Dict<K, V>::reserve(int n) {
211
30
  Slab<int>* new_i = nullptr;
212
30
  Slab<K>* new_k = nullptr;
213
30
  Slab<V>* new_v = nullptr;
214
  // log("--- reserve %d", capacity_);
215
  //
216
30
  if (capacity_ < n) {  // TODO: use load factor, not exact fit
217
    // calculate the number of keys and values we should have
218
7
    capacity_ = RoundCapacity(n + kCapacityAdjust) - kCapacityAdjust;
219
220
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
221
    // load factor?
222
7
    int index_len = capacity_;
223
7
    new_i = NewSlab<int>(index_len);
224
225
    // For the linear search to work
226
81
    for (int i = 0; i < index_len; ++i) {
227
74
      new_i->items_[i] = kEmptyEntry;
228
74
    }
229
230
    // These are DENSE.
231
7
    new_k = NewSlab<K>(capacity_);
232
7
    new_v = NewSlab<V>(capacity_);
233
234
7
    if (keys_ != nullptr) {
235
      // Right now the index is the same size as keys and values.
236
5
      memcpy(new_i->items_, entry_->items_, len_ * sizeof(int));
237
238
5
      memcpy(new_k->items_, keys_->items_, len_ * sizeof(K));
239
5
      memcpy(new_v->items_, values_->items_, len_ * sizeof(V));
240
5
    }
241
242
7
    entry_ = new_i;
243
7
    keys_ = new_k;
244
7
    values_ = new_v;
245
7
  }
246
30
}
247
248
// d[key] in Python: raises KeyError if not found
249
template <typename K, typename V>
250
94
V Dict<K, V>::index_(K key) {
251
94
  int pos = position_of_key(key);
252
94
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
94
  } else {
255
94
    return values_->items_[pos];
256
94
  }
257
94
}
_ZN4DictIP3StrS1_E6index_ES1_
Line
Count
Source
250
8
V Dict<K, V>::index_(K key) {
251
8
  int pos = position_of_key(key);
252
8
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
8
  } else {
255
8
    return values_->items_[pos];
256
8
  }
257
8
}
_ZN4DictIP3StriE6index_ES1_
Line
Count
Source
250
19
V Dict<K, V>::index_(K key) {
251
19
  int pos = position_of_key(key);
252
19
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
19
  } else {
255
19
    return values_->items_[pos];
256
19
  }
257
19
}
_ZN4DictIiP3StrE6index_Ei
Line
Count
Source
250
7
V Dict<K, V>::index_(K key) {
251
7
  int pos = position_of_key(key);
252
7
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
7
  } else {
255
7
    return values_->items_[pos];
256
7
  }
257
7
}
_ZN4DictIiiE6index_Ei
Line
Count
Source
250
52
V Dict<K, V>::index_(K key) {
251
52
  int pos = position_of_key(key);
252
52
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
52
  } else {
255
52
    return values_->items_[pos];
256
52
  }
257
52
}
_ZN4DictIP6Tuple2IiiEiE6index_ES2_
Line
Count
Source
250
4
V Dict<K, V>::index_(K key) {
251
4
  int pos = position_of_key(key);
252
4
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
4
  } else {
255
4
    return values_->items_[pos];
256
4
  }
257
4
}
_ZN4DictIP6Tuple2IP3StriEiE6index_ES4_
Line
Count
Source
250
4
V Dict<K, V>::index_(K key) {
251
4
  int pos = position_of_key(key);
252
4
  if (pos == -1) {
253
0
    throw Alloc<KeyError>();
254
4
  } else {
255
4
    return values_->items_[pos];
256
4
  }
257
4
}
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEE6index_ES1_
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE6index_ES1_
258
259
// Get a key.
260
// Returns nullptr if not found (Can't use this for non-pointer types?)
261
template <typename K, typename V>
262
7
V Dict<K, V>::get(K key) {
263
7
  int pos = position_of_key(key);
264
7
  if (pos == -1) {
265
4
    return nullptr;
266
4
  } else {
267
3
    return values_->items_[pos];
268
3
  }
269
7
}
_ZN4DictIiP3StrE3getEi
Line
Count
Source
262
4
V Dict<K, V>::get(K key) {
263
4
  int pos = position_of_key(key);
264
4
  if (pos == -1) {
265
2
    return nullptr;
266
2
  } else {
267
2
    return values_->items_[pos];
268
2
  }
269
4
}
_ZN4DictIP3StrS1_E3getES1_
Line
Count
Source
262
3
V Dict<K, V>::get(K key) {
263
3
  int pos = position_of_key(key);
264
3
  if (pos == -1) {
265
2
    return nullptr;
266
2
  } else {
267
1
    return values_->items_[pos];
268
1
  }
269
3
}
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE3getES1_
270
271
// Get a key, but return a default if not found.
272
// expr_parse.py uses this with OTHER_BALANCE
273
template <typename K, typename V>
274
2
V Dict<K, V>::get(K key, V default_val) {
275
2
  int pos = position_of_key(key);
276
2
  if (pos == -1) {
277
2
    return default_val;
278
2
  } else {
279
0
    return values_->items_[pos];
280
0
  }
281
2
}
_ZN4DictIP3StrS1_E3getES1_S1_
Line
Count
Source
274
2
V Dict<K, V>::get(K key, V default_val) {
275
2
  int pos = position_of_key(key);
276
2
  if (pos == -1) {
277
2
    return default_val;
278
2
  } else {
279
0
    return values_->items_[pos];
280
0
  }
281
2
}
Unexecuted instantiation: _ZN4DictIiP3StrE3getEiS1_
Unexecuted instantiation: _ZN4DictIP3StriE3getES1_i
282
283
template <typename K, typename V>
284
10
List<K>* Dict<K, V>::keys() {
285
10
  return ListFromDictSlab<K>(entry_, keys_, capacity_);
286
10
}
_ZN4DictIP3StriE4keysEv
Line
Count
Source
284
8
List<K>* Dict<K, V>::keys() {
285
8
  return ListFromDictSlab<K>(entry_, keys_, capacity_);
286
8
}
_ZN4DictIP3StrS1_E4keysEv
Line
Count
Source
284
2
List<K>* Dict<K, V>::keys() {
285
2
  return ListFromDictSlab<K>(entry_, keys_, capacity_);
286
2
}
287
288
// For AssocArray transformations
289
template <typename K, typename V>
290
4
List<V>* Dict<K, V>::values() {
291
4
  return ListFromDictSlab<V>(entry_, values_, capacity_);
292
4
}
_ZN4DictIP3StriE6valuesEv
Line
Count
Source
290
2
List<V>* Dict<K, V>::values() {
291
2
  return ListFromDictSlab<V>(entry_, values_, capacity_);
292
2
}
_ZN4DictIP3StrS1_E6valuesEv
Line
Count
Source
290
2
List<V>* Dict<K, V>::values() {
291
2
  return ListFromDictSlab<V>(entry_, values_, capacity_);
292
2
}
293
294
template <typename K, typename V>
295
4
void Dict<K, V>::clear() {
296
  // Maintain invariant
297
16
  for (int i = 0; i < capacity_; ++i) {
298
12
    entry_->items_[i] = kEmptyEntry;
299
12
  }
300
301
4
  if (keys_) {
302
2
    memset(keys_->items_, 0, len_ * sizeof(K));  // zero for GC scan
303
2
  }
304
4
  if (values_) {
305
2
    memset(values_->items_, 0, len_ * sizeof(V));  // zero for GC scan
306
2
  }
307
4
  len_ = 0;
308
4
}
_ZN4DictIiP3StrE5clearEv
Line
Count
Source
295
2
void Dict<K, V>::clear() {
296
  // Maintain invariant
297
2
  for (int i = 0; i < capacity_; ++i) {
298
0
    entry_->items_[i] = kEmptyEntry;
299
0
  }
300
301
2
  if (keys_) {
302
0
    memset(keys_->items_, 0, len_ * sizeof(K));  // zero for GC scan
303
0
  }
304
2
  if (values_) {
305
0
    memset(values_->items_, 0, len_ * sizeof(V));  // zero for GC scan
306
0
  }
307
2
  len_ = 0;
308
2
}
_ZN4DictIP3StriE5clearEv
Line
Count
Source
295
2
void Dict<K, V>::clear() {
296
  // Maintain invariant
297
14
  for (int i = 0; i < capacity_; ++i) {
298
12
    entry_->items_[i] = kEmptyEntry;
299
12
  }
300
301
2
  if (keys_) {
302
2
    memset(keys_->items_, 0, len_ * sizeof(K));  // zero for GC scan
303
2
  }
304
2
  if (values_) {
305
2
    memset(values_->items_, 0, len_ * sizeof(V));  // zero for GC scan
306
2
  }
307
2
  len_ = 0;
308
2
}
309
310
// Returns the position in the array.  Used by dict_contains(), index(),
311
// get(), and set().
312
//
313
// For now this does a linear search.
314
// TODO:
315
// - hash functions, and linear probing.
316
// - resizing based on load factor
317
//   - which requires rehashing (re-insert all items)
318
// - Special case to intern Str* when it's hashed?  How?
319
//   - Should we have wrappers like:
320
//   - V GetAndIntern<V>(D, &string_key)
321
//   - SetAndIntern<V>(D, &string_key, value)
322
//   This will enable duplicate copies of the string to be garbage collected
323
template <typename K, typename V>
324
395
int Dict<K, V>::position_of_key(K key) {
325
3.31k
  for (int i = 0; i < capacity_; ++i) {
326
3.23k
    int special = entry_->items_[i];  // NOT an index now
327
3.23k
    if (special == kDeletedEntry) {
328
2
      continue;  // keep searching
329
2
    }
330
3.22k
    if (special == kEmptyEntry) {
331
196
      return -1;  // not found
332
196
    }
333
3.03k
    if (keys_equal(keys_->items_[i], key)) {
334
111
      return i;
335
111
    }
336
3.03k
  }
337
88
  return -1;  // table is completely full?  Does this happen?
338
395
}
_ZN4DictIP3StrS1_E15position_of_keyES1_
Line
Count
Source
324
53
int Dict<K, V>::position_of_key(K key) {
325
611
  for (int i = 0; i < capacity_; ++i) {
326
597
    int special = entry_->items_[i];  // NOT an index now
327
597
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
597
    if (special == kEmptyEntry) {
331
28
      return -1;  // not found
332
28
    }
333
569
    if (keys_equal(keys_->items_[i], key)) {
334
11
      return i;
335
11
    }
336
569
  }
337
14
  return -1;  // table is completely full?  Does this happen?
338
53
}
_ZN4DictIP3StriE15position_of_keyES1_
Line
Count
Source
324
142
int Dict<K, V>::position_of_key(K key) {
325
1.75k
  for (int i = 0; i < capacity_; ++i) {
326
1.71k
    int special = entry_->items_[i];  // NOT an index now
327
1.71k
    if (special == kDeletedEntry) {
328
2
      continue;  // keep searching
329
2
    }
330
1.71k
    if (special == kEmptyEntry) {
331
83
      return -1;  // not found
332
83
    }
333
1.63k
    if (keys_equal(keys_->items_[i], key)) {
334
25
      return i;
335
25
    }
336
1.63k
  }
337
34
  return -1;  // table is completely full?  Does this happen?
338
142
}
_ZN4DictIiP3StrE15position_of_keyEi
Line
Count
Source
324
23
int Dict<K, V>::position_of_key(K key) {
325
27
  for (int i = 0; i < capacity_; ++i) {
326
19
    int special = entry_->items_[i];  // NOT an index now
327
19
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
19
    if (special == kEmptyEntry) {
331
4
      return -1;  // not found
332
4
    }
333
15
    if (keys_equal(keys_->items_[i], key)) {
334
11
      return i;
335
11
    }
336
15
  }
337
8
  return -1;  // table is completely full?  Does this happen?
338
23
}
_ZN4DictIiiE15position_of_keyEi
Line
Count
Source
324
98
int Dict<K, V>::position_of_key(K key) {
325
390
  for (int i = 0; i < capacity_; ++i) {
326
378
    int special = entry_->items_[i];  // NOT an index now
327
378
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
378
    if (special == kEmptyEntry) {
331
30
      return -1;  // not found
332
30
    }
333
348
    if (keys_equal(keys_->items_[i], key)) {
334
56
      return i;
335
56
    }
336
348
  }
337
12
  return -1;  // table is completely full?  Does this happen?
338
98
}
_ZN4DictIP6Tuple2IiiEiE15position_of_keyES2_
Line
Count
Source
324
8
int Dict<K, V>::position_of_key(K key) {
325
12
  for (int i = 0; i < capacity_; ++i) {
326
10
    int special = entry_->items_[i];  // NOT an index now
327
10
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
10
    if (special == kEmptyEntry) {
331
2
      return -1;  // not found
332
2
    }
333
8
    if (keys_equal(keys_->items_[i], key)) {
334
4
      return i;
335
4
    }
336
8
  }
337
2
  return -1;  // table is completely full?  Does this happen?
338
8
}
_ZN4DictIP6Tuple2IP3StriEiE15position_of_keyES4_
Line
Count
Source
324
8
int Dict<K, V>::position_of_key(K key) {
325
12
  for (int i = 0; i < capacity_; ++i) {
326
10
    int special = entry_->items_[i];  // NOT an index now
327
10
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
10
    if (special == kEmptyEntry) {
331
2
      return -1;  // not found
332
2
    }
333
8
    if (keys_equal(keys_->items_[i], key)) {
334
4
      return i;
335
4
    }
336
8
  }
337
2
  return -1;  // table is completely full?  Does this happen?
338
8
}
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEE15position_of_keyEi
_ZN4DictIP3StrPN12runtime_asdl7value_tEE15position_of_keyES1_
Line
Count
Source
324
33
int Dict<K, V>::position_of_key(K key) {
325
271
  for (int i = 0; i < capacity_; ++i) {
326
262
    int special = entry_->items_[i];  // NOT an index now
327
262
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
262
    if (special == kEmptyEntry) {
331
24
      return -1;  // not found
332
24
    }
333
238
    if (keys_equal(keys_->items_[i], key)) {
334
0
      return i;
335
0
    }
336
238
  }
337
9
  return -1;  // table is completely full?  Does this happen?
338
33
}
_ZN4DictIP3StrPN4args7_ActionEE15position_of_keyES1_
Line
Count
Source
324
30
int Dict<K, V>::position_of_key(K key) {
325
244
  for (int i = 0; i < capacity_; ++i) {
326
237
    int special = entry_->items_[i];  // NOT an index now
327
237
    if (special == kDeletedEntry) {
328
0
      continue;  // keep searching
329
0
    }
330
237
    if (special == kEmptyEntry) {
331
23
      return -1;  // not found
332
23
    }
333
214
    if (keys_equal(keys_->items_[i], key)) {
334
0
      return i;
335
0
    }
336
214
  }
337
7
  return -1;  // table is completely full?  Does this happen?
338
30
}
339
340
template <typename K, typename V>
341
279
void Dict<K, V>::set(K key, V val) {
342
279
  int pos = position_of_key(key);
343
279
  if (pos == -1) {  // new pair
344
274
    reserve(len_ + 1);
345
274
    keys_->items_[len_] = key;
346
274
    values_->items_[len_] = val;
347
348
274
    entry_->items_[len_] = 0;  // new special value
349
350
274
    ++len_;
351
274
  } else {
352
5
    values_->items_[pos] = val;
353
5
  }
354
279
}
_ZN4DictIP3StrS1_E3setES1_S1_
Line
Count
Source
341
38
void Dict<K, V>::set(K key, V val) {
342
38
  int pos = position_of_key(key);
343
38
  if (pos == -1) {  // new pair
344
38
    reserve(len_ + 1);
345
38
    keys_->items_[len_] = key;
346
38
    values_->items_[len_] = val;
347
348
38
    entry_->items_[len_] = 0;  // new special value
349
350
38
    ++len_;
351
38
  } else {
352
0
    values_->items_[pos] = val;
353
0
  }
354
38
}
_ZN4DictIP3StriE3setES1_i
Line
Count
Source
341
116
void Dict<K, V>::set(K key, V val) {
342
116
  int pos = position_of_key(key);
343
116
  if (pos == -1) {  // new pair
344
115
    reserve(len_ + 1);
345
115
    keys_->items_[len_] = key;
346
115
    values_->items_[len_] = val;
347
348
115
    entry_->items_[len_] = 0;  // new special value
349
350
115
    ++len_;
351
115
  } else {
352
1
    values_->items_[pos] = val;
353
1
  }
354
116
}
_ZN4DictIiP3StrE3setEiS1_
Line
Count
Source
341
8
void Dict<K, V>::set(K key, V val) {
342
8
  int pos = position_of_key(key);
343
8
  if (pos == -1) {  // new pair
344
8
    reserve(len_ + 1);
345
8
    keys_->items_[len_] = key;
346
8
    values_->items_[len_] = val;
347
348
8
    entry_->items_[len_] = 0;  // new special value
349
350
8
    ++len_;
351
8
  } else {
352
0
    values_->items_[pos] = val;
353
0
  }
354
8
}
_ZN4DictIiiE3setEii
Line
Count
Source
341
46
void Dict<K, V>::set(K key, V val) {
342
46
  int pos = position_of_key(key);
343
46
  if (pos == -1) {  // new pair
344
42
    reserve(len_ + 1);
345
42
    keys_->items_[len_] = key;
346
42
    values_->items_[len_] = val;
347
348
42
    entry_->items_[len_] = 0;  // new special value
349
350
42
    ++len_;
351
42
  } else {
352
4
    values_->items_[pos] = val;
353
4
  }
354
46
}
_ZN4DictIP6Tuple2IiiEiE3setES2_i
Line
Count
Source
341
4
void Dict<K, V>::set(K key, V val) {
342
4
  int pos = position_of_key(key);
343
4
  if (pos == -1) {  // new pair
344
4
    reserve(len_ + 1);
345
4
    keys_->items_[len_] = key;
346
4
    values_->items_[len_] = val;
347
348
4
    entry_->items_[len_] = 0;  // new special value
349
350
4
    ++len_;
351
4
  } else {
352
0
    values_->items_[pos] = val;
353
0
  }
354
4
}
_ZN4DictIP6Tuple2IP3StriEiE3setES4_i
Line
Count
Source
341
4
void Dict<K, V>::set(K key, V val) {
342
4
  int pos = position_of_key(key);
343
4
  if (pos == -1) {  // new pair
344
4
    reserve(len_ + 1);
345
4
    keys_->items_[len_] = key;
346
4
    values_->items_[len_] = val;
347
348
4
    entry_->items_[len_] = 0;  // new special value
349
350
4
    ++len_;
351
4
  } else {
352
0
    values_->items_[pos] = val;
353
0
  }
354
4
}
Unexecuted instantiation: _ZN4DictIiP6Tuple2IP4ListIPS1_IPS0_IiiEEEPS_IiiEEE3setEiSB_
_ZN4DictIP3StrPN12runtime_asdl7value_tEE3setES1_S4_
Line
Count
Source
341
33
void Dict<K, V>::set(K key, V val) {
342
33
  int pos = position_of_key(key);
343
33
  if (pos == -1) {  // new pair
344
33
    reserve(len_ + 1);
345
33
    keys_->items_[len_] = key;
346
33
    values_->items_[len_] = val;
347
348
33
    entry_->items_[len_] = 0;  // new special value
349
350
33
    ++len_;
351
33
  } else {
352
0
    values_->items_[pos] = val;
353
0
  }
354
33
}
_ZN4DictIP3StrPN4args7_ActionEE3setES1_S4_
Line
Count
Source
341
30
void Dict<K, V>::set(K key, V val) {
342
30
  int pos = position_of_key(key);
343
30
  if (pos == -1) {  // new pair
344
30
    reserve(len_ + 1);
345
30
    keys_->items_[len_] = key;
346
30
    values_->items_[len_] = val;
347
348
30
    entry_->items_[len_] = 0;  // new special value
349
350
30
    ++len_;
351
30
  } else {
352
0
    values_->items_[pos] = val;
353
0
  }
354
30
}
355
356
template <class K, class V>
357
2
void Dict<K, V>::update(List<Tuple2<K, V>*>* kvs) {
358
6
  for (ListIter<Tuple2<K, V>*> it(kvs); !it.Done(); it.Next()) {
359
4
    set(it.Value()->at0(), it.Value()->at1());
360
4
  }
361
2
}
362
363
template <typename K, typename V>
364
45
inline int len(const Dict<K, V>* d) {
365
45
  return d->len_;
366
45
}
_Z3lenIP3StrS1_EiPK4DictIT_T0_E
Line
Count
Source
364
13
inline int len(const Dict<K, V>* d) {
365
13
  return d->len_;
366
13
}
_Z3lenIP3StriEiPK4DictIT_T0_E
Line
Count
Source
364
19
inline int len(const Dict<K, V>* d) {
365
19
  return d->len_;
366
19
}
_Z3lenIiP3StrEiPK4DictIT_T0_E
Line
Count
Source
364
1
inline int len(const Dict<K, V>* d) {
365
1
  return d->len_;
366
1
}
_Z3lenIiiEiPK4DictIT_T0_E
Line
Count
Source
364
12
inline int len(const Dict<K, V>* d) {
365
12
  return d->len_;
366
12
}
Unexecuted instantiation: _Z3lenIP3StrPN4args7_ActionEEiPK4DictIT_T0_E
367
368
template <class K, class V>
369
class DictIter {
370
 public:
371
11
  explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) {
372
11
  }
_ZN8DictIterIP3StriEC2EP4DictIS1_iE
Line
Count
Source
371
9
  explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) {
372
9
  }
_ZN8DictIterIP3StrS1_EC2EP4DictIS1_S1_E
Line
Count
Source
371
2
  explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) {
372
2
  }
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEEC2EP4DictIS1_S4_E
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7HayNodeEEC2EP4DictIS1_S4_E
373
17
  void Next() {
374
17
    pos_ = ValidPosAfter(pos_ + 1);
375
17
  }
_ZN8DictIterIP3StriE4NextEv
Line
Count
Source
373
17
  void Next() {
374
17
    pos_ = ValidPosAfter(pos_ + 1);
375
17
  }
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E4NextEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE4NextEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7HayNodeEE4NextEv
376
28
  bool Done() {
377
28
    return pos_ == -1;
378
28
  }
_ZN8DictIterIP3StriE4DoneEv
Line
Count
Source
376
26
  bool Done() {
377
26
    return pos_ == -1;
378
26
  }
_ZN8DictIterIP3StrS1_E4DoneEv
Line
Count
Source
376
2
  bool Done() {
377
2
    return pos_ == -1;
378
2
  }
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE4DoneEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7HayNodeEE4DoneEv
379
17
  K Key() {
380
17
    return D_->keys_->items_[pos_];
381
17
  }
_ZN8DictIterIP3StriE3KeyEv
Line
Count
Source
379
17
  K Key() {
380
17
    return D_->keys_->items_[pos_];
381
17
  }
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E3KeyEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE3KeyEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7HayNodeEE3KeyEv
382
10
  V Value() {
383
10
    return D_->values_->items_[pos_];
384
10
  }
_ZN8DictIterIP3StriE5ValueEv
Line
Count
Source
382
10
  V Value() {
383
10
    return D_->values_->items_[pos_];
384
10
  }
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E5ValueEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE5ValueEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7HayNodeEE5ValueEv
385
386
 private:
387
28
  int ValidPosAfter(int pos) {
388
    // Returns the position of a valid entry at or after index i_.  Or -1 if
389
    // there isn't one.  Advances i_ too.
390
32
    while (true) {
391
32
      if (pos >= D_->capacity_) {
392
2
        return -1;
393
2
      }
394
30
      int index = D_->entry_->items_[pos];
395
30
      if (index == kDeletedEntry) {
396
4
        ++pos;
397
4
        continue;  // increment again
398
4
      }
399
26
      if (index == kEmptyEntry) {
400
9
        return -1;
401
9
      }
402
17
      break;
403
26
    }
404
17
    return pos;
405
28
  }
_ZN8DictIterIP3StriE13ValidPosAfterEi
Line
Count
Source
387
26
  int ValidPosAfter(int pos) {
388
    // Returns the position of a valid entry at or after index i_.  Or -1 if
389
    // there isn't one.  Advances i_ too.
390
28
    while (true) {
391
28
      if (pos >= D_->capacity_) {
392
2
        return -1;
393
2
      }
394
26
      int index = D_->entry_->items_[pos];
395
26
      if (index == kDeletedEntry) {
396
2
        ++pos;
397
2
        continue;  // increment again
398
2
      }
399
24
      if (index == kEmptyEntry) {
400
7
        return -1;
401
7
      }
402
17
      break;
403
24
    }
404
17
    return pos;
405
26
  }
_ZN8DictIterIP3StrS1_E13ValidPosAfterEi
Line
Count
Source
387
2
  int ValidPosAfter(int pos) {
388
    // Returns the position of a valid entry at or after index i_.  Or -1 if
389
    // there isn't one.  Advances i_ too.
390
4
    while (true) {
391
4
      if (pos >= D_->capacity_) {
392
0
        return -1;
393
0
      }
394
4
      int index = D_->entry_->items_[pos];
395
4
      if (index == kDeletedEntry) {
396
2
        ++pos;
397
2
        continue;  // increment again
398
2
      }
399
2
      if (index == kEmptyEntry) {
400
2
        return -1;
401
2
      }
402
0
      break;
403
2
    }
404
0
    return pos;
405
2
  }
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7value_tEE13ValidPosAfterEi
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl7HayNodeEE13ValidPosAfterEi
406
407
  Dict<K, V>* D_;
408
  int pos_;
409
};
410
411
// dict(l) converts a list of (k, v) tuples into a dict
412
template <typename K, typename V>
413
2
Dict<K, V>* dict(List<Tuple2<K, V>*>* l) {
414
2
  auto ret = Alloc<Dict<K, V>>();
415
2
  ret->reserve(len(l));
416
6
  for (ListIter<Tuple2<K, V>*> it(l); !it.Done(); it.Next()) {
417
4
    ret->set(it.Value()->at0(), it.Value()->at1());
418
4
  }
419
2
  return ret;
420
2
}
421
422
#endif  // MYCPP_GC_DICT_H