cpp

Coverage Report

Created: 2022-11-10 11:34

/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
6
// Non-negative entries in entry_ are array indices into keys_ and values_.
7
// There are two special negative entries.
8
9
// index that means this Dict item was deleted (a tombstone).
10
const int kDeletedEntry = -1;
11
12
// index that means this Dict entry is free.  Because we have Dict[int, int],
13
// we can't use a sentinel entry in keys_.  It has to be a sentinel entry in
14
// entry_.
15
const int kEmptyEntry = -2;
16
17
// Helper for keys() and values()
18
template <typename T>
19
7
List<T>* ListFromDictSlab(Slab<int>* index, Slab<T>* slab, int n) {
20
  // TODO: Reserve the right amount of space
21
7
  List<T>* result = nullptr;
22
7
  StackRoots _roots({&index, &slab, &result});
23
24
7
  result = Alloc<List<T>>();
25
26
23
  for (int i = 0; i < n; ++i) {
27
23
    int special = index->items_[i];
28
23
    if (special == kDeletedEntry) {
29
0
      continue;
30
0
    }
31
23
    if (special == kEmptyEntry) {
32
7
      break;
33
7
    }
34
16
    result->append(slab->items_[i]);
35
16
  }
36
7
  return result;
37
7
}
_Z16ListFromDictSlabIP3StrEP4ListIT_EP4SlabIiEPS6_IS3_Ei
Line
Count
Source
19
6
List<T>* ListFromDictSlab(Slab<int>* index, Slab<T>* slab, int n) {
20
  // TODO: Reserve the right amount of space
21
6
  List<T>* result = nullptr;
22
6
  StackRoots _roots({&index, &slab, &result});
23
24
6
  result = Alloc<List<T>>();
25
26
19
  for (int i = 0; i < n; ++i) {
27
19
    int special = index->items_[i];
28
19
    if (special == kDeletedEntry) {
29
0
      continue;
30
0
    }
31
19
    if (special == kEmptyEntry) {
32
6
      break;
33
6
    }
34
13
    result->append(slab->items_[i]);
35
13
  }
36
6
  return result;
37
6
}
_Z16ListFromDictSlabIiEP4ListIT_EP4SlabIiEPS4_IS1_Ei
Line
Count
Source
19
1
List<T>* ListFromDictSlab(Slab<int>* index, Slab<T>* slab, int n) {
20
  // TODO: Reserve the right amount of space
21
1
  List<T>* result = nullptr;
22
1
  StackRoots _roots({&index, &slab, &result});
23
24
1
  result = Alloc<List<T>>();
25
26
4
  for (int i = 0; i < n; ++i) {
27
4
    int special = index->items_[i];
28
4
    if (special == kDeletedEntry) {
29
0
      continue;
30
0
    }
31
4
    if (special == kEmptyEntry) {
32
1
      break;
33
1
    }
34
3
    result->append(slab->items_[i]);
35
3
  }
36
1
  return result;
37
1
}
38
39
// Type that is layout-compatible with List to avoid invalid-offsetof warnings.
40
// Unit tests assert that they have the same layout.
41
class _DummyDict {
42
 public:
43
  OBJ_HEADER()
44
  int len_;
45
  int capacity_;
46
  void* entry_;
47
  void* keys_;
48
  void* values_;
49
};
50
51
// A dict has 3 pointers the GC needs to follow.
52
16
constexpr uint16_t maskof_Dict() {
53
16
  return maskbit(offsetof(_DummyDict, entry_)) |
54
16
         maskbit(offsetof(_DummyDict, keys_)) |
55
16
         maskbit(offsetof(_DummyDict, values_));
56
16
}
57
58
template <class K, class V>
59
class Dict : public Obj {
60
 public:
61
16
  Dict() : Obj(Tag::FixedSize, maskof_Dict(), sizeof(Dict)) {
62
16
    assert(len_ == 0);
63
0
    assert(capacity_ == 0);
64
0
    assert(entry_ == nullptr);
65
0
    assert(keys_ == nullptr);
66
0
    assert(values_ == nullptr);
67
16
  }
_ZN4DictIiP3StrEC2Ev
Line
Count
Source
61
3
  Dict() : Obj(Tag::FixedSize, maskof_Dict(), sizeof(Dict)) {
62
3
    assert(len_ == 0);
63
0
    assert(capacity_ == 0);
64
0
    assert(entry_ == nullptr);
65
0
    assert(keys_ == nullptr);
66
0
    assert(values_ == nullptr);
67
3
  }
_ZN4DictIP3StriEC2Ev
Line
Count
Source
61
10
  Dict() : Obj(Tag::FixedSize, maskof_Dict(), sizeof(Dict)) {
62
10
    assert(len_ == 0);
63
0
    assert(capacity_ == 0);
64
0
    assert(entry_ == nullptr);
65
0
    assert(keys_ == nullptr);
66
0
    assert(values_ == nullptr);
67
10
  }
_ZN4DictIP3StrS1_EC2Ev
Line
Count
Source
61
2
  Dict() : Obj(Tag::FixedSize, maskof_Dict(), sizeof(Dict)) {
62
2
    assert(len_ == 0);
63
0
    assert(capacity_ == 0);
64
0
    assert(entry_ == nullptr);
65
0
    assert(keys_ == nullptr);
66
0
    assert(values_ == nullptr);
67
2
  }
_ZN4DictIiiEC2Ev
Line
Count
Source
61
1
  Dict() : Obj(Tag::FixedSize, maskof_Dict(), sizeof(Dict)) {
62
1
    assert(len_ == 0);
63
0
    assert(capacity_ == 0);
64
0
    assert(entry_ == nullptr);
65
0
    assert(keys_ == nullptr);
66
0
    assert(values_ == nullptr);
67
1
  }
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEEC2Ev
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEEC2Ev
68
69
  Dict(std::initializer_list<K> keys, std::initializer_list<V> values)
70
      : Obj(Tag::FixedSize, maskof_Dict(), sizeof(Dict)) {
71
    assert(len_ == 0);
72
    assert(capacity_ == 0);
73
    assert(entry_ == nullptr);
74
    assert(keys_ == nullptr);
75
    assert(values_ == nullptr);
76
  }
77
78
  // This relies on the fact that containers of 4-byte ints are reduced by 2
79
  // items, which is greater than (or equal to) the reduction of any other
80
  // type
81
  static const int kCapacityAdjust = kSlabHeaderSize / sizeof(int);
82
  static_assert(kSlabHeaderSize % sizeof(int) == 0,
83
                "Slab header size should be multiple of key size");
84
85
  void reserve(int n);
86
87
  // d[key] in Python: raises KeyError if not found
88
  V index_(K key);
89
90
  // Get a key.
91
  // Returns nullptr if not found (Can't use this for non-pointer types?)
92
  V get(K key);
93
94
  // Get a key, but return a default if not found.
95
  // expr_parse.py uses this with OTHER_BALANCE
96
  V get(K key, V default_val);
97
98
  // Implements d[k] = v.  May resize the dictionary.
99
  //
100
  // TODO: Need to specialize this for StackRoots!  Gah!
101
  void set(K key, V val);
102
103
  void remove(K key);
104
105
  List<K>* keys();
106
107
  // For AssocArray transformations
108
  List<V>* values();
109
110
  void clear();
111
112
  // Returns the position in the array.  Used by dict_contains(), index(),
113
  // get(), and set().
114
  //
115
  // For now this does a linear search.
116
  // TODO:
117
  // - hash functions, and linear probing.
118
  // - resizing based on load factor
119
  //   - which requires rehashing (re-insert all items)
120
  // - Special case to intern Str* when it's hashed?  How?
121
  //   - Should we have wrappers like:
122
  //   - V GetAndIntern<V>(D, &string_key)
123
  //   - SetAndIntern<V>(D, &string_key, value)
124
  //   This will enable duplicate copies of the string to be garbage collected
125
  int position_of_key(K key);
126
127
  // int index_size_;  // size of index (sparse)
128
  int len_;       // number of entries (keys and values, almost dense)
129
  int capacity_;  // number of entries before resizing
130
131
  // These 3 slabs are resized at the same time.
132
  Slab<int>* entry_;  // NOW: kEmptyEntry, kDeletedEntry, or 0.
133
                      // LATER: indices which are themselves indexed by // hash
134
                      // value % capacity_
135
  Slab<K>* keys_;     // Dict<int, V>
136
  Slab<V>* values_;   // Dict<K, int>
137
138
  DISALLOW_COPY_AND_ASSIGN(Dict)
139
};
140
141
template <typename K, typename V>
142
5
inline bool dict_contains(Dict<K, V>* haystack, K needle) {
143
5
  return haystack->position_of_key(needle) != -1;
144
5
}
_Z13dict_containsIiP3StrEbP4DictIT_T0_ES3_
Line
Count
Source
142
2
inline bool dict_contains(Dict<K, V>* haystack, K needle) {
143
2
  return haystack->position_of_key(needle) != -1;
144
2
}
_Z13dict_containsIP3StriEbP4DictIT_T0_ES3_
Line
Count
Source
142
3
inline bool dict_contains(Dict<K, V>* haystack, K needle) {
143
3
  return haystack->position_of_key(needle) != -1;
144
3
}
145
146
template <typename K, typename V>
147
9
Dict<K, V>* NewDict() {
148
9
  auto self = Alloc<Dict<K, V>>();
149
9
  return self;
150
9
}
_Z7NewDictIiiEP4DictIT_T0_Ev
Line
Count
Source
147
1
Dict<K, V>* NewDict() {
148
1
  auto self = Alloc<Dict<K, V>>();
149
1
  return self;
150
1
}
_Z7NewDictIP3StrS1_EP4DictIT_T0_Ev
Line
Count
Source
147
2
Dict<K, V>* NewDict() {
148
2
  auto self = Alloc<Dict<K, V>>();
149
2
  return self;
150
2
}
_Z7NewDictIP3StriEP4DictIT_T0_Ev
Line
Count
Source
147
4
Dict<K, V>* NewDict() {
148
4
  auto self = Alloc<Dict<K, V>>();
149
4
  return self;
150
4
}
_Z7NewDictIiP3StrEP4DictIT_T0_Ev
Line
Count
Source
147
2
Dict<K, V>* NewDict() {
148
2
  auto self = Alloc<Dict<K, V>>();
149
2
  return self;
150
2
}
Unexecuted instantiation: _Z7NewDictIP3StrPN12runtime_asdl8hay_nodeEEP4DictIT_T0_Ev
Unexecuted instantiation: _Z7NewDictIP3StrPN4args7_ActionEEP4DictIT_T0_Ev
Unexecuted instantiation: _Z7NewDictIP3StrPN12runtime_asdl7value_tEEP4DictIT_T0_Ev
151
152
template <typename K, typename V>
153
Dict<K, V>* NewDict(std::initializer_list<K> keys,
154
0
                    std::initializer_list<V> values) {
155
0
  assert(keys.size() == values.size());
156
0
  auto self = Alloc<Dict<K, V>>();
157
0
  StackRoots _roots({&self});
158
159
0
  auto v = values.begin();  // This simulates a "zip" loop
160
0
  for (auto key : keys) {
161
0
    self->set(key, *v);
162
0
    ++v;
163
0
  }
164
165
0
  return self;
166
0
}
167
168
template <typename K, typename V>
169
79
void Dict<K, V>::reserve(int n) {
170
79
  auto self = this;
171
79
  Slab<int>* new_i = nullptr;
172
79
  Slab<K>* new_k = nullptr;
173
79
  Slab<V>* new_v = nullptr;
174
79
  StackRoots _roots({&self, &new_i, &new_k, &new_v});
175
176
  // log("--- reserve %d", capacity_);
177
  //
178
79
  if (self->capacity_ < n) {  // TODO: use load factor, not exact fit
179
    // calculate the number of keys and values we should have
180
21
    self->capacity_ = RoundUp(n + kCapacityAdjust) - kCapacityAdjust;
181
182
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
183
    // load factor?
184
21
    int index_len = self->capacity_;
185
21
    new_i = NewSlab<int>(index_len);
186
187
    // For the linear search to work
188
267
    for (int i = 0; i < index_len; ++i) {
189
246
      new_i->items_[i] = kEmptyEntry;
190
246
    }
191
192
    // These are DENSE.
193
21
    new_k = NewSlab<K>(self->capacity_);
194
21
    new_v = NewSlab<V>(self->capacity_);
195
196
21
    if (self->keys_ != nullptr) {
197
      // Right now the index is the same size as keys and values.
198
5
      memcpy(new_i->items_, self->entry_->items_, self->len_ * sizeof(int));
199
200
5
      memcpy(new_k->items_, self->keys_->items_, self->len_ * sizeof(K));
201
5
      memcpy(new_v->items_, self->values_->items_, self->len_ * sizeof(V));
202
5
    }
203
204
21
    self->entry_ = new_i;
205
21
    self->keys_ = new_k;
206
21
    self->values_ = new_v;
207
21
  }
208
79
}
_ZN4DictIiP3StrE7reserveEi
Line
Count
Source
169
3
void Dict<K, V>::reserve(int n) {
170
3
  auto self = this;
171
3
  Slab<int>* new_i = nullptr;
172
3
  Slab<K>* new_k = nullptr;
173
3
  Slab<V>* new_v = nullptr;
174
3
  StackRoots _roots({&self, &new_i, &new_k, &new_v});
175
176
  // log("--- reserve %d", capacity_);
177
  //
178
3
  if (self->capacity_ < n) {  // TODO: use load factor, not exact fit
179
    // calculate the number of keys and values we should have
180
3
    self->capacity_ = RoundUp(n + kCapacityAdjust) - kCapacityAdjust;
181
182
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
183
    // load factor?
184
3
    int index_len = self->capacity_;
185
3
    new_i = NewSlab<int>(index_len);
186
187
    // For the linear search to work
188
21
    for (int i = 0; i < index_len; ++i) {
189
18
      new_i->items_[i] = kEmptyEntry;
190
18
    }
191
192
    // These are DENSE.
193
3
    new_k = NewSlab<K>(self->capacity_);
194
3
    new_v = NewSlab<V>(self->capacity_);
195
196
3
    if (self->keys_ != nullptr) {
197
      // Right now the index is the same size as keys and values.
198
0
      memcpy(new_i->items_, self->entry_->items_, self->len_ * sizeof(int));
199
200
0
      memcpy(new_k->items_, self->keys_->items_, self->len_ * sizeof(K));
201
0
      memcpy(new_v->items_, self->values_->items_, self->len_ * sizeof(V));
202
0
    }
203
204
3
    self->entry_ = new_i;
205
3
    self->keys_ = new_k;
206
3
    self->values_ = new_v;
207
3
  }
208
3
}
_ZN4DictIP3StriE7reserveEi
Line
Count
Source
169
58
void Dict<K, V>::reserve(int n) {
170
58
  auto self = this;
171
58
  Slab<int>* new_i = nullptr;
172
58
  Slab<K>* new_k = nullptr;
173
58
  Slab<V>* new_v = nullptr;
174
58
  StackRoots _roots({&self, &new_i, &new_k, &new_v});
175
176
  // log("--- reserve %d", capacity_);
177
  //
178
58
  if (self->capacity_ < n) {  // TODO: use load factor, not exact fit
179
    // calculate the number of keys and values we should have
180
13
    self->capacity_ = RoundUp(n + kCapacityAdjust) - kCapacityAdjust;
181
182
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
183
    // load factor?
184
13
    int index_len = self->capacity_;
185
13
    new_i = NewSlab<int>(index_len);
186
187
    // For the linear search to work
188
179
    for (int i = 0; i < index_len; ++i) {
189
166
      new_i->items_[i] = kEmptyEntry;
190
166
    }
191
192
    // These are DENSE.
193
13
    new_k = NewSlab<K>(self->capacity_);
194
13
    new_v = NewSlab<V>(self->capacity_);
195
196
13
    if (self->keys_ != nullptr) {
197
      // Right now the index is the same size as keys and values.
198
3
      memcpy(new_i->items_, self->entry_->items_, self->len_ * sizeof(int));
199
200
3
      memcpy(new_k->items_, self->keys_->items_, self->len_ * sizeof(K));
201
3
      memcpy(new_v->items_, self->values_->items_, self->len_ * sizeof(V));
202
3
    }
203
204
13
    self->entry_ = new_i;
205
13
    self->keys_ = new_k;
206
13
    self->values_ = new_v;
207
13
  }
208
58
}
_ZN4DictIP3StrS1_E7reserveEi
Line
Count
Source
169
2
void Dict<K, V>::reserve(int n) {
170
2
  auto self = this;
171
2
  Slab<int>* new_i = nullptr;
172
2
  Slab<K>* new_k = nullptr;
173
2
  Slab<V>* new_v = nullptr;
174
2
  StackRoots _roots({&self, &new_i, &new_k, &new_v});
175
176
  // log("--- reserve %d", capacity_);
177
  //
178
2
  if (self->capacity_ < n) {  // TODO: use load factor, not exact fit
179
    // calculate the number of keys and values we should have
180
2
    self->capacity_ = RoundUp(n + kCapacityAdjust) - kCapacityAdjust;
181
182
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
183
    // load factor?
184
2
    int index_len = self->capacity_;
185
2
    new_i = NewSlab<int>(index_len);
186
187
    // For the linear search to work
188
14
    for (int i = 0; i < index_len; ++i) {
189
12
      new_i->items_[i] = kEmptyEntry;
190
12
    }
191
192
    // These are DENSE.
193
2
    new_k = NewSlab<K>(self->capacity_);
194
2
    new_v = NewSlab<V>(self->capacity_);
195
196
2
    if (self->keys_ != nullptr) {
197
      // Right now the index is the same size as keys and values.
198
0
      memcpy(new_i->items_, self->entry_->items_, self->len_ * sizeof(int));
199
200
0
      memcpy(new_k->items_, self->keys_->items_, self->len_ * sizeof(K));
201
0
      memcpy(new_v->items_, self->values_->items_, self->len_ * sizeof(V));
202
0
    }
203
204
2
    self->entry_ = new_i;
205
2
    self->keys_ = new_k;
206
2
    self->values_ = new_v;
207
2
  }
208
2
}
_ZN4DictIiiE7reserveEi
Line
Count
Source
169
16
void Dict<K, V>::reserve(int n) {
170
16
  auto self = this;
171
16
  Slab<int>* new_i = nullptr;
172
16
  Slab<K>* new_k = nullptr;
173
16
  Slab<V>* new_v = nullptr;
174
16
  StackRoots _roots({&self, &new_i, &new_k, &new_v});
175
176
  // log("--- reserve %d", capacity_);
177
  //
178
16
  if (self->capacity_ < n) {  // TODO: use load factor, not exact fit
179
    // calculate the number of keys and values we should have
180
3
    self->capacity_ = RoundUp(n + kCapacityAdjust) - kCapacityAdjust;
181
182
    // TODO: This is SPARSE.  How to compute a size that ensures a decent
183
    // load factor?
184
3
    int index_len = self->capacity_;
185
3
    new_i = NewSlab<int>(index_len);
186
187
    // For the linear search to work
188
53
    for (int i = 0; i < index_len; ++i) {
189
50
      new_i->items_[i] = kEmptyEntry;
190
50
    }
191
192
    // These are DENSE.
193
3
    new_k = NewSlab<K>(self->capacity_);
194
3
    new_v = NewSlab<V>(self->capacity_);
195
196
3
    if (self->keys_ != nullptr) {
197
      // Right now the index is the same size as keys and values.
198
2
      memcpy(new_i->items_, self->entry_->items_, self->len_ * sizeof(int));
199
200
2
      memcpy(new_k->items_, self->keys_->items_, self->len_ * sizeof(K));
201
2
      memcpy(new_v->items_, self->values_->items_, self->len_ * sizeof(V));
202
2
    }
203
204
3
    self->entry_ = new_i;
205
3
    self->keys_ = new_k;
206
3
    self->values_ = new_v;
207
3
  }
208
16
}
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEE7reserveEi
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE7reserveEi
209
210
// d[key] in Python: raises KeyError if not found
211
template <typename K, typename V>
212
28
V Dict<K, V>::index_(K key) {
213
28
  int pos = position_of_key(key);
214
28
  if (pos == -1) {
215
0
    throw Alloc<KeyError>();
216
28
  } else {
217
28
    return values_->items_[pos];
218
28
  }
219
28
}
_ZN4DictIiP3StrE6index_Ei
Line
Count
Source
212
2
V Dict<K, V>::index_(K key) {
213
2
  int pos = position_of_key(key);
214
2
  if (pos == -1) {
215
0
    throw Alloc<KeyError>();
216
2
  } else {
217
2
    return values_->items_[pos];
218
2
  }
219
2
}
_ZN4DictIP3StriE6index_ES1_
Line
Count
Source
212
8
V Dict<K, V>::index_(K key) {
213
8
  int pos = position_of_key(key);
214
8
  if (pos == -1) {
215
0
    throw Alloc<KeyError>();
216
8
  } else {
217
8
    return values_->items_[pos];
218
8
  }
219
8
}
_ZN4DictIiiE6index_Ei
Line
Count
Source
212
17
V Dict<K, V>::index_(K key) {
213
17
  int pos = position_of_key(key);
214
17
  if (pos == -1) {
215
0
    throw Alloc<KeyError>();
216
17
  } else {
217
17
    return values_->items_[pos];
218
17
  }
219
17
}
_ZN4DictIP3StrS1_E6index_ES1_
Line
Count
Source
212
1
V Dict<K, V>::index_(K key) {
213
1
  int pos = position_of_key(key);
214
1
  if (pos == -1) {
215
0
    throw Alloc<KeyError>();
216
1
  } else {
217
1
    return values_->items_[pos];
218
1
  }
219
1
}
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEE6index_ES1_
220
221
// Get a key.
222
// Returns nullptr if not found (Can't use this for non-pointer types?)
223
template <typename K, typename V>
224
2
V Dict<K, V>::get(K key) {
225
2
  int pos = position_of_key(key);
226
2
  if (pos == -1) {
227
1
    return nullptr;
228
1
  } else {
229
1
    return values_->items_[pos];
230
1
  }
231
2
}
232
233
// Get a key, but return a default if not found.
234
// expr_parse.py uses this with OTHER_BALANCE
235
template <typename K, typename V>
236
0
V Dict<K, V>::get(K key, V default_val) {
237
0
  int pos = position_of_key(key);
238
0
  if (pos == -1) {
239
0
    return default_val;
240
0
  } else {
241
0
    return values_->items_[pos];
242
0
  }
243
0
}
Unexecuted instantiation: _ZN4DictIiP3StrE3getEiS1_
Unexecuted instantiation: _ZN4DictIP3StriE3getES1_i
244
245
template <typename K, typename V>
246
5
List<K>* Dict<K, V>::keys() {
247
5
  return ListFromDictSlab<K>(entry_, keys_, capacity_);
248
5
}
_ZN4DictIP3StriE4keysEv
Line
Count
Source
246
4
List<K>* Dict<K, V>::keys() {
247
4
  return ListFromDictSlab<K>(entry_, keys_, capacity_);
248
4
}
_ZN4DictIP3StrS1_E4keysEv
Line
Count
Source
246
1
List<K>* Dict<K, V>::keys() {
247
1
  return ListFromDictSlab<K>(entry_, keys_, capacity_);
248
1
}
249
250
// For AssocArray transformations
251
template <typename K, typename V>
252
2
List<V>* Dict<K, V>::values() {
253
2
  return ListFromDictSlab<V>(entry_, values_, capacity_);
254
2
}
_ZN4DictIP3StriE6valuesEv
Line
Count
Source
252
1
List<V>* Dict<K, V>::values() {
253
1
  return ListFromDictSlab<V>(entry_, values_, capacity_);
254
1
}
_ZN4DictIP3StrS1_E6valuesEv
Line
Count
Source
252
1
List<V>* Dict<K, V>::values() {
253
1
  return ListFromDictSlab<V>(entry_, values_, capacity_);
254
1
}
255
256
template <typename K, typename V>
257
1
void Dict<K, V>::clear() {
258
  // Maintain invariant
259
7
  for (int i = 0; i < capacity_; ++i) {
260
6
    entry_->items_[i] = kEmptyEntry;
261
6
  }
262
263
1
  memset(keys_->items_, 0, len_ * sizeof(K));    // zero for GC scan
264
1
  memset(values_->items_, 0, len_ * sizeof(V));  // zero for GC scan
265
1
  len_ = 0;
266
1
}
267
268
// Returns the position in the array.  Used by dict_contains(), index(),
269
// get(), and set().
270
//
271
// For now this does a linear search.
272
// TODO:
273
// - hash functions, and linear probing.
274
// - resizing based on load factor
275
//   - which requires rehashing (re-insert all items)
276
// - Special case to intern Str* when it's hashed?  How?
277
//   - Should we have wrappers like:
278
//   - V GetAndIntern<V>(D, &string_key)
279
//   - SetAndIntern<V>(D, &string_key, value)
280
//   This will enable duplicate copies of the string to be garbage collected
281
template <typename K, typename V>
282
119
int Dict<K, V>::position_of_key(K key) {
283
119
  auto self = this;
284
119
  StackRoots _roots({&self});
285
286
1.06k
  for (int i = 0; i < self->capacity_; ++i) {
287
1.04k
    int special = self->entry_->items_[i];  // NOT an index now
288
1.04k
    if (special == kDeletedEntry) {
289
3
      continue;  // keep searching
290
3
    }
291
1.04k
    if (special == kEmptyEntry) {
292
62
      return -1;  // not found
293
62
    }
294
979
    if (keys_equal(self->keys_->items_[i], key)) {
295
36
      return i;
296
36
    }
297
979
  }
298
21
  return -1;  // table is completely full?  Does this happen?
299
119
}
_ZN4DictIiP3StrE15position_of_keyEi
Line
Count
Source
282
9
int Dict<K, V>::position_of_key(K key) {
283
9
  auto self = this;
284
9
  StackRoots _roots({&self});
285
286
11
  for (int i = 0; i < self->capacity_; ++i) {
287
8
    int special = self->entry_->items_[i];  // NOT an index now
288
8
    if (special == kDeletedEntry) {
289
0
      continue;  // keep searching
290
0
    }
291
8
    if (special == kEmptyEntry) {
292
2
      return -1;  // not found
293
2
    }
294
6
    if (keys_equal(self->keys_->items_[i], key)) {
295
4
      return i;
296
4
    }
297
6
  }
298
3
  return -1;  // table is completely full?  Does this happen?
299
9
}
_ZN4DictIP3StriE15position_of_keyES1_
Line
Count
Source
282
72
int Dict<K, V>::position_of_key(K key) {
283
72
  auto self = this;
284
72
  StackRoots _roots({&self});
285
286
881
  for (int i = 0; i < self->capacity_; ++i) {
287
868
    int special = self->entry_->items_[i];  // NOT an index now
288
868
    if (special == kDeletedEntry) {
289
3
      continue;  // keep searching
290
3
    }
291
865
    if (special == kEmptyEntry) {
292
47
      return -1;  // not found
293
47
    }
294
818
    if (keys_equal(self->keys_->items_[i], key)) {
295
12
      return i;
296
12
    }
297
818
  }
298
13
  return -1;  // table is completely full?  Does this happen?
299
72
}
_ZN4DictIP3StrS1_E15position_of_keyES1_
Line
Count
Source
282
4
int Dict<K, V>::position_of_key(K key) {
283
4
  auto self = this;
284
4
  StackRoots _roots({&self});
285
286
4
  for (int i = 0; i < self->capacity_; ++i) {
287
2
    int special = self->entry_->items_[i];  // NOT an index now
288
2
    if (special == kDeletedEntry) {
289
0
      continue;  // keep searching
290
0
    }
291
2
    if (special == kEmptyEntry) {
292
0
      return -1;  // not found
293
0
    }
294
2
    if (keys_equal(self->keys_->items_[i], key)) {
295
2
      return i;
296
2
    }
297
2
  }
298
2
  return -1;  // table is completely full?  Does this happen?
299
4
}
_ZN4DictIiiE15position_of_keyEi
Line
Count
Source
282
34
int Dict<K, V>::position_of_key(K key) {
283
34
  auto self = this;
284
34
  StackRoots _roots({&self});
285
286
169
  for (int i = 0; i < self->capacity_; ++i) {
287
166
    int special = self->entry_->items_[i];  // NOT an index now
288
166
    if (special == kDeletedEntry) {
289
0
      continue;  // keep searching
290
0
    }
291
166
    if (special == kEmptyEntry) {
292
13
      return -1;  // not found
293
13
    }
294
153
    if (keys_equal(self->keys_->items_[i], key)) {
295
18
      return i;
296
18
    }
297
153
  }
298
3
  return -1;  // table is completely full?  Does this happen?
299
34
}
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEE15position_of_keyES1_
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE15position_of_keyES1_
300
301
// Four overloads for dict_set()!  TODO: Is there a nicer way to do this?
302
// e.g. Dict<int, int>
303
template <typename K, typename V>
304
16
void dict_set(Dict<K, V>* self, K key, V val) {
305
16
  StackRoots _roots({&self});
306
307
16
  self->reserve(self->len_ + 1);
308
16
  self->keys_->items_[self->len_] = key;
309
16
  self->values_->items_[self->len_] = val;
310
311
16
  self->entry_->items_[self->len_] = 0;  // new special value
312
313
16
  ++self->len_;
314
16
}
315
316
// e.g. Dict<Str*, int>
317
template <typename K, typename V>
318
58
void dict_set(Dict<K*, V>* self, K* key, V val) {
319
58
  StackRoots _roots({&self, &key});
320
321
58
  self->reserve(self->len_ + 1);
322
58
  self->keys_->items_[self->len_] = key;
323
58
  self->values_->items_[self->len_] = val;
324
325
58
  self->entry_->items_[self->len_] = 0;  // new special value
326
327
58
  ++self->len_;
328
58
}
329
330
// e.g. Dict<int, Str*>
331
template <typename K, typename V>
332
3
void dict_set(Dict<K, V*>* self, K key, V* val) {
333
3
  StackRoots _roots({&self, &val});
334
335
3
  self->reserve(self->len_ + 1);
336
3
  self->keys_->items_[self->len_] = key;
337
3
  self->values_->items_[self->len_] = val;
338
339
3
  self->entry_->items_[self->len_] = 0;  // new special value
340
341
3
  ++self->len_;
342
3
}
343
344
// e.g. Dict<Str*, Str*>
345
template <typename K, typename V>
346
2
void dict_set(Dict<K*, V*>* self, K* key, V* val) {
347
2
  StackRoots _roots({&self, &key, &val});
348
349
2
  self->reserve(self->len_ + 1);
350
2
  self->keys_->items_[self->len_] = key;
351
2
  self->values_->items_[self->len_] = val;
352
353
2
  self->entry_->items_[self->len_] = 0;  // new special value
354
355
2
  ++self->len_;
356
2
}
_Z8dict_setI3StrS0_EvP4DictIPT_PT0_ES3_S5_
Line
Count
Source
346
2
void dict_set(Dict<K*, V*>* self, K* key, V* val) {
347
2
  StackRoots _roots({&self, &key, &val});
348
349
2
  self->reserve(self->len_ + 1);
350
2
  self->keys_->items_[self->len_] = key;
351
2
  self->values_->items_[self->len_] = val;
352
353
2
  self->entry_->items_[self->len_] = 0;  // new special value
354
355
2
  ++self->len_;
356
2
}
Unexecuted instantiation: _Z8dict_setI3StrN12runtime_asdl7value_tEEvP4DictIPT_PT0_ES5_S7_
Unexecuted instantiation: _Z8dict_setI3StrN4args7_ActionEEvP4DictIPT_PT0_ES5_S7_
357
358
template <typename K, typename V>
359
81
void Dict<K, V>::set(K key, V val) {
360
81
  auto self = this;
361
81
  StackRoots _roots({&self});  // May not need this here?
362
363
81
  int pos = self->position_of_key(key);
364
81
  if (pos == -1) {             // new pair
365
79
    dict_set(self, key, val);  // ALLOCATES
366
79
  } else {
367
2
    self->values_->items_[pos] = val;
368
2
  }
369
81
}
_ZN4DictIiP3StrE3setEiS1_
Line
Count
Source
359
3
void Dict<K, V>::set(K key, V val) {
360
3
  auto self = this;
361
3
  StackRoots _roots({&self});  // May not need this here?
362
363
3
  int pos = self->position_of_key(key);
364
3
  if (pos == -1) {             // new pair
365
3
    dict_set(self, key, val);  // ALLOCATES
366
3
  } else {
367
0
    self->values_->items_[pos] = val;
368
0
  }
369
3
}
_ZN4DictIP3StriE3setES1_i
Line
Count
Source
359
59
void Dict<K, V>::set(K key, V val) {
360
59
  auto self = this;
361
59
  StackRoots _roots({&self});  // May not need this here?
362
363
59
  int pos = self->position_of_key(key);
364
59
  if (pos == -1) {             // new pair
365
58
    dict_set(self, key, val);  // ALLOCATES
366
58
  } else {
367
1
    self->values_->items_[pos] = val;
368
1
  }
369
59
}
_ZN4DictIP3StrS1_E3setES1_S1_
Line
Count
Source
359
2
void Dict<K, V>::set(K key, V val) {
360
2
  auto self = this;
361
2
  StackRoots _roots({&self});  // May not need this here?
362
363
2
  int pos = self->position_of_key(key);
364
2
  if (pos == -1) {             // new pair
365
2
    dict_set(self, key, val);  // ALLOCATES
366
2
  } else {
367
0
    self->values_->items_[pos] = val;
368
0
  }
369
2
}
_ZN4DictIiiE3setEii
Line
Count
Source
359
17
void Dict<K, V>::set(K key, V val) {
360
17
  auto self = this;
361
17
  StackRoots _roots({&self});  // May not need this here?
362
363
17
  int pos = self->position_of_key(key);
364
17
  if (pos == -1) {             // new pair
365
16
    dict_set(self, key, val);  // ALLOCATES
366
16
  } else {
367
1
    self->values_->items_[pos] = val;
368
1
  }
369
17
}
Unexecuted instantiation: _ZN4DictIP3StrPN12runtime_asdl7value_tEE3setES1_S4_
Unexecuted instantiation: _ZN4DictIP3StrPN4args7_ActionEE3setES1_S4_
370
371
template <typename K, typename V>
372
18
inline int len(const Dict<K, V>* d) {
373
18
  return d->len_;
374
18
}
_Z3lenIP3StriEiPK4DictIT_T0_E
Line
Count
Source
372
10
inline int len(const Dict<K, V>* d) {
373
10
  return d->len_;
374
10
}
_Z3lenIP3StrS1_EiPK4DictIT_T0_E
Line
Count
Source
372
4
inline int len(const Dict<K, V>* d) {
373
4
  return d->len_;
374
4
}
_Z3lenIiiEiPK4DictIT_T0_E
Line
Count
Source
372
4
inline int len(const Dict<K, V>* d) {
373
4
  return d->len_;
374
4
}
Unexecuted instantiation: _Z3lenIiP3StrEiPK4DictIT_T0_E
375
376
template <typename K, typename V>
377
3
void dict_remove(Dict<K, V>* haystack, K needle) {
378
3
  int pos = haystack->position_of_key(needle);
379
3
  if (pos == -1) {
380
0
    return;
381
0
  }
382
3
  haystack->entry_->items_[pos] = kDeletedEntry;
383
  // Zero out for GC.  These could be nullptr or 0
384
3
  haystack->keys_->items_[pos] = 0;
385
3
  haystack->values_->items_[pos] = 0;
386
3
  haystack->len_--;
387
3
}
_Z11dict_removeIP3StriEvP4DictIT_T0_ES3_
Line
Count
Source
377
2
void dict_remove(Dict<K, V>* haystack, K needle) {
378
2
  int pos = haystack->position_of_key(needle);
379
2
  if (pos == -1) {
380
0
    return;
381
0
  }
382
2
  haystack->entry_->items_[pos] = kDeletedEntry;
383
  // Zero out for GC.  These could be nullptr or 0
384
2
  haystack->keys_->items_[pos] = 0;
385
2
  haystack->values_->items_[pos] = 0;
386
2
  haystack->len_--;
387
2
}
_Z11dict_removeIP3StrS1_EvP4DictIT_T0_ES3_
Line
Count
Source
377
1
void dict_remove(Dict<K, V>* haystack, K needle) {
378
1
  int pos = haystack->position_of_key(needle);
379
1
  if (pos == -1) {
380
0
    return;
381
0
  }
382
1
  haystack->entry_->items_[pos] = kDeletedEntry;
383
  // Zero out for GC.  These could be nullptr or 0
384
1
  haystack->keys_->items_[pos] = 0;
385
1
  haystack->values_->items_[pos] = 0;
386
1
  haystack->len_--;
387
1
}
388
389
template <typename K, typename V>
390
2
void Dict<K, V>::remove(K key) {
391
2
  dict_remove(this, key);
392
2
}
_ZN4DictIP3StriE6removeES1_
Line
Count
Source
390
1
void Dict<K, V>::remove(K key) {
391
1
  dict_remove(this, key);
392
1
}
_ZN4DictIP3StrS1_E6removeES1_
Line
Count
Source
390
1
void Dict<K, V>::remove(K key) {
391
1
  dict_remove(this, key);
392
1
}
393
394
template <class K, class V>
395
class DictIter {
396
 public:
397
7
  explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) {
398
7
  }
