+ assert(mc->mc_flags & C_INITIALIZED);
+
+ mp = mc->mc_pg[mc->mc_top];
+
+ if (mc->mc_db->md_flags & MDB_DUPSORT) {
+ leaf = NODEPTR(mp, mc->mc_ki[mc->mc_top]);
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ if (op == MDB_NEXT || op == MDB_NEXT_DUP) {
+ rc = mdb_cursor_next(&mc->mc_xcursor->mx_cursor, data, NULL, MDB_NEXT);
+ if (op != MDB_NEXT || rc == MDB_SUCCESS)
+ return rc;
+ }
+ } else {
+ mc->mc_xcursor->mx_cursor.mc_flags &= ~C_INITIALIZED;
+ if (op == MDB_NEXT_DUP)
+ return MDB_NOTFOUND;
+ }
+ }
+
+ DPRINTF("cursor_next: top page is %zu in cursor %p", mp->mp_pgno, (void *) mc);
+
+ if (mc->mc_ki[mc->mc_top] + 1u >= NUMKEYS(mp)) {
+ DPUTS("=====> move to next sibling page");
+ if (mdb_cursor_sibling(mc, 1) != MDB_SUCCESS) {
+ mc->mc_flags |= C_EOF;
+ mc->mc_flags &= ~C_INITIALIZED;
+ return MDB_NOTFOUND;
+ }
+ mp = mc->mc_pg[mc->mc_top];
+ DPRINTF("next page is %zu, key index %u", mp->mp_pgno, mc->mc_ki[mc->mc_top]);
+ } else
+ mc->mc_ki[mc->mc_top]++;
+
+ DPRINTF("==> cursor points to page %zu with %u keys, key index %u",
+ mp->mp_pgno, NUMKEYS(mp), mc->mc_ki[mc->mc_top]);
+
+ if (IS_LEAF2(mp)) {
+ key->mv_size = mc->mc_db->md_pad;
+ key->mv_data = LEAF2KEY(mp, mc->mc_ki[mc->mc_top], key->mv_size);
+ return MDB_SUCCESS;
+ }
+
+ assert(IS_LEAF(mp));
+ leaf = NODEPTR(mp, mc->mc_ki[mc->mc_top]);
+
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ mdb_xcursor_init1(mc, leaf);
+ }
+ if (data) {
+ if ((rc = mdb_node_read(mc->mc_txn, leaf, data) != MDB_SUCCESS))
+ return rc;
+
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ rc = mdb_cursor_first(&mc->mc_xcursor->mx_cursor, data, NULL);
+ if (rc != MDB_SUCCESS)
+ return rc;
+ }
+ }
+
+ MDB_SET_KEY(leaf, key);
+ return MDB_SUCCESS;
+}
+
+/** Move the cursor to the previous data item. */
+static int
+mdb_cursor_prev(MDB_cursor *mc, MDB_val *key, MDB_val *data, MDB_cursor_op op)
+{
+ MDB_page *mp;
+ MDB_node *leaf;
+ int rc;
+
+ assert(mc->mc_flags & C_INITIALIZED);
+
+ mp = mc->mc_pg[mc->mc_top];
+
+ if (mc->mc_db->md_flags & MDB_DUPSORT) {
+ leaf = NODEPTR(mp, mc->mc_ki[mc->mc_top]);
+ if (op == MDB_PREV || op == MDB_PREV_DUP) {
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ rc = mdb_cursor_prev(&mc->mc_xcursor->mx_cursor, data, NULL, MDB_PREV);
+ if (op != MDB_PREV || rc == MDB_SUCCESS)
+ return rc;
+ } else {
+ mc->mc_xcursor->mx_cursor.mc_flags &= ~C_INITIALIZED;
+ if (op == MDB_PREV_DUP)
+ return MDB_NOTFOUND;
+ }
+ }
+ }
+
+ DPRINTF("cursor_prev: top page is %zu in cursor %p", mp->mp_pgno, (void *) mc);
+
+ if (mc->mc_ki[mc->mc_top] == 0) {
+ DPUTS("=====> move to prev sibling page");
+ if (mdb_cursor_sibling(mc, 0) != MDB_SUCCESS) {
+ mc->mc_flags &= ~C_INITIALIZED;
+ return MDB_NOTFOUND;
+ }
+ mp = mc->mc_pg[mc->mc_top];
+ mc->mc_ki[mc->mc_top] = NUMKEYS(mp) - 1;
+ DPRINTF("prev page is %zu, key index %u", mp->mp_pgno, mc->mc_ki[mc->mc_top]);
+ } else
+ mc->mc_ki[mc->mc_top]--;
+
+ mc->mc_flags &= ~C_EOF;
+
+ DPRINTF("==> cursor points to page %zu with %u keys, key index %u",
+ mp->mp_pgno, NUMKEYS(mp), mc->mc_ki[mc->mc_top]);
+
+ if (IS_LEAF2(mp)) {
+ key->mv_size = mc->mc_db->md_pad;
+ key->mv_data = LEAF2KEY(mp, mc->mc_ki[mc->mc_top], key->mv_size);
+ return MDB_SUCCESS;
+ }
+
+ assert(IS_LEAF(mp));
+ leaf = NODEPTR(mp, mc->mc_ki[mc->mc_top]);
+
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ mdb_xcursor_init1(mc, leaf);
+ }
+ if (data) {
+ if ((rc = mdb_node_read(mc->mc_txn, leaf, data) != MDB_SUCCESS))
+ return rc;
+
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ rc = mdb_cursor_last(&mc->mc_xcursor->mx_cursor, data, NULL);
+ if (rc != MDB_SUCCESS)
+ return rc;
+ }
+ }
+
+ MDB_SET_KEY(leaf, key);
+ return MDB_SUCCESS;
+}
+
+/** Set the cursor on a specific data item. */
+static int
+mdb_cursor_set(MDB_cursor *mc, MDB_val *key, MDB_val *data,
+ MDB_cursor_op op, int *exactp)
+{
+ int rc;
+ MDB_page *mp;
+ MDB_node *leaf;
+ DKBUF;
+
+ assert(mc);
+ assert(key);
+ assert(key->mv_size > 0);
+
+ /* See if we're already on the right page */
+ if (mc->mc_flags & C_INITIALIZED) {
+ MDB_val nodekey;
+
+ mp = mc->mc_pg[mc->mc_top];
+ if (!NUMKEYS(mp)) {
+ mc->mc_ki[mc->mc_top] = 0;
+ return MDB_NOTFOUND;
+ }
+ if (mp->mp_flags & P_LEAF2) {
+ nodekey.mv_size = mc->mc_db->md_pad;
+ nodekey.mv_data = LEAF2KEY(mp, 0, nodekey.mv_size);
+ } else {
+ leaf = NODEPTR(mp, 0);
+ MDB_SET_KEY(leaf, &nodekey);
+ }
+ rc = mc->mc_dbx->md_cmp(key, &nodekey);
+ if (rc == 0) {
+ /* Probably happens rarely, but first node on the page
+ * was the one we wanted.
+ */
+ mc->mc_ki[mc->mc_top] = 0;
+ leaf = NODEPTR(mp, 0);
+ if (exactp)
+ *exactp = 1;
+ goto set1;
+ }
+ if (rc > 0) {
+ unsigned int i;
+ unsigned int nkeys = NUMKEYS(mp);
+ if (nkeys > 1) {
+ if (mp->mp_flags & P_LEAF2) {
+ nodekey.mv_data = LEAF2KEY(mp,
+ nkeys-1, nodekey.mv_size);
+ } else {
+ leaf = NODEPTR(mp, nkeys-1);
+ MDB_SET_KEY(leaf, &nodekey);
+ }
+ rc = mc->mc_dbx->md_cmp(key, &nodekey);
+ if (rc == 0) {
+ /* last node was the one we wanted */
+ mc->mc_ki[mc->mc_top] = nkeys-1;
+ leaf = NODEPTR(mp, nkeys-1);
+ if (exactp)
+ *exactp = 1;
+ goto set1;
+ }
+ if (rc < 0) {
+ /* This is definitely the right page, skip search_page */
+ rc = 0;
+ goto set2;
+ }
+ }
+ /* If any parents have right-sibs, search.
+ * Otherwise, there's nothing further.
+ */
+ for (i=0; i<mc->mc_top; i++)
+ if (mc->mc_ki[i] <
+ NUMKEYS(mc->mc_pg[i])-1)
+ break;
+ if (i == mc->mc_top) {
+ /* There are no other pages */
+ mc->mc_ki[mc->mc_top] = nkeys;
+ return MDB_NOTFOUND;
+ }
+ }
+ if (!mc->mc_top) {
+ /* There are no other pages */
+ mc->mc_ki[mc->mc_top] = 0;
+ return MDB_NOTFOUND;
+ }
+ }
+
+ rc = mdb_page_search(mc, key, 0);
+ if (rc != MDB_SUCCESS)
+ return rc;
+
+ mp = mc->mc_pg[mc->mc_top];
+ assert(IS_LEAF(mp));
+
+set2:
+ leaf = mdb_node_search(mc, key, exactp);
+ if (exactp != NULL && !*exactp) {
+ /* MDB_SET specified and not an exact match. */
+ return MDB_NOTFOUND;
+ }
+
+ if (leaf == NULL) {
+ DPUTS("===> inexact leaf not found, goto sibling");
+ if ((rc = mdb_cursor_sibling(mc, 1)) != MDB_SUCCESS)
+ return rc; /* no entries matched */
+ mp = mc->mc_pg[mc->mc_top];
+ assert(IS_LEAF(mp));
+ leaf = NODEPTR(mp, 0);
+ }
+
+set1:
+ mc->mc_flags |= C_INITIALIZED;
+ mc->mc_flags &= ~C_EOF;
+
+ if (IS_LEAF2(mp)) {
+ key->mv_size = mc->mc_db->md_pad;
+ key->mv_data = LEAF2KEY(mp, mc->mc_ki[mc->mc_top], key->mv_size);
+ return MDB_SUCCESS;
+ }
+
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ mdb_xcursor_init1(mc, leaf);
+ }
+ if (data) {
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ if (op == MDB_SET || op == MDB_SET_RANGE) {
+ rc = mdb_cursor_first(&mc->mc_xcursor->mx_cursor, data, NULL);
+ } else {
+ int ex2, *ex2p;
+ if (op == MDB_GET_BOTH) {
+ ex2p = &ex2;
+ ex2 = 0;
+ } else {
+ ex2p = NULL;
+ }
+ rc = mdb_cursor_set(&mc->mc_xcursor->mx_cursor, data, NULL, MDB_SET_RANGE, ex2p);
+ if (rc != MDB_SUCCESS)
+ return rc;
+ }
+ } else if (op == MDB_GET_BOTH || op == MDB_GET_BOTH_RANGE) {
+ MDB_val d2;
+ if ((rc = mdb_node_read(mc->mc_txn, leaf, &d2)) != MDB_SUCCESS)
+ return rc;
+ rc = mc->mc_dbx->md_dcmp(data, &d2);
+ if (rc) {
+ if (op == MDB_GET_BOTH || rc > 0)
+ return MDB_NOTFOUND;
+ }
+
+ } else {
+ if (mc->mc_xcursor)
+ mc->mc_xcursor->mx_cursor.mc_flags &= ~C_INITIALIZED;
+ if ((rc = mdb_node_read(mc->mc_txn, leaf, data)) != MDB_SUCCESS)
+ return rc;
+ }
+ }
+
+ /* The key already matches in all other cases */
+ if (op == MDB_SET_RANGE)
+ MDB_SET_KEY(leaf, key);
+ DPRINTF("==> cursor placed on key [%s]", DKEY(key));
+
+ return rc;
+}
+
+/** Move the cursor to the first item in the database. */
+static int
+mdb_cursor_first(MDB_cursor *mc, MDB_val *key, MDB_val *data)
+{
+ int rc;
+ MDB_node *leaf;
+
+ if (!(mc->mc_flags & C_INITIALIZED) || mc->mc_top) {
+ rc = mdb_page_search(mc, NULL, 0);
+ if (rc != MDB_SUCCESS)
+ return rc;
+ }
+ assert(IS_LEAF(mc->mc_pg[mc->mc_top]));
+
+ leaf = NODEPTR(mc->mc_pg[mc->mc_top], 0);
+ mc->mc_flags |= C_INITIALIZED;
+ mc->mc_flags &= ~C_EOF;
+
+ mc->mc_ki[mc->mc_top] = 0;
+
+ if (IS_LEAF2(mc->mc_pg[mc->mc_top])) {
+ key->mv_size = mc->mc_db->md_pad;
+ key->mv_data = LEAF2KEY(mc->mc_pg[mc->mc_top], 0, key->mv_size);
+ return MDB_SUCCESS;
+ }
+
+ if (data) {
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ mdb_xcursor_init1(mc, leaf);
+ rc = mdb_cursor_first(&mc->mc_xcursor->mx_cursor, data, NULL);
+ if (rc)
+ return rc;
+ } else {
+ if (mc->mc_xcursor)
+ mc->mc_xcursor->mx_cursor.mc_flags &= ~C_INITIALIZED;
+ if ((rc = mdb_node_read(mc->mc_txn, leaf, data)) != MDB_SUCCESS)
+ return rc;
+ }
+ }
+ MDB_SET_KEY(leaf, key);
+ return MDB_SUCCESS;
+}
+
+/** Move the cursor to the last item in the database. */
+static int
+mdb_cursor_last(MDB_cursor *mc, MDB_val *key, MDB_val *data)
+{
+ int rc;
+ MDB_node *leaf;
+ MDB_val lkey;
+
+ lkey.mv_size = MAXKEYSIZE+1;
+ lkey.mv_data = NULL;
+
+ if (!(mc->mc_flags & C_INITIALIZED) || mc->mc_top) {
+ rc = mdb_page_search(mc, &lkey, 0);
+ if (rc != MDB_SUCCESS)
+ return rc;
+ }
+ assert(IS_LEAF(mc->mc_pg[mc->mc_top]));
+
+ leaf = NODEPTR(mc->mc_pg[mc->mc_top], NUMKEYS(mc->mc_pg[mc->mc_top])-1);
+ mc->mc_flags |= C_INITIALIZED;
+ mc->mc_flags &= ~C_EOF;
+
+ mc->mc_ki[mc->mc_top] = NUMKEYS(mc->mc_pg[mc->mc_top]) - 1;
+
+ if (IS_LEAF2(mc->mc_pg[mc->mc_top])) {
+ key->mv_size = mc->mc_db->md_pad;
+ key->mv_data = LEAF2KEY(mc->mc_pg[mc->mc_top], mc->mc_ki[mc->mc_top], key->mv_size);
+ return MDB_SUCCESS;
+ }
+
+ if (data) {
+ if (F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ mdb_xcursor_init1(mc, leaf);
+ rc = mdb_cursor_last(&mc->mc_xcursor->mx_cursor, data, NULL);
+ if (rc)
+ return rc;
+ } else {
+ if (mc->mc_xcursor)
+ mc->mc_xcursor->mx_cursor.mc_flags &= ~C_INITIALIZED;
+ if ((rc = mdb_node_read(mc->mc_txn, leaf, data)) != MDB_SUCCESS)
+ return rc;
+ }
+ }
+
+ MDB_SET_KEY(leaf, key);
+ return MDB_SUCCESS;
+}
+
+int
+mdb_cursor_get(MDB_cursor *mc, MDB_val *key, MDB_val *data,
+ MDB_cursor_op op)
+{
+ int rc;
+ int exact = 0;
+
+ assert(mc);
+
+ switch (op) {
+ case MDB_GET_BOTH:
+ case MDB_GET_BOTH_RANGE:
+ if (data == NULL || mc->mc_xcursor == NULL) {
+ rc = EINVAL;
+ break;
+ }
+ /* FALLTHRU */
+ case MDB_SET:
+ case MDB_SET_RANGE:
+ if (key == NULL || key->mv_size == 0 || key->mv_size > MAXKEYSIZE) {
+ rc = EINVAL;
+ } else if (op == MDB_SET_RANGE)
+ rc = mdb_cursor_set(mc, key, data, op, NULL);
+ else
+ rc = mdb_cursor_set(mc, key, data, op, &exact);
+ break;
+ case MDB_GET_MULTIPLE:
+ if (data == NULL ||
+ !(mc->mc_db->md_flags & MDB_DUPFIXED) ||
+ !(mc->mc_flags & C_INITIALIZED)) {
+ rc = EINVAL;
+ break;
+ }
+ rc = MDB_SUCCESS;
+ if (!(mc->mc_xcursor->mx_cursor.mc_flags & C_INITIALIZED) ||
+ (mc->mc_xcursor->mx_cursor.mc_flags & C_EOF))
+ break;
+ goto fetchm;
+ case MDB_NEXT_MULTIPLE:
+ if (data == NULL ||
+ !(mc->mc_db->md_flags & MDB_DUPFIXED)) {
+ rc = EINVAL;
+ break;
+ }
+ if (!(mc->mc_flags & C_INITIALIZED))
+ rc = mdb_cursor_first(mc, key, data);
+ else
+ rc = mdb_cursor_next(mc, key, data, MDB_NEXT_DUP);
+ if (rc == MDB_SUCCESS) {
+ if (mc->mc_xcursor->mx_cursor.mc_flags & C_INITIALIZED) {
+ MDB_cursor *mx;
+fetchm:
+ mx = &mc->mc_xcursor->mx_cursor;
+ data->mv_size = NUMKEYS(mx->mc_pg[mx->mc_top]) *
+ mx->mc_db->md_pad;
+ data->mv_data = METADATA(mx->mc_pg[mx->mc_top]);
+ mx->mc_ki[mx->mc_top] = NUMKEYS(mx->mc_pg[mx->mc_top])-1;
+ } else {
+ rc = MDB_NOTFOUND;
+ }
+ }
+ break;
+ case MDB_NEXT:
+ case MDB_NEXT_DUP:
+ case MDB_NEXT_NODUP:
+ if (!(mc->mc_flags & C_INITIALIZED))
+ rc = mdb_cursor_first(mc, key, data);
+ else
+ rc = mdb_cursor_next(mc, key, data, op);
+ break;
+ case MDB_PREV:
+ case MDB_PREV_DUP:
+ case MDB_PREV_NODUP:
+ if (!(mc->mc_flags & C_INITIALIZED) || (mc->mc_flags & C_EOF))
+ rc = mdb_cursor_last(mc, key, data);
+ else
+ rc = mdb_cursor_prev(mc, key, data, op);
+ break;
+ case MDB_FIRST:
+ rc = mdb_cursor_first(mc, key, data);
+ break;
+ case MDB_FIRST_DUP:
+ if (data == NULL ||
+ !(mc->mc_db->md_flags & MDB_DUPSORT) ||
+ !(mc->mc_flags & C_INITIALIZED) ||
+ !(mc->mc_xcursor->mx_cursor.mc_flags & C_INITIALIZED)) {
+ rc = EINVAL;
+ break;
+ }
+ rc = mdb_cursor_first(&mc->mc_xcursor->mx_cursor, data, NULL);
+ break;
+ case MDB_LAST:
+ rc = mdb_cursor_last(mc, key, data);
+ break;
+ case MDB_LAST_DUP:
+ if (data == NULL ||
+ !(mc->mc_db->md_flags & MDB_DUPSORT) ||
+ !(mc->mc_flags & C_INITIALIZED) ||
+ !(mc->mc_xcursor->mx_cursor.mc_flags & C_INITIALIZED)) {
+ rc = EINVAL;
+ break;
+ }
+ rc = mdb_cursor_last(&mc->mc_xcursor->mx_cursor, data, NULL);
+ break;
+ default:
+ DPRINTF("unhandled/unimplemented cursor operation %u", op);
+ rc = EINVAL;
+ break;
+ }
+
+ return rc;