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 "../lib/util/rbtree.h"
23 #define DBWRAP_RBT_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
*)talloc_size(rec_priv
->db_ctx
,
135 offsetof(struct db_rbt_node
, data
) + rec
->key
.dsize
139 TALLOC_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 TALLOC_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 TALLOC_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
= DBWRAP_RBT_ALIGN(sizeof(struct db_record
))
247 + sizeof(struct db_rbt_rec
);
251 * We need to keep the key around for later store
256 result
= (struct db_record
*)talloc_size(mem_ctx
, size
);
257 if (result
== NULL
) {
261 rec_priv
= (struct db_rbt_rec
*)
262 ((char *)result
+ DBWRAP_RBT_ALIGN(sizeof(struct db_record
)));
263 rec_priv
->db_ctx
= ctx
;
265 result
->store
= db_rbt_store
;
266 result
->delete_rec
= db_rbt_delete
;
267 result
->private_data
= rec_priv
;
271 result
->key
= search_key
;
272 result
->value
= search_val
;
275 rec_priv
->node
= NULL
;
276 result
->key
.dptr
= (uint8
*)
277 ((char *)rec_priv
+ sizeof(*rec_priv
));
278 result
->key
.dsize
= key
.dsize
;
279 memcpy(result
->key
.dptr
, key
.dptr
, key
.dsize
);
281 result
->value
= tdb_null
;
287 static int db_rbt_fetch(struct db_context
*db
, TALLOC_CTX
*mem_ctx
,
288 TDB_DATA key
, TDB_DATA
*data
)
290 struct db_rbt_ctx
*ctx
= talloc_get_type_abort(
291 db
->private_data
, struct db_rbt_ctx
);
295 struct db_rbt_node
*r
= NULL
;
296 TDB_DATA search_key
, search_val
;
299 n
= ctx
->tree
.rb_node
;
306 db_rbt_parse_node(r
, &search_key
, &search_val
);
308 res
= db_rbt_compare(key
, search_key
);
327 result
= (uint8
*)talloc_memdup(mem_ctx
, search_val
.dptr
,
329 if (result
== NULL
) {
334 data
->dsize
= search_val
.dsize
;
339 static int db_rbt_traverse(struct db_context
*db
,
340 int (*f
)(struct db_record
*db
,
345 * Nobody uses this so far, and unused code is broken code :-)
350 static int db_rbt_get_seqnum(struct db_context
*db
)
355 static int db_rbt_trans_dummy(struct db_context
*db
)
358 * Transactions are pretty pointless in-memory, just return success.
363 struct db_context
*db_open_rbt(TALLOC_CTX
*mem_ctx
)
365 struct db_context
*result
;
367 result
= talloc(mem_ctx
, struct db_context
);
369 if (result
== NULL
) {
373 result
->private_data
= TALLOC_ZERO_P(result
, struct db_rbt_ctx
);
375 if (result
->private_data
== NULL
) {
380 result
->fetch_locked
= db_rbt_fetch_locked
;
381 result
->fetch
= db_rbt_fetch
;
382 result
->traverse
= db_rbt_traverse
;
383 result
->traverse_read
= db_rbt_traverse
;
384 result
->get_seqnum
= db_rbt_get_seqnum
;
385 result
->transaction_start
= db_rbt_trans_dummy
;
386 result
->transaction_commit
= db_rbt_trans_dummy
;
387 result
->transaction_cancel
= db_rbt_trans_dummy
;