Data Structures | Macros | Typedefs | Functions | Variables

test_radixtree.c File Reference

#include "postgres.h"
#include "common/int.h"
#include "common/pg_prng.h"
#include "fmgr.h"
#include "utils/memutils.h"
#include "utils/timestamp.h"
#include "lib/radixtree.h"

Include dependency graph for test_radixtree.c:

Go to the source code of this file.

Data Structures

struct rt_node_class_test_elem

Macros

#define EXPECT_TRUE(expr)

#define EXPECT_FALSE(expr)

#define EXPECT_EQ_U64(result_expr, expected_expr)

#define RT_PREFIX rt

#define RT_SCOPE

#define RT_DECLARE

#define RT_DEFINE

#define RT_USE_DELETE

#define RT_VALUE_TYPE TestValueType

#define RT_DEBUG

Typedefs

typedef uint64 TestValueType

typedef struct rt_node_class_test_elem rt_node_class_test_elem

Functions

static uint64 rt_num_entries (rt_radix_tree *tree)

PG_FUNCTION_INFO_V1 (test_radixtree)

static void test_empty (void)

static void test_basic (rt_node_class_test_elem *test_info, int shift, bool asc)

static int key_cmp (const void *a, const void *b)

static void test_random (void)

Datum test_radixtree (PG_FUNCTION_ARGS)

Variables

static rt_node_class_test_elem rt_node_class_tests []

PG_MODULE_MAGIC

Macro Definition Documentation

◆ EXPECT_EQ_U64

#define EXPECT_EQ_U64 ( result_expr,

expected_expr

)

Value:

