/**
* Key/data structure -- a Data-Base Thang
*
* That's the actual comment from the BerkeleyDB source code.
*/
struct DBT {
void *data; ///< Key/data
u_int32_t size; ///< Key/data length
u_int32_t ulen; ///< Only used with DB_DBT_USERMEM
u_int32_t dlen; ///< Only used with DB_DBT_PARTIAL
u_int32_t doff; ///< Only used with DB_DBT_PARTIAL
void *app_data; ///< Applications are allowed to associate opaque data.
u_int32_t flags; ///< Unused
}
Point Reads
Support for searching down the tree in search of a single value.
API
BerkeleyDB offers a get() method on DB, allowing the reading of the stored value corresponding to a key. To represent a key or value, it uses a DBT struct which describes the memory and its size.
See also the official docs for DBT.
The get() method to implement is defined as:
struct DB {
/**
* Get the value for a key.
*
* It is the user's responsibility to manage the memory pointed to by
* `key`, and ensure that it is valid for the lifetime of the call.
*
* `data` should be zero-initialized upon calling get(), and it is the
* library's responsibility to manage the memory pointed to by data->data.
* This memory will remain valid until the next call to the library which
* returns a DBT to the user.
*
* @param db The opened DB in which to fetch a key.
* @param txn The transaction within which this get operation is scoped.
* For us, this must be NULL.
* @param key A DBT owned by the user to describe the kv-pair to fetch.
* @param data A zero-initialized DBT, which will be written to with
* the data and size of the associated data.
* @param flags Ignored for us.
* @return 0, if the key was found
* DB_NOTFOUND, if the key was not found
*/
int (*get)(DB *db, DB_TXN *txn, DBT *key, DBT *data, u_int32_t flags);
// The default mode of operation is that the library is responsible for
// freeing or reusing any returned state when the next call to any data
// returning operation is made. The way that this works is that the DB
// struct has members which let you store what had been returned to a
// user previously, so that you can remember what pointers had been
// returned on a previous call. There's more to remember for other APIs
// but for now, we only need to remember what was returned in the `data`
// argument to `get`.
DBT my_rdata; ///< My Remembered Data.
}
See also the offical docs for DB->get().
There are flags you could optionally support, if it’d make it easier for you to write tests or demo code:
-
DB_DBT_MALLOC:datawas allocated viamalloc(), and it is the caller’s responsibility tofree()it. -
DB_DBT_USERMEM:datawas allocated by the user, and points to a region of memory of sizeulen.
If you don’t support any flags, I would suggest ASSERT()ing that flags is 0, or return -ENOTSUP, as if you try out some bindings with your library later and they happen to pass the flags, it’ll lead to a corruption or crash.
Algorithm
Examining the entries in an internal B-Tree page is going to yield InternalEntrys that look like:
And the goal is to find the correct next page to read by comparing the target key against the data in the InternalEntry. Your goal is to find the maximum key that’s less than or equal to your target key. If get() was provided a target key of NNNN, then the goal is to identify offset 60 of PgNo: 4, Data: MMMM as the proper entry, and repeat the search on page 4 next. One could binary search this, but the offsets are maintained in order, and so I found a linear scan the easiest.
Specifically, for internal pages, iterate over the entries with a sliding window of size 2, such that one visits the offset pairs of:
-
(NULL, 100)
-
(100, 80)
-
(80, 60)
-
(60, 40)
-
(40, 20)
-
(20, NULL)
in specifically that order. You’re searching to find a (left, right), where left.data <= target_key && target_key < right.data, and skip the comparison on NULL. If your target key is less than the first InternalEntry's data value, then your target key is not found in the B-Tree. Start with the root page. Repeat on each page indicated by the identified InternalEntry's PgNo until you reach a page where page.level == 1.
Once you’re on a leaf page, there will be KeyDataEntrys instead.
Recall that there will always be an even number of offsets and entries on a leaf page, with the first entry being a key, and the second being the data. Iterate over all the entries in pairs (a tumbling window of size 2), and if pair[0].data == target_key, then return pair[1].data as the found key. If was no matching key, then the key doesn’t exist in the B-Tree.
Task
Using the test data generated by gendata.py provided in Page Format, implement the support necessary to run:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <db.h>
#define DATABASE "testdata.bdb"
void test_get(DB* dbp, const char* keystr) {
DBT key, data;
// Zero-initialize key/data pair
memset(&key, 0, sizeof(DBT));
memset(&data, 0, sizeof(DBT));
key.data = (char*)keystr;
key.size = strlen(key.data);
// Get data from the database
int rc = dbp->get(dbp, NULL, &key, &data, 0);
if (rc == 0)
printf("key: %s, data: %s\n", (char *)key.data, (char *)data.data);
else if (rc == DB_NOTFOUND)
printf("key not found\n");
else
printf("Unknown error: %d\n", rc);
}
int main() {
DB *dbp;
int ret;
// Initialize DB structure
if ((ret = db_create(&dbp, NULL, 0)) != 0) {
fprintf(stderr, "db_create: %s\n", db_strerror(ret));
exit(1);
}
// Open the database
if ((ret = dbp->open(dbp, NULL, DATABASE, NULL, DB_BTREE, DB_CREATE, 0664)) != 0) {
fprintf(stderr, "dbp->open: %d\n", ret);
goto err;
}
test_get(dbp, "bbbbbbbbbbbbbbbbbbbb");
test_get(dbp, "kjshdfkhjdsfhdsj");
test_get(dbp, "ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss");
err:
if (dbp != NULL)
dbp->close(dbp, 0);
return 0;
}
Which should output:
key: bbbbbbbbbbbbbbbbbbbb, data: bbbbbbbbbbbbbbbbbbbb
key not found
key: ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss, data: ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss