data_structures: 36018adade6d src/btree

view src/btree_mem.c @ 23:36018adade6d

valgrind reporting no memory leaks now.

author	Eris Caffee <discordia@eldalin.com>
date	Fri, 19 Oct 2012 18:19:39 -0500
parents	e56a76090d80
children	f27bdd5d40d0

line source

1 /*

2 This is a fairly straightforward implementation of a B-Tree in memory modeled after

3 Cormen, et al., Introduction to Algorithms, Chapter 18

4 */

6 #include <stdio.h>

7 #include <stdlib.h>

8 #include <stdbool.h>

10 #include "btree_mem.h"

12 struct btree_mem_node

13 {

14 int nkeys;

15 void ** key;

16 void ** data;

17 struct btree_mem_node ** child;

18 bool leaf;

19 };

21 struct btree_mem

22 {

23 int mindeg;

24 struct btree_mem_node * root;

25 int (*cmp)(void *, void *);

26 };

28 struct btree_mem_node * btree_mem_node_new (struct btree_mem * bt);

29 void btree_mem_node_delete (struct btree_mem_node * node);

31 struct btree_mem_node * btree_mem_node_find (struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i);

33 void * btree_mem_node_insert (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);

34 void * btree_mem_node_insert_nonfull (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);

36 struct btree_mem_node * btree_mem_split_child (struct btree_mem * bt, struct btree_mem_node * x, int i);

38 void btree_mem_node_walk_nodes_preorder (struct btree_mem_node * node, void (*f)(struct btree_mem_node *));

39 void btree_mem_node_walk_inorder (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);

40 void btree_mem_node_dump (struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth);

42 void * btree_mem_node_remove (struct btree_mem * bt, struct btree_mem_node * node, void * key,

43 void ** key_value, void ** data_value);

45 void btree_mem_node_add_key (struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data);

46 void * btree_mem_node_remove_key (struct btree_mem_node * node, int i);

47 struct btree_mem_node * btree_mem_node_find_prev (struct btree_mem_node * node);

48 struct btree_mem_node * btree_mem_node_find_next (struct btree_mem_node * node);

49 void btree_mem_node_merge (struct btree_mem_node * a, struct btree_mem_node * b);

51 #ifdef DEBUG

52 #define DEBUG_BLOCK(x) x

54 void btree_mem_node_print_keys(struct btree_mem_node * node);

56 #else

57 #define DEBUG_BLOCK(x)

58 #endif

60 void printit(int h, void * k, void * d)

61 {

62 for (int i = 0; i < h; i++)

63 printf("\t");

64 printf("%d %s\n", *((int*)k), (char *) d);

65 }

68 ////////////////////////////////////////////////////////////////////////////////

69 struct btree_mem *

70 btree_mem_new(int min_degree, int (*cmp)(void *, void *))

71 {

72 struct btree_mem * bt = malloc(sizeof(struct btree_mem));

73 if (NULL == bt)

74 return NULL;

76 bt->mindeg = min_degree;

77 bt->cmp = cmp;

79 printf("Getting new root node\n");

80 bt->root = btree_mem_node_new(bt);

81 if (NULL == bt->root)

82 {

83 free(bt);

84 return NULL;

85 }

87 bt->root->leaf = true;

88 return bt;

89 }

91 ////////////////////////////////////////////////////////////////////////////////

92 // IMPORTANT NOTE: All keys and data must be removed first or else memory

93 // will leak.

94 void

95 btree_mem_delete(struct btree_mem * bt)

96 {

97 // TODO: walk down the tree and delete all nodes.

99 btree_mem_node_walk_nodes_preorder(bt->root, btree_mem_node_delete);

100 free(bt);

101 }

102

103 ////////////////////////////////////////////////////////////////////////////////

104 struct btree_mem_node *

105 btree_mem_node_new(struct btree_mem * bt)

