|
|
The branch, v3-2-test has been updated
via e81629339589e2e7f464b3dca55730ff2d0877e4 (commit)
via 66bd6837b593a7127bd5098afc990d3fb7a5a35a (commit)
via 54e5d4404619443caed32e2acff8921cdbff9ed1 (commit)
via c871fd802f3c0c5ef1f63b2d01a636c885f22b23 (commit)
via 8a3289f913fc0432211b0e9937da1d71d4e18893 (commit)
via efa8764c21edfbd09f535900ba37359d72903bf8 (commit)
via 1e214b536b0628db299d701839e62a4ac52727c9 (commit)
from aec5f1512660953168a2c55b2890cd6c076b8a92 (commit)
http://gitweb.samba.org/?p=samba.git;a=shortlog;h=v3-2-test
- Log -----------------------------------------------------------------
commit e81629339589e2e7f464b3dca55730ff2d0877e4
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Sat Nov 24 21:42:46 2007 +0100
use dbwrap_rbt in loadparm.c
commit 66bd6837b593a7127bd5098afc990d3fb7a5a35a
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Sat Nov 24 19:56:41 2007 +0100
Convert ServiceHash to dbwrap
commit 54e5d4404619443caed32e2acff8921cdbff9ed1
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Fri Nov 9 23:43:24 2007 +0100
dbwrap_rbt
This is meant as a replacement for the internal tdb. To me it seems a bit
silly
that for in-memory structures we do our own memory management. With this rbt
based approach we can make use of the system-supplied malloc.
commit c871fd802f3c0c5ef1f63b2d01a636c885f22b23
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Mon Dec 10 13:20:24 2007 +0100
Make the Linux rbtrees compile within Samba
commit 8a3289f913fc0432211b0e9937da1d71d4e18893
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Mon Dec 10 13:11:51 2007 +0100
Add rbtree.[ch] from the Linux kernel
These are copies taken from 94545baded0bfbabdc30a3a4cb48b3db479dd6ef from
Linus' kernel tree
commit efa8764c21edfbd09f535900ba37359d72903bf8
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Sat Nov 24 20:21:19 2007 +0100
Add db_tdb_fetch
commit 1e214b536b0628db299d701839e62a4ac52727c9
Author: Volker Lendecke <vl@xxxxxxxxx>
Date: Sat Nov 24 19:56:16 2007 +0100
Add dbwrap bystring service routines
-----------------------------------------------------------------------
Summary of changes:
source/Makefile.in | 6 +-
source/include/dbwrap.h | 5 +
source/include/rbtree.h | 132 +++++++++++++++
source/lib/dbwrap.c | 42 +++++
source/lib/dbwrap_rbt.c | 303 +++++++++++++++++++++++++++++++++
source/lib/dbwrap_tdb.c | 27 +++
source/lib/rbtree.c | 422 ++++++++++++++++++++++++++++++++++++++++++++++
source/param/loadparm.c | 73 +++++---
source/torture/torture.c | 83 +++++++++
9 files changed, 1063 insertions(+), 30 deletions(-)
create mode 100644 source/include/rbtree.h
create mode 100644 source/lib/dbwrap_rbt.c
create mode 100644 source/lib/rbtree.c
Changeset truncated at 500 lines:
diff --git a/source/Makefile.in b/source/Makefile.in
index f686ac0..e636a91 100644
--- a/source/Makefile.in
+++ b/source/Makefile.in
@@ -224,8 +224,8 @@ TDBBASE_OBJ = lib/tdb/common/tdb.o lib/tdb/common/dump.o
lib/tdb/common/error.o
lib/tdb/common/open.o lib/tdb/common/transaction.o \
lib/tdb/common/traverse.o
-TDB_OBJ = $(TDBBASE_OBJ) lib/util_tdb.o\
- lib/dbwrap.o lib/dbwrap_tdb.o lib/dbwrap_ctdb.o
+TDB_OBJ = $(TDBBASE_OBJ) lib/util_tdb.o \
+ lib/dbwrap.o lib/dbwrap_tdb.o lib/dbwrap_ctdb.o lib/dbwrap_rbt.o
SMBLDAP_OBJ = @SMBLDAP@ @SMBLDAPUTIL@
@@ -282,7 +282,7 @@ TALLOC_OBJ = lib/talloc/talloc.o
LIB_WITHOUT_PROTO_OBJ = $(LIBREPLACE_OBJ) $(SOCKET_WRAPPER_OBJ)
$(NSS_WRAPPER_OBJ) $(TALLOC_OBJ) \
lib/messages.o librpc/gen_ndr/ndr_messaging.o lib/messages_local.o \
lib/messages_ctdbd.o lib/packet.o lib/ctdbd_conn.o lib/talloc_stack.o \
- lib/interfaces.o
+ lib/interfaces.o lib/rbtree.o
LIB_WITH_PROTO_OBJ = $(VERSION_OBJ) lib/charcnv.o lib/debug.o lib/fault.o \
lib/interface.o lib/md4.o \
diff --git a/source/include/dbwrap.h b/source/include/dbwrap.h
index c175f69..3bb378c 100644
--- a/source/include/dbwrap.h
+++ b/source/include/dbwrap.h
@@ -50,5 +50,10 @@ struct db_context *db_open(TALLOC_CTX *mem_ctx,
int hash_size, int tdb_flags,
int open_flags, mode_t mode);
+NTSTATUS dbwrap_delete_bystring(struct db_context *db, const char *key);
+NTSTATUS dbwrap_store_bystring(struct db_context *db, const char *key,
+ TDB_DATA data, int flags);
+TDB_DATA dbwrap_fetch_bystring(struct db_context *db, TALLOC_CTX *mem_ctx,
+ const char *key);
#endif /* __DBWRAP_H__ */
diff --git a/source/include/rbtree.h b/source/include/rbtree.h
new file mode 100644
index 0000000..1cfd346
--- /dev/null
+++ b/source/include/rbtree.h
@@ -0,0 +1,132 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@xxxxxxx>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ Some example of insert and search follows here. The search is a plain
+ normal search over an ordered tree. The insert instead must be implemented
+ int two steps: as first thing the code must insert the element in
+ order as a red leaf in the tree, then the support library function
+ rb_insert_color() must be called. Such function will do the
+ not trivial work to rebalance the rbtree if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+ unsigned long offset)
+{
+ struct rb_node * n = inode->i_rb_page_cache.rb_node;
+ struct page * page;
+
+ while (n)
+ {
+ page = rb_entry(n, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ n = n->rb_left;
+ else if (offset > page->offset)
+ n = n->rb_right;
+ else
+ return page;
+ }
+ return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+ struct rb_node * parent = NULL;
+ struct page * page;
+
+ while (*p)
+ {
+ parent = *p;
+ page = rb_entry(parent, struct page, rb_page_cache);
+
+ if (offset < page->offset)
+ p = &(*p)->rb_left;
+ else if (offset > page->offset)
+ p = &(*p)->rb_right;
+ else
+ return page;
+ }
+
+ rb_link_node(node, parent, p);
+
+ return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct rb_node * node)
+{
+ struct page * ret;
+ if ((ret = __rb_insert_page_cache(inode, offset, node)))
+ goto out;
+ rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+ return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef _LINUX_RBTREE_H
+#define _LINUX_RBTREE_H
+
+struct rb_node
+{
+ unsigned long rb_parent_color;
+ struct rb_node *rb_right;
+ struct rb_node *rb_left;
+};
+
+struct rb_root
+{
+ struct rb_node *rb_node;
+};
+
+
+#define RB_ROOT (struct rb_root) { NULL, }
+
+#if 0
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+#endif
+
+void rb_insert_color(struct rb_node *, struct rb_root *);
+void rb_erase(struct rb_node *, struct rb_root *);
+
+/* Find logical next and previous nodes in a tree */
+struct rb_node *rb_next(struct rb_node *);
+struct rb_node *rb_prev(struct rb_node *);
+struct rb_node *rb_first(struct rb_root *);
+struct rb_node *rb_last(struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new_node,
+ struct rb_root *root);
+
+void rb_link_node(struct rb_node * node, struct rb_node * parent,
+ struct rb_node ** rb_link);
+
+#endif /* _LINUX_RBTREE_H */
diff --git a/source/lib/dbwrap.c b/source/lib/dbwrap.c
index 3abd0e2..4e16d18 100644
--- a/source/lib/dbwrap.c
+++ b/source/lib/dbwrap.c
@@ -84,3 +84,45 @@ struct db_context *db_open(TALLOC_CTX *mem_ctx,
return result;
}
+
+NTSTATUS dbwrap_delete_bystring(struct db_context *db, const char *key)
+{
+ struct db_record *rec;
+ NTSTATUS status;
+
+ rec = db->fetch_locked(db, talloc_tos(), string_term_tdb_data(key));
+ if (rec == NULL) {
+ return NT_STATUS_NO_MEMORY;
+ }
+ status = rec->delete_rec(rec);
+ TALLOC_FREE(rec);
+ return status;
+}
+
+NTSTATUS dbwrap_store_bystring(struct db_context *db, const char *key,
+ TDB_DATA data, int flags)
+{
+ struct db_record *rec;
+ NTSTATUS status;
+
+ rec = db->fetch_locked(db, talloc_tos(), string_term_tdb_data(key));
+ if (rec == NULL) {
+ return NT_STATUS_NO_MEMORY;
+ }
+
+ status = rec->store(rec, data, flags);
+ TALLOC_FREE(rec);
+ return status;
+}
+
+TDB_DATA dbwrap_fetch_bystring(struct db_context *db, TALLOC_CTX *mem_ctx,
+ const char *key)
+{
+ TDB_DATA result;
+
+ if (db->fetch(db, mem_ctx, string_term_tdb_data(key), &result) == -1) {
+ return make_tdb_data(NULL, 0);
+ }
+
+ return result;
+}
diff --git a/source/lib/dbwrap_rbt.c b/source/lib/dbwrap_rbt.c
new file mode 100644
index 0000000..df568a0
--- /dev/null
+++ b/source/lib/dbwrap_rbt.c
@@ -0,0 +1,303 @@
+/*
+ Unix SMB/CIFS implementation.
+ Database interface wrapper around red-black trees
+ Copyright (C) Volker Lendecke 2007
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "includes.h"
+#include "rbtree.h"
+
+struct db_rbt_ctx {
+ struct rb_root tree;
+};
+
+struct db_rbt_rec {
+ struct db_rbt_ctx *db_ctx;
+ struct db_rbt_node *node;
+};
+
+/* The structure that ends up in the tree */
+
+struct db_rbt_node {
+ struct rb_node rb_node;
+ size_t keysize, valuesize;
+
+ /*
+ * key and value are appended implicitly, "data" is only here as a
+ * target for offsetof()
+ */
+
+ char data[];
+};
+
+/*
+ * dissect a db_rbt_node into its implicit key and value parts
+ */
+
+static void db_rbt_parse_node(struct db_rbt_node *node,
+ TDB_DATA *key, TDB_DATA *value)
+{
+ key->dptr = ((uint8 *)node) + offsetof(struct db_rbt_node, data);
+ key->dsize = node->keysize;
+ value->dptr = key->dptr + node->keysize;
+ value->dsize = node->valuesize;
+}
+
+static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
+{
+ struct db_rbt_rec *rec_priv = talloc_get_type_abort(
+ rec->private_data, struct db_rbt_rec);
+
+ struct db_rbt_node *node;
+
+ struct rb_node ** p;
+ struct rb_node * parent;
+
+ TDB_DATA this_key, this_val;
+
+ if (rec_priv->node != NULL) {
+
+ /*
+ * The record was around previously
+ */
+
+ db_rbt_parse_node(rec_priv->node, &this_key, &this_val);
+
+ SMB_ASSERT(this_key.dsize == rec->key.dsize);
+ SMB_ASSERT(memcmp(this_key.dptr, rec->key.dptr,
+ this_key.dsize) == 0);
+
+ if (this_val.dsize >= data.dsize) {
+ /*
+ * The new value fits into the old space
+ */
+ memcpy(this_val.dptr, data.dptr, data.dsize);
+ rec_priv->node->valuesize = data.dsize;
+ return NT_STATUS_OK;
+ }
+
+ /*
+ * We need to delete the key from the tree and start fresh,
+ * there's not enough space in the existing record
+ */
+
+ rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
+ SAFE_FREE(rec_priv->node);
+ }
+
+ node = (struct db_rbt_node *)SMB_MALLOC(
+ offsetof(struct db_rbt_node, data) + rec->key.dsize
+ + data.dsize);
+
+ if (node == NULL) {
+ return NT_STATUS_NO_MEMORY;
+ }
+
+ ZERO_STRUCT(node->rb_node);
+
+ node->keysize = rec->key.dsize;
+ node->valuesize = data.dsize;
+
+ db_rbt_parse_node(node, &this_key, &this_val);
+
+ memcpy(this_key.dptr, rec->key.dptr, node->keysize);
+ memcpy(this_val.dptr, data.dptr, node->valuesize);
+
+ parent = NULL;
+ p = &rec_priv->db_ctx->tree.rb_node;
+
+ while (*p) {
+ struct db_rbt_node *r;
+ TDB_DATA search_key, search_val;
+ int res;
+
+ parent = (*p);
+
+ r = (struct db_rbt_node *)
+ ((char *)(*p) - offsetof(struct db_rbt_node, rb_node));
+
+ db_rbt_parse_node(r, &search_key, &search_val);
+
+ res = memcmp(this_key.dptr, search_key.dptr,
+ MIN(this_key.dsize, search_key.dsize));
+
+ if ((res < 0)
+ || ((res == 0)
+ && (this_key.dsize < search_key.dsize))) {
+ p = &(*p)->rb_left;
+ }
+ else if ((res > 0)
+ || ((res == 0)
+ && (this_key.dsize > search_key.dsize))) {
+ p = &(*p)->rb_right;
+ }
+ else {
+ smb_panic("someone messed with the tree");
+ }
+ }
+
+ rb_link_node(&node->rb_node, parent, p);
+ rb_insert_color(&node->rb_node, &rec_priv->db_ctx->tree);
+
+ return NT_STATUS_OK;
+}
+
+static NTSTATUS db_rbt_delete(struct db_record *rec)
+{
+ struct db_rbt_rec *rec_priv = talloc_get_type_abort(
+ rec->private_data, struct db_rbt_rec);
+
+ if (rec_priv->node == NULL) {
+ return NT_STATUS_OK;
+ }
+
+ rb_erase(&rec_priv->node->rb_node, &rec_priv->db_ctx->tree);
+ SAFE_FREE(rec_priv->node);
+
+ return NT_STATUS_OK;
+}
+
+static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
+ TALLOC_CTX *mem_ctx,
+ TDB_DATA key)
+{
+ struct db_rbt_ctx *ctx = talloc_get_type_abort(
+ db_ctx->private_data, struct db_rbt_ctx);
+
+ struct db_rbt_rec *rec_priv;
+ struct db_record *result;
+ struct rb_node *n;
+
+ result = talloc(mem_ctx, struct db_record);
+
+ if (result == NULL) {
+ return NULL;
+ }
+
+ rec_priv = talloc(result, struct db_rbt_rec);
+
+ if (rec_priv == NULL) {
+ TALLOC_FREE(result);
+ return NULL;
+ }
+
+ rec_priv->db_ctx = ctx;
+
+ result->store = db_rbt_store;
+ result->delete_rec = db_rbt_delete;
+ result->private_data = rec_priv;
+
+ n = ctx->tree.rb_node;
+
+ while (n != NULL) {
+ struct db_rbt_node *r;
+ TDB_DATA search_key, search_val;
+ int res;
+
+ r = (struct db_rbt_node *)
+ ((char *)n - offsetof(struct db_rbt_node, rb_node));
+
+ db_rbt_parse_node(r, &search_key, &search_val);
+
+ res = memcmp(key.dptr, search_key.dptr,
+ MIN(key.dsize, search_key.dsize));
+
+ if ((res < 0)
+ || ((res == 0) && (key.dsize < search_key.dsize))) {
+ n = n->rb_left;
+ }
+ else if ((res > 0)
+ || ((res == 0) && (key.dsize > search_key.dsize))) {
+ n = n->rb_right;
+ }
+ else {
+ rec_priv->node = r;
+ result->key = search_key;
+ result->value = search_val;
+ return result;
+ }
+ }
+
+ result->key.dsize = key.dsize;
+ result->key.dptr = (uint8_t *)talloc_memdup(
+ result, key.dptr, key.dsize);
+
+ if (result->key.dptr == NULL) {
+ TALLOC_FREE(result);
+ return NULL;
+ }
+
+ rec_priv->node = NULL;
+ result->value.dsize = 0;
+ result->value.dptr = NULL;
+ return result;
+}
+
+static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
+ TDB_DATA key, TDB_DATA *data)
+{
+ struct db_record *rec;
+
+ if (!(rec = db->fetch_locked(db, mem_ctx, key))) {
+ return -1;
+ }
+
+ data->dsize = rec->value.dsize;
+ data->dptr = (uint8 *)talloc_memdup(mem_ctx, rec->value.dptr,
+ rec->value.dsize);
+ TALLOC_FREE(rec);
+ return 0;
+}
+
+
+static int db_rbt_traverse(struct db_context *db,
+ int (*f)(struct db_record *db,
--
Samba Shared Repository
|
|