Author: idra Date: 2006-11-26 06:04:35 +0000 (Sun, 26 Nov 2006) New Revision: 19907
WebSVN: http://websvn.samba.org/cgi-bin/viewcvs.cgi?view=rev&root=samba&rev=19907 Log: this function is used a lot use a binary search to get the right handler Modified: branches/SAMBA_4_0/source/lib/ldb/common/ldb_attributes.c Changeset: Modified: branches/SAMBA_4_0/source/lib/ldb/common/ldb_attributes.c =================================================================== --- branches/SAMBA_4_0/source/lib/ldb/common/ldb_attributes.c 2006-11-26 04:39:17 UTC (rev 19906) +++ branches/SAMBA_4_0/source/lib/ldb/common/ldb_attributes.c 2006-11-26 06:04:35 UTC (rev 19907) @@ -39,29 +39,34 @@ 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 @@ 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; }