106 {

107 struct btree_mem_node * node = malloc(sizeof(struct btree_mem_node));

108 if (NULL == node)

109 return NULL;

110

111 printf("Allocated node %p\n", node);

112 int maxchild = 2*bt->mindeg;

113

114 node->key = malloc( (maxchild - 1) * sizeof(void *));

115 if (NULL == node->key)

116 {

117 free(node);

118 return NULL;

119 }

120

121 node->data = malloc( (maxchild - 1) * sizeof(void *));

122 if (NULL == node->data)

123 {

124 free(node->key);

125 free(node);

126 return NULL;

127 }

128

129 node->child = malloc( maxchild * sizeof(struct btree_mem_node *));

130 if (NULL == node->data)

131 {

132 free(node->data);

133 free(node->key);

134 free(node);

135 return NULL;

136 }

137

138 for (int i = 0; i < maxchild - 1; i++)

139 {

140 node->key[i] = NULL;

141 node->data[i] = NULL;

142 node->child[i] = NULL;

143 }

144 node->child[maxchild-1] = NULL;

145

146 node->nkeys = 0;

147 node->leaf = false;

148

149 return node;

150 }

151

152 ////////////////////////////////////////////////////////////////////////////////

153 // IMPORTANT NOTE: All keys and data must be removed first or else memory

154 // will leak.

155 void

156 btree_mem_node_delete(struct btree_mem_node * node)

157 {

158 printf("Freeing node %p\n", node);

159 free(node->child);

160 free(node->data);

161 free(node->key);

162 free(node);

163 }

164

165 ////////////////////////////////////////////////////////////////////////////////

166 void *

167 btree_mem_find(struct btree_mem * bt, void * key)

168 {

169 int i;

170 struct btree_mem_node * node = btree_mem_node_find(bt, bt->root, key, &i);

171 if (NULL == node)

172 return NULL;

173 return node->data[i];

174 }

175

176 ////////////////////////////////////////////////////////////////////////////////

177 struct btree_mem_node *

178 btree_mem_node_find(struct btree_mem * bt, struct btree_mem_node * node, void * key, int * i)

179 {

180 *i = 0;

181 while (( *i < node->nkeys) && (bt->cmp(key, node->key[*i]) > 0) )

182 (*i)++;

183 if ( (*i < node->nkeys) && (bt->cmp(key, node->key[*i]) == 0) )

184 return node;

185 if (node->leaf)

186 return NULL;

187 else

188 return btree_mem_node_find(bt, node->child[*i], key, i);

189 }

190

191 ////////////////////////////////////////////////////////////////////////////////

192 void *

193 btree_mem_insert(struct btree_mem * bt, void * key, void * data)

194 {

195 DEBUG_BLOCK( printf("Inserting key %d data >%s<\n", *((int *) key), (char *) data); )

196 struct btree_mem_node * s = bt->root;

197

198 // If the root node is full, split it here.

199 if ((2 * bt->mindeg - 1) == s->nkeys)

200 {

201 printf("Splitting root node. Allocating new node\n");

202 s = btree_mem_node_new(bt);

203 if (NULL == s)

204 return NULL;

205 s->child[0] = bt->root;

206 bt->root = s;

207 btree_mem_split_child(bt, s, 0);

208 }

209 return btree_mem_node_insert_nonfull(bt, s, key, data);

210 }

211

212 ////////////////////////////////////////////////////////////////////////////////

213 void *

214 btree_mem_node_insert_nonfull(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)

215 {

216 int i = node->nkeys - 1;

217 if (node->leaf)

218 {

219 //DEBUG_BLOCK( printf("node->nkeys: %d\n", node->nkeys); )

220 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )

221 {

222 node->key[i+1] = node->key[i];

223 node->data[i+1] = node->data[i];

224 i--;

225 }

226 node->key[i+1] = key;

227 node->data[i+1] = data;

228 node->nkeys++;

229 return key;

230 }

231 else

232 {

233 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )

234 i--;

235 i++;

236

237 if (node->child[i]->nkeys == (2 * bt->mindeg - 1))

