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/>.
23 #define ALIGN(_size_) (((_size_)+15)&~15)
30 struct db_rbt_ctx *db_ctx;
31 struct db_rbt_node *node;
34 /* The structure that ends up in the tree */
37 struct rb_node rb_node;
38 size_t keysize, valuesize;
41 * key and value are appended implicitly, "data" is only here as a
42 * target for offsetof()
49 * Hide the ugly pointer calculations in a function
52 static struct db_rbt_node *db_rbt2node(struct rb_node *node)
54 return (struct db_rbt_node *)
55 ((char *)node - offsetof(struct db_rbt_node, rb_node));
62 static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
66 res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
68 if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
71 if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
78 * dissect a db_rbt_node into its implicit key and value parts
81 static void db_rbt_parse_node(struct db_rbt_node *node,
82 TDB_DATA *key, TDB_DATA *value)
84 key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
85 key->dsize = node->keysize;
86 value->dptr = key->dptr + node->keysize;
87 value->dsize = node->valuesize;
90 static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
92 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
93 struct db_rbt_node *node;
96 struct rb_node * parent;
98 TDB_DATA this_key, this_val;
100 if (rec_priv->node != NULL) {
103 * The record was around previously
106 db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
108 SMB_ASSERT(this_key.dsize == rec->key.dsize);
109 SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
110 this_key.dsize) == 0);
112 if (this_val.dsize >= data.dsize) {
114 * The new value fits into the old space
116 memcpy(this_val.dptr, data.dptr, data.dsize);
117 rec_priv->node->valuesize = data.dsize;
122 * We need to delete the key from the tree and start fresh,
123 * there's not enough space in the existing record
126 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
129 * Keep the existing node around for a while: If the record
130 * existed before, we reference the key data in there.
134 node = (struct db_rbt_node *)SMB_MALLOC(
135 offsetof(struct db_rbt_node, data) + rec->key.dsize
139 SAFE_FREE(rec_priv->node);
140 return NT_STATUS_NO_MEMORY;
143 ZERO_STRUCT(node->rb_node);
145 node->keysize = rec->key.dsize;
146 node->valuesize = data.dsize;
148 db_rbt_parse_node(node, &this_key, &this_val);
150 memcpy(this_key.dptr, rec->key.dptr, node->keysize);
151 SAFE_FREE(rec_priv->node);
153 memcpy(this_val.dptr, data.dptr, node->valuesize);
156 p = &rec_priv->db_ctx->tree.rb_node;
159 struct db_rbt_node *r;
160 TDB_DATA search_key, search_val;
167 db_rbt_parse_node(r, &search_key, &search_val);
169 res = db_rbt_compare(this_key, search_key);
178 smb_panic("someone messed with the tree");
182 rb_link_node(&node->rb_node, parent, p);
183 rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
188 static NTSTATUS db_rbt_delete(struct db_record *rec)
190 struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
192 if (rec_priv->node == NULL) {
196 rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
197 SAFE_FREE(rec_priv->node);
202 static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
206 struct db_rbt_ctx *ctx = talloc_get_type_abort(
207 db_ctx->private_data, struct db_rbt_ctx);
209 struct db_rbt_rec *rec_priv;
210 struct db_record *result;
214 struct db_rbt_node *r = NULL;
215 TDB_DATA search_key = tdb_null, search_val = tdb_null;
217 n = ctx->tree.rb_node;
224 db_rbt_parse_node(r, &search_key, &search_val);
226 res = db_rbt_compare(key, search_key);
241 * In this low-level routine, play tricks to reduce the number of
242 * tallocs to one. Not recommened for general use, but here it pays
246 size = ALIGN(sizeof(struct db_record)) + sizeof(struct db_rbt_rec);
250 * We need to keep the key around for later store
255 result = (struct db_record *)talloc_size(mem_ctx, size);
256 if (result == NULL) {
260 rec_priv = (struct db_rbt_rec *)
261 ((char *)result + ALIGN(sizeof(struct db_record)));
262 rec_priv->db_ctx = ctx;
264 result->store = db_rbt_store;
265 result->delete_rec = db_rbt_delete;
266 result->private_data = rec_priv;
270 result->key = search_key;
271 result->value = search_val;
274 rec_priv->node = NULL;
275 result->key.dptr = (uint8 *)
276 ((char *)rec_priv + sizeof(*rec_priv));
277 result->key.dsize = key.dsize;
278 memcpy(result->key.dptr, key.dptr, key.dsize);
280 result->value = tdb_null;
286 static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
287 TDB_DATA key, TDB_DATA *data)
289 struct db_rbt_ctx *ctx = talloc_get_type_abort(
290 db->private_data, struct db_rbt_ctx);
294 struct db_rbt_node *r = NULL;
295 TDB_DATA search_key, search_val;
298 n = ctx->tree.rb_node;
305 db_rbt_parse_node(r, &search_key, &search_val);
307 res = db_rbt_compare(key, search_key);
326 result = (uint8 *)talloc_memdup(mem_ctx, search_val.dptr,
328 if (result == NULL) {
333 data->dsize = search_val.dsize;
338 static int db_rbt_traverse(struct db_context *db,
339 int (*f)(struct db_record *db,
344 * Nobody uses this so far, and unused code is broken code :-)
349 static int db_rbt_get_seqnum(struct db_context *db)
354 static int db_rbt_trans_dummy(struct db_context *db)
357 * Transactions are pretty pointless in-memory, just return success.
362 struct db_context *db_open_rbt(TALLOC_CTX *mem_ctx)
364 struct db_context *result;
366 result = talloc(mem_ctx, struct db_context);
368 if (result == NULL) {
372 result->private_data = TALLOC_ZERO_P(result, struct db_rbt_ctx);
374 if (result->private_data == NULL) {
379 result->fetch_locked = db_rbt_fetch_locked;
380 result->fetch = db_rbt_fetch;
381 result->traverse = db_rbt_traverse;
382 result->traverse_read = db_rbt_traverse;
383 result->get_seqnum = db_rbt_get_seqnum;
384 result->transaction_start = db_rbt_trans_dummy;
385 result->transaction_commit = db_rbt_trans_dummy;
386 result->transaction_cancel = db_rbt_trans_dummy;