Lines Matching defs:bt
92 #define PAGEFILL(bt, mp) (1000 * ((bt)->head.psize - PAGEHDRSZ - SIZELEFT(mp)) / \
93 ((bt)->head.psize - PAGEHDRSZ))
142 static struct mpage *mpage_lookup(struct btree *bt, pgno_t pgno);
143 static void mpage_add(struct btree *bt, struct mpage *mp);
145 static void mpage_del(struct btree *bt, struct mpage *mp);
146 static void mpage_flush(struct btree *bt);
147 static struct mpage *mpage_copy(struct btree *bt, struct mpage *mp);
148 static void mpage_prune(struct btree *bt);
149 static void mpage_dirty(struct btree *bt, struct mpage *mp);
150 static struct mpage *mpage_touch(struct btree *bt, struct mpage *mp);
168 struct btree *bt;
194 struct btree *bt; /* btree is ref'd */
231 static int btree_read_page(struct btree *bt, pgno_t pgno,
233 static struct mpage *btree_get_mpage(struct btree *bt, pgno_t pgno);
234 static int btree_search_page_root(struct btree *bt,
238 static int btree_search_page(struct btree *bt,
243 static int btree_write_header(struct btree *bt, int fd);
244 static int btree_read_header(struct btree *bt);
246 static int btree_read_meta(struct btree *bt, pgno_t *p_next);
247 static int btree_write_meta(struct btree *bt, pgno_t root,
249 static void btree_ref(struct btree *bt);
251 static struct node *btree_search_node(struct btree *bt, struct mpage *mp,
253 static int btree_add_node(struct btree *bt, struct mpage *mp,
256 static void btree_del_node(struct btree *bt, struct mpage *mp,
258 static int btree_read_data(struct btree *bt, struct mpage *mp,
261 static int btree_rebalance(struct btree *bt, struct mpage *mp);
262 static int btree_update_key(struct btree *bt, struct mpage *mp,
264 static int btree_adjust_prefix(struct btree *bt,
266 static int btree_move_node(struct btree *bt, struct mpage *src,
268 static int btree_merge(struct btree *bt, struct mpage *src,
270 static int btree_split(struct btree *bt, struct mpage **mpp,
273 static struct mpage *btree_new_page(struct btree *bt, uint32_t flags);
274 static int btree_write_overflow_data(struct btree *bt,
281 static int bt_set_key(struct btree *bt, struct mpage *mp,
291 static void bt_reduce_separator(struct btree *bt, struct node *min,
293 static void remove_prefix(struct btree *bt, struct btval *key,
295 static void expand_prefix(struct btree *bt, struct mpage *mp,
297 static void concat_prefix(struct btree *bt, char *s1, size_t n1,
299 static void common_prefix(struct btree *bt, struct btkey *min,
301 static void find_common_prefix(struct btree *bt, struct mpage *mp);
303 static size_t bt_leaf_size(struct btree *bt, struct btval *key,
305 static size_t bt_branch_size(struct btree *bt, struct btval *key);
307 static pgno_t btree_compact_tree(struct btree *bt, pgno_t pgno,
356 btree_cmp(struct btree *bt, const struct btval *a, const struct btval *b)
358 return bt->cmp(a, b);
362 common_prefix(struct btree *bt, struct btkey *min, struct btkey *max,
374 if (F_ISSET(bt->flags, BT_REVERSEKEY)) {
408 remove_prefix(struct btree *bt, struct btval *key, size_t pfxlen)
410 if (pfxlen == 0 || bt->cmp != NULL)
417 if (!F_ISSET(bt->flags, BT_REVERSEKEY))
422 expand_prefix(struct btree *bt, struct mpage *mp, indx_t indx,
429 concat_prefix(bt, mp->prefix.str, mp->prefix.len,
434 bt_cmp(struct btree *bt, const struct btval *key1, const struct btval *key2,
437 if (F_ISSET(bt->flags, BT_REVERSEKEY))
468 mpage_lookup(struct btree *bt, pgno_t pgno)
473 mp = RB_FIND(page_cache, bt->page_cache, &find);
475 bt->stat.hits++;
477 TAILQ_REMOVE(bt->lru_queue, mp, lru_next);
478 TAILQ_INSERT_TAIL(bt->lru_queue, mp, lru_next);
484 mpage_add(struct btree *bt, struct mpage *mp)
486 assert(RB_INSERT(page_cache, bt->page_cache, mp) == NULL);
487 bt->stat.cache_size++;
488 TAILQ_INSERT_TAIL(bt->lru_queue, mp, lru_next);
501 mpage_del(struct btree *bt, struct mpage *mp)
503 assert(RB_REMOVE(page_cache, bt->page_cache, mp) == mp);
504 assert(bt->stat.cache_size > 0);
505 bt->stat.cache_size--;
506 TAILQ_REMOVE(bt->lru_queue, mp, lru_next);
510 mpage_flush(struct btree *bt)
514 while ((mp = RB_MIN(page_cache, bt->page_cache)) != NULL) {
515 mpage_del(bt, mp);
521 mpage_copy(struct btree *bt, struct mpage *mp)
527 if ((copy->page = malloc(bt->head.psize)) == NULL) {
531 bcopy(mp->page, copy->page, bt->head.psize);
545 mpage_prune(struct btree *bt)
549 for (mp = TAILQ_FIRST(bt->lru_queue); mp; mp = next) {
550 if (bt->stat.cache_size <= bt->stat.max_cache)
554 mpage_del(bt, mp);
563 mpage_dirty(struct btree *bt, struct mpage *mp)
565 assert(bt != NULL);
566 assert(bt->txn != NULL);
570 SIMPLEQ_INSERT_TAIL(bt->txn->dirty_queue, mp, next);
577 mpage_touch(struct btree *bt, struct mpage *mp)
579 assert(bt != NULL);
580 assert(bt->txn != NULL);
584 DPRINTF("touching page %u -> %u", mp->pgno, bt->txn->next_pgno);
586 mpage_del(bt, mp);
588 if ((mp = mpage_copy(bt, mp)) == NULL)
591 mp->pgno = mp->page->pgno = bt->txn->next_pgno++;
592 mpage_dirty(bt, mp);
593 mpage_add(bt, mp);
605 btree_read_page(struct btree *bt, pgno_t pgno, struct page *page)
610 bt->stat.reads++;
611 if ((rc = pread(bt->fd, page, bt->head.psize, (off_t)pgno*bt->head.psize)) == 0) {
615 } else if (rc != (ssize_t)bt->head.psize) {
634 btree_sync(struct btree *bt)
636 if (!F_ISSET(bt->flags, BT_NOSYNC))
637 return fsync(bt->fd);
642 btree_txn_begin(struct btree *bt, int rdonly)
646 if (!rdonly && bt->txn != NULL) {
668 if (flock(bt->fd, LOCK_EX | LOCK_NB) != 0) {
675 bt->txn = txn;
678 txn->bt = bt;
679 btree_ref(bt);
681 if (btree_read_meta(bt, &txn->next_pgno) != BT_SUCCESS) {
686 txn->root = bt->meta.root;
687 DPRINTF("begin transaction on btree %p, root page %u", bt, txn->root);
696 struct btree *bt;
701 bt = txn->bt;
702 DPRINTF("abort transaction on btree %p, root page %u", bt, txn->root);
710 mpage_del(bt, mp);
716 txn->bt->txn = NULL;
717 if (flock(txn->bt->fd, LOCK_UN) != 0) {
719 txn->bt->fd, strerror(errno));
724 btree_close(txn->bt);
735 struct btree *bt;
739 assert(txn->bt != NULL);
741 bt = txn->bt;
750 if (txn != bt->txn) {
767 if (F_ISSET(bt->flags, BT_FIXPADDING)) {
768 size = lseek(bt->fd, 0, SEEK_END);
769 size += bt->head.psize - (size % bt->head.psize);
771 if (ftruncate(bt->fd, size) != 0) {
776 bt->flags &= ~BT_FIXPADDING;
780 bt, txn->root);
789 iov[n].iov_len = bt->head.psize;
801 rc = writev(bt->fd, iov, n);
802 if (rc != (ssize_t)bt->head.psize*n) {
822 if (btree_sync(bt) != 0 ||
823 btree_write_meta(bt, txn->root, 0) != BT_SUCCESS ||
824 btree_sync(bt) != 0) {
830 mpage_prune(bt);
837 btree_write_header(struct btree *bt, int fd)
846 assert(bt != NULL);
864 bcopy(h, &bt->head, sizeof(*h));
866 rc = write(fd, p, bt->head.psize);
868 if (rc != (ssize_t)bt->head.psize) {
878 btree_read_header(struct btree *bt)
885 assert(bt != NULL);
890 if ((rc = pread(bt->fd, page, PAGESIZE, 0)) == 0) {
917 bt->head.version, BT_VERSION);
922 bcopy(h, &bt->head, sizeof(*h));
927 btree_write_meta(struct btree *bt, pgno_t root, unsigned int flags)
935 assert(bt != NULL);
936 assert(bt->txn != NULL);
938 if ((mp = btree_new_page(bt, P_META)) == NULL)
941 bt->meta.prev_meta = bt->meta.root;
942 bt->meta.root = root;
943 bt->meta.flags = flags;
944 bt->meta.created_at = time(0);
945 bt->meta.revisions++;
946 SHA1((unsigned char *)&bt->meta, METAHASHLEN, bt->meta.hash);
950 bcopy(&bt->meta, meta, sizeof(*meta));
952 rc = write(bt->fd, mp->page, bt->head.psize);
954 SIMPLEQ_REMOVE_HEAD(bt->txn->dirty_queue, next);
955 if (rc != (ssize_t)bt->head.psize) {
961 if ((bt->size = lseek(bt->fd, 0, SEEK_END)) == -1) {
963 bt->size = 0;
1001 btree_read_meta(struct btree *bt, pgno_t *p_next)
1008 assert(bt != NULL);
1010 if ((size = lseek(bt->fd, 0, SEEK_END)) == -1)
1015 if (size < bt->size) {
1021 if (size == bt->head.psize) { /* there is only the header */
1027 next_pgno = size / bt->head.psize;
1036 if (size % bt->head.psize != 0) {
1038 bt->flags |= BT_FIXPADDING;
1045 if (size == bt->size) {
1047 if (F_ISSET(bt->meta.flags, BT_TOMBSTONE)) {
1054 bt->size = size;
1057 if ((mp = btree_get_mpage(bt, meta_pgno)) == NULL)
1068 bcopy(meta, &bt->meta, sizeof(bt->meta));
1085 struct btree *bt;
1092 if ((bt = calloc(1, sizeof(*bt))) == NULL)
1094 bt->fd = fd;
1095 bt->flags = flags;
1096 bt->flags &= ~BT_FIXPADDING;
1097 bt->ref = 1;
1098 bt->meta.root = P_INVALID;
1100 if ((bt->page_cache = calloc(1, sizeof(*bt->page_cache))) == NULL)
1102 bt->stat.max_cache = BT_MAXCACHE_DEF;
1103 RB_INIT(bt->page_cache);
1105 if ((bt->lru_queue = calloc(1, sizeof(*bt->lru_queue))) == NULL)
1107 TAILQ_INIT(bt->lru_queue);
1109 if (btree_read_header(bt) != 0) {
1113 btree_write_header(bt, bt->fd);
1116 if (btree_read_meta(bt, NULL) != 0)
1120 bt->head.version, bt->head.psize);
1121 DPRINTF("timestamp: %s", ctime(&bt->meta.created_at));
1122 DPRINTF("depth: %u", bt->meta.depth);
1123 DPRINTF("entries: %llu", bt->meta.entries);
1124 DPRINTF("revisions: %u", bt->meta.revisions);
1125 DPRINTF("branch pages: %u", bt->meta.branch_pages);
1126 DPRINTF("leaf pages: %u", bt->meta.leaf_pages);
1127 DPRINTF("overflow pages: %u", bt->meta.overflow_pages);
1128 DPRINTF("root: %u", bt->meta.root);
1129 DPRINTF("previous meta page: %u", bt->meta.prev_meta);
1131 return bt;
1134 free(bt->lru_queue);
1135 free(bt->page_cache);
1136 free(bt);
1144 struct btree *bt;
1154 if ((bt = btree_open_fd(fd, flags)) == NULL)
1157 bt->path = strdup(path);
1158 DPRINTF("opened btree %p", bt);
1161 return bt;
1165 btree_ref(struct btree *bt)
1167 bt->ref++;
1168 DPRINTF("ref is now %d on btree %p", bt->ref, bt);
1172 btree_close(struct btree *bt)
1174 if (bt == NULL)
1177 if (--bt->ref == 0) {
1178 DPRINTF("ref is zero, closing btree %p", bt);
1179 close(bt->fd);
1180 mpage_flush(bt);
1181 free(bt->lru_queue);
1182 free(bt->path);
1183 free(bt->page_cache);
1184 free(bt);
1186 DPRINTF("ref is now %d on btree %p", bt->ref, bt);
1197 btree_search_node(struct btree *bt, struct mpage *mp, struct btval *key,
1224 if (bt->cmp)
1225 rc = bt->cmp(key, &nodekey);
1227 rc = bt_cmp(bt, key, &nodekey, &mp->prefix);
1289 btree_get_mpage(struct btree *bt, pgno_t pgno)
1293 mp = mpage_lookup(bt, pgno);
1297 if ((mp->page = malloc(bt->head.psize)) == NULL) {
1301 if (btree_read_page(bt, pgno, mp->page) != BT_SUCCESS) {
1306 mpage_add(bt, mp);
1314 concat_prefix(struct btree *bt, char *s1, size_t n1, char *s2, size_t n2,
1318 if (F_ISSET(bt->flags, BT_REVERSEKEY)) {
1329 find_common_prefix(struct btree *bt, struct mpage *mp)
1336 if (bt->cmp != NULL)
1358 expand_prefix(bt, lp->parent, lbound, &lprefix);
1359 expand_prefix(bt, up->parent, ubound, &uprefix);
1360 common_prefix(bt, &lprefix, &uprefix, &mp->prefix);
1370 btree_search_page_root(struct btree *bt, struct mpage *root, struct btval *key,
1391 node = btree_search_node(bt, mp, key, &exact, &i);
1410 if ((mp = btree_get_mpage(bt, NODEPGNO(node))) == NULL)
1414 find_common_prefix(bt, mp);
1419 if (modify && (mp = mpage_touch(bt, mp)) == NULL)
1443 btree_search_page(struct btree *bt, struct btree_txn *txn, struct btval *key,
1461 if ((rc = btree_read_meta(bt, NULL)) != BT_SUCCESS)
1463 root = bt->meta.root;
1477 if ((mp = btree_get_mpage(bt, root)) == NULL)
1486 if ((mp = mpage_touch(bt, mp)) == NULL)
1491 return btree_search_page_root(bt, mp, key, cursor, modify, mpp);
1495 btree_read_data(struct btree *bt, struct mpage *mp, struct node *leaf,
1505 max = bt->head.psize - PAGEHDRSZ;
1536 if ((omp = btree_get_mpage(bt, pgno)) == NULL ||
1555 btree_txn_get(struct btree *bt, struct btree_txn *txn,
1566 if (bt != NULL && txn != NULL && bt != txn->bt) {
1571 if (bt == NULL) {
1576 bt = txn->bt;
1584 if ((rc = btree_search_page(bt, txn, key, NULL, 0, &mp)) != BT_SUCCESS)
1587 leaf = btree_search_node(bt, mp, key, &exact, NULL);
1589 rc = btree_read_data(bt, mp, leaf, data);
1595 mpage_prune(bt);
1635 if ((mp = btree_get_mpage(cursor->bt, indx->n_pgno)) == NULL)
1641 find_common_prefix(cursor->bt, mp);
1647 bt_set_key(struct btree *bt, struct mpage *mp, struct node *node,
1658 concat_prefix(bt,
1711 if (data && btree_read_data(cursor->bt, mp, leaf, data) != BT_SUCCESS)
1714 if (bt_set_key(cursor->bt, mp, leaf, key) != 0)
1733 rc = btree_search_page(cursor->bt, cursor->txn, key, cursor, 0, &mp);
1739 leaf = btree_search_node(cursor->bt, mp, key, exactp, &top->ki);
1760 if (data && btree_read_data(cursor->bt, mp, leaf, data) != BT_SUCCESS)
1763 if (bt_set_key(cursor->bt, mp, leaf, key) != 0)
1778 rc = btree_search_page(cursor->bt, cursor->txn, NULL, cursor, 0, &mp);
1787 if (data && btree_read_data(cursor->bt, mp, leaf, data) != BT_SUCCESS)
1790 if (bt_set_key(cursor->bt, mp, leaf, key) != 0)
1835 mpage_prune(cursor->bt);
1841 btree_new_page(struct btree *bt, uint32_t flags)
1845 assert(bt != NULL);
1846 assert(bt->txn != NULL);
1849 bt->txn->next_pgno, bt->head.psize);
1852 if ((mp->page = malloc(bt->head.psize)) == NULL) {
1856 mp->pgno = mp->page->pgno = bt->txn->next_pgno++;
1859 mp->page->upper = bt->head.psize;
1862 bt->meta.branch_pages++;
1864 bt->meta.leaf_pages++;
1866 bt->meta.overflow_pages++;
1868 mpage_add(bt, mp);
1869 mpage_dirty(bt, mp);
1875 bt_leaf_size(struct btree *bt, struct btval *key, struct btval *data)
1880 if (data->size >= bt->head.psize / BT_MINKEYS) {
1889 bt_branch_size(struct btree *bt, struct btval *key)
1894 if (sz >= bt->head.psize / BT_MINKEYS) {
1904 btree_write_overflow_data(struct btree *bt, struct page *p, struct btval *data)
1912 max = bt->head.psize - PAGEHDRSZ;
1920 if ((next = btree_new_page(bt, P_OVERFLOW)) == NULL)
1940 btree_add_node(struct btree *bt, struct mpage *mp, indx_t indx,
1967 } else if (data->size >= bt->head.psize / BT_MINKEYS) {
1972 if ((ofp = btree_new_page(bt, P_OVERFLOW)) == NULL)
2023 if (btree_write_overflow_data(bt, ofp->page,
2033 btree_del_node(struct btree *bt, struct mpage *mp, indx_t indx)
2072 btree_txn_cursor_open(struct btree *bt, struct btree_txn *txn)
2076 if (bt != NULL && txn != NULL && bt != txn->bt) {
2081 if (bt == NULL) {
2086 bt = txn->bt;
2091 cursor->bt = bt;
2093 btree_ref(bt);
2106 btree_close(cursor->bt);
2112 btree_update_key(struct btree *bt, struct mpage *mp, indx_t indx,
2157 btree_adjust_prefix(struct btree *bt, struct mpage *src, int delta)
2172 if (F_ISSET(bt->flags, BT_REVERSEKEY))
2178 if (F_ISSET(bt->flags, BT_REVERSEKEY)) {
2191 if (btree_update_key(bt, src, i, &key) != BT_SUCCESS)
2201 btree_move_node(struct btree *bt, struct mpage *src, indx_t srcindx,
2222 find_common_prefix(bt, src);
2228 if ((mp = btree_get_mpage(bt, NODEPGNO(srcnode))) == NULL)
2232 find_common_prefix(bt, mp);
2237 if ((src = mpage_touch(bt, src)) == NULL ||
2238 (dst = mpage_touch(bt, dst)) == NULL)
2241 find_common_prefix(bt, dst);
2248 common_prefix(bt, &srckey, &dst->prefix, &tmpkey);
2250 if (btree_adjust_prefix(bt, dst,
2261 assert(btree_search_page_root(bt, src, NULL, NULL, 0,
2263 expand_prefix(bt, low, 0, &srckey);
2270 find_common_prefix(bt, src);
2274 concat_prefix(bt, src->prefix.str, src->prefix.len,
2282 remove_prefix(bt, &key, dst->prefix.len);
2285 rc = btree_add_node(bt, dst, dstindx, &key, &data, NODEPGNO(srcnode),
2292 btree_del_node(bt, src, srcindx);
2297 expand_prefix(bt, src, 0, &tmpkey);
2300 remove_prefix(bt, &key, src->parent->prefix.len);
2304 if (btree_update_key(bt, src->parent, src->parent_index,
2312 assert(btree_update_key(bt, src, 0, &nullkey) == BT_SUCCESS);
2316 expand_prefix(bt, dst, 0, &tmpkey);
2319 remove_prefix(bt, &key, dst->parent->prefix.len);
2323 if (btree_update_key(bt, dst->parent, dst->parent_index,
2331 assert(btree_update_key(bt, dst, 0, &nullkey) == BT_SUCCESS);
2338 find_common_prefix(bt, src);
2340 if (btree_adjust_prefix(bt, src,
2346 find_common_prefix(bt, dst);
2348 if (btree_adjust_prefix(bt, dst,
2357 find_common_prefix(bt, mp);
2360 if ((mp = mpage_touch(bt, mp)) == NULL)
2362 if (btree_adjust_prefix(bt, mp,
2372 btree_merge(struct btree *bt, struct mpage *src, struct mpage *dst)
2385 assert(bt->txn != NULL);
2388 if ((src = mpage_touch(bt, src)) == NULL ||
2389 (dst = mpage_touch(bt, dst)) == NULL)
2392 find_common_prefix(bt, src);
2393 find_common_prefix(bt, dst);
2398 common_prefix(bt, &src->prefix, &dst->prefix, &dstpfx);
2400 if (btree_adjust_prefix(bt, dst,
2418 assert(btree_search_page_root(bt, src, NULL, NULL, 0,
2420 expand_prefix(bt, low, 0, &tmpkey);
2424 expand_prefix(bt, src, i, &tmpkey);
2430 remove_prefix(bt, &key, dst->prefix.len);
2433 rc = btree_add_node(bt, dst, NUMKEYS(dst), &key,
2440 dst->pgno, NUMKEYS(dst), (float)PAGEFILL(bt, dst) / 10);
2444 btree_del_node(bt, src->parent, src->parent_index);
2447 if (btree_update_key(bt, src->parent, 0, &key) != BT_SUCCESS)
2451 find_common_prefix(bt, src);
2456 bt->meta.leaf_pages--;
2458 bt->meta.branch_pages--;
2460 return btree_rebalance(bt, src->parent);
2466 btree_rebalance(struct btree *bt, struct mpage *mp)
2474 assert(bt != NULL);
2475 assert(bt->txn != NULL);
2480 mp->pgno, NUMKEYS(mp), (float)PAGEFILL(bt, mp) / 10);
2482 if (PAGEFILL(bt, mp) >= FILL_THRESHOLD) {
2493 bt->txn->root = P_INVALID;
2494 bt->meta.depth--;
2495 bt->meta.leaf_pages--;
2498 bt->txn->root = NODEPGNO(NODEPTR(mp, 0));
2499 if ((root = btree_get_mpage(bt, bt->txn->root)) == NULL)
2502 bt->meta.depth--;
2503 bt->meta.branch_pages--;
2526 if ((neighbor = btree_get_mpage(bt, NODEPGNO(node))) == NULL)
2536 if ((neighbor = btree_get_mpage(bt, NODEPGNO(node))) == NULL)
2545 neighbor->pgno, NUMKEYS(neighbor), (float)PAGEFILL(bt, neighbor) / 10);
2554 if (PAGEFILL(bt, neighbor) >= FILL_THRESHOLD && NUMKEYS(neighbor) >= 2)
2555 return btree_move_node(bt, neighbor, si, mp, di);
2558 return btree_merge(bt, neighbor, mp);
2560 return btree_merge(bt, mp, neighbor);
2565 btree_txn_del(struct btree *bt, struct btree_txn *txn,
2577 if (bt != NULL && txn != NULL && bt != txn->bt) {
2587 if (bt == NULL) {
2592 bt = txn->bt;
2602 if ((txn = btree_txn_begin(bt, 0)) == NULL)
2606 if ((rc = btree_search_page(bt, txn, key, NULL, 1, &mp)) != BT_SUCCESS)
2609 leaf = btree_search_node(bt, mp, key, &exact, &ki);
2616 if (data && (rc = btree_read_data(bt, NULL, leaf, data)) != BT_SUCCESS)
2619 btree_del_node(bt, mp, ki);
2620 bt->meta.entries--;
2621 rc = btree_rebalance(bt, mp);
2632 mpage_prune(bt);
2644 bt_reduce_separator(struct btree *bt, struct node *min, struct btval *sep)
2650 if (F_ISSET(bt->flags, BT_REVERSEKEY)) {
2696 btree_split(struct btree *bt, struct mpage **mpp, unsigned int *newindxp,
2711 assert(bt != NULL);
2712 assert(bt->txn != NULL);
2725 if ((mp->parent = btree_new_page(bt, P_BRANCH)) == NULL)
2728 bt->txn->root = mp->parent->pgno;
2730 bt->meta.depth++;
2733 if (btree_add_node(bt, mp->parent, 0, NULL, NULL,
2741 if ((pright = btree_new_page(bt, mp->page->flags)) == NULL)
2748 if ((copy = malloc(bt->head.psize)) == NULL)
2750 bcopy(mp->page, copy, bt->head.psize);
2752 memset(&mp->page->ptrs, 0, bt->head.psize - PAGEHDRSZ);
2754 mp->page->upper = bt->head.psize;
2764 remove_prefix(bt, &sepkey, mp->prefix.len);
2771 if (IS_LEAF(mp) && bt->cmp == NULL) {
2775 bt_reduce_separator(bt, node, &sepkey);
2779 if (bt->cmp == NULL) {
2781 concat_prefix(bt, mp->prefix.str, mp->prefix.len,
2791 if (SIZELEFT(pright->parent) < bt_branch_size(bt, &sepkey)) {
2792 rc = btree_split(bt, &pright->parent, &pright->parent_index,
2804 remove_prefix(bt, &sepkey, pright->parent->prefix.len);
2805 rc = btree_add_node(bt, pright->parent, pright->parent_index,
2815 find_common_prefix(bt, pright);
2819 find_common_prefix(bt, mp);
2874 remove_prefix(bt, &rkey, pfx_diff);
2876 rc = btree_add_node(bt, p, j, &rkey, &rdata, pgno,flags);
2884 btree_txn_put(struct btree *bt, struct btree_txn *txn,
2896 if (bt != NULL && txn != NULL && bt != txn->bt) {
2906 if (bt == NULL) {
2911 bt = txn->bt;
2924 if ((txn = btree_txn_begin(bt, 0)) == NULL)
2928 rc = btree_search_page(bt, txn, key, NULL, 1, &mp);
2930 leaf = btree_search_node(bt, mp, key, &exact, &ki);
2939 btree_del_node(bt, mp, ki);
2948 if ((mp = btree_new_page(bt, P_LEAF)) == NULL) {
2953 bt->meta.depth++;
2969 if (SIZELEFT(mp) < bt_leaf_size(bt, key, data)) {
2970 rc = btree_split(bt, &mp, &ki, &xkey, data, P_INVALID);
2973 remove_prefix(bt, &xkey, mp->prefix.len);
2974 rc = btree_add_node(bt, mp, ki, &xkey, data, 0, 0);
2980 bt->meta.entries++;
2989 mpage_prune(bt);
2994 btree_compact_tree(struct btree *bt, pgno_t pgno, struct btree *btc)
3005 if ((mp = btree_get_mpage(bt, pgno)) == NULL)
3007 if ((p = malloc(bt->head.psize)) == NULL)
3009 bcopy(mp->page, p, bt->head.psize);
3017 node->n_pgno = btree_compact_tree(bt, node->n_pgno, btc);
3028 next = btree_compact_tree(bt, next, btc);
3039 *pnext = btree_compact_tree(bt, *pnext, btc);
3049 rc = write(btc->fd, p, bt->head.psize);
3051 if (rc != (ssize_t)bt->head.psize)
3053 mpage_prune(bt);
3058 btree_compact(struct btree *bt)
3066 assert(bt != NULL);
3068 DPRINTF("compacting btree %p with path %s", bt, bt->path);
3070 if (bt->path == NULL) {
3075 if ((txn = btree_txn_begin(bt, 0)) == NULL)
3078 if (asprintf(&compact_path, "%s.compact.XXXXXX", bt->path) == -1) {
3091 bcopy(&bt->meta, &btc->meta, sizeof(bt->meta));
3097 if (bt->meta.root != P_INVALID) {
3098 root = btree_compact_tree(bt, bt->meta.root, btc);
3107 DPRINTF("renaming %s to %s", compact_path, bt->path);
3108 if (rename(compact_path, bt->path) != 0)
3114 if (btree_write_meta(bt, P_INVALID, BT_TOMBSTONE) != BT_SUCCESS)
3121 mpage_prune(bt);
3130 mpage_prune(bt);
3137 btree_revert(struct btree *bt)
3139 if (btree_read_meta(bt, NULL) != 0)
3142 DPRINTF("truncating file at page %u", bt->meta.root);
3143 return ftruncate(bt->fd, bt->head.psize * bt->meta.root);
3147 btree_set_cache_size(struct btree *bt, unsigned int cache_size)
3149 bt->stat.max_cache = cache_size;
3153 btree_get_flags(struct btree *bt)
3155 return (bt->flags & ~BT_FIXPADDING);
3159 btree_get_path(struct btree *bt)
3161 return bt->path;
3165 btree_stat(struct btree *bt)
3167 if (bt == NULL)
3170 bt->stat.branch_pages = bt->meta.branch_pages;
3171 bt->stat.leaf_pages = bt->meta.leaf_pages;
3172 bt->stat.overflow_pages = bt->meta.overflow_pages;
3173 bt->stat.revisions = bt->meta.revisions;
3174 bt->stat.depth = bt->meta.depth;
3175 bt->stat.entries = bt->meta.entries;
3176 bt->stat.psize = bt->head.psize;
3177 bt->stat.created_at = bt->meta.created_at;
3179 return &bt->stat;