238 {

239 if (NULL == btree_mem_split_child(bt, node, i))

240 return NULL;

241 if (bt->cmp(key, node->key[i]) > 0)

242 i++;

243 }

244 return btree_mem_node_insert_nonfull(bt, node->child[i], key, data);

245 }

246 }

247

248 ////////////////////////////////////////////////////////////////////////////////

249 // x - a non-full node

250 // i - The index of a full node y in x's child list.

251 //

252 // Split y in half, adding the newly created node z as a new child of x.

253 // z will be placed after y in the child list.

254

255 struct btree_mem_node *

256 btree_mem_split_child(struct btree_mem * bt, struct btree_mem_node * x, int i)

257 {

258

259 struct btree_mem_node * y = x->child[i];

260

261 // Allocate new node.

262 printf("splitting child allocating new node\n");

263 struct btree_mem_node * z = btree_mem_node_new(bt);

264 if (NULL == z)

265 return NULL;

266

267 // Load z with the second half of y's data;

268 z->leaf = y->leaf;

269 z->nkeys = bt->mindeg - 1;

270 for (int j = 0; j < bt->mindeg - 1; j++)

271 {

272 z->key[j] = y->key[j + bt->mindeg];

273 z->data[j] = y->data[j + bt->mindeg];

274 }

275 if (! y->leaf)

276 {

277 for (int j = 0; j < bt->mindeg; j++)

278 z->child[j] = y->child[j + bt->mindeg];

279 }

280

281 // Update y's nkeys.

282 y->nkeys = bt->mindeg - 1;

283

284 // Make a hole in x's child list for the new node z.

285 for (int j = x->nkeys; j >= i + 1; j--)

286 x->child[j+1] = x->child[j];

287 x->child[i+1] = z;

288

289 // Make a hole in x's key list for the new node z.

290 for (int j = x->nkeys - 1; j >= i; j--)

291 {

292 x->key[j+1] = x->key[j];

293 x->data[j+1] = x->data[j];

294 }

295 x->key[i] = y->key[bt->mindeg-1];

296 x->data[i] = y->data[bt->mindeg-1];

297

298 x->nkeys += 1;

299

300 return z;

301 }

302

303 ////////////////////////////////////////////////////////////////////////////////

304 void

305 btree_mem_node_walk_nodes_preorder(struct btree_mem_node * node, void (*f)(struct btree_mem_node *))

306 {

307 if (! node->leaf)

308 {

309 for (int i = 0; i < node->nkeys; i++)

310 btree_mem_node_walk_nodes_preorder(node->child[i], f);

311 }

312 f(node);

313 }

314

315 ////////////////////////////////////////////////////////////////////////////////

316 void

317 btree_mem_walk_inorder(struct btree_mem * bt, void (*f)(int, void const * const, void *))

318 {

319 btree_mem_node_walk_inorder(bt->root, f, 0);

320 }

321

322 ////////////////////////////////////////////////////////////////////////////////

323 void

324 btree_mem_node_walk_inorder(struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth)

325 {

326

327 if (0 == node->nkeys)

328 {

329 if (NULL != node->child[0])

330 btree_mem_node_walk_inorder(node->child[0], f, depth+1);

331 return;

332 }

333

334 for (int i = 0; i < node->nkeys; i++)

335 {

336 if (! node->leaf)

337 btree_mem_node_walk_inorder(node->child[i], f, depth+1);

338 f(depth, node->key[i], node->data[i]);

339 }

340 if (! node->leaf)

341 btree_mem_node_walk_inorder(node->child[node->nkeys], f, depth+1);

342 }

343

344 ////////////////////////////////////////////////////////////////////////////////

345 void

346 btree_mem_dump(struct btree_mem * bt, void (*f)(int, void const * const, void *))

347 {

348 btree_mem_node_dump(bt->root, f, 0);

349 }

350

351 ////////////////////////////////////////////////////////////////////////////////

352 void

353 btree_mem_node_dump(struct btree_mem_node * node, void (*f)(int, void const * const, void *), int depth)

