summaryrefslogtreecommitdiff
path: root/source3/lib/dbwrap_rbt.c
diff options
context:
space:
mode:
authorVolker Lendecke <vl@samba.org>2008-01-12 10:38:17 +0100
committerVolker Lendecke <vl@samba.org>2008-01-12 20:11:10 +0100
commit4af27ec877d67afc719bccd350dae33ef8dd62b5 (patch)
tree28fc87484cd0959668a09ae7d6cf9d5993dff530 /source3/lib/dbwrap_rbt.c
parent2aa12fff43691ee768468d58c7df51594c73ed53 (diff)
downloadsamba-4af27ec877d67afc719bccd350dae33ef8dd62b5.tar.gz
samba-4af27ec877d67afc719bccd350dae33ef8dd62b5.tar.bz2
samba-4af27ec877d67afc719bccd350dae33ef8dd62b5.zip
Restructure dbwrap_rbt
In this low-level code, play tricks to reduce the number of allocations to the possible minimum. I would not recommend this for higher-level code, but here it pays off. (This used to be commit 71b1e6ff1595fbaa8dd49b996c45541531c7e98c)
Diffstat (limited to 'source3/lib/dbwrap_rbt.c')
-rw-r--r--source3/lib/dbwrap_rbt.c186
1 files changed, 127 insertions, 59 deletions
diff --git a/source3/lib/dbwrap_rbt.c b/source3/lib/dbwrap_rbt.c
index 93d73f29d1..633b695b52 100644
--- a/source3/lib/dbwrap_rbt.c
+++ b/source3/lib/dbwrap_rbt.c
@@ -1,7 +1,7 @@
/*
Unix SMB/CIFS implementation.
Database interface wrapper around red-black trees
- Copyright (C) Volker Lendecke 2007
+ Copyright (C) Volker Lendecke 2007, 2008
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
@@ -20,6 +20,8 @@
#include "includes.h"
#include "rbtree.h"
+#define ALIGN(_size_) (((_size_)+15)&~15)
+
struct db_rbt_ctx {
struct rb_root tree;
};
@@ -44,6 +46,35 @@ struct db_rbt_node {
};
/*
+ * Hide the ugly pointer calculations in a function
+ */
+
+static struct db_rbt_node *db_rbt2node(struct rb_node *node)
+{
+ return (struct db_rbt_node *)
+ ((char *)node - offsetof(struct db_rbt_node, rb_node));
+}
+
+/*
+ * Compare two keys
+ */
+
+static int db_rbt_compare(TDB_DATA a, TDB_DATA b)
+{
+ int res;
+
+ res = memcmp(a.dptr, b.dptr, MIN(a.dsize, b.dsize));
+
+ if ((res < 0) || ((res == 0) && (a.dsize < b.dsize))) {
+ return -1;
+ }
+ if ((res > 0) || ((res == 0) && (a.dsize > b.dsize))) {
+ return 1;
+ }
+ return 0;
+}
+
+/*
* dissect a db_rbt_node into its implicit key and value parts
*/
@@ -58,9 +89,7 @@ static void db_rbt_parse_node(struct db_rbt_node *node,
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_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
struct db_rbt_node *node;
struct rb_node ** p;
@@ -133,22 +162,16 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
parent = (*p);
- r = (struct db_rbt_node *)
- ((char *)(*p) - offsetof(struct db_rbt_node, rb_node));
+ r = db_rbt2node(*p);
db_rbt_parse_node(r, &search_key, &search_val);
- res = memcmp(this_key.dptr, search_key.dptr,
- MIN(this_key.dsize, search_key.dsize));
+ res = db_rbt_compare(this_key, search_key);
- if ((res < 0)
- || ((res == 0)
- && (this_key.dsize < search_key.dsize))) {
+ if (res == -1) {
p = &(*p)->rb_left;
}
- else if ((res > 0)
- || ((res == 0)
- && (this_key.dsize > search_key.dsize))) {
+ else if (res == 1) {
p = &(*p)->rb_right;
}
else {
@@ -164,8 +187,7 @@ static NTSTATUS db_rbt_store(struct db_record *rec, TDB_DATA data, int flag)
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);
+ struct db_rbt_rec *rec_priv = (struct db_rbt_rec *)rec->private_data;
if (rec_priv->node == NULL) {
return NT_STATUS_OK;
@@ -187,85 +209,128 @@ static struct db_record *db_rbt_fetch_locked(struct db_context *db_ctx,
struct db_rbt_rec *rec_priv;
struct db_record *result;
struct rb_node *n;
+ size_t size;
+ bool found = false;
+ struct db_rbt_node *r = NULL;
+ TDB_DATA search_key = tdb_null, search_val = tdb_null;
- result = talloc(mem_ctx, struct db_record);
+ n = ctx->tree.rb_node;
- if (result == NULL) {
- return NULL;
+ while (n != NULL) {
+ int res;
+
+ r = db_rbt2node(n);
+
+ db_rbt_parse_node(r, &search_key, &search_val);
+
+ res = db_rbt_compare(key, search_key);
+
+ if (res == -1) {
+ n = n->rb_left;
+ }
+ else if (res == 1) {
+ n = n->rb_right;
+ }
+ else {
+ found = true;
+ break;
+ }
}
- rec_priv = talloc(result, struct db_rbt_rec);
+ /*
+ * In this low-level routine, play tricks to reduce the number of
+ * tallocs to one. Not recommened for general use, but here it pays
+ * off.
+ */
- if (rec_priv == NULL) {
- TALLOC_FREE(result);
+ size = ALIGN(sizeof(struct db_record)) + sizeof(struct db_rbt_rec);
+
+ if (!found) {
+ /*
+ * We need to keep the key around for later store
+ */
+ size += key.dsize;
+ }
+
+ result = (struct db_record *)talloc_size(mem_ctx, size);
+ if (result == NULL) {
return NULL;
}
+ rec_priv = (struct db_rbt_rec *)
+ ((char *)result + ALIGN(sizeof(struct db_record)));
rec_priv->db_ctx = ctx;
result->store = db_rbt_store;
result->delete_rec = db_rbt_delete;
result->private_data = rec_priv;
+ if (found) {
+ rec_priv->node = r;
+ result->key = search_key;
+ result->value = search_val;
+ }
+ else {
+ rec_priv->node = NULL;
+ result->key.dptr = (uint8 *)
+ ((char *)rec_priv + sizeof(*rec_priv));
+ result->key.dsize = key.dsize;
+ memcpy(result->key.dptr, key.dptr, key.dsize);
+
+ result->value = tdb_null;
+ }
+
+ return result;
+}
+
+static int db_rbt_fetch(struct db_context *db, TALLOC_CTX *mem_ctx,
+ TDB_DATA key, TDB_DATA *data)
+{
+ struct db_rbt_ctx *ctx = talloc_get_type_abort(
+ db->private_data, struct db_rbt_ctx);
+
+ struct rb_node *n;
+ bool found = false;
+ struct db_rbt_node *r = NULL;
+ TDB_DATA search_key, search_val;
+ uint8_t *result;
+
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));
+ r = db_rbt2node(n);
db_rbt_parse_node(r, &search_key, &search_val);
- res = memcmp(key.dptr, search_key.dptr,
- MIN(key.dsize, search_key.dsize));
+ res = db_rbt_compare(key, search_key);
- if ((res < 0)
- || ((res == 0) && (key.dsize < search_key.dsize))) {
+ if (res == -1) {
n = n->rb_left;
}
- else if ((res > 0)
- || ((res == 0) && (key.dsize > search_key.dsize))) {
+ else if (res == 1) {
n = n->rb_right;
}
else {
- rec_priv->node = r;
- result->key = search_key;
- result->value = search_val;
- return result;
+ found = true;
+ break;
}
}
- 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;
+ if (!found) {
+ *data = tdb_null;
+ return 0;
}
- 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))) {
+ result = (uint8 *)talloc_memdup(mem_ctx, search_val.dptr,
+ search_val.dsize);
+ if (result == NULL) {
return -1;
}
- data->dsize = rec->value.dsize;
- data->dptr = (uint8 *)talloc_memdup(mem_ctx, rec->value.dptr,
- rec->value.dsize);
- TALLOC_FREE(rec);
+ data->dptr = result;
+ data->dsize = search_val.dsize;
return 0;
}
@@ -275,6 +340,9 @@ static int db_rbt_traverse(struct db_context *db,
void *private_data),
void *private_data)
{
+ /*
+ * Nobody uses this so far, and unused code is broken code :-)
+ */
return -1;
}