/**
* 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
:data
was allocated viamalloc()
, and it is the caller’s responsibility tofree()
it. -
DB_DBT_USERMEM
:data
was 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 InternalEntry
s 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 KeyDataEntry
s 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