354 {

355

356 if (0 == node->nkeys)

357 {

358 if (NULL != node->child[0])

359 btree_mem_node_dump(node->child[0], f, depth+1);

360 return;

361 }

362

363 for (int i = 0; i < node->nkeys; i++)

364 {

365 if (! node->leaf)

366 btree_mem_node_dump(node->child[i], f, depth+1);

367 printf("node: %p nkeys %10d \t", node, node->nkeys);

368 f(depth, node->key[i], node->data[i]);

369 }

370 if (! node->leaf)

371 btree_mem_node_dump(node->child[node->nkeys], f, depth+1);

372 }

373

374 ////////////////////////////////////////////////////////////////////////////////

375 void *

376 btree_mem_remove(struct btree_mem * bt, void * key, void ** key_value, void ** data_value)

377 {

378 if ( (NULL == bt) || (NULL == key) || (NULL == key_value) || (NULL == data_value) )

379 return NULL;

380

381 DEBUG_BLOCK( printf("Removing %d\n", *((int *) key)); )

382 void * data = btree_mem_node_remove(bt, bt->root, key, key_value, data_value);

383 if (NULL == data)

384 return NULL;

385

386 if ( (0 == bt->root->nkeys) && (bt->root->child[0]) )

387 {

388 DEBUG_BLOCK( printf("Freeing the root node\n"); )

389 struct btree_mem_node * n = bt->root;

390 bt->root = bt->root->child[0];

391 btree_mem_node_delete(n);

392 }

393 return data;

394 }

395

396 ////////////////////////////////////////////////////////////////////////////////

397 // Assumption: node has bt->mindeg keys or is the root.

398

399 void *

400 btree_mem_node_remove(struct btree_mem * bt, struct btree_mem_node * node, void * key, void ** key_value, void ** data_value)

