+ 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;
+}
+
+/** Touch all the pages in the cursor stack.
+ * Makes sure all the pages are writable, before attempting a write operation.
+ * @param[in] mc The cursor to operate on.
+ */
+static int
+mdb_cursor_touch(MDB_cursor *mc)
+{
+ int rc;
+
+ if (mc->mc_dbi > MAIN_DBI && !(*mc->mc_dbflag & DB_DIRTY)) {
+ MDB_cursor mc2;
+ mdb_cursor_init(&mc2, mc->mc_txn, MAIN_DBI, NULL);
+ rc = mdb_page_search(&mc2, &mc->mc_dbx->md_name, 1);
+ if (rc)
+ return rc;
+ *mc->mc_dbflag = DB_DIRTY;
+ }
+ for (mc->mc_top = 0; mc->mc_top < mc->mc_snum; mc->mc_top++) {
+ rc = mdb_page_touch(mc);
+ if (rc)
+ return rc;
+ }
+ mc->mc_top = mc->mc_snum-1;
+ return MDB_SUCCESS;
+}
+
+int
+mdb_cursor_put(MDB_cursor *mc, MDB_val *key, MDB_val *data,
+ unsigned int flags)
+{
+ MDB_node *leaf = NULL;
+ MDB_val xdata, *rdata, dkey;
+ MDB_page *fp;
+ MDB_db dummy;
+ int do_sub = 0;
+ unsigned int mcount = 0;
+ size_t nsize;
+ int rc, rc2;
+ MDB_pagebuf pbuf;
+ char dbuf[MAXKEYSIZE+1];
+ unsigned int nflags;
+ DKBUF;
+
+ if (F_ISSET(mc->mc_txn->mt_flags, MDB_TXN_RDONLY))
+ return EACCES;
+
+ DPRINTF("==> put db %u key [%s], size %zu, data size %zu",
+ mc->mc_dbi, DKEY(key), key ? key->mv_size:0, data->mv_size);
+
+ dkey.mv_size = 0;
+
+ if (flags == MDB_CURRENT) {
+ if (!(mc->mc_flags & C_INITIALIZED))
+ return EINVAL;
+ rc = MDB_SUCCESS;
+ } else if (mc->mc_db->md_root == P_INVALID) {
+ MDB_page *np;
+ /* new database, write a root leaf page */
+ DPUTS("allocating new root leaf page");
+ if ((np = mdb_page_new(mc, P_LEAF, 1)) == NULL) {
+ return ENOMEM;
+ }
+ mc->mc_snum = 0;
+ mdb_cursor_push(mc, np);
+ mc->mc_db->md_root = np->mp_pgno;
+ mc->mc_db->md_depth++;
+ *mc->mc_dbflag = DB_DIRTY;
+ if ((mc->mc_db->md_flags & (MDB_DUPSORT|MDB_DUPFIXED))
+ == MDB_DUPFIXED)
+ np->mp_flags |= P_LEAF2;
+ mc->mc_flags |= C_INITIALIZED;
+ rc = MDB_NOTFOUND;
+ goto top;
+ } else {
+ int exact = 0;
+ MDB_val d2;
+ rc = mdb_cursor_set(mc, key, &d2, MDB_SET, &exact);
+ if ((flags & MDB_NOOVERWRITE) && rc == 0) {
+ DPRINTF("duplicate key [%s]", DKEY(key));
+ *data = d2;
+ return MDB_KEYEXIST;
+ }
+ if (rc && rc != MDB_NOTFOUND)
+ return rc;
+ }
+
+ /* Cursor is positioned, now make sure all pages are writable */
+ rc2 = mdb_cursor_touch(mc);
+ if (rc2)
+ return rc2;
+
+top:
+ /* The key already exists */
+ if (rc == MDB_SUCCESS) {
+ /* there's only a key anyway, so this is a no-op */
+ if (IS_LEAF2(mc->mc_pg[mc->mc_top])) {
+ unsigned int ksize = mc->mc_db->md_pad;
+ if (key->mv_size != ksize)
+ return EINVAL;
+ if (flags == MDB_CURRENT) {
+ char *ptr = LEAF2KEY(mc->mc_pg[mc->mc_top], mc->mc_ki[mc->mc_top], ksize);
+ memcpy(ptr, key->mv_data, ksize);
+ }
+ return MDB_SUCCESS;
+ }
+
+ leaf = NODEPTR(mc->mc_pg[mc->mc_top], mc->mc_ki[mc->mc_top]);
+
+ /* DB has dups? */
+ if (F_ISSET(mc->mc_db->md_flags, MDB_DUPSORT)) {
+ /* Was a single item before, must convert now */
+more:
+ if (!F_ISSET(leaf->mn_flags, F_DUPDATA)) {
+ /* Just overwrite the current item */
+ if (flags == MDB_CURRENT)
+ goto current;
+
+ dkey.mv_size = NODEDSZ(leaf);
+ dkey.mv_data = NODEDATA(leaf);
+#if UINT_MAX < SIZE_MAX
+ if (mc->mc_dbx->md_dcmp == mdb_cmp_int && dkey.mv_size == sizeof(size_t))
+#ifdef MISALIGNED_OK
+ mc->mc_dbx->md_dcmp = mdb_cmp_long;
+#else
+ mc->mc_dbx->md_dcmp = mdb_cmp_cint;
+#endif
+#endif
+ /* if data matches, ignore it */
+ if (!mc->mc_dbx->md_dcmp(data, &dkey))
+ return (flags == MDB_NODUPDATA) ? MDB_KEYEXIST : MDB_SUCCESS;
+
+ /* create a fake page for the dup items */
+ memcpy(dbuf, dkey.mv_data, dkey.mv_size);
+ dkey.mv_data = dbuf;
+ fp = (MDB_page *)&pbuf;
+ fp->mp_pgno = mc->mc_pg[mc->mc_top]->mp_pgno;
+ fp->mp_flags = P_LEAF|P_DIRTY|P_SUBP;
+ fp->mp_lower = PAGEHDRSZ;
+ fp->mp_upper = PAGEHDRSZ + dkey.mv_size + data->mv_size;
+ if (mc->mc_db->md_flags & MDB_DUPFIXED) {
+ fp->mp_flags |= P_LEAF2;
+ fp->mp_pad = data->mv_size;
+ } else {
+ fp->mp_upper += 2 * sizeof(indx_t) + 2 * NODESIZE +
+ (dkey.mv_size & 1) + (data->mv_size & 1);
+ }
+ mdb_node_del(mc->mc_pg[mc->mc_top], mc->mc_ki[mc->mc_top], 0);
+ do_sub = 1;
+ rdata = &xdata;
+ xdata.mv_size = fp->mp_upper;
+ xdata.mv_data = fp;
+ flags |= F_DUPDATA;
+ goto new_sub;
+ }
+ if (!F_ISSET(leaf->mn_flags, F_SUBDATA)) {
+ /* See if we need to convert from fake page to subDB */
+ MDB_page *mp;
+ unsigned int offset;
+ unsigned int i;
+
+ fp = NODEDATA(leaf);
+ if (flags == MDB_CURRENT) {
+ fp->mp_flags |= P_DIRTY;
+ COPY_PGNO(fp->mp_pgno, mc->mc_pg[mc->mc_top]->mp_pgno);
+ mc->mc_xcursor->mx_cursor.mc_pg[0] = fp;
+ flags |= F_DUPDATA;
+ goto put_sub;
+ }
+ if (mc->mc_db->md_flags & MDB_DUPFIXED) {
+ offset = fp->mp_pad;
+ } else {
+ offset = NODESIZE + sizeof(indx_t) + data->mv_size;
+ }
+ offset += offset & 1;
+ if (NODESIZE + sizeof(indx_t) + NODEKSZ(leaf) + NODEDSZ(leaf) +
+ offset >= (mc->mc_txn->mt_env->me_psize - PAGEHDRSZ) /
+ MDB_MINKEYS) {
+ /* yes, convert it */
+ dummy.md_flags = 0;
+ if (mc->mc_db->md_flags & MDB_DUPFIXED) {
+ dummy.md_pad = fp->mp_pad;
+ dummy.md_flags = MDB_DUPFIXED;
+ if (mc->mc_db->md_flags & MDB_INTEGERDUP)
+ dummy.md_flags |= MDB_INTEGERKEY;
+ }
+ dummy.md_depth = 1;
+ dummy.md_branch_pages = 0;
+ dummy.md_leaf_pages = 1;
+ dummy.md_overflow_pages = 0;
+ dummy.md_entries = NUMKEYS(fp);
+ rdata = &xdata;
+ xdata.mv_size = sizeof(MDB_db);
+ xdata.mv_data = &dummy;
+ mp = mdb_page_alloc(mc, 1);
+ if (!mp)
+ return ENOMEM;
+ offset = mc->mc_txn->mt_env->me_psize - NODEDSZ(leaf);
+ flags |= F_DUPDATA|F_SUBDATA;
+ dummy.md_root = mp->mp_pgno;
+ } else {
+ /* no, just grow it */
+ rdata = &xdata;
+ xdata.mv_size = NODEDSZ(leaf) + offset;
+ xdata.mv_data = &pbuf;
+ mp = (MDB_page *)&pbuf;
+ mp->mp_pgno = mc->mc_pg[mc->mc_top]->mp_pgno;
+ flags |= F_DUPDATA;
+ }
+ mp->mp_flags = fp->mp_flags | P_DIRTY;
+ mp->mp_pad = fp->mp_pad;
+ mp->mp_lower = fp->mp_lower;
+ mp->mp_upper = fp->mp_upper + offset;
+ if (IS_LEAF2(fp)) {
+ memcpy(METADATA(mp), METADATA(fp), NUMKEYS(fp) * fp->mp_pad);
+ } else {
+ nsize = NODEDSZ(leaf) - fp->mp_upper;
+ memcpy((char *)mp + mp->mp_upper, (char *)fp + fp->mp_upper, nsize);
+ for (i=0; i<NUMKEYS(fp); i++)
+ mp->mp_ptrs[i] = fp->mp_ptrs[i] + offset;
+ }
+ mdb_node_del(mc->mc_pg[mc->mc_top], mc->mc_ki[mc->mc_top], 0);
+ do_sub = 1;
+ goto new_sub;
+ }
+ /* data is on sub-DB, just store it */
+ flags |= F_DUPDATA|F_SUBDATA;
+ goto put_sub;
+ }
+current:
+ /* overflow page overwrites need special handling */
+ if (F_ISSET(leaf->mn_flags, F_BIGDATA)) {
+ MDB_page *omp;
+ pgno_t pg;
+ int ovpages, dpages;
+
+ ovpages = OVPAGES(NODEDSZ(leaf), mc->mc_txn->mt_env->me_psize);
+ dpages = OVPAGES(data->mv_size, mc->mc_txn->mt_env->me_psize);
+ memcpy(&pg, NODEDATA(leaf), sizeof(pg));
+ mdb_page_get(mc->mc_txn, pg, &omp);
+ /* Is the ov page writable and large enough? */
+ if ((omp->mp_flags & P_DIRTY) && ovpages >= dpages) {
+ /* yes, overwrite it. Note in this case we don't
+ * bother to try shrinking the node if the new data
+ * is smaller than the overflow threshold.
+ */
+ if (F_ISSET(flags, MDB_RESERVE))
+ data->mv_data = METADATA(omp);
+ else
+ memcpy(METADATA(omp), data->mv_data, data->mv_size);
+ goto done;
+ } else {
+ /* no, free ovpages */
+ int i;
+ mc->mc_db->md_overflow_pages -= ovpages;
+ for (i=0; i<ovpages; i++) {
+ DPRINTF("freed ov page %zu", pg);
+ mdb_midl_append(&mc->mc_txn->mt_free_pgs, pg);
+ pg++;
+ }