do { \

uint64 _result = (result_expr); \

uint64 _expected = (expected_expr); \

if (_result != _expected) \

elog(ERROR, \

"%s yielded %" PRIx64 ", expected %" PRIx64 " (%s) in file \"%s\" line %u", \

#result_expr, _result, _expected, #expected_expr, __FILE__, __LINE__); \

} while (0)

ERROR

#define ERROR

Definition: elog.h:39

Definition at line 41 of file test_radixtree.c.

◆ EXPECT_FALSE

#define EXPECT_FALSE ( expr )

Value:

do { \

if (expr) \

elog(ERROR, \

"%s was unexpectedly true in file \"%s\" line %u", \

#expr, __FILE__, __LINE__); \

} while (0)

Definition at line 33 of file test_radixtree.c.

◆ EXPECT_TRUE

#define EXPECT_TRUE ( expr )

Value:

do { \

if (!(expr)) \

elog(ERROR, \

"%s was unexpectedly false in file \"%s\" line %u", \

#expr, __FILE__, __LINE__); \

} while (0)

Definition at line 25 of file test_radixtree.c.

◆ RT_DEBUG

#define RT_DEBUG

Definition at line 103 of file test_radixtree.c.

◆ RT_DECLARE

#define RT_DECLARE

Definition at line 96 of file test_radixtree.c.

◆ RT_DEFINE

#define RT_DEFINE

Definition at line 97 of file test_radixtree.c.

◆ RT_PREFIX

#define RT_PREFIX rt

Definition at line 94 of file test_radixtree.c.

◆ RT_SCOPE

#define RT_SCOPE

Definition at line 95 of file test_radixtree.c.

◆ RT_USE_DELETE

#define RT_USE_DELETE

Definition at line 98 of file test_radixtree.c.

◆ RT_VALUE_TYPE

#define RT_VALUE_TYPE TestValueType

Definition at line 99 of file test_radixtree.c.

Typedef Documentation

◆ rt_node_class_test_elem

typedef struct rt_node_class_test_elem rt_node_class_test_elem

◆ TestValueType

typedef uint64 TestValueType

Definition at line 56 of file test_radixtree.c.

Function Documentation

◆ key_cmp()

static int key_cmp ( const void * a,

const void * b

)

static

Definition at line 287 of file test_radixtree.c.

288{

289 return pg_cmp_u64(*(const uint64 *) a, *(const uint64 *) b);

290}

uint64

uint64_t uint64

Definition: c.h:539

pg_cmp_u64

static int pg_cmp_u64(uint64 a, uint64 b)

Definition: int.h:664

b

int b

Definition: isn.c:74

a

int a

Definition: isn.c:73

References a, b, and pg_cmp_u64().

Referenced by test_random().

◆ PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1 ( test_radixtree )

◆ rt_num_entries()

static uint64 rt_num_entries ( rt_radix_tree * tree )

static

Definition at line 111 of file test_radixtree.c.

112{

113 return tree->ctl->num_keys;

114}

tree

Definition: radixtree.h:1828

References tree.

Referenced by test_empty(), and test_random().

◆ test_basic()

static void test_basic ( rt_node_class_test_elem * test_info,

int shift,

bool asc

)

static

Definition at line 162 of file test_radixtree.c.

163{

164 rt_radix_tree *radixtree;

165 rt_iter *iter;

166 uint64 *keys;

167 int children = test_info->nkeys;

168#ifdef TEST_SHARED_RT

169 int tranche_id = LWLockNewTrancheId("test_radix_tree");

170 dsa_area *dsa;

171

172 dsa = dsa_create(tranche_id);

173 radixtree = rt_create(dsa, tranche_id);

174#else

175 MemoryContext radixtree_ctx;

176

177 radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,

178 "test_radix_tree",

179 ALLOCSET_SMALL_SIZES);

180 radixtree = rt_create(radixtree_ctx);

181#endif

182

183 elog(NOTICE, "testing node %s with shift %d and %s keys",

184 test_info->class_name, shift, asc ? "ascending" : "descending");

185

186 keys = palloc(sizeof(uint64) * children);

187 for (int i = 0; i < children; i++)

188 {

189 if (asc)

190 keys[i] = (uint64) i << shift;

191 else

192 keys[i] = (uint64) (children - 1 - i) << shift;

193 }

194

195 /*

196 * Insert keys. Since the tree was just created, rt_set should return

197 * false.

198 */

199 for (int i = 0; i < children; i++)

200 EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));

201

202 rt_stats(radixtree);

203

204 /* look up keys */

205 for (int i = 0; i < children; i++)

206 {

207 TestValueType *value;

208

209 value = rt_find(radixtree, keys[i]);

210

211 /* Test rt_find returns the expected value */

212 EXPECT_TRUE(value != NULL);

213 EXPECT_EQ_U64(*value, (TestValueType) keys[i]);

214 }

215

216 /* update keys */

217 for (int i = 0; i < children; i++)

218 {

219 TestValueType update = keys[i] + 1;

220

221 /* rt_set should report the key found */

222 EXPECT_TRUE(rt_set(radixtree, keys[i], (TestValueType *) &update));

223 }

224

225 /* delete and re-insert keys */

226 for (int i = 0; i < children; i++)

227 {

228 EXPECT_TRUE(rt_delete(radixtree, keys[i]));

229 EXPECT_FALSE(rt_set(radixtree, keys[i], (TestValueType *) &keys[i]));

230 }

231

232 /* look up keys after deleting and re-inserting */

233 for (int i = 0; i < children; i++)

234 {

235 TestValueType *value;

236

237 value = rt_find(radixtree, keys[i]);

238

239 /* Test that rt_find returns the expected value */

240 EXPECT_TRUE(value != NULL);

241 EXPECT_EQ_U64(*value, (TestValueType) keys[i]);

242 }

243

244 /* test that iteration returns the expected keys and values */

245 iter = rt_begin_iterate(radixtree);

246

247 for (int i = 0; i < children; i++)

248 {

249 uint64 expected;

250 uint64 iterkey;

251 TestValueType *iterval;

252

253 /* iteration is ordered by key, so adjust expected value accordingly */

254 if (asc)

255 expected = keys[i];

256 else

257 expected = keys[children - 1 - i];

258

259 iterval = rt_iterate_next(iter, &iterkey);

260

261 EXPECT_TRUE(iterval != NULL);

262 EXPECT_EQ_U64(iterkey, expected);

263 EXPECT_EQ_U64(*iterval, expected);

264 }

265

266 rt_end_iterate(iter);

267

268 /* delete all keys again */

269 for (int i = 0; i < children; i++)

270 EXPECT_TRUE(rt_delete(radixtree, keys[i]));

271

272 /* test that all keys were deleted */

273 for (int i = 0; i < children; i++)

274 EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL);

275

276 rt_stats(radixtree);

277

278 pfree(keys);

279 rt_free(radixtree);

