cpp

Coverage Report

Created: 2023-03-07 20:24

/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
  }
_ZN4DictIP3StrS1_EC2Ev
Line
Count
Source
52
9
        values_(nullptr) {
53
9
  }
_ZN4DictIP3StriEC2Ev
Line
Count
Source
52
17
        values_(nullptr) {
53
17
  }
_ZN4DictIiP3StrEC2Ev
Line
Count
Source
52
8
        values_(nullptr) {
53
8
  }
_ZN4DictIiiEC2Ev
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
}
_ZN4DictIiiE7reserveEi
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
}
_ZN4DictIiiE6index_Ei
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
}
_ZN4DictIiP3StrE3getEi
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
}
_ZN4DictIP3StriE4keysEv
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
}
_ZN4DictIiiE3setEii
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