2 Unix SMB/CIFS implementation.
3 Database interface wrapper around red-black trees
4 Copyright (C) Volker Lendecke 2007, 2008
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
21 #include "dbwrap/dbwrap.h"
22 #include "dbwrap/dbwrap_private.h"
23 #include "dbwrap/dbwrap_rbt.h"
24 #include "../lib/util/rbtree.h"
26 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
33 struct db_rbt_ctx *db_ctx;
34 struct db_rbt_node *node;
37 /* The structure that ends up in the tree */
40 struct rb_node rb_node;
41 size_t keysize, valuesize;
44 * key and value are appended implicitly, "data" is only here as a
45 * target for offsetof()
52 * Hide the ugly pointer calculations in a function
55 static struct db_rbt_node *db_rbt2node(struct rb_node *node)
57 return (struct db_rbt_node *)
58 ((char *)node - offsetof(struct db_rbt_node, rb_node));
65 static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
69 res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
71 if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
74 if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
81 * dissect a db_rbt_node into its implicit key and value parts
84 static void db_rbt_parse_node(struct db_rbt_node *node,
85 TDB_DATA *key, TDB_DATA *value)
87 key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
88 key->dsize = node->keysize;
89 value->dptr = key->dptr + node->keysize;
90 value->dsize = node->valuesize;
93 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
95 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
96 struct db_rbt_node *node;
99 struct rb_node * parent;
101 TDB_DATA this_key, this_val;
103 if (rec_priv->node != NULL) {
106 * The record was around previously
109 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
111 SMB_ASSERT(this_key.dsize == rec->key.dsize);
112 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
113 this_key.dsize) == 0);
115 if (this_val.dsize >= data.dsize) {
117 * The new value fits into the old space
119 memcpy(this_val.dptr, data.dptr, data.dsize);
120 rec_priv->node->valuesize = data.dsize;
125 * We need to delete the key from the tree and start fresh,
126 * there's not enough space in the existing record
129 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
132 * Keep the existing node around for a while: If the record
133 * existed before, we reference the key data in there.
137 node = (struct db_rbt_node *)talloc_size(rec_priv->db_ctx,
138 offsetof(struct db_rbt_node, data) + rec->key.dsize
142 TALLOC_FREE(rec_priv->node);
143 return NT_STATUS_NO_MEMORY;
146 ZERO_STRUCT(node->rb_node);
148 node->keysize = rec->key.dsize;
149 node->valuesize = data.dsize;
151 db_rbt_parse_node(node, &this_key, &this_val);
153 memcpy(this_key.dptr, rec->key.dptr, node->keysize);
154 TALLOC_FREE(rec_priv->node);
156 memcpy(this_val.dptr, data.dptr, node->valuesize);
159 p = &rec_priv->db_ctx->tree.rb_node;
162 struct db_rbt_node *r;
163 TDB_DATA search_key, search_val;
170 db_rbt_parse_node(r, &search_key, &search_val);
172 res = db_rbt_compare(this_key, search_key);
181 smb_panic("someone messed with the tree");
185 rb_link_node(&node->rb_node, parent, p);
186 rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
191 static NTSTATUS db_rbt_delete(struct db_record *rec)
193 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
195 if (rec_priv->node == NULL) {
199 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
200 TALLOC_FREE(rec_priv->node);
204 struct db_rbt_search_result {
207 struct db_rbt_node* node;
210 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
211 struct db_rbt_search_result *result)
213 struct db_rbt_ctx *ctx = talloc_get_type_abort(
214 db->private_data, struct db_rbt_ctx);
218 struct db_rbt_node *r = NULL;
219 TDB_DATA search_key, search_val;
221 n = ctx->tree.rb_node;
228 db_rbt_parse_node(r, &search_key, &search_val);
230 res = db_rbt_compare(key, search_key);
243 if (result != NULL) {
245 result->key = search_key;
246 result->val = search_val;
249 ZERO_STRUCT(*result);
255 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
259 struct db_rbt_ctx *ctx = talloc_get_type_abort(
260 db_ctx->private_data, struct db_rbt_ctx);
262 struct db_rbt_rec *rec_priv;
263 struct db_record *result;
266 struct db_rbt_search_result res;
268 found = db_rbt_search_internal(db_ctx, key, &res);
271 * In this low-level routine, play tricks to reduce the number of
272 * tallocs to one. Not recommened for general use, but here it pays
276 size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
277 + sizeof(struct db_rbt_rec);
281 * We need to keep the key around for later store
286 result = (struct db_record *)talloc_size(mem_ctx, size);
287 if (result == NULL) {
291 rec_priv = (struct db_rbt_rec *)
292 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
293 rec_priv->db_ctx = ctx;
295 result->store = db_rbt_store;
296 result->delete_rec = db_rbt_delete;
297 result->private_data = rec_priv;
299 rec_priv->node = res.node;
300 result->value = res.val;
303 result->key = res.key;
306 result->key.dptr = (uint8 *)
307 ((char *)rec_priv + sizeof(*rec_priv));
308 result->key.dsize = key.dsize;
309 memcpy(result->key.dptr, key.dptr, key.dsize);
315 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
317 return db_rbt_search_internal(db, key, NULL);
320 static int db_rbt_wipe(struct db_context *db)
322 struct db_rbt_ctx *old_ctx = talloc_get_type_abort(
323 db->private_data, struct db_rbt_ctx);
324 struct db_rbt_ctx *new_ctx = talloc_zero(db, struct db_rbt_ctx);
325 if (new_ctx == NULL) {
328 db->private_data = new_ctx;
329 talloc_free(old_ctx);
333 static NTSTATUS db_rbt_parse_record(struct db_context *db, TDB_DATA key,
334 void (*parser)(TDB_DATA key, TDB_DATA data,
338 struct db_rbt_search_result res;
339 bool found = db_rbt_search_internal(db, key, &res);
342 return NT_STATUS_NOT_FOUND;
344 parser(res.key, res.val, private_data);
348 static NTSTATUS db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
349 TDB_DATA key, TDB_DATA *data)
352 struct db_rbt_search_result res;
354 bool found = db_rbt_search_internal(db, key, &res);
358 return NT_STATUS_NOT_FOUND;
361 result = (uint8_t*)talloc_memdup(mem_ctx, res.val.dptr, res.val.dsize);
362 if (result == NULL) {
363 return NT_STATUS_NO_MEMORY;
367 data->dsize = res.val.dsize;
371 static int db_rbt_traverse_internal(struct rb_node *n,
372 int (*f)(struct db_record *db,
374 void *private_data, uint32_t* count)
376 struct db_rbt_node *r;
377 struct db_record rec;
384 ret = db_rbt_traverse_internal(n->rb_left, f, private_data, count);
391 db_rbt_parse_node(r, &rec.key, &rec.value);
393 ret = f(&rec, private_data);
399 return db_rbt_traverse_internal(n->rb_right, f, private_data, count);
402 static int db_rbt_traverse(struct db_context *db,
403 int (*f)(struct db_record *db,
407 struct db_rbt_ctx *ctx = talloc_get_type_abort(
408 db->private_data, struct db_rbt_ctx);
411 int ret = db_rbt_traverse_internal(ctx->tree.rb_node, f, private_data, &count);
415 if (count > INT_MAX) {
421 static int db_rbt_get_seqnum(struct db_context *db)
426 static int db_rbt_trans_dummy(struct db_context *db)
429 * Transactions are pretty pointless in-memory, just return success.
434 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
436 struct db_context *result;
438 result = talloc(mem_ctx, struct db_context);
440 if (result == NULL) {
444 result->private_data = talloc_zero(result, struct db_rbt_ctx);
446 if (result->private_data == NULL) {
451 result->fetch_locked = db_rbt_fetch_locked;
452 result->fetch = db_rbt_fetch;
453 result->traverse = db_rbt_traverse;
454 result->traverse_read = db_rbt_traverse;
455 result->get_seqnum = db_rbt_get_seqnum;
456 result->transaction_start = db_rbt_trans_dummy;
457 result->transaction_commit = db_rbt_trans_dummy;
458 result->transaction_cancel = db_rbt_trans_dummy;
459 result->exists = db_rbt_exists;
460 result->wipe = db_rbt_wipe;
461 result->parse_record = db_rbt_parse_record;