280

281#ifdef TEST_SHARED_RT

282 dsa_detach(dsa);

283#endif

284}

dsa_detach

void dsa_detach(dsa_area *area)

Definition: dsa.c:1967

dsa_create

#define dsa_create(tranche_id)

Definition: dsa.h:117

elog

#define elog(elevel,...)

Definition: elog.h:226

NOTICE

#define NOTICE

Definition: elog.h:35

value

static struct @169 value

i

int i

Definition: isn.c:77

LWLockNewTrancheId

int LWLockNewTrancheId(const char *name)

Definition: lwlock.c:596

pfree

void pfree(void *pointer)

Definition: mcxt.c:1594

palloc

void * palloc(Size size)

Definition: mcxt.c:1365

CurrentMemoryContext

MemoryContext CurrentMemoryContext

Definition: mcxt.c:160

AllocSetContextCreate

#define AllocSetContextCreate

Definition: memutils.h:129

ALLOCSET_SMALL_SIZES

#define ALLOCSET_SMALL_SIZES

Definition: memutils.h:170

MemoryContextData

Definition: memnodes.h:118

dsa_area

Definition: dsa.c:348

rt_node_class_test_elem::class_name

char * class_name

Definition: test_radixtree.c:64

rt_node_class_test_elem::nkeys

int nkeys

Definition: test_radixtree.c:65

EXPECT_TRUE

#define EXPECT_TRUE(expr)

Definition: test_radixtree.c:25

TestValueType

uint64 TestValueType

Definition: test_radixtree.c:56

EXPECT_FALSE

#define EXPECT_FALSE(expr)

Definition: test_radixtree.c:33

EXPECT_EQ_U64

#define EXPECT_EQ_U64(result_expr, expected_expr)

Definition: test_radixtree.c:41

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, rt_node_class_test_elem::class_name, CurrentMemoryContext, dsa_create, dsa_detach(), elog, EXPECT_EQ_U64, EXPECT_FALSE, EXPECT_TRUE, i, LWLockNewTrancheId(), rt_node_class_test_elem::nkeys, NOTICE, palloc(), pfree(), and value.

Referenced by test_radixtree().

◆ test_empty()

static void test_empty ( void )

static

Definition at line 121 of file test_radixtree.c.

122{

123 rt_radix_tree *radixtree;

124 rt_iter *iter;

125 uint64 key;

126#ifdef TEST_SHARED_RT

127 int tranche_id = LWLockNewTrancheId("test_radix_tree");

128 dsa_area *dsa;

129

130 dsa = dsa_create(tranche_id);

131 radixtree = rt_create(dsa, tranche_id);

132#else

133 MemoryContext radixtree_ctx;

134

135 radixtree_ctx = AllocSetContextCreate(CurrentMemoryContext,

136 "test_radix_tree",

137 ALLOCSET_SMALL_SIZES);

138 radixtree = rt_create(radixtree_ctx);

139#endif

140

141 /* Should not find anything in an empty tree */

142 EXPECT_TRUE(rt_find(radixtree, 0) == NULL);

143 EXPECT_TRUE(rt_find(radixtree, 1) == NULL);

144 EXPECT_TRUE(rt_find(radixtree, PG_UINT64_MAX) == NULL);

145 EXPECT_FALSE(rt_delete(radixtree, 0));

146 EXPECT_TRUE(rt_num_entries(radixtree) == 0);

147

148 /* Iterating on an empty tree should not return anything */

149 iter = rt_begin_iterate(radixtree);

150 EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL);

151 rt_end_iterate(iter);

152

153 rt_free(radixtree);

154

155#ifdef TEST_SHARED_RT

156 dsa_detach(dsa);

157#endif

158}

PG_UINT64_MAX

#define PG_UINT64_MAX

Definition: c.h:598

sort-test.key

key

Definition: sort-test.py:19

rt_num_entries

static uint64 rt_num_entries(rt_radix_tree *tree)

Definition: test_radixtree.c:111

References ALLOCSET_SMALL_SIZES, AllocSetContextCreate, CurrentMemoryContext, dsa_create, dsa_detach(), EXPECT_FALSE, EXPECT_TRUE, sort-test::key, LWLockNewTrancheId(), PG_UINT64_MAX, and rt_num_entries().

