1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
//===--- PrebuiltStringMap.cpp - Unit tests for PrebuiltStringMap ---------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
#include "swift/Runtime/PrebuiltStringMap.h"
#include "gtest/gtest.h"
static bool stringIsNull(const char *str) { return str == nullptr; }
TEST(PrebuiltStringMapTest, PrebuiltStringMap) {
auto testOnce = [&](unsigned testEntryCount) {
std::vector<std::pair<std::string, unsigned>> testVector;
testVector.reserve(testEntryCount);
for (unsigned i = 0; i < testEntryCount; i++) {
std::string key;
for (unsigned j = 0; j < i; j++)
key += std::to_string(j);
testVector.push_back({key, i});
}
using Map = swift::PrebuiltStringMap<const char *, unsigned, stringIsNull>;
unsigned mapSize = testEntryCount * 4 / 3;
void *mapAllocation = calloc(1, Map::byteSize(mapSize));
Map *map = new (mapAllocation) Map(mapSize);
// Populate the map.
for (auto &[key, value] : testVector) {
const char *keyCStr = key.c_str();
auto *element = map->insert(keyCStr);
EXPECT_NE(element, nullptr);
element->key = keyCStr;
element->value = value;
}
// Verify that we can find all the test values.
for (auto &[key, value] : testVector) {
const char *keyCStr = key.c_str();
auto *element = map->find(keyCStr);
EXPECT_NE(element, nullptr);
EXPECT_EQ(element->key, key);
EXPECT_EQ(element->value, value);
}
// Test the interface that takes a string and length without NUL
// termination.
for (auto &[key, value] : testVector) {
auto keyCopy = key;
keyCopy += "xyz";
const char *keyCStr = keyCopy.c_str();
auto *element = map->find(keyCStr, key.size());
EXPECT_NE(element, nullptr);
EXPECT_EQ(element->key, key);
EXPECT_EQ(element->value, value);
}
// Verify that nonexistent keys are not found.
const char *nonexistentKey = "ceci n'est pas une clef";
auto *element = map->find(nonexistentKey);
EXPECT_EQ(element, nullptr);
free(mapAllocation);
};
testOnce(10);
testOnce(100);
testOnce(1000);
}
TEST(PrebuiltStringMapTest, PrebuiltAuxDataImplicitStringMap) {
auto testOnce = [&](unsigned testEntryCount) {
// Test a map containing positive integers, where the key is a string
// derived from the integer. The aux data is the negative of the integer.
using Map = swift::PrebuiltAuxDataImplicitStringMap<uint64_t, int32_t>;
auto getKey = [](unsigned n) {
std::string key;
for (unsigned i = 0; i < n; i++) {
key += 'A' + (i % 26);
}
return key;
};
unsigned mapSize = testEntryCount * 4 / 3;
void *mapAllocation = calloc(1, Map::byteSize(mapSize));
Map *map = new (mapAllocation) Map(mapSize);
// Populate the map.
for (unsigned n = 0; n < testEntryCount; n++) {
auto key = getKey(n);
auto isNull = [](auto pointers) { return *pointers.first == 0; };
auto pointers = map->insert(key.c_str(), isNull);
EXPECT_NE(pointers.first, nullptr);
EXPECT_NE(pointers.second, nullptr);
*pointers.first = n;
*pointers.second = -(int64_t)n;
}
// Verify that we can find all the test values.
for (unsigned n = 0; n < testEntryCount; n++) {
auto key = getKey(n);
auto keyLength = key.size();
// Add some trash to the end to make sure the lookup doesn't look beyond
// the specified length.
key += "xyz";
auto isMatch = [n](auto pointers) { return *pointers.first == n; };
auto isNull = [](auto pointers) { return *pointers.first == 0; };
auto pointers = map->find(key.c_str(), keyLength, isMatch, isNull);
EXPECT_NE(pointers.first, nullptr);
EXPECT_NE(pointers.second, nullptr);
EXPECT_EQ(*pointers.first, n);
EXPECT_EQ(*pointers.second, -(int64_t)n);
}
// Verfy a nonexistent value is not found.
const char *nonexistentKey = "ceci n'est pas une clef";
auto isMatch = [](auto pointers) { return false; };
auto isNull = [](auto pointers) { return *pointers.first == 0; };
auto pointers =
map->find(nonexistentKey, strlen(nonexistentKey), isMatch, isNull);
EXPECT_EQ(*pointers.first, 0);
EXPECT_EQ(*pointers.second, 0);
};
testOnce(10);
testOnce(100);
testOnce(1000);
}
|
