binaryen/test/example/small_set.cpp at waitqueue-api · WebAssembly/binaryen · GitHub

History

281 lines (238 loc) · 6.13 KB

Raw

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

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

#include <algorithm>

#include <cassert>

#include <iostream>

#include <vector>

#include "support/small_set.h"

using namespace wasm;

template<typename T>

void assertContents(T& t, const std::vector<int>& expectedContents) {

assert(t.size() == expectedContents.size());

for (auto item : expectedContents) {

assert(t.contains(item));

}

// Also test this using an iterator and a const iterator to also get

// coverage there.

for (auto& item : t) {

assert(std::find(expectedContents.begin(), expectedContents.end(), item) !=

expectedContents.end());

}

for (const auto& item : t) {

assert(std::find(expectedContents.begin(), expectedContents.end(), item) !=

expectedContents.end());

}

template<typename T> void testAPI() {

{

T t;

// build up with no duplicates

assert(t.empty());

assert(t.size() == 0);

t.insert(1);

assertContents(t, {1});

assert(!t.empty());

assert(t.size() == 1);

t.insert(2);

assertContents(t, {1, 2});

assert(!t.empty());

assert(t.size() == 2);

t.insert(3);

assertContents(t, {1, 2, 3});

assert(!t.empty());

// unwind

assert(t.size() == 3);

t.erase(3);

assertContents(t, {1, 2});

assert(t.size() == 2);

t.erase(2);

assertContents(t, {1});

assert(t.size() == 1);

t.erase(1);

assertContents(t, {});

assert(t.size() == 0);

assert(t.empty());

}

{

T t;

// build up with duplicates

t.insert(1);

t.insert(2);

t.insert(3);

assertContents(t, {1, 2, 3});

assert(t.size() == 3);

// unwind by erasing (in the opposite direction from before)

assert(t.contains(1));

assert(t.contains(2));

assert(t.contains(3));

assert(!t.contains(1337));

t.erase(1);

assert(!t.contains(1));

assert(t.size() == 2);

assert(t.contains(2));

t.erase(2);

assert(!t.contains(2));

assert(t.size() == 1);

assert(t.contains(3));

t.erase(3);

assert(!t.contains(1));

assert(!t.contains(2));

assert(!t.contains(3));

assert(!t.contains(1337));

assert(t.size() == 0);

}

{

T t;

// build up

t.insert(1);

t.insert(2);

t.insert(3);

// unwind by clearing

t.clear();

assert(t.size() == 0);

assert(t.empty());

}

{

T t, u;

// comparisons

assert(t == u);

t.insert(1);

assert(t != u);

u.insert(1);

assert(t == u);

u.erase(1);

assert(t != u);

u.insert(2);

assert(t != u);

}

{

T t, u;

// comparisons should ignore the order of insertion

t.insert(1);

t.insert(2);

u.insert(2);

u.insert(1);

assert(t == u);

}

{

T t, u;

// comparisons should ignore the mode: in a SmallSet<1>, a set of size 1

// can be either fixed - if we just grew it to size 1 - or flexible - if we

// grew it enough to be flexible, then shrank it back (as it only becomes

// fixed at size 0).

t.insert(1);

u.insert(1);

u.insert(2);

// one extra item in u

assert(t != u);

assert(u != t);

// remove the extra item

u.erase(2);

assert(t == u);

assert(u == t);

}

{

T t, u;

// as above, but for size 2, and don't erase the last item added

t.insert(1);

t.insert(2);

u.insert(3);

u.insert(2);

u.insert(1);

// one extra item in u

assert(t != u);

assert(u != t);

// remove the extra item

u.erase(3);

assert(t == u);

assert(u == t);

}

template<typename T> void testInternals() {

{

T s;

// Start out using fixed storage.

assert(s.TEST_ONLY_NEVER_USE_usingFixed());

// Adding one item still keeps us using fixed storage, as that is the exact

// amount we have in fact.

s.insert(0);

assert(s.TEST_ONLY_NEVER_USE_usingFixed());

// Adding one more item forces us to use flexible storage.

s.insert(1);

assert(!s.TEST_ONLY_NEVER_USE_usingFixed());

// Removing an item returns us to size 1, *but we keep using flexible

// storage*. We do not ping-pong between flexible and fixed; once flexible,

// we stay that way.

s.erase(0);

assert(!s.TEST_ONLY_NEVER_USE_usingFixed());

// However, removing all items does return us to using fixed storage, should

// we ever insert again.

s.erase(1);

assert(s.empty());

assert(s.TEST_ONLY_NEVER_USE_usingFixed());

// And once more we can add an additional item while remaining fixed.

s.insert(10);

assert(s.TEST_ONLY_NEVER_USE_usingFixed());

}

// Iterate over an input object and check we have the same items, in the same

// order, as we expect.

template<typename T>

void assertEqualOrdered(const T& t, const std::vector<int>& expected) {

size_t index = 0;

for (auto x : t) {

assert(index < expected.size());

assert(x == expected[index]);

index++;

}

template<typename T> void testOrdering() {

T t;

// Do some inserts at the end.

t.insert(1);

assertEqualOrdered(t, {1});

t.insert(2);

assertEqualOrdered(t, {1, 2});

t.insert(3);

assertEqualOrdered(t, {1, 2, 3});

// Erase the start.

t.erase(1);

assertEqualOrdered(t, {2, 3});

// Insert at the start.

t.insert(1);

assertEqualOrdered(t, {1, 2, 3});

// Erase the end.

t.erase(3);

assertEqualOrdered(t, {1, 2});

// Erase the end.

t.erase(2);

assertEqualOrdered(t, {1});

// Insert at the end.

t.insert(3);

assertEqualOrdered(t, {1, 3});

// Insert at the middle.

t.insert(2);

assertEqualOrdered(t, {1, 2, 3});

// Erase the middle.

t.erase(2);

assertEqualOrdered(t, {1, 3});

}

int main() {

testAPI<SmallSet<int, 0>>();

testAPI<SmallSet<int, 1>>();

testAPI<SmallSet<int, 2>>();

testAPI<SmallSet<int, 3>>();

testAPI<SmallSet<int, 10>>();

testAPI<SmallUnorderedSet<int, 0>>();

testAPI<SmallUnorderedSet<int, 1>>();

testAPI<SmallUnorderedSet<int, 2>>();

testAPI<SmallUnorderedSet<int, 3>>();

testAPI<SmallUnorderedSet<int, 10>>();

testInternals<SmallSet<int, 1>>();

testInternals<SmallUnorderedSet<int, 1>>();

testOrdering<SmallSet<int, 0>>();

testOrdering<SmallSet<int, 1>>();

testOrdering<SmallSet<int, 2>>();

testOrdering<SmallSet<int, 3>>();

testOrdering<SmallSet<int, 10>>();

std::cout << "ok.\n";

}

binaryen/test/example/small_set.cpp at waitqueue-api · WebAssembly/binaryen · GitHub

Uh oh!

Expand file tree

Breadcrumbs

small_set.cpp

Latest commit

History

Breadcrumbs

small_set.cpp

File metadata and controls