Referenced by test_radixtree().

◆ test_radixtree()

Datum test_radixtree ( PG_FUNCTION_ARGS )

Definition at line 431 of file test_radixtree.c.

432{

433 /* borrowed from RT_MAX_SHIFT */

434 const int max_shift = (sizeof(uint64) - 1) * BITS_PER_BYTE;

435

436 test_empty();

437

438 for (int i = 0; i < lengthof(rt_node_class_tests); i++)

439 {

440 rt_node_class_test_elem *test_info = &(rt_node_class_tests[i]);

441

442 /* a tree with one level, i.e. a single node under the root node */

443 test_basic(test_info, 0, true);

444 test_basic(test_info, 0, false);

445

446 /* a tree with two levels */

447 test_basic(test_info, 8, true);

448 test_basic(test_info, 8, false);

449

450 /* a tree with the maximum number of levels */

451 test_basic(test_info, max_shift, true);

452 test_basic(test_info, max_shift, false);

453 }

454

455 test_random();

456

457 PG_RETURN_VOID();

458}

lengthof

#define lengthof(array)

Definition: c.h:787

PG_RETURN_VOID

#define PG_RETURN_VOID()

Definition: fmgr.h:349

BITS_PER_BYTE

#define BITS_PER_BYTE

Definition: pg_config_manual.h:101

rt_node_class_test_elem

Definition: test_radixtree.c:63

test_random

static void test_random(void)

Definition: test_radixtree.c:293

test_empty

static void test_empty(void)

Definition: test_radixtree.c:121

test_basic

static void test_basic(rt_node_class_test_elem *test_info, int shift, bool asc)

Definition: test_radixtree.c:162

rt_node_class_tests

static rt_node_class_test_elem rt_node_class_tests[]

Definition: test_radixtree.c:68

References BITS_PER_BYTE, i, lengthof, PG_RETURN_VOID, rt_node_class_tests, test_basic(), test_empty(), and test_random().

◆ test_random()

static void test_random ( void )

static

Definition at line 293 of file test_radixtree.c.

294{

295 rt_radix_tree *radixtree;

296 rt_iter *iter;

297 pg_prng_state state;

298

299 /* limit memory usage by limiting the key space */

300 uint64 filter = ((uint64) (0x07 << 24) | (0xFF << 16) | 0xFF);

301 uint64 seed = GetCurrentTimestamp();

302 int num_keys = 100000;

303 uint64 *keys;

304#ifdef TEST_SHARED_RT

305 int tranche_id = LWLockNewTrancheId("test_radix_tree");

306 dsa_area *dsa;

307

308 dsa = dsa_create(tranche_id);

309 radixtree = rt_create(dsa, tranche_id);

310#else

311 MemoryContext radixtree_ctx;

312

313 radixtree_ctx = SlabContextCreate(CurrentMemoryContext,

314 "test_radix_tree",

315 SLAB_DEFAULT_BLOCK_SIZE,

316 sizeof(TestValueType));

317 radixtree = rt_create(radixtree_ctx);

318#endif

319

320 /* add some random values */

321 pg_prng_seed(&state, seed);

322 keys = (TestValueType *) palloc(sizeof(uint64) * num_keys);

323 for (uint64 i = 0; i < num_keys; i++)

324 {

325 uint64 key = pg_prng_uint64(&state) & filter;

326 TestValueType val = (TestValueType) key;

327

328 /* save in an array */

329 keys[i] = key;

330

331 rt_set(radixtree, key, &val);

332 }

333

334 rt_stats(radixtree);

335

336 for (uint64 i = 0; i < num_keys; i++)

337 {

338 TestValueType *value;

339

340 value = rt_find(radixtree, keys[i]);

341

342 /* Test rt_find for values just inserted */

343 EXPECT_TRUE(value != NULL);

344 EXPECT_EQ_U64(*value, keys[i]);

345 }

346

347 /* sort keys for iteration and absence tests */

348 qsort(keys, num_keys, sizeof(uint64), key_cmp);

349

350 /* should not find numbers in between the keys */

351 for (uint64 i = 0; i < num_keys - 1; i++)

352 {

353 TestValueType *value;

354

355 /* skip duplicate and adjacent keys */

356 if (keys[i + 1] == keys[i] || keys[i + 1] == keys[i] + 1)

357 continue;

358

359 /* should not find the number right after key */

360 value = rt_find(radixtree, keys[i] + 1);

361 EXPECT_TRUE(value == NULL);

362 }

363

364 /* should not find numbers lower than lowest key */

365 for (uint64 key = 0; key < keys[0]; key++)

366 {

367 TestValueType *value;

368

369 /* arbitrary stopping point */

370 if (key > 10000)

371 break;

372

373 value = rt_find(radixtree, key);

374 EXPECT_TRUE(value == NULL);

375 }

376

377 /* should not find numbers higher than highest key */

378 for (uint64 i = 1; i < 10000; i++)

379 {

380 TestValueType *value;

381

382 value = rt_find(radixtree, keys[num_keys - 1] + i);

383 EXPECT_TRUE(value == NULL);

384 }

385

386 /* test that iteration returns the expected keys and values */

387 iter = rt_begin_iterate(radixtree);

388

389 for (int i = 0; i < num_keys; i++)

390 {

391 uint64 expected;

392 uint64 iterkey;

393 TestValueType *iterval;

394

395 /* skip duplicate keys */

396 if (i < num_keys - 1 && keys[i + 1] == keys[i])

397 continue;

398

399 expected = keys[i];

400 iterval = rt_iterate_next(iter, &iterkey);

401

402 EXPECT_TRUE(iterval != NULL);

403 EXPECT_EQ_U64(iterkey, expected);

404 EXPECT_EQ_U64(*iterval, expected);

405 }

406

407 rt_end_iterate(iter);

408

409 /* reset random number generator for deletion */

410 pg_prng_seed(&state, seed);

411

412 /* delete in original random order */

413 for (uint64 i = 0; i < num_keys; i++)

414 {

415 uint64 key = pg_prng_uint64(&state) & filter;

416

417 rt_delete(radixtree, key);

418 }

419

420 EXPECT_TRUE(rt_num_entries(radixtree) == 0);

421

422 pfree(keys);

423 rt_free(radixtree);

424

425#ifdef TEST_SHARED_RT

426 dsa_detach(dsa);

427#endif

428}