_ZN8DictIterIP3StriEC2EP4DictIS1_iE
Line
Count
Source
397
6
  explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) {
398
6
  }
_ZN8DictIterIP3StrS1_EC2EP4DictIS1_S1_E
Line
Count
Source
397
1
  explicit DictIter(Dict<K, V>* D) : D_(D), pos_(ValidPosAfter(0)) {
398
1
  }
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEEC2EP4DictIS1_S4_E
399
13
  void Next() {
400
13
    pos_ = ValidPosAfter(pos_ + 1);
401
13
  }
_ZN8DictIterIP3StriE4NextEv
Line
Count
Source
399
13
  void Next() {
400
13
    pos_ = ValidPosAfter(pos_ + 1);
401
13
  }
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E4NextEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE4NextEv
402
20
  bool Done() {
403
20
    return pos_ == -1;
404
20
  }
_ZN8DictIterIP3StriE4DoneEv
Line
Count
Source
402
19
  bool Done() {
403
19
    return pos_ == -1;
404
19
  }
_ZN8DictIterIP3StrS1_E4DoneEv
Line
Count
Source
402
1
  bool Done() {
403
1
    return pos_ == -1;
404
1
  }
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE4DoneEv
405
13
  K Key() {
406
13
    return D_->keys_->items_[pos_];
407
13
  }
