summaryrefslogtreecommitdiff
path: root/source4/dsdb/schema
diff options
context:
space:
mode:
authorKamen Mazdrashki <kamenim@samba.org>2010-06-19 00:00:08 +0300
committerKamen Mazdrashki <kamenim@samba.org>2010-06-21 02:57:55 +0300
commit267645ca55f7825e87a098c9dc51f132aac1f452 (patch)
tree53aed64981161a0625ffa9fcab5bd0376e470dda /source4/dsdb/schema
parentecbe9a74c6757415720657fbd3ba207989b47848 (diff)
downloadsamba-267645ca55f7825e87a098c9dc51f132aac1f452.tar.gz
samba-267645ca55f7825e87a098c9dc51f132aac1f452.tar.bz2
samba-267645ca55f7825e87a098c9dc51f132aac1f452.zip
s4/dsdb-schema: Index attributes on msDS-IntId value
O(n) search for dsdb_attribute by msDS-IntId value was replaced by binary-search in ordered index. I've choosen the approach of separate index on msDS-IntId values as I think it is more clear what we are searching for. And it should little bit faster as we can clearly determine in which index to perform the search based on ATTID value - ATTIDs based on prefixMap and ATTIDs based on msDS-IntId are in separate ranges. Other way to implement this index was to merge msDS-IntId values in attributeID_id index. This led me to a shorted but not so obvious implementation.
Diffstat (limited to 'source4/dsdb/schema')
-rw-r--r--source4/dsdb/schema/schema.h2
-rw-r--r--source4/dsdb/schema/schema_query.c8
-rw-r--r--source4/dsdb/schema/schema_set.c25
3 files changed, 28 insertions, 7 deletions
diff --git a/source4/dsdb/schema/schema.h b/source4/dsdb/schema/schema.h
index 0cbc21868f..34423be809 100644
--- a/source4/dsdb/schema/schema.h
+++ b/source4/dsdb/schema/schema.h
@@ -209,6 +209,8 @@ struct dsdb_schema {
struct dsdb_attribute **attributes_by_attributeID_id;
struct dsdb_attribute **attributes_by_attributeID_oid;
struct dsdb_attribute **attributes_by_linkID;
+ uint32_t num_int_id_attr;
+ struct dsdb_attribute **attributes_by_msDS_IntId;
struct {
bool we_are_master;
diff --git a/source4/dsdb/schema/schema_query.c b/source4/dsdb/schema/schema_query.c
index 4ff84185f8..8ea79ff4bb 100644
--- a/source4/dsdb/schema/schema_query.c
+++ b/source4/dsdb/schema/schema_query.c
@@ -65,11 +65,9 @@ const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_
/* check for msDS-IntId type attribute */
if (dsdb_pfm_get_attid_type(id) == dsdb_attid_type_intid) {
- for (c = schema->attributes; c; c = c->next) {
- if (c->msDS_IntId == id) {
- return c;
- }
- }
+ BINARY_ARRAY_SEARCH_P(schema->attributes_by_msDS_IntId,
+ schema->num_int_id_attr, msDS_IntId, id, uint32_cmp, c);
+ return c;
}
BINARY_ARRAY_SEARCH_P(schema->attributes_by_attributeID_id,
diff --git a/source4/dsdb/schema/schema_set.c b/source4/dsdb/schema/schema_set.c
index 5ecbad214f..fc255a1cd3 100644
--- a/source4/dsdb/schema/schema_set.c
+++ b/source4/dsdb/schema/schema_set.c
@@ -230,6 +230,7 @@ static int dsdb_setup_sorted_accessors(struct ldb_context *ldb,
struct dsdb_class *cur;
struct dsdb_attribute *a;
unsigned int i;
+ unsigned int num_int_id;
talloc_free(schema->classes_by_lDAPDisplayName);
talloc_free(schema->classes_by_governsID_id);
@@ -268,35 +269,54 @@ static int dsdb_setup_sorted_accessors(struct ldb_context *ldb,
/* now build the attribute accessor arrays */
talloc_free(schema->attributes_by_lDAPDisplayName);
talloc_free(schema->attributes_by_attributeID_id);
+ talloc_free(schema->attributes_by_msDS_IntId);
talloc_free(schema->attributes_by_attributeID_oid);
talloc_free(schema->attributes_by_linkID);
- /* count the attributes */
- for (i=0, a=schema->attributes; a; i++, a=a->next) /* noop */ ;
+ /* count the attributes
+ * and attributes with msDS-IntId set */
+ num_int_id = 0;
+ for (i=0, a=schema->attributes; a; i++, a=a->next) {
+ if (a->msDS_IntId != 0) {
+ num_int_id++;
+ }
+ }
schema->num_attributes = i;
+ schema->num_int_id_attr = num_int_id;
/* setup attributes_by_* */
schema->attributes_by_lDAPDisplayName = talloc_array(schema, struct dsdb_attribute *, i);
schema->attributes_by_attributeID_id = talloc_array(schema, struct dsdb_attribute *, i);
+ schema->attributes_by_msDS_IntId = talloc_array(schema,
+ struct dsdb_attribute *, num_int_id);
schema->attributes_by_attributeID_oid = talloc_array(schema, struct dsdb_attribute *, i);
schema->attributes_by_linkID = talloc_array(schema, struct dsdb_attribute *, i);
if (schema->attributes_by_lDAPDisplayName == NULL ||
schema->attributes_by_attributeID_id == NULL ||
+ schema->attributes_by_msDS_IntId == NULL ||
schema->attributes_by_attributeID_oid == NULL ||
schema->attributes_by_linkID == NULL) {
goto failed;
}
+ num_int_id = 0;
for (i=0, a=schema->attributes; a; i++, a=a->next) {
schema->attributes_by_lDAPDisplayName[i] = a;
schema->attributes_by_attributeID_id[i] = a;
schema->attributes_by_attributeID_oid[i] = a;
schema->attributes_by_linkID[i] = a;
+ /* append attr-by-msDS-IntId values */
+ if (a->msDS_IntId != 0) {
+ schema->attributes_by_msDS_IntId[num_int_id] = a;
+ num_int_id++;
+ }
}
+ SMB_ASSERT(num_int_id == schema->num_int_id_attr);
/* sort the arrays */
TYPESAFE_QSORT(schema->attributes_by_lDAPDisplayName, schema->num_attributes, dsdb_compare_attribute_by_lDAPDisplayName);
TYPESAFE_QSORT(schema->attributes_by_attributeID_id, schema->num_attributes, dsdb_compare_attribute_by_attributeID_id);
+ TYPESAFE_QSORT(schema->attributes_by_msDS_IntId, schema->num_int_id_attr, dsdb_compare_attribute_by_attributeID_id);
TYPESAFE_QSORT(schema->attributes_by_attributeID_oid, schema->num_attributes, dsdb_compare_attribute_by_attributeID_oid);
TYPESAFE_QSORT(schema->attributes_by_linkID, schema->num_attributes, dsdb_compare_attribute_by_linkID);
@@ -309,6 +329,7 @@ failed:
schema->classes_by_cn = NULL;
schema->attributes_by_lDAPDisplayName = NULL;
schema->attributes_by_attributeID_id = NULL;
+ schema->attributes_by_msDS_IntId = NULL;
schema->attributes_by_attributeID_oid = NULL;
schema->attributes_by_linkID = NULL;
ldb_oom(ldb);