GetCurrentTimestamp

TimestampTz GetCurrentTimestamp(void)

Definition: timestamp.c:1645

val

long val

Definition: informix.c:689

SLAB_DEFAULT_BLOCK_SIZE

#define SLAB_DEFAULT_BLOCK_SIZE

Definition: memutils.h:189

pg_prng_uint64

uint64 pg_prng_uint64(pg_prng_state *state)

Definition: pg_prng.c:134

pg_prng_seed

void pg_prng_seed(pg_prng_state *state, uint64 seed)

Definition: pg_prng.c:89

qsort

#define qsort(a, b, c, d)

Definition: port.h:479

SlabContextCreate

MemoryContext SlabContextCreate(MemoryContext parent, const char *name, Size blockSize, Size chunkSize)

Definition: slab.c:322

pg_prng_state

Definition: pg_prng.h:20

state

Definition: regguts.h:323

key_cmp

static int key_cmp(const void *a, const void *b)

Definition: test_radixtree.c:287

References CurrentMemoryContext, dsa_create, dsa_detach(), EXPECT_EQ_U64, EXPECT_TRUE, GetCurrentTimestamp(), i, sort-test::key, key_cmp(), LWLockNewTrancheId(), palloc(), pfree(), pg_prng_seed(), pg_prng_uint64(), qsort, rt_num_entries(), SLAB_DEFAULT_BLOCK_SIZE, SlabContextCreate(), val, and value.

Referenced by test_radixtree().

Variable Documentation

◆ PG_MODULE_MAGIC

PG_MODULE_MAGIC

Definition at line 116 of file test_radixtree.c.

◆ rt_node_class_tests

rt_node_class_test_elem rt_node_class_tests[]

static

Initial value:

=

{

.class_name = "node-4",

.nkeys = 2,

},

{

.class_name = "node-16-lo",

.nkeys = 15,

},

{

.class_name = "node-16-hi",

.nkeys = 30,

},

{

.class_name = "node-48",

.nkeys = 60,

},

{

.class_name = "node-256",

.nkeys = 256,

},

}

Definition at line 68 of file test_radixtree.c.

Referenced by test_radixtree().