#include "includes.h"
#include "dsdb/samdb/samdb.h"
+/* a binary array search, where the array is an array of pointers to structures,
+ and we want to find a match for 'target' on 'field' in those structures.
+
+ Inputs:
+ array: base pointer to an array of structures
+ arrray_size: number of elements in the array
+ field: the name of the field in the structure we are keying off
+ target: the field value we are looking for
+ comparison_fn: the comparison function
+ result: where the result of the search is put
+
+ if the element is found, then 'result' is set to point to the found array element. If not,
+ then 'result' is set to NULL.
+
+ The array is assumed to be sorted by the same comparison_fn as the
+ search (with, for example, qsort)
+ */
+#define BINARY_ARRAY_SEARCH(array, array_size, field, target, comparison_fn, result) do { \
+ int32_t _b, _e; \
+ (result) = NULL; \
+ for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
+ int32_t _i = (_b+_e)/2; \
+ int _r = comparison_fn(target, array[_i]->field); \
+ if (_r == 0) { (result) = array[_i]; break; } \
+ if (_r < 0) _e = _i - 1; else _b = _i + 1; \
+ } } while (0)
+
+
+static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
+ const struct dsdb_schema *schema,
+ const char **class_list,
+ enum dsdb_attr_list_query query);
+
+static int uint32_cmp(uint32_t c1, uint32_t c2)
+{
+ return c1 - c2;
+}
+
+static int strcasecmp_with_ldb_val(const struct ldb_val *target, const char *str)
+{
+ int ret = strncasecmp((const char *)target->data, str, target->length);
+ if (ret == 0) {
+ return (target->length - strlen(str));
+ }
+ return ret;
+}
+
const struct dsdb_attribute *dsdb_attribute_by_attributeID_id(const struct dsdb_schema *schema,
uint32_t id)
{
- struct dsdb_attribute *cur;
+ struct dsdb_attribute *c;
/*
* 0xFFFFFFFF is used as value when no mapping table is available,
*/
if (id == 0xFFFFFFFF) return NULL;
- /* TODO: add binary search */
- for (cur = schema->attributes; cur; cur = cur->next) {
- if (cur->attributeID_id != id) continue;
-
- return cur;
- }
-
- return NULL;
+ BINARY_ARRAY_SEARCH(schema->attributes_by_attributeID_id,
+ schema->num_attributes, attributeID_id, id, uint32_cmp, c);
+ return c;
}
const struct dsdb_attribute *dsdb_attribute_by_attributeID_oid(const struct dsdb_schema *schema,
const char *oid)
{
- struct dsdb_attribute *cur;
+ struct dsdb_attribute *c;
if (!oid) return NULL;
- /* TODO: add binary search */
- for (cur = schema->attributes; cur; cur = cur->next) {
- if (strcmp(cur->attributeID_oid, oid) != 0) continue;
-
- return cur;
- }
-
- return NULL;
+ BINARY_ARRAY_SEARCH(schema->attributes_by_attributeID_oid,
+ schema->num_attributes, attributeID_oid, oid, strcasecmp, c);
+ return c;
}
const struct dsdb_attribute *dsdb_attribute_by_lDAPDisplayName(const struct dsdb_schema *schema,
const char *name)
{
- struct dsdb_attribute *cur;
+ struct dsdb_attribute *c;
if (!name) return NULL;
- /* TODO: add binary search */
- for (cur = schema->attributes; cur; cur = cur->next) {
- if (strcasecmp(cur->lDAPDisplayName, name) != 0) continue;
-
- return cur;
- }
-
- return NULL;
+ BINARY_ARRAY_SEARCH(schema->attributes_by_lDAPDisplayName,
+ schema->num_attributes, lDAPDisplayName, name, strcasecmp, c);
+ return c;
}
const struct dsdb_attribute *dsdb_attribute_by_linkID(const struct dsdb_schema *schema,
int linkID)
{
- struct dsdb_attribute *cur;
+ struct dsdb_attribute *c;
- /* TODO: add binary search */
- for (cur = schema->attributes; cur; cur = cur->next) {
- if (cur->linkID != linkID) continue;
-
- return cur;
- }
-
- return NULL;
+ BINARY_ARRAY_SEARCH(schema->attributes_by_linkID,
+ schema->num_attributes, linkID, linkID, uint32_cmp, c);
+ return c;
}
const struct dsdb_class *dsdb_class_by_governsID_id(const struct dsdb_schema *schema,
uint32_t id)
{
- struct dsdb_class *cur;
+ struct dsdb_class *c;
/*
* 0xFFFFFFFF is used as value when no mapping table is available,
*/
if (id == 0xFFFFFFFF) return NULL;
- /* TODO: add binary search */
- for (cur = schema->classes; cur; cur = cur->next) {
- if (cur->governsID_id != id) continue;
-
- return cur;
- }
-
- return NULL;
+ BINARY_ARRAY_SEARCH(schema->classes_by_governsID_id,
+ schema->num_classes, governsID_id, id, uint32_cmp, c);
+ return c;
}
const struct dsdb_class *dsdb_class_by_governsID_oid(const struct dsdb_schema *schema,
const char *oid)
{
- struct dsdb_class *cur;
-
+ struct dsdb_class *c;
if (!oid) return NULL;
-
- /* TODO: add binary search */
- for (cur = schema->classes; cur; cur = cur->next) {
- if (strcmp(cur->governsID_oid, oid) != 0) continue;
-
- return cur;
- }
-
- return NULL;
+ BINARY_ARRAY_SEARCH(schema->classes_by_governsID_oid,
+ schema->num_classes, governsID_oid, oid, strcasecmp, c);
+ return c;
}
const struct dsdb_class *dsdb_class_by_lDAPDisplayName(const struct dsdb_schema *schema,
const char *name)
{
- struct dsdb_class *cur;
-
+ struct dsdb_class *c;
if (!name) return NULL;
+ BINARY_ARRAY_SEARCH(schema->classes_by_lDAPDisplayName,
+ schema->num_classes, lDAPDisplayName, name, strcasecmp, c);
+ return c;
+}
- /* TODO: add binary search */
- for (cur = schema->classes; cur; cur = cur->next) {
- if (strcasecmp(cur->lDAPDisplayName, name) != 0) continue;
-
- return cur;
- }
-
- return NULL;
+const struct dsdb_class *dsdb_class_by_lDAPDisplayName_ldb_val(const struct dsdb_schema *schema,
+ struct ldb_val *name)
+{
+ struct dsdb_class *c;
+ if (!name) return NULL;
+ BINARY_ARRAY_SEARCH(schema->classes_by_lDAPDisplayName,
+ schema->num_classes, lDAPDisplayName, name, strcasecmp_with_ldb_val, c);
+ return c;
}
const struct dsdb_class *dsdb_class_by_cn(const struct dsdb_schema *schema,
const char *cn)
{
- struct dsdb_class *cur;
-
+ struct dsdb_class *c;
if (!cn) return NULL;
+ BINARY_ARRAY_SEARCH(schema->classes_by_cn,
+ schema->num_classes, cn, cn, strcasecmp, c);
+ return c;
+}
- /* TODO: add binary search */
- for (cur = schema->classes; cur; cur = cur->next) {
- if (strcasecmp(cur->cn, cn) != 0) continue;
-
- return cur;
- }
-
- return NULL;
+const struct dsdb_class *dsdb_class_by_cn_ldb_val(const struct dsdb_schema *schema,
+ struct ldb_val *cn)
+{
+ struct dsdb_class *c;
+ if (!cn) return NULL;
+ BINARY_ARRAY_SEARCH(schema->classes_by_cn,
+ schema->num_classes, cn, cn, strcasecmp_with_ldb_val, c);
+ return c;
}
const char *dsdb_lDAPDisplayName_by_id(const struct dsdb_schema *schema,
const struct dsdb_attribute *a;
const struct dsdb_class *c;
- /* TODO: add binary search */
a = dsdb_attribute_by_attributeID_id(schema, id);
if (a) {
return a->lDAPDisplayName;
return WERR_OK;
}
-char **merge_attr_list(TALLOC_CTX *mem_ctx,
- char **attrs, const char **new_attrs)
+const char **merge_attr_list(TALLOC_CTX *mem_ctx,
+ const char **attrs, const char * const*new_attrs)
{
- char **ret_attrs;
+ const char **ret_attrs;
int i;
- size_t new_len, orig_len = str_list_length((const char **)attrs);
+ size_t new_len, orig_len = str_list_length(attrs);
if (!new_attrs) {
return attrs;
}
ret_attrs = talloc_realloc(mem_ctx,
- attrs, char *, orig_len + str_list_length(new_attrs) + 1);
+ attrs, const char *, orig_len + str_list_length(new_attrs) + 1);
if (ret_attrs) {
for (i=0; i < str_list_length(new_attrs); i++) {
ret_attrs[orig_len + i] = new_attrs[i];
considering subclasses, auxillary classes etc)
*/
-char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *class, enum dsdb_attr_list_query query)
+const char **dsdb_attribute_list(TALLOC_CTX *mem_ctx, const struct dsdb_class *sclass, enum dsdb_attr_list_query query)
{
- char **attr_list = NULL;
+ const char **attr_list = NULL;
switch (query) {
case DSDB_SCHEMA_ALL_MAY:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->mayContain);
- attr_list = merge_attr_list(mem_ctx, attr_list, class->systemMayContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
break;
case DSDB_SCHEMA_ALL_MUST:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->mustContain);
- attr_list = merge_attr_list(mem_ctx, attr_list, class->systemMustContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
break;
case DSDB_SCHEMA_SYS_MAY:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->systemMayContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
break;
case DSDB_SCHEMA_SYS_MUST:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->systemMustContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
break;
case DSDB_SCHEMA_MAY:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->mayContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
break;
case DSDB_SCHEMA_MUST:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->mustContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
break;
case DSDB_SCHEMA_ALL:
- attr_list = merge_attr_list(mem_ctx, attr_list, class->mayContain);
- attr_list = merge_attr_list(mem_ctx, attr_list, class->systemMayContain);
- attr_list = merge_attr_list(mem_ctx, attr_list, class->mustContain);
- attr_list = merge_attr_list(mem_ctx, attr_list, class->systemMustContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mayContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMayContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->mustContain);
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass->systemMustContain);
break;
}
return attr_list;
}
-static char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
- const struct dsdb_schema *schema,
- const char **class_list,
- enum dsdb_attr_list_query query)
+static const char **attribute_list_from_class(TALLOC_CTX *mem_ctx,
+ const struct dsdb_schema *schema,
+ const struct dsdb_class *sclass,
+ enum dsdb_attr_list_query query)
{
- int i;
- const struct dsdb_class *class;
+ const char **this_class_list;
+ const char **system_recursive_list;
+ const char **recursive_list;
+ const char **attr_list;
+
+ this_class_list = dsdb_attribute_list(mem_ctx, sclass, query);
+
+ recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
+ sclass->systemAuxiliaryClass,
+ query);
+
+ system_recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
+ sclass->auxiliaryClass,
+ query);
- char **attr_list = NULL;
- char **this_class_list;
- char **recursive_list;
+ attr_list = this_class_list;
+ attr_list = merge_attr_list(mem_ctx, attr_list, recursive_list);
+ attr_list = merge_attr_list(mem_ctx, attr_list, system_recursive_list);
+ return attr_list;
+}
+
+/* Return a full attribute list for a given class list (as a ldb_message_element)
+
+ Via attribute_list_from_class() this calls itself when recursing on auxiliary classes
+ */
+static const char **dsdb_full_attribute_list_internal(TALLOC_CTX *mem_ctx,
+ const struct dsdb_schema *schema,
+ const char **class_list,
+ enum dsdb_attr_list_query query)
+{
+ int i;
+ const char **attr_list = NULL;
for (i=0; class_list && class_list[i]; i++) {
- class = dsdb_class_by_lDAPDisplayName(schema, class_list[i]);
-
- this_class_list = dsdb_attribute_list(mem_ctx, class, query);
- attr_list = merge_attr_list(mem_ctx, attr_list, (const char **)this_class_list);
+ const char **sclass_list
+ = attribute_list_from_class(mem_ctx, schema,
+ dsdb_class_by_lDAPDisplayName(schema, class_list[i]),
+ query);
- recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
- class->systemAuxiliaryClass,
- query);
-
- attr_list = merge_attr_list(mem_ctx, attr_list, (const char **)recursive_list);
-
- recursive_list = dsdb_full_attribute_list_internal(mem_ctx, schema,
- class->auxiliaryClass,
- query);
-
- attr_list = merge_attr_list(mem_ctx, attr_list, (const char **)recursive_list);
-
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
}
return attr_list;
}
-char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,
- const struct dsdb_schema *schema,
- const char **class_list,
- enum dsdb_attr_list_query query)
+/* Return a full attribute list for a given class list (as a ldb_message_element)
+
+ Using the ldb_message_element ensures we do length-limited
+ comparisons, rather than casting the possibly-unterminated string
+
+ Via attribute_list_from_class() this calls
+ dsdb_full_attribute_list_internal() when recursing on auxiliary classes
+ */
+static const char **dsdb_full_attribute_list_internal_el(TALLOC_CTX *mem_ctx,
+ const struct dsdb_schema *schema,
+ const struct ldb_message_element *el,
+ enum dsdb_attr_list_query query)
{
- char **attr_list = dsdb_full_attribute_list_internal(mem_ctx, schema, class_list, query);
- size_t new_len = str_list_length((const char **)attr_list);
+ int i;
+ const char **attr_list = NULL;
+ for (i=0; i < el->num_values; i++) {
+ const char **sclass_list
+ = attribute_list_from_class(mem_ctx, schema,
+ dsdb_class_by_lDAPDisplayName_ldb_val(schema, &el->values[i]),
+ query);
+
+ attr_list = merge_attr_list(mem_ctx, attr_list, sclass_list);
+ }
+ return attr_list;
+}
+
+/* Helper function to remove duplicates from the attribute list to be returned */
+static const char **dedup_attr_list(const char **attr_list)
+{
+ size_t new_len = str_list_length(attr_list);
/* Remove duplicates */
if (new_len > 1) {
int i;
(comparison_fn_t)strcasecmp);
for (i=1 ; i < new_len; i++) {
- char **val1 = &attr_list[i-1];
- char **val2 = &attr_list[i];
+ const char **val1 = &attr_list[i-1];
+ const char **val2 = &attr_list[i];
if (ldb_attr_cmp(*val1, *val2) == 0) {
memmove(val1, val2, (new_len - i) * sizeof( *attr_list));
new_len--;
}
return attr_list;
}
+
+/* Return a full attribute list for a given class list (as a ldb_message_element)
+
+ Using the ldb_message_element ensures we do length-limited
+ comparisons, rather than casting the possibly-unterminated string
+
+ The result contains only unique values
+ */
+const char **dsdb_full_attribute_list(TALLOC_CTX *mem_ctx,
+ const struct dsdb_schema *schema,
+ const struct ldb_message_element *class_list,
+ enum dsdb_attr_list_query query)
+{
+ const char **attr_list = dsdb_full_attribute_list_internal_el(mem_ctx, schema, class_list, query);
+ return dedup_attr_list(attr_list);
+}