From edf78694661259e6760f3af044139bbd0d948146 Mon Sep 17 00:00:00 2001
From: Howard Chu <hyc@symas.com>
Date: Tue, 9 Aug 2011 03:26:45 -0700
Subject: [PATCH] Add cursor_prev

---
 libraries/libmdb/mdb.c   | 56 +++++++++++++++++++++++++++++++++++++++-
 libraries/libmdb/mdb.h   |  2 +-
 libraries/libmdb/mtest.c |  7 +++++
 3 files changed, 63 insertions(+), 2 deletions(-)

diff --git a/libraries/libmdb/mdb.c b/libraries/libmdb/mdb.c
index aa7f3d8ea6..d9fbad616b 100644
--- a/libraries/libmdb/mdb.c
+++ b/libraries/libmdb/mdb.c
@@ -362,6 +362,8 @@ static int		 mdb_set_key(MDB_node *node, MDB_val *key);
 static int		 mdb_sibling(MDB_cursor *cursor, int move_right);
 static int		 mdb_cursor_next(MDB_cursor *cursor,
 			    MDB_val *key, MDB_val *data);
+static int		 mdb_cursor_prev(MDB_cursor *cursor,
+			    MDB_val *key, MDB_val *data);
 static int		 mdb_cursor_set(MDB_cursor *cursor,
 			    MDB_val *key, MDB_val *data, int *exactp);
 static int		 mdb_cursor_first(MDB_cursor *cursor,
@@ -1753,6 +1755,46 @@ mdb_cursor_next(MDB_cursor *cursor, MDB_val *key, MDB_val *data)
 	return mdb_set_key(leaf, key);
 }
 
+static int
+mdb_cursor_prev(MDB_cursor *cursor, MDB_val *key, MDB_val *data)
+{
+	MDB_ppage	*top;
+	MDB_page	*mp;
+	MDB_node	*leaf;
+
+	assert(cursor->mc_initialized);
+
+	top = CURSOR_TOP(cursor);
+	mp = top->mp_page;
+
+	DPRINTF("cursor_prev: top page is %lu in cursor %p", mp->mp_pgno, (void *) cursor);
+
+	if (top->mp_ki == 0)  {
+		DPRINTF("=====> move to prev sibling page");
+		if (mdb_sibling(cursor, 0) != MDB_SUCCESS) {
+			return ENOENT;
+		}
+		top = CURSOR_TOP(cursor);
+		mp = top->mp_page;
+		top->mp_ki = NUMKEYS(mp) - 1;
+		DPRINTF("prev page is %lu, key index %u", mp->mp_pgno, top->mp_ki);
+	} else
+		top->mp_ki--;
+
+	cursor->mc_eof = 0;
+
+	DPRINTF("==> cursor points to page %lu with %u keys, key index %u",
+	    mp->mp_pgno, NUMKEYS(mp), top->mp_ki);
+
+	assert(IS_LEAF(mp));
+	leaf = NODEPTR(mp, top->mp_ki);
+
+	if (data && mdb_read_data(cursor->mc_txn->mt_env, leaf, data) != MDB_SUCCESS)
+		return MDB_FAIL;
+
+	return mdb_set_key(leaf, key);
+}
+
 static int
 mdb_cursor_set(MDB_cursor *cursor, MDB_val *key, MDB_val *data,
     int *exactp)
@@ -1831,6 +1873,7 @@ static int
 mdb_cursor_last(MDB_cursor *cursor, MDB_val *key, MDB_val *data)
 {
 	int		 rc;
+	MDB_ppage	*top;
 	MDB_pageparent	mpp;
 	MDB_node	*leaf;
 	MDB_val	lkey;
@@ -1845,7 +1888,10 @@ mdb_cursor_last(MDB_cursor *cursor, MDB_val *key, MDB_val *data)
 
 	leaf = NODEPTR(mpp.mp_page, NUMKEYS(mpp.mp_page)-1);
 	cursor->mc_initialized = 1;
-	cursor->mc_eof = 1;
+	cursor->mc_eof = 0;
+
+	top = CURSOR_TOP(cursor);
+	top->mp_ki = NUMKEYS(top->mp_page) - 1;
 
 	if (data && (rc = mdb_read_data(cursor->mc_txn->mt_env, leaf, data)) != MDB_SUCCESS)
 		return rc;
@@ -1880,6 +1926,14 @@ mdb_cursor_get(MDB_cursor *cursor, MDB_val *key, MDB_val *data,
 		else
 			rc = mdb_cursor_next(cursor, key, data);
 		break;
+	case MDB_PREV:
+		if (!cursor->mc_initialized || cursor->mc_eof) {
+			while (CURSOR_TOP(cursor) != NULL)
+				cursor_pop_page(cursor);
+			rc = mdb_cursor_last(cursor, key, data);
+		} else
+			rc = mdb_cursor_prev(cursor, key, data);
+		break;
 	case MDB_FIRST:
 		while (CURSOR_TOP(cursor) != NULL)
 			cursor_pop_page(cursor);
diff --git a/libraries/libmdb/mdb.h b/libraries/libmdb/mdb.h
index 566a32cff9..c7841c434c 100644
--- a/libraries/libmdb/mdb.h
+++ b/libraries/libmdb/mdb.h
@@ -58,7 +58,7 @@ typedef enum MDB_cursor_op {		/* cursor operations */
 	MDB_FIRST,
 	MDB_NEXT,
 	MDB_LAST,
-	MDB_PREV,				/* not implemented */
+	MDB_PREV,
 	MDB_GET_BOTH,			/* position at key/data */
 	MDB_GET_BOTH_RANGE		/* position at key, nearest data */
 } MDB_cursor_op;
diff --git a/libraries/libmdb/mtest.c b/libraries/libmdb/mtest.c
index 628446f840..c473ca2214 100644
--- a/libraries/libmdb/mtest.c
+++ b/libraries/libmdb/mtest.c
@@ -91,11 +91,18 @@ int main(int argc,char * argv[])
 		rc = mdbenv_stat(env, &mst);
 		rc = mdb_txn_begin(env, 1, &txn);
 		rc = mdb_cursor_open(txn, dbi, &cursor);
+		printf("Cursor next\n");
 		while ((rc = mdb_cursor_get(cursor, &key, &data, MDB_NEXT)) == 0) {
 			printf("key: %.*s, data: %.*s\n",
 				(int) key.mv_size,  (char *) key.mv_data,
 				(int) data.mv_size, (char *) data.mv_data);
 		}
+		printf("Cursor prev\n");
+		while ((rc = mdb_cursor_get(cursor, &key, &data, MDB_PREV)) == 0) {
+			printf("key: %.*s, data: %.*s\n",
+				(int) key.mv_size,  (char *) key.mv_data,
+				(int) data.mv_size, (char *) data.mv_data);
+		}
 #if 0
 		/* write ops aren't coordinated with cursors,
 		 * this stuff all breaks
-- 
2.39.5