401 {

402

403 DEBUG_BLOCK( btree_mem_node_print_keys(node); )

404

405 int i = node->nkeys - 1;

406 while ( (i >= 0) && (bt->cmp(key, node->key[i]) < 0) )

407 i--;

408

409 if ( (i >= 0) && (bt->cmp(key, node->key[i]) == 0) )

410 {

411 // key is in node at key[i]

412 *key_value = node->key[i];

413 *data_value = node->data[i];

414 // printf("Will return key_value %p (%d) data_value %p (%s)\n", *key_value, *((int*)(*key_value)), *data_value, (char*)(*data_value));

415 if (node->leaf)

416 {

417 // case 1

418 DEBUG_BLOCK( printf("remove: case 1\n"); )

419 btree_mem_node_remove_key(node, i);

420 return *data_value;

421 }

422 else

423 {

424 struct btree_mem_node * prev = node->child[i];

425 struct btree_mem_node * next = node->child[i+1];

426

427 // if (child prev that precedes key in node has at least bt->mindeg keys) ||

428 // (child next that follows key in node has at least bt->mindeg keys)

429 if ( (prev->nkeys >= bt->mindeg) || (next->nkeys >= bt->mindeg) )

430 {

431 struct btree_mem_node * kp;

432 if (prev->nkeys >= bt->mindeg)

433 {

434 // case 2a

435 DEBUG_BLOCK( printf("remove: case 2a\n"); );

436 kp = btree_mem_node_find_prev(prev);

437 node->key[i] = kp->key[kp->nkeys-1];

438 node->data[i] = kp->data[kp->nkeys];

439 void *kv, *dv;

440 node->data[i] = btree_mem_node_remove(bt, prev, kp->key[kp->nkeys-1], kv, dv);

441 }

442 else

443 {

444 // case 2b

445 DEBUG_BLOCK( printf("remove: case 2b\n"); )

446 kp = btree_mem_node_find_next(next);

447 node->key[i] = kp->key[0];

448 node->data[i] = kp->data[0];

449 void *kv, *dv;

450 node->data[i] = btree_mem_node_remove(bt, next, kp->key[0], kv, dv);

451 }

452 node->key[i] = kp;

453 return *data_value;

454 }

455 else

456 {

457 // case 2c

458 DEBUG_BLOCK( printf("remove: case 2c\n"); )

459 btree_mem_node_add_key(bt, prev, node->key[i], node->data[i]);

460 btree_mem_node_remove_key(node, i);

461 for (int j = i+1; j <= node->nkeys+1; j++)

462 node->child[j] = node->child[j+1];

463 btree_mem_node_merge(prev, next);

464 btree_mem_node_delete(next);

465 void *kv, *dv;

466 btree_mem_node_remove(bt, prev, key, &kv, &dv);

467 return *data_value;

468 }

469 }

470 }

471 else

472 {

473 if (node->leaf)

474 {

475 DEBUG_BLOCK( printf("remove: key not found\n"); )

476 return NULL;

477 }

478

479 // key is in child[i+1], if anywhere

480 struct btree_mem_node * c = node->child[i+1];

481

482 DEBUG_BLOCK( printf("remove: key should be in node %p\n", c); )

483 if (c->nkeys == bt->mindeg - 1)

484 {

485 struct btree_mem_node * prev = NULL;

486 if (i >= 0)

487 prev = node->child[i];

488

489 struct btree_mem_node * next = NULL;

490 if (i+2 <= node->nkeys)

491 next = node->child[i+2];

492

493 DEBUG_BLOCK( printf("remove: prev %p next %p\n", prev, next); )

494

495 if ( (prev) && (prev->nkeys >= bt->mindeg) )

496 {

497 // case 3a (with prev sibling)

498 // Move node->key[i] into c->key[0] shifting over existing keys

499 // Move prev->key[prev->nkeys-1] into node->key[i]

500 // if (prev->leaf)

501 // move prev->child[prev->nkeys] into c->child[0] shifting over existing children

502 // prev->nkeys--;

503

504 DEBUG_BLOCK( printf("remove: case 3a.1\n"); )

505

506 btree_mem_node_add_key(bt, c, node->key[i-1], node->data[i-1]);

507

508 node->key[i-1] = prev->key[prev->nkeys-1];

509 node->data[i-1] = prev->data[prev->nkeys-1];

510

511 if (! prev->leaf)

512 {

513 for (int j = c->nkeys; j >= 0; j--)

514 c->child[j+1] = c->child[j];

515 c->child[0] = prev->child[prev->nkeys];

516 }

517

518 prev->nkeys--;

519 }

520 else if ( (next) && (next->nkeys >= bt->mindeg) )

521 {

522 // case 3a (with next sibling)

523 // Symmetric with the above

524

525 DEBUG_BLOCK( printf("remove: case 3a.2\n"); )

526 btree_mem_node_add_key(bt, c, node->key[i+1], node->data[i+1]);

527

528 node->key[i+1] = next->key[0];

529 node->data[i+1] = next->data[0];

530 for (int j = 0; j < next->nkeys - 1; j++)

531 {

532 next->key[j] = next->key[j+1];

533 next->data[j] = next->data[j+1];

534 }

535

536 if (! next->leaf)

537 {

538 c->child[c->nkeys] = next->child[0];

539 for (int j = 0; j < next->nkeys; j++)

540 next->child[j] = next->child[j+1];

541 }

542

543 next->nkeys--;

544

545 }

546 else

547 {

548 // case 3b

549 DEBUG_BLOCK( printf("remove: case 3b\n"); )

550 // printf("=====\n"); btree_mem_node_dump(node, printit, 0); printf("=====\n");

551 // printf("node %p i %d\n", node, i); fflush(stdout);

552 // printf("adding %d to %p\n", *((int*)node->key[i+1]), (next ? next : prev)); fflush(stdout);

553 if (next)

554 btree_mem_node_merge(c, next);

555 else

556 btree_mem_node_merge(prev, c);

557

558 btree_mem_node_add_key(bt, (next ? c : prev), node->key[i+1], node->data[i+1]);

559

560 btree_mem_node_remove_key(node, i+1);

561

562 if (next)

563 {

564 for (int j = i+2; j <= node->nkeys+1; j++)

565 node->child[j] = node->child[j+1];

566 btree_mem_node_delete(next);

567 }

568 else

569 {

570 for (int j = i; j <= node->nkeys+1; j++)

571 node->child[j] = node->child[j+1];

572 btree_mem_node_delete(c);

573 c = prev;

574 }

575 }

576 }

577 return btree_mem_node_remove(bt, c, key, key_value, data_value);

578 }

579 }

