summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSimo Sorce <idra@samba.org>2006-11-26 06:04:35 +0000
committerGerald (Jerry) Carter <jerry@samba.org>2007-10-10 14:28:35 -0500
commit096aa31e945c9e856ea58a52888a3d51d725105d (patch)
treeba8220a067ed3baa46d724c84b661ce355bf9a78
parent4f8b4a8ef19da2bcbeea1ae79e9ebbdb8de08169 (diff)
downloadsamba-096aa31e945c9e856ea58a52888a3d51d725105d.tar.gz
samba-096aa31e945c9e856ea58a52888a3d51d725105d.tar.bz2
samba-096aa31e945c9e856ea58a52888a3d51d725105d.zip
r19907: this function is used a lot
use a binary search to get the right handler (This used to be commit 789e1088c9ce923ca5a6d703b69810eba3bcd4d0)
-rw-r--r--source4/lib/ldb/common/ldb_attributes.c58
1 files changed, 40 insertions, 18 deletions
diff --git a/source4/lib/ldb/common/ldb_attributes.c b/source4/lib/ldb/common/ldb_attributes.c
index 61dd624c25..75a4b60759 100644
--- a/source4/lib/ldb/common/ldb_attributes.c
+++ b/source4/lib/ldb/common/ldb_attributes.c
@@ -39,29 +39,34 @@ int ldb_set_attrib_handlers(struct ldb_context *ldb,
const struct ldb_attrib_handler *handlers,
unsigned num_handlers)
{
- int i;
+ int i, j, n;
struct ldb_attrib_handler *h;
+ n = ldb->schema.num_attrib_handlers + num_handlers;
h = talloc_realloc(ldb, ldb->schema.attrib_handlers,
- struct ldb_attrib_handler,
- ldb->schema.num_attrib_handlers + num_handlers);
+ struct ldb_attrib_handler, n);
if (h == NULL) {
ldb_oom(ldb);
return -1;
}
ldb->schema.attrib_handlers = h;
- memcpy(h + ldb->schema.num_attrib_handlers,
- handlers, sizeof(*h) * num_handlers);
- for (i=0;i<num_handlers;i++) {
- if (h[ldb->schema.num_attrib_handlers+i].flags & LDB_ATTR_FLAG_ALLOCATED) {
- h[ldb->schema.num_attrib_handlers+i].attr = talloc_strdup(ldb->schema.attrib_handlers,
- h[ldb->schema.num_attrib_handlers+i].attr);
- if (h[ldb->schema.num_attrib_handlers+i].attr == NULL) {
+
+ for (i = 0; i < num_handlers; i++) {
+ for (j = 0; j < ldb->schema.num_attrib_handlers; j++) {
+ if (ldb_attr_cmp(handlers[i].attr, h[j].attr) < 0) {
+ memmove(h+j+1, h+j, sizeof(*h) * (ldb->schema.num_attrib_handlers-j));
+ break;
+ }
+ }
+ h[j] = handlers[i];
+ if (h[j].flags & LDB_ATTR_FLAG_ALLOCATED) {
+ h[j].attr = talloc_strdup(h, h[j].attr);
+ if (h[j].attr == NULL) {
ldb_oom(ldb);
return -1;
}
}
+ ldb->schema.num_attrib_handlers++;
}
- ldb->schema.num_attrib_handlers += num_handlers;
return 0;
}
@@ -114,17 +119,34 @@ static const struct ldb_attrib_handler ldb_default_attrib_handler = {
const struct ldb_attrib_handler *ldb_attrib_handler(struct ldb_context *ldb,
const char *attrib)
{
- int i;
+ int i, e, b = 0, r;
const struct ldb_attrib_handler *def = &ldb_default_attrib_handler;
- /* TODO: should be replaced with a binary search, with a sort on add */
- for (i=0;i<ldb->schema.num_attrib_handlers;i++) {
- if (strcmp(ldb->schema.attrib_handlers[i].attr, "*") == 0) {
- def = &ldb->schema.attrib_handlers[i];
- }
- if (ldb_attr_cmp(attrib, ldb->schema.attrib_handlers[i].attr) == 0) {
+
+ /* as handlers are sorted, '*' must be the first if present */
+ if (strcmp(ldb->schema.attrib_handlers[0].attr, "*") == 0) {
+ def = &ldb->schema.attrib_handlers[0];
+ b = 1;
+ }
+
+ /* do a binary search on the array */
+ e = ldb->schema.num_attrib_handlers - 1;
+
+ while (b <= e) {
+
+ i = (b + e) / 2;
+
+ r = ldb_attr_cmp(attrib, ldb->schema.attrib_handlers[i].attr);
+ if (r == 0) {
return &ldb->schema.attrib_handlers[i];
}
+ if (r < 0) {
+ e = i - 1;
+ } else {
+ b = i + 1;
+ }
+
}
+
return def;
}