bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "str-intern.h"
3
4#include "handles.h"
5#include "runtime.h"
6#include "thread.h"
7
8namespace py {
9
10word internSetComputeRemaining(word data_length) {
11 return (data_length * 2) / 3;
12}
13
14RawObject internSetGrow(Thread* thread, RawMutableTuple data_raw,
15 word* remaining_out) {
16 HandleScope scope(thread);
17 Runtime* runtime = thread->runtime();
18 Tuple old_data(&scope, data_raw);
19 word old_capacity = old_data.length();
20 word new_capacity = old_capacity * 2;
21 word new_remaining = internSetComputeRemaining(new_capacity);
22 DCHECK(Utils::isPowerOfTwo(new_capacity), "must be power of two");
23 word mask = new_capacity - 1;
24 MutableTuple new_data(&scope, runtime->newMutableTuple(new_capacity));
25 for (word i = 0, length = old_data.length(); i < length; i++) {
26 RawObject slot = old_data.at(i);
27 if (slot == SmallInt::fromWord(0)) {
28 continue;
29 }
30 word hash = LargeStr::cast(slot).header().hashCode();
31 word index = hash & mask;
32 word num_probes = 0;
33 while (new_data.at(index) != SmallInt::fromWord(0)) {
34 num_probes++;
35 index = (index + num_probes) & mask;
36 }
37 new_data.atPut(index, slot);
38 new_remaining--;
39 }
40 DCHECK(new_remaining > 0, "must have remaining slots");
41 *remaining_out = new_remaining;
42 return *new_data;
43}
44
45bool internSetContains(RawMutableTuple data, RawLargeStr str) {
46 word hash = str.header().hashCode();
47 if (hash == Header::kUninitializedHash) {
48 return false;
49 }
50 DCHECK(Utils::isPowerOfTwo(data.length()), "length must be power of two");
51 word mask = data.length() - 1;
52 word idx = hash & mask;
53 word num_probes = 0;
54 for (;;) {
55 RawObject slot = data.at(idx);
56 if (slot == str) {
57 return true;
58 }
59 if (slot == SmallInt::fromWord(0)) {
60 return false;
61 }
62 num_probes++;
63 idx = (idx + num_probes) & mask;
64 }
65}
66
67} // namespace py