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"
25 #include "../lib/util/dlinklist.h"
27 #define DBWRAP_RBT_ALIGN(_size_) (((_size_)+15)&~15)
31 struct db_rbt_node
*nodes
;
33 struct db_rbt_node
**traverse_nextp
;
37 struct db_rbt_node
*node
;
40 /* The structure that ends up in the tree */
43 struct rb_node rb_node
;
44 size_t keysize
, valuesize
;
45 struct db_rbt_node
*prev
, *next
;
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 size_t key_offset
, value_offset
;
86 key_offset
= DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node
));
87 key
->dptr
= ((uint8_t *)node
) + key_offset
;
88 key
->dsize
= node
->keysize
;
90 value_offset
= DBWRAP_RBT_ALIGN(node
->keysize
);
91 value
->dptr
= key
->dptr
+ value_offset
;
92 value
->dsize
= node
->valuesize
;
95 static ssize_t
db_rbt_reclen(size_t keylen
, size_t valuelen
)
99 len
= DBWRAP_RBT_ALIGN(sizeof(struct db_rbt_node
));
101 tmp
= DBWRAP_RBT_ALIGN(keylen
);
112 if (len
< valuelen
) {
121 static NTSTATUS
db_rbt_store(struct db_record
*rec
, TDB_DATA data
, int flag
)
123 struct db_rbt_ctx
*db_ctx
= talloc_get_type_abort(
124 rec
->db
->private_data
, struct db_rbt_ctx
);
125 struct db_rbt_rec
*rec_priv
= (struct db_rbt_rec
*)rec
->private_data
;
126 struct db_rbt_node
*node
;
129 struct rb_node
*parent
= NULL
;
130 struct db_rbt_node
*parent_node
= NULL
;
133 TDB_DATA this_key
, this_val
;
135 if (db_ctx
->traverse_read
> 0) {
136 return NT_STATUS_MEDIA_WRITE_PROTECTED
;
139 if (rec_priv
->node
!= NULL
) {
142 * The record was around previously
145 db_rbt_parse_node(rec_priv
->node
, &this_key
, &this_val
);
147 SMB_ASSERT(this_key
.dsize
== rec
->key
.dsize
);
148 SMB_ASSERT(memcmp(this_key
.dptr
, rec
->key
.dptr
,
149 this_key
.dsize
) == 0);
151 if (this_val
.dsize
>= data
.dsize
) {
153 * The new value fits into the old space
155 memcpy(this_val
.dptr
, data
.dptr
, data
.dsize
);
156 rec_priv
->node
->valuesize
= data
.dsize
;
161 reclen
= db_rbt_reclen(rec
->key
.dsize
, data
.dsize
);
163 return NT_STATUS_INSUFFICIENT_RESOURCES
;
166 node
= talloc_zero_size(db_ctx
, reclen
);
168 return NT_STATUS_NO_MEMORY
;
171 if (rec_priv
->node
!= NULL
) {
172 if (db_ctx
->traverse_nextp
!= NULL
) {
173 if (*db_ctx
->traverse_nextp
== rec_priv
->node
) {
174 *db_ctx
->traverse_nextp
= node
;
179 * We need to delete the key from the tree and start fresh,
180 * there's not enough space in the existing record
183 rb_erase(&rec_priv
->node
->rb_node
, &db_ctx
->tree
);
184 DLIST_REMOVE(db_ctx
->nodes
, rec_priv
->node
);
187 * Keep the existing node around for a while: If the record
188 * existed before, we reference the key data in there.
192 node
->keysize
= rec
->key
.dsize
;
193 node
->valuesize
= data
.dsize
;
195 db_rbt_parse_node(node
, &this_key
, &this_val
);
197 memcpy(this_key
.dptr
, rec
->key
.dptr
, node
->keysize
);
198 TALLOC_FREE(rec_priv
->node
);
199 rec_priv
->node
= node
;
201 memcpy(this_val
.dptr
, data
.dptr
, node
->valuesize
);
204 p
= &db_ctx
->tree
.rb_node
;
207 struct db_rbt_node
*r
;
208 TDB_DATA search_key
, search_val
;
216 db_rbt_parse_node(r
, &search_key
, &search_val
);
218 res
= db_rbt_compare(this_key
, search_key
);
227 smb_panic("someone messed with the tree");
231 rb_link_node(&node
->rb_node
, parent
, p
);
232 DLIST_ADD_AFTER(db_ctx
->nodes
, node
, parent_node
);
233 rb_insert_color(&node
->rb_node
, &db_ctx
->tree
);
238 static NTSTATUS
db_rbt_delete(struct db_record
*rec
)
240 struct db_rbt_ctx
*db_ctx
= talloc_get_type_abort(
241 rec
->db
->private_data
, struct db_rbt_ctx
);
242 struct db_rbt_rec
*rec_priv
= (struct db_rbt_rec
*)rec
->private_data
;
244 if (db_ctx
->traverse_read
> 0) {
245 return NT_STATUS_MEDIA_WRITE_PROTECTED
;
248 if (rec_priv
->node
== NULL
) {
252 if (db_ctx
->traverse_nextp
!= NULL
) {
253 if (*db_ctx
->traverse_nextp
== rec_priv
->node
) {
254 *db_ctx
->traverse_nextp
= rec_priv
->node
->next
;
258 rb_erase(&rec_priv
->node
->rb_node
, &db_ctx
->tree
);
259 DLIST_REMOVE(db_ctx
->nodes
, rec_priv
->node
);
260 TALLOC_FREE(rec_priv
->node
);
265 struct db_rbt_search_result
{
268 struct db_rbt_node
* node
;
271 static bool db_rbt_search_internal(struct db_context
*db
, TDB_DATA key
,
272 struct db_rbt_search_result
*result
)
274 struct db_rbt_ctx
*ctx
= talloc_get_type_abort(
275 db
->private_data
, struct db_rbt_ctx
);
279 struct db_rbt_node
*r
= NULL
;
280 TDB_DATA search_key
= { 0 };
281 TDB_DATA search_val
= { 0 };
283 n
= ctx
->tree
.rb_node
;
290 db_rbt_parse_node(r
, &search_key
, &search_val
);
292 res
= db_rbt_compare(key
, search_key
);
305 if (result
!= NULL
) {
307 result
->key
= search_key
;
308 result
->val
= search_val
;
311 ZERO_STRUCT(*result
);
317 static struct db_record
*db_rbt_fetch_locked(struct db_context
*db_ctx
,
321 struct db_rbt_rec
*rec_priv
;
322 struct db_record
*result
;
325 struct db_rbt_search_result res
;
327 found
= db_rbt_search_internal(db_ctx
, key
, &res
);
330 * In this low-level routine, play tricks to reduce the number of
331 * tallocs to one. Not recommened for general use, but here it pays
335 size
= DBWRAP_RBT_ALIGN(sizeof(struct db_record
))
336 + sizeof(struct db_rbt_rec
);
340 * We need to keep the key around for later store
345 result
= (struct db_record
*)talloc_size(mem_ctx
, size
);
346 if (result
== NULL
) {
350 rec_priv
= (struct db_rbt_rec
*)
351 ((char *)result
+ DBWRAP_RBT_ALIGN(sizeof(struct db_record
)));
353 result
->store
= db_rbt_store
;
354 result
->delete_rec
= db_rbt_delete
;
355 result
->private_data
= rec_priv
;
357 rec_priv
->node
= res
.node
;
358 result
->value
= res
.val
;
361 result
->key
= res
.key
;
364 result
->key
.dptr
= (uint8_t *)
365 ((char *)rec_priv
+ sizeof(*rec_priv
));
366 result
->key
.dsize
= key
.dsize
;
367 memcpy(result
->key
.dptr
, key
.dptr
, key
.dsize
);
373 static int db_rbt_exists(struct db_context
*db
, TDB_DATA key
)
375 return db_rbt_search_internal(db
, key
, NULL
);
378 static int db_rbt_wipe(struct db_context
*db
)
380 struct db_rbt_ctx
*old_ctx
= talloc_get_type_abort(
381 db
->private_data
, struct db_rbt_ctx
);
382 struct db_rbt_ctx
*new_ctx
= talloc_zero(db
, struct db_rbt_ctx
);
383 if (new_ctx
== NULL
) {
386 db
->private_data
= new_ctx
;
387 talloc_free(old_ctx
);
391 static NTSTATUS
db_rbt_parse_record(struct db_context
*db
, TDB_DATA key
,
392 void (*parser
)(TDB_DATA key
, TDB_DATA data
,
396 struct db_rbt_search_result res
;
397 bool found
= db_rbt_search_internal(db
, key
, &res
);
400 return NT_STATUS_NOT_FOUND
;
402 parser(res
.key
, res
.val
, private_data
);
406 static int db_rbt_traverse_internal(struct db_context
*db
,
407 int (*f
)(struct db_record
*db
,
409 void *private_data
, uint32_t* count
,
412 struct db_rbt_ctx
*ctx
= talloc_get_type_abort(
413 db
->private_data
, struct db_rbt_ctx
);
414 struct db_rbt_node
*cur
= NULL
;
415 struct db_rbt_node
*next
= NULL
;
418 for (cur
= ctx
->nodes
; cur
!= NULL
; cur
= next
) {
419 struct db_record rec
;
420 struct db_rbt_rec rec_priv
;
423 next
= rec_priv
.node
->next
;
427 rec
.private_data
= &rec_priv
;
428 rec
.store
= db_rbt_store
;
429 rec
.delete_rec
= db_rbt_delete
;
430 db_rbt_parse_node(rec_priv
.node
, &rec
.key
, &rec
.value
);
433 ctx
->traverse_nextp
= &next
;
435 ret
= f(&rec
, private_data
);
438 ctx
->traverse_nextp
= NULL
;
443 if (rec_priv
.node
!= NULL
) {
444 next
= rec_priv
.node
->next
;
451 static int db_rbt_traverse_read(struct db_context
*db
,
452 int (*f
)(struct db_record
*db
,
456 struct db_rbt_ctx
*ctx
= talloc_get_type_abort(
457 db
->private_data
, struct db_rbt_ctx
);
461 ctx
->traverse_read
++;
462 ret
= db_rbt_traverse_internal(db
,
463 f
, private_data
, &count
,
465 ctx
->traverse_read
--;
469 if (count
> INT_MAX
) {
475 static int db_rbt_traverse(struct db_context
*db
,
476 int (*f
)(struct db_record
*db
,
480 struct db_rbt_ctx
*ctx
= talloc_get_type_abort(
481 db
->private_data
, struct db_rbt_ctx
);
485 if (ctx
->traverse_nextp
!= NULL
) {
489 if (ctx
->traverse_read
> 0) {
490 return db_rbt_traverse_read(db
, f
, private_data
);
493 ret
= db_rbt_traverse_internal(db
,
494 f
, private_data
, &count
,
499 if (count
> INT_MAX
) {
505 static int db_rbt_get_seqnum(struct db_context
*db
)
510 static int db_rbt_trans_dummy(struct db_context
*db
)
513 * Transactions are pretty pointless in-memory, just return success.
518 static size_t db_rbt_id(struct db_context
*db
, uint8_t *id
, size_t idlen
)
520 if (idlen
>= sizeof(struct db_context
*)) {
521 memcpy(id
, &db
, sizeof(struct db_context
*));
523 return sizeof(struct db_context
*);
526 struct db_context
*db_open_rbt(TALLOC_CTX
*mem_ctx
)
528 struct db_context
*result
;
530 result
= talloc_zero(mem_ctx
, struct db_context
);
532 if (result
== NULL
) {
536 result
->private_data
= talloc_zero(result
, struct db_rbt_ctx
);
538 if (result
->private_data
== NULL
) {
543 result
->fetch_locked
= db_rbt_fetch_locked
;
544 result
->traverse
= db_rbt_traverse
;
545 result
->traverse_read
= db_rbt_traverse_read
;
546 result
->get_seqnum
= db_rbt_get_seqnum
;
547 result
->transaction_start
= db_rbt_trans_dummy
;
548 result
->transaction_commit
= db_rbt_trans_dummy
;
549 result
->transaction_cancel
= db_rbt_trans_dummy
;
550 result
->exists
= db_rbt_exists
;
551 result
->wipe
= db_rbt_wipe
;
552 result
->parse_record
= db_rbt_parse_record
;
553 result
->id
= db_rbt_id
;
554 result
->name
= "dbwrap rbt";