580

581 ////////////////////////////////////////////////////////////////////////////////

582 // Assumption: node is not full

583 // Assumption: key is not already in node

584 void

585 btree_mem_node_add_key(struct btree_mem * bt, struct btree_mem_node * node, void * key, void * data)

586 {

587 int i = node->nkeys;

588 while ( (i > 0) && (bt->cmp(key, node->key[i-1]) < 0) )

589 i--;

590

591 for (int j = node->nkeys - 1; j >= i; j--)

592 {

593 node->key[j+1] = node->key[j];

594 node->data[j+1] = node->data[j];

595 }

596

597 node->key[i] = key;

598 node->data[i] = data;

599 node->nkeys++;

600 }

601

602 ////////////////////////////////////////////////////////////////////////////////

603 // Assumption: node has at least mindeg keys.

604 // Does not remove any children.

605 void *

606 btree_mem_node_remove_key(struct btree_mem_node * node, int i)

607 {

608 void * data = node->key[i];

609 for (int j = i; j < node->nkeys-1; j++)

610 {

611 node->key[j] = node->key[j+1];

612 node->data[j] = node->data[j+1];

613 }

614 node->nkeys--;

615 return data;

616 }

617

618 ////////////////////////////////////////////////////////////////////////////////

619 // Return the node of the lowest valued key of the subtree rooted at node

620 struct btree_mem_node *

621 btree_mem_node_find_prev(struct btree_mem_node * node)

622 {

623 if (0 == node->nkeys)

624 return NULL;

625

626 if (node->leaf)

627 return node;

628

629 return btree_mem_node_find_prev(node->child[0]);

630 }

631

632 ////////////////////////////////////////////////////////////////////////////////

633 // Return the node of the highest valued key of the subtree rooted at node

634 struct btree_mem_node *

635 btree_mem_node_find_next(struct btree_mem_node * node)

636 {

637 if (0 == node->nkeys)

638 return NULL;

639

640 if (node->leaf)

641 return node->key[node->nkeys-1];

642

643 return btree_mem_node_find_next(node->child[node->nkeys]);

644 }

645

646 /////////////////////////////////////////////////////////////////////////////////

647 // move all keys/data/children from node b into node a

648 // Assumption: all keys in b come after the keys in a

649 void

650 btree_mem_node_merge(struct btree_mem_node * a, struct btree_mem_node * b)

651 {

652 int i = a->nkeys;

653 int j = 0;

654 for (; j < b->nkeys; i++, j++)

655 {

656 a->key[i] = b->key[j];

657 a->data[i] = b->data[j];

658 }

659

660 if (! a->leaf)

661 {

662 for (i = a->nkeys + 1 , j = 0; j <= b->nkeys; i++, j++)

663 a->child[i] = b->child[j];

664 }

665

666 a->nkeys += b->nkeys;

667 b->nkeys = 0;

668 }

669

670 /////////////////////////////////////////////////////////////////////////////////

671 #ifdef DEBUG

672 void

673 btree_mem_node_print_keys(struct btree_mem_node * node)

674 {

675 printf("node: %p nkeys %10d keys: ", node, node->nkeys);

676 for (int i = 0; i < node->nkeys; i++)

677 printf("%d ", *((int *) node->key[i]));

678 printf("\n");

679 }

680 #endif

681

Mercurial > data_structures

view src/btree_mem.c @ 23:36018adade6d