bernsteinbear.com
this repo has no description
1/* Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com) */
2#pragma once
3
4#include "globals.h"
5#include "handles-decl.h"
6#include "objects.h"
7#include "runtime.h"
8#include "thread.h"
9
10namespace py {
11
12// Add `LargeStr` object `str` to the intern set `data`. Sets `*result` to
13// an equal existing string in the table and returns `false` or inserts `str`
14// to the table and returns `true`. The return value should be used to count
15// down a "remaining" counter and grow the set when necessary.
16bool internSetAdd(Thread* thread, RawMutableTuple data, const Object& str,
17 RawObject* result);
18
19// Sets `*result` to an existing string object equal to `bytes` and returns
20// `false` or creates a new `LargeStr` from `bytes`, inserts it into the table
21// and returns `true`. The return value should be used to count down a
22// "remaining" counter and grow the set when necessary.
23bool internSetAddFromAll(Thread* thread, RawMutableTuple data, View<byte> bytes,
24 RawObject* result);
25
26word internSetComputeRemaining(word data_length);
27
28bool internSetContains(RawMutableTuple data, RawLargeStr str);
29
30RawObject internSetGrow(Thread* thread, RawMutableTuple data,
31 word* remaining_out);
32
33inline bool internSetAddFromAll(Thread* thread, RawMutableTuple data,
34 View<byte> bytes, RawObject* result) {
35 DCHECK(bytes.length() > SmallStr::kMaxLength, "only need to intern LargeStr");
36 Runtime* runtime = thread->runtime();
37 word hash = runtime->bytesHash(bytes);
38 DCHECK(Utils::isPowerOfTwo(data.length()), "table size must be power of two");
39 word mask = data.length() - 1;
40 word index = hash & mask;
41 word num_probes = 0;
42 for (;;) {
43 RawObject slot = data.at(index);
44 if (slot == SmallInt::fromWord(0)) {
45 RawLargeStr new_str = LargeStr::cast(runtime->newStrWithAll(bytes));
46 new_str.setHeader(new_str.header().withHashCode(hash));
47 data.atPut(index, new_str);
48 *result = new_str;
49 return true;
50 }
51 if (LargeStr::cast(slot).equalsBytes(bytes)) {
52 *result = slot;
53 return false;
54 }
55
56 num_probes++;
57 index = (index + num_probes) & mask;
58 }
59}
60
61inline bool internSetAdd(Thread* thread, RawMutableTuple data,
62 const Object& str, RawObject* result) {
63 DCHECK(str.isLargeStr(), "expected large string");
64 Runtime* runtime = thread->runtime();
65 word hash = runtime->valueHash(*str);
66 DCHECK(Utils::isPowerOfTwo(data.length()), "table size must be power of two");
67 word mask = data.length() - 1;
68 word index = hash & mask;
69 word num_probes = 0;
70 for (;;) {
71 RawObject slot = data.at(index);
72 if (slot == str) {
73 *result = *str;
74 return false;
75 }
76 if (slot == SmallInt::fromWord(0)) {
77 data.atPut(index, *str);
78 *result = *str;
79 return true;
80 }
81 if (LargeStr::cast(slot).equals(LargeStr::cast(*str))) {
82 *result = slot;
83 return false;
84 }
85
86 num_probes++;
87 index = (index + num_probes) & mask;
88 }
89}
90
91} // namespace py