_ZN8DictIterIP3StriE3KeyEv
Line
Count
Source
405
13
  K Key() {
406
13
    return D_->keys_->items_[pos_];
407
13
  }
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E3KeyEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE3KeyEv
408
8
  V Value() {
409
8
    return D_->values_->items_[pos_];
410
8
  }
_ZN8DictIterIP3StriE5ValueEv
Line
Count
Source
408
8
  V Value() {
409
8
    return D_->values_->items_[pos_];
410
8
  }
Unexecuted instantiation: _ZN8DictIterIP3StrS1_E5ValueEv
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE5ValueEv
411
412
 private:
413
20
  int ValidPosAfter(int pos) {
414
    // Returns the position of a valid entry at or after index i_.  Or -1 if
415
    // there isn't one.  Advances i_ too.
416
22
    while (true) {
417
22
      if (pos >= D_->capacity_) {
418
0
        return -1;
419
0
      }
420
22
      int index = D_->entry_->items_[pos];
421
22
      if (index == kDeletedEntry) {
422
2
        ++pos;
423
2
        continue;  // increment again
424
2
      }
425
20
      if (index == kEmptyEntry) {
426
7
        return -1;
427
7
      }
428
13
      break;
429
20
    }
430
13
    return pos;
431
20
  }
_ZN8DictIterIP3StriE13ValidPosAfterEi
Line
Count
Source
413
19
  int ValidPosAfter(int pos) {
414
    // Returns the position of a valid entry at or after index i_.  Or -1 if
415
    // there isn't one.  Advances i_ too.
416
20
    while (true) {
417
20
      if (pos >= D_->capacity_) {
418
0
        return -1;
419
0
      }
420
20
      int index = D_->entry_->items_[pos];
421
20
      if (index == kDeletedEntry) {
422
1
        ++pos;
423
1
        continue;  // increment again
424
1
      }
425
19
      if (index == kEmptyEntry) {
426
6
        return -1;
427
6
      }
428
13
      break;
429
19
    }
430
13
    return pos;
431
19
  }
_ZN8DictIterIP3StrS1_E13ValidPosAfterEi
Line
Count
Source
413
1
  int ValidPosAfter(int pos) {
414
    // Returns the position of a valid entry at or after index i_.  Or -1 if
415
    // there isn't one.  Advances i_ too.
416
2
    while (true) {
417
2
      if (pos >= D_->capacity_) {
418
0
        return -1;
419
0
      }
420
2
      int index = D_->entry_->items_[pos];
421
2
      if (index == kDeletedEntry) {
422
1
        ++pos;
423
1
        continue;  // increment again
424
1
      }
425
1
      if (index == kEmptyEntry) {
426
1
        return -1;
427
1
      }
428
0
      break;
429
1
    }
430
0
    return pos;
431
1
  }
Unexecuted instantiation: _ZN8DictIterIP3StrPN12runtime_asdl8hay_nodeEE13ValidPosAfterEi
432
433
  Dict<K, V>* D_;
434
  int pos_;
435
};
436
437
#endif  // MYCPP_GC_DICT_H