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_node *node;
36 /* The structure that ends up in the tree */
39 struct rb_node rb_node;
40 size_t keysize, valuesize;
44 * Hide the ugly pointer calculations in a function
47 static struct db_rbt_node *db_rbt2node(struct rb_node *node)
49 return (struct db_rbt_node *)
50 ((char *)node - offsetof(struct db_rbt_node, rb_node));
57 static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
61 res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
63 if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
66 if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
73 * dissect a db_rbt_node into its implicit key and value parts
76 static void db_rbt_parse_node(struct db_rbt_node *node,
77 TDB_DATA *key, TDB_DATA *value)
79 size_t key_offset, value_offset;
81 key_offset = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
82 key->dptr = ((uint8_t *)node) + key_offset;
83 key->dsize = node->keysize;
85 value_offset = DBWRAP_RBT_ALIGN(node->keysize);
86 value->dptr = key->dptr + value_offset;
87 value->dsize = node->valuesize;
90 static ssize_t db_rbt_reclen(size_t keylen, size_t valuelen)
94 len = DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node));
96 tmp = DBWRAP_RBT_ALIGN(keylen);
107 if (len < valuelen) {
116 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
118 struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
119 rec->db->private_data, struct db_rbt_ctx);
120 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
121 struct db_rbt_node *node;
124 struct rb_node * parent;
127 TDB_DATA this_key, this_val;
129 if (rec_priv->node != NULL) {
132 * The record was around previously
135 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
137 SMB_ASSERT(this_key.dsize == rec->key.dsize);
138 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
139 this_key.dsize) == 0);
141 if (this_val.dsize >= data.dsize) {
143 * The new value fits into the old space
145 memcpy(this_val.dptr, data.dptr, data.dsize);
146 rec_priv->node->valuesize = data.dsize;
151 reclen = db_rbt_reclen(rec->key.dsize, data.dsize);
153 return NT_STATUS_INSUFFICIENT_RESOURCES;
156 node = talloc_zero_size(db_ctx, reclen);
158 return NT_STATUS_NO_MEMORY;
161 if (rec_priv->node != NULL) {
163 * We need to delete the key from the tree and start fresh,
164 * there's not enough space in the existing record
167 rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
170 * Keep the existing node around for a while: If the record
171 * existed before, we reference the key data in there.
175 node->keysize = rec->key.dsize;
176 node->valuesize = data.dsize;
178 db_rbt_parse_node(node, &this_key, &this_val);
180 memcpy(this_key.dptr, rec->key.dptr, node->keysize);
181 TALLOC_FREE(rec_priv->node);
182 rec_priv->node = node;
184 memcpy(this_val.dptr, data.dptr, node->valuesize);
187 p = &db_ctx->tree.rb_node;
190 struct db_rbt_node *r;
191 TDB_DATA search_key, search_val;
198 db_rbt_parse_node(r, &search_key, &search_val);
200 res = db_rbt_compare(this_key, search_key);
209 smb_panic("someone messed with the tree");
213 rb_link_node(&node->rb_node, parent, p);
214 rb_insert_color(&node->rb_node, &db_ctx->tree);
219 static NTSTATUS db_rbt_delete(struct db_record *rec)
221 struct db_rbt_ctx *db_ctx = talloc_get_type_abort(
222 rec->db->private_data, struct db_rbt_ctx);
223 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
225 if (rec_priv->node == NULL) {
229 rb_erase(&rec_priv->node->rb_node, &db_ctx->tree);
230 TALLOC_FREE(rec_priv->node);
235 static NTSTATUS db_rbt_store_deny(struct db_record *rec, TDB_DATA data, int flag)
237 return NT_STATUS_MEDIA_WRITE_PROTECTED;
240 static NTSTATUS db_rbt_delete_deny(struct db_record *rec)
242 return NT_STATUS_MEDIA_WRITE_PROTECTED;
245 struct db_rbt_search_result {
248 struct db_rbt_node* node;
251 static bool db_rbt_search_internal(struct db_context *db, TDB_DATA key,
252 struct db_rbt_search_result *result)
254 struct db_rbt_ctx *ctx = talloc_get_type_abort(
255 db->private_data, struct db_rbt_ctx);
259 struct db_rbt_node *r = NULL;
260 TDB_DATA search_key, search_val;
262 n = ctx->tree.rb_node;
269 db_rbt_parse_node(r, &search_key, &search_val);
271 res = db_rbt_compare(key, search_key);
284 if (result != NULL) {
286 result->key = search_key;
287 result->val = search_val;
290 ZERO_STRUCT(*result);
296 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
300 struct db_rbt_rec *rec_priv;
301 struct db_record *result;
304 struct db_rbt_search_result res;
306 found = db_rbt_search_internal(db_ctx, key, &res);
309 * In this low-level routine, play tricks to reduce the number of
310 * tallocs to one. Not recommened for general use, but here it pays
314 size = DBWRAP_RBT_ALIGN(sizeof(struct db_record))
315 + sizeof(struct db_rbt_rec);
319 * We need to keep the key around for later store
324 result = (struct db_record *)talloc_size(mem_ctx, size);
325 if (result == NULL) {
329 rec_priv = (struct db_rbt_rec *)
330 ((char *)result + DBWRAP_RBT_ALIGN(sizeof(struct db_record)));
332 result->store = db_rbt_store;
333 result->delete_rec = db_rbt_delete;
334 result->private_data = rec_priv;
336 rec_priv->node = res.node;
337 result->value = res.val;
340 result->key = res.key;
343 result->key.dptr = (uint8_t *)
344 ((char *)rec_priv + sizeof(*rec_priv));
345 result->key.dsize = key.dsize;
346 memcpy(result->key.dptr, key.dptr, key.dsize);
352 static int db_rbt_exists(struct db_context *db, TDB_DATA key)
354 return db_rbt_search_internal(db, key, NULL);
357 static int db_rbt_wipe(struct db_context *db)
359 struct db_rbt_ctx *old_ctx = talloc_get_type_abort(
360 db->private_data, struct db_rbt_ctx);
361 struct db_rbt_ctx *new_ctx = talloc_zero(db, struct db_rbt_ctx);
362 if (new_ctx == NULL) {
365 db->private_data = new_ctx;
366 talloc_free(old_ctx);
370 static NTSTATUS db_rbt_parse_record(struct db_context *db, TDB_DATA key,
371 void (*parser)(TDB_DATA key, TDB_DATA data,
375 struct db_rbt_search_result res;
376 bool found = db_rbt_search_internal(db, key, &res);
379 return NT_STATUS_NOT_FOUND;
381 parser(res.key, res.val, private_data);
385 static int db_rbt_traverse_internal(struct db_context *db,
387 int (*f)(struct db_record *db,
389 void *private_data, uint32_t* count,
392 struct rb_node *rb_right;
393 struct rb_node *rb_left;
394 struct db_record rec;
395 struct db_rbt_rec rec_priv;
402 rb_left = n->rb_left;
403 rb_right = n->rb_right;
405 ret = db_rbt_traverse_internal(db, rb_left, f, private_data, count, rw);
410 rec_priv.node = db_rbt2node(n);
411 /* n might be altered by the callback function */
416 rec.private_data = &rec_priv;
418 rec.store = db_rbt_store;
419 rec.delete_rec = db_rbt_delete;
421 rec.store = db_rbt_store_deny;
422 rec.delete_rec = db_rbt_delete_deny;
424 db_rbt_parse_node(rec_priv.node, &rec.key, &rec.value);
426 ret = f(&rec, private_data);
432 if (rec_priv.node != NULL) {
434 * If the current record is still there
435 * we should take the current rb_right.
437 rb_right = rec_priv.node->rb_node.rb_right;
440 return db_rbt_traverse_internal(db, rb_right, f, private_data, count, rw);
443 static int db_rbt_traverse(struct db_context *db,
444 int (*f)(struct db_record *db,
448 struct db_rbt_ctx *ctx = talloc_get_type_abort(
449 db->private_data, struct db_rbt_ctx);
452 int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
453 f, private_data, &count,
458 if (count > INT_MAX) {
464 static int db_rbt_traverse_read(struct db_context *db,
465 int (*f)(struct db_record *db,
469 struct db_rbt_ctx *ctx = talloc_get_type_abort(
470 db->private_data, struct db_rbt_ctx);
473 int ret = db_rbt_traverse_internal(db, ctx->tree.rb_node,
474 f, private_data, &count,
479 if (count > INT_MAX) {
485 static int db_rbt_get_seqnum(struct db_context *db)
490 static int db_rbt_trans_dummy(struct db_context *db)
493 * Transactions are pretty pointless in-memory, just return success.
498 static void db_rbt_id(struct db_context *db, const uint8_t **id, size_t *idlen)
501 *idlen = sizeof(struct db_context *);
504 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
506 struct db_context *result;
508 result = talloc_zero(mem_ctx, struct db_context);
510 if (result == NULL) {
514 result->private_data = talloc_zero(result, struct db_rbt_ctx);
516 if (result->private_data == NULL) {
521 result->fetch_locked = db_rbt_fetch_locked;
522 result->traverse = db_rbt_traverse;
523 result->traverse_read = db_rbt_traverse_read;
524 result->get_seqnum = db_rbt_get_seqnum;
525 result->transaction_start = db_rbt_trans_dummy;
526 result->transaction_commit = db_rbt_trans_dummy;
527 result->transaction_cancel = db_rbt_trans_dummy;
528 result->exists = db_rbt_exists;
529 result->wipe = db_rbt_wipe;
530 result->parse_record = db_rbt_parse_record;
531 result->id = db_rbt_id;
532 result->name = "dbwrap rbt";