summaryrefslogtreecommitdiff
path: root/source4/lib/ldb/common
diff options
context:
space:
mode:
Diffstat (limited to 'source4/lib/ldb/common')
-rw-r--r--source4/lib/ldb/common/ldb.c129
-rw-r--r--source4/lib/ldb/common/ldb_ldif.c476
-rw-r--r--source4/lib/ldb/common/ldb_parse.c460
-rw-r--r--source4/lib/ldb/common/util.c102
4 files changed, 1167 insertions, 0 deletions
diff --git a/source4/lib/ldb/common/ldb.c b/source4/lib/ldb/common/ldb.c
new file mode 100644
index 0000000000..90b77e1e7f
--- /dev/null
+++ b/source4/lib/ldb/common/ldb.c
@@ -0,0 +1,129 @@
+/*
+ ldb database library
+
+ Copyright (C) Andrew Tridgell 2004
+
+ ** NOTE! The following LGPL license applies to the ldb
+ ** library. This does NOT imply that all of Samba is released
+ ** under the LGPL
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+/*
+ * Name: ldb
+ *
+ * Component: ldb core API
+ *
+ * Description: core API routines interfacing to ldb backends
+ *
+ * Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+/*
+ connect to a database. The URL can either be one of the following forms
+ ldb://path
+ ldapi://path
+
+ flags is made up of LDB_FLG_*
+
+ the options are passed uninterpreted to the backend, and are
+ backend specific
+*/
+struct ldb_context *ldb_connect(const char *url, unsigned int flags,
+ const char *options[])
+{
+
+ if (strncmp(url, "tdb:", 4) == 0) {
+ return ltdb_connect(url, flags, options);
+ }
+
+ if (strncmp(url, "ldap", 4) == 0) {
+ return lldb_connect(url, flags, options);
+ }
+
+ errno = EINVAL;
+ return NULL;
+}
+
+/*
+ close the connection to the database
+*/
+int ldb_close(struct ldb_context *ldb)
+{
+ return ldb->ops->close(ldb);
+}
+
+
+/*
+ search the database given a LDAP-like search expression
+
+ return the number of records found, or -1 on error
+*/
+int ldb_search(struct ldb_context *ldb,
+ const char *base,
+ enum ldb_scope scope,
+ const char *expression,
+ const char *attrs[], struct ldb_message ***res)
+{
+ return ldb->ops->search(ldb, base, scope, expression, attrs, res);
+}
+
+/*
+ free a set of messages returned by ldb_search
+*/
+int ldb_search_free(struct ldb_context *ldb, struct ldb_message **msgs)
+{
+ return ldb->ops->search_free(ldb, msgs);
+}
+
+
+/*
+ add a record to the database. Will fail if a record with the given class and key
+ already exists
+*/
+int ldb_add(struct ldb_context *ldb,
+ const struct ldb_message *message)
+{
+ return ldb->ops->add(ldb, message);
+}
+
+/*
+ modify the specified attributes of a record
+*/
+int ldb_modify(struct ldb_context *ldb,
+ const struct ldb_message *message)
+{
+ return ldb->ops->modify(ldb, message);
+}
+
+
+/*
+ delete a record from the database
+*/
+int ldb_delete(struct ldb_context *ldb, const char *dn)
+{
+ return ldb->ops->delete(ldb, dn);
+}
+
+/*
+ return extended error information
+*/
+const char *ldb_errstring(struct ldb_context *ldb)
+{
+ return ldb->ops->errstring(ldb);
+}
diff --git a/source4/lib/ldb/common/ldb_ldif.c b/source4/lib/ldb/common/ldb_ldif.c
new file mode 100644
index 0000000000..198c984823
--- /dev/null
+++ b/source4/lib/ldb/common/ldb_ldif.c
@@ -0,0 +1,476 @@
+/*
+ ldb database library
+
+ Copyright (C) Andrew Tridgell 2004
+
+ ** NOTE! The following LGPL license applies to the ldb
+ ** library. This does NOT imply that all of Samba is released
+ ** under the LGPL
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+/*
+ * Name: ldb
+ *
+ * Component: ldif routines
+ *
+ * Description: ldif pack/unpack routines
+ *
+ * Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+
+/*
+ this base64 decoder was taken from jitterbug (written by tridge).
+ we might need to replace it with a new version
+*/
+static int base64_decode(char *s)
+{
+ const char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+ int bit_offset, byte_offset, idx, i, n;
+ unsigned char *d = (unsigned char *)s;
+ char *p;
+
+ n=i=0;
+
+ while (*s && (p=strchr(b64,*s))) {
+ idx = (int)(p - b64);
+ byte_offset = (i*6)/8;
+ bit_offset = (i*6)%8;
+ d[byte_offset] &= ~((1<<(8-bit_offset))-1);
+ if (bit_offset < 3) {
+ d[byte_offset] |= (idx << (2-bit_offset));
+ n = byte_offset+1;
+ } else {
+ d[byte_offset] |= (idx >> (bit_offset-2));
+ d[byte_offset+1] = 0;
+ d[byte_offset+1] |= (idx << (8-(bit_offset-2))) & 0xFF;
+ n = byte_offset+2;
+ }
+ s++; i++;
+ }
+
+ if (*s && !p) {
+ /* the only termination allowed */
+ if (*s != '=') {
+ return -1;
+ }
+ }
+
+ /* null terminate */
+ d[n] = 0;
+ return n;
+}
+
+
+/*
+ encode as base64
+ caller frees
+*/
+char *ldb_base64_encode(const char *buf, int len)
+{
+ const char *b64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+ int bit_offset, byte_offset, idx, i;
+ unsigned char *d = (unsigned char *)buf;
+ int bytes = (len*8 + 5)/6;
+ char *out;
+
+ out = malloc(bytes+2);
+ if (!out) return NULL;
+
+ for (i=0;i<bytes;i++) {
+ byte_offset = (i*6)/8;
+ bit_offset = (i*6)%8;
+ if (bit_offset < 3) {
+ idx = (d[byte_offset] >> (2-bit_offset)) & 0x3F;
+ } else {
+ idx = (d[byte_offset] << (bit_offset-2)) & 0x3F;
+ if (byte_offset+1 < len) {
+ idx |= (d[byte_offset+1] >> (8-(bit_offset-2)));
+ }
+ }
+ out[i] = b64[idx];
+ }
+
+ out[i++] = '=';
+ out[i] = 0;
+
+ return out;
+}
+
+/*
+ see if a buffer should be base64 encoded
+*/
+int ldb_should_b64_encode(const struct ldb_val *val)
+{
+ int i;
+ unsigned char *p = val->data;
+
+ if (val->length == 0 || p[0] == ' ' || p[0] == ':') {
+ return 1;
+ }
+
+ for (i=0; i<val->length; i++) {
+ if (!isprint(p[i]) || p[i] == '\n') {
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/* this macro is used to handle the return checking on fprintf_fn() */
+#define CHECK_RET do { if (ret < 0) return ret; total += ret; } while (0)
+
+/*
+ write a line folded string onto a file
+*/
+static int fold_string(int (*fprintf_fn)(void *, const char *, ...), void *private,
+ const char *buf, size_t length, int start_pos)
+{
+ int i;
+ int total=0, ret;
+
+ for (i=0;i<length;i++) {
+ ret = fprintf_fn(private, "%c", buf[i]);
+ CHECK_RET;
+ if (i != (length-1) && (i + start_pos) % 77 == 0) {
+ ret = fprintf_fn(private, "\n ");
+ CHECK_RET;
+ }
+ }
+
+ return total;
+}
+
+/*
+ encode as base64 to a file
+*/
+static int base64_encode_f(int (*fprintf_fn)(void *, const char *, ...), void *private,
+ const char *buf, int len, int start_pos)
+{
+ char *b = ldb_base64_encode(buf, len);
+ int ret;
+
+ if (!b) {
+ return -1;
+ }
+
+ ret = fold_string(fprintf_fn, private, b, strlen(b), start_pos);
+
+ free(b);
+ return ret;
+}
+
+/*
+ write to ldif, using a caller supplied write method
+*/
+int ldif_write(int (*fprintf_fn)(void *, const char *, ...),
+ void *private,
+ const struct ldb_message *msg)
+{
+ int i;
+ int total=0, ret;
+
+ ret = fprintf_fn(private, "dn: %s\n", msg->dn);
+ CHECK_RET;
+
+ for (i=0;i<msg->num_elements;i++) {
+ if (ldb_should_b64_encode(&msg->elements[i].value)) {
+ ret = fprintf_fn(private, "%s:: ", msg->elements[i].name);
+ CHECK_RET;
+ ret = base64_encode_f(fprintf_fn, private,
+ msg->elements[i].value.data,
+ msg->elements[i].value.length,
+ strlen(msg->elements[i].name)+3);
+ CHECK_RET;
+ ret = fprintf_fn(private, "\n");
+ CHECK_RET;
+ } else {
+ ret = fprintf_fn(private, "%s: ", msg->elements[i].name);
+ CHECK_RET;
+ ret = fold_string(fprintf_fn, private,
+ msg->elements[i].value.data,
+ msg->elements[i].value.length,
+ strlen(msg->elements[i].name)+2);
+ CHECK_RET;
+ ret = fprintf_fn(private, "\n");
+ CHECK_RET;
+ }
+ }
+ ret = fprintf_fn(private,"\n");
+ CHECK_RET;
+
+ return total;
+}
+
+#undef CHECK_RET
+
+
+/*
+ pull a ldif chunk, which is defined as a piece of data ending in \n\n or EOF
+ this routine removes any RFC2849 continuations and comments
+
+ caller frees
+*/
+static char *next_chunk(int (*fgetc_fn)(void *), void *private)
+{
+ size_t alloc_size=0, chunk_size = 0;
+ char *chunk = NULL;
+ int c;
+ int in_comment = 0;
+
+ while ((c = fgetc_fn(private)) != EOF) {
+ if (chunk_size == alloc_size) {
+ char *c2;
+ alloc_size += 1024;
+ c2 = realloc_p(chunk, char, alloc_size);
+ if (!c2) {
+ free(chunk);
+ errno = ENOMEM;
+ return NULL;
+ }
+ chunk = c2;
+ }
+
+ if (in_comment) {
+ if (c == '\n') {
+ in_comment = 0;
+ }
+ continue;
+ }
+
+ /* handle continuation lines - see RFC2849 */
+ if (c == ' ' && chunk_size > 1 && chunk[chunk_size-1] == '\n') {
+ chunk_size--;
+ continue;
+ }
+
+ /* chunks are terminated by a double line-feed */
+ if (c == '\n' && chunk_size > 0 && chunk[chunk_size-1] == '\n') {
+ chunk[chunk_size-1] = 0;
+ return chunk;
+ }
+
+ if (c == '#' && (chunk_size == 0 || chunk[chunk_size-1] == '\n')) {
+ in_comment = 1;
+ continue;
+ }
+
+ /* ignore leading blank lines */
+ if (chunk_size == 0 && c == '\n') {
+ continue;
+ }
+
+ chunk[chunk_size++] = c;
+ }
+
+ return chunk;
+}
+
+
+/* simple ldif attribute parser */
+static int next_attr(char **s, char **attr, struct ldb_val *value)
+{
+ char *p;
+ int base64_encoded = 0;
+
+ p = strchr(*s, ':');
+ if (!p) {
+ return -1;
+ }
+
+ *p++ = 0;
+
+ if (*p == ':') {
+ base64_encoded = 1;
+ p++;
+ }
+
+ *attr = *s;
+
+ while (isspace(*p)) {
+ p++;
+ }
+
+ value->data = p;
+
+ p = strchr(p, '\n');
+
+ if (!p) {
+ value->length = strlen((char *)value->data);
+ *s = ((char *)value->data) + value->length;
+ } else {
+ value->length = p - (char *)value->data;
+ *s = p+1;
+ *p = 0;
+ }
+
+ if (base64_encoded) {
+ int len = base64_decode(value->data);
+ if (len == -1) {
+ /* it wasn't valid base64 data */
+ return -1;
+ }
+ value->length = len;
+ }
+
+ return 0;
+}
+
+
+/*
+ free a message from a ldif_read
+*/
+void ldif_read_free(struct ldb_message *msg)
+{
+ if (msg->elements) free(msg->elements);
+ if (msg->private) free(msg->private);
+ free(msg);
+}
+
+/*
+ read from a LDIF source, creating a ldb_message
+*/
+struct ldb_message *ldif_read(int (*fgetc_fn)(void *), void *private)
+{
+ struct ldb_message *msg;
+ char *attr=NULL, *chunk=NULL, *s;
+ struct ldb_val value;
+
+ value.data = NULL;
+
+ msg = malloc_p(struct ldb_message);
+ if (!msg) return NULL;
+
+ msg->dn = NULL;
+ msg->elements = NULL;
+ msg->num_elements = 0;
+ msg->private = NULL;
+
+ chunk = next_chunk(fgetc_fn, private);
+ if (!chunk) {
+ goto failed;
+ }
+
+ msg->private = chunk;
+ s = chunk;
+
+ if (next_attr(&s, &attr, &value) != 0) {
+ goto failed;
+ }
+
+ /* first line must be a dn */
+ if (strcmp(attr, "dn") != 0) {
+ fprintf(stderr, "First line must be a dn not '%s'\n", attr);
+ goto failed;
+ }
+
+ msg->dn = value.data;
+
+ while (next_attr(&s, &attr, &value) == 0) {
+ msg->elements = realloc_p(msg->elements,
+ struct ldb_message_element,
+ msg->num_elements+1);
+ if (!msg->elements) {
+ goto failed;
+ }
+ msg->elements[msg->num_elements].flags = 0;
+ msg->elements[msg->num_elements].name = attr;
+ msg->elements[msg->num_elements].value = value;
+ msg->num_elements++;
+ }
+
+ return msg;
+
+failed:
+ if (msg) ldif_read_free(msg);
+ return NULL;
+}
+
+
+
+/*
+ a wrapper around ldif_read() for reading from FILE*
+*/
+struct ldif_read_file_state {
+ FILE *f;
+};
+
+static int fgetc_file(void *private)
+{
+ struct ldif_read_file_state *state = private;
+ return fgetc(state->f);
+}
+
+struct ldb_message *ldif_read_file(FILE *f)
+{
+ struct ldif_read_file_state state;
+ state.f = f;
+ return ldif_read(fgetc_file, &state);
+}
+
+
+/*
+ a wrapper around ldif_read() for reading from const char*
+*/
+struct ldif_read_string_state {
+ const char *s;
+};
+
+static int fgetc_string(void *private)
+{
+ struct ldif_read_string_state *state = private;
+ if (state->s[0] != 0) {
+ return *state->s++;
+ }
+ return EOF;
+}
+
+struct ldb_message *ldif_read_string(const char *s)
+{
+ struct ldif_read_string_state state;
+ state.s = s;
+ return ldif_read(fgetc_string, &state);
+}
+
+
+/*
+ wrapper around ldif_write() for a file
+*/
+struct ldif_write_file_state {
+ FILE *f;
+};
+
+static int fprintf_file(void *private, const char *fmt, ...)
+{
+ struct ldif_write_file_state *state = private;
+ int ret;
+ va_list ap;
+
+ va_start(ap, fmt);
+ ret = vfprintf(state->f, fmt, ap);
+ va_end(ap);
+ return ret;
+}
+
+int ldif_write_file(FILE *f, const struct ldb_message *msg)
+{
+ struct ldif_write_file_state state;
+ state.f = f;
+ return ldif_write(fprintf_file, &state, msg);
+}
diff --git a/source4/lib/ldb/common/ldb_parse.c b/source4/lib/ldb/common/ldb_parse.c
new file mode 100644
index 0000000000..4f8d469e6c
--- /dev/null
+++ b/source4/lib/ldb/common/ldb_parse.c
@@ -0,0 +1,460 @@
+/*
+ ldb database library
+
+ Copyright (C) Andrew Tridgell 2004
+
+ ** NOTE! The following LGPL license applies to the ldb
+ ** library. This does NOT imply that all of Samba is released
+ ** under the LGPL
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+/*
+ * Name: ldb
+ *
+ * Component: ldb expression parsing
+ *
+ * Description: parse LDAP-like search expressions
+ *
+ * Author: Andrew Tridgell
+ */
+
+/*
+ TODO:
+ - add RFC2254 binary string handling
+ - possibly add ~=, <= and >= handling
+ - expand the test suite
+ - add better parse error handling
+
+*/
+
+#include "includes.h"
+
+
+/*
+a filter is defined by:
+ <filter> ::= '(' <filtercomp> ')'
+ <filtercomp> ::= <and> | <or> | <not> | <simple>
+ <and> ::= '&' <filterlist>
+ <or> ::= '|' <filterlist>
+ <not> ::= '!' <filter>
+ <filterlist> ::= <filter> | <filter> <filterlist>
+ <simple> ::= <attributetype> <filtertype> <attributevalue>
+ <filtertype> ::= '=' | '~=' | '<=' | '>='
+*/
+
+/*
+ return next token element. Caller frees
+*/
+static char *ldb_parse_lex(const char **s)
+{
+ const char *p = *s;
+ char *ret;
+
+ while (isspace(*p)) {
+ p++;
+ }
+ *s = p;
+
+ if (*p == 0) {
+ return NULL;
+ }
+
+ if (strchr("()&|=!", *p)) {
+ (*s) = p+1;
+ ret = strndup(p, 1);
+ if (!ret) {
+ errno = ENOMEM;
+ }
+ return ret;
+ }
+
+ while (*p && (isalnum(*p) || !strchr("()&|=!", *p))) {
+ p++;
+ }
+
+ if (p == *s) {
+ return NULL;
+ }
+
+ ret = strndup(*s, p - *s);
+ if (!ret) {
+ errno = ENOMEM;
+ }
+
+ *s = p;
+
+ return ret;
+}
+
+/*
+ find a matching close brace in a string
+*/
+static const char *match_brace(const char *s)
+{
+ unsigned int count = 0;
+ while (*s && (count != 0 || *s != ')')) {
+ if (*s == '(') {
+ count++;
+ }
+ if (*s == ')') {
+ count--;
+ }
+ s++;
+ }
+ if (! *s) {
+ return NULL;
+ }
+ return s;
+}
+
+
+static struct ldb_parse_tree *ldb_parse_filter(const char **s);
+
+/*
+ <simple> ::= <attributetype> <filtertype> <attributevalue>
+*/
+static struct ldb_parse_tree *ldb_parse_simple(const char *s)
+{
+ char *eq, *val, *l;
+ struct ldb_parse_tree *ret;
+
+ l = ldb_parse_lex(&s);
+ if (!l) {
+ fprintf(stderr, "Unexpected end of expression\n");
+ return NULL;
+ }
+
+ if (strchr("()&|=", *l)) {
+ fprintf(stderr, "Unexpected token '%s'\n", l);
+ free(l);
+ return NULL;
+ }
+
+ eq = ldb_parse_lex(&s);
+ if (!eq || strcmp(eq, "=") != 0) {
+ fprintf(stderr, "Expected '='\n");
+ free(l);
+ if (eq) free(eq);
+ return NULL;
+ }
+ free(eq);
+
+ val = ldb_parse_lex(&s);
+ if (val && strchr("()&|=", *val)) {
+ fprintf(stderr, "Unexpected token '%s'\n", val);
+ free(l);
+ if (val) free(val);
+ return NULL;
+ }
+
+ ret = malloc_p(struct ldb_parse_tree);
+ if (!ret) {
+ errno = ENOMEM;
+ return NULL;
+ }
+
+ ret->operation = LDB_OP_SIMPLE;
+ ret->u.simple.attr = l;
+ ret->u.simple.value.data = val;
+ ret->u.simple.value.length = val?strlen(val):0;
+
+ return ret;
+}
+
+
+/*
+ parse a filterlist
+ <and> ::= '&' <filterlist>
+ <or> ::= '|' <filterlist>
+ <filterlist> ::= <filter> | <filter> <filterlist>
+*/
+static struct ldb_parse_tree *ldb_parse_filterlist(enum ldb_parse_op op, const char *s)
+{
+ struct ldb_parse_tree *ret, *next;
+
+ ret = malloc_p(struct ldb_parse_tree);
+ if (!ret) {
+ errno = ENOMEM;
+ return NULL;
+ }
+
+ ret->operation = op;
+ ret->u.list.num_elements = 1;
+ ret->u.list.elements = malloc_p(struct ldb_parse_tree *);
+ if (!ret->u.list.elements) {
+ errno = ENOMEM;
+ free(ret);
+ return NULL;
+ }
+
+ ret->u.list.elements[0] = ldb_parse_filter(&s);
+ if (!ret->u.list.elements[0]) {
+ free(ret->u.list.elements);
+ free(ret);
+ return NULL;
+ }
+
+ while (isspace(*s)) s++;
+
+ while (*s && (next = ldb_parse_filter(&s))) {
+ struct ldb_parse_tree **e;
+ e = realloc_p(ret->u.list.elements,
+ struct ldb_parse_tree *,
+ ret->u.list.num_elements+1);
+ if (!e) {
+ errno = ENOMEM;
+ ldb_parse_tree_free(next);
+ ldb_parse_tree_free(ret);
+ return NULL;
+ }
+ ret->u.list.elements = e;
+ ret->u.list.elements[ret->u.list.num_elements] = next;
+ ret->u.list.num_elements++;
+ while (isspace(*s)) s++;
+ }
+
+ return ret;
+}
+
+
+/*
+ <not> ::= '!' <filter>
+*/
+static struct ldb_parse_tree *ldb_parse_not(const char *s)
+{
+ struct ldb_parse_tree *ret;
+
+ ret = malloc_p(struct ldb_parse_tree);
+ if (!ret) {
+ errno = ENOMEM;
+ return NULL;
+ }
+
+ ret->operation = LDB_OP_NOT;
+ ret->u.not.child = ldb_parse_filter(&s);
+ if (!ret->u.not.child) {
+ free(ret);
+ return NULL;
+ }
+
+ return ret;
+}
+
+/*
+ parse a filtercomp
+ <filtercomp> ::= <and> | <or> | <not> | <simple>
+*/
+static struct ldb_parse_tree *ldb_parse_filtercomp(const char *s)
+{
+ while (isspace(*s)) s++;
+
+ switch (*s) {
+ case '&':
+ return ldb_parse_filterlist(LDB_OP_AND, s+1);
+
+ case '|':
+ return ldb_parse_filterlist(LDB_OP_OR, s+1);
+
+ case '!':
+ return ldb_parse_not(s+1);
+
+ case '(':
+ case ')':
+ fprintf(stderr, "Unexpected token '%c'\n", *s);
+ return NULL;
+ }
+
+ return ldb_parse_simple(s);
+}
+
+
+/*
+ <filter> ::= '(' <filtercomp> ')'
+*/
+static struct ldb_parse_tree *ldb_parse_filter(const char **s)
+{
+ char *l, *s2;
+ const char *p, *p2;
+ struct ldb_parse_tree *ret;
+
+ l = ldb_parse_lex(s);
+ if (!l) {
+ fprintf(stderr, "Unexpected end of expression\n");
+ return NULL;
+ }
+
+ if (strcmp(l, "(") != 0) {
+ free(l);
+ fprintf(stderr, "Expected '('\n");
+ return NULL;
+ }
+ free(l);
+
+ p = match_brace(*s);
+ if (!p) {
+ fprintf(stderr, "Parse error - mismatched braces\n");
+ return NULL;
+ }
+ p2 = p + 1;
+
+ s2 = strndup(*s, p - *s);
+ if (!s2) {
+ errno = ENOMEM;
+ return NULL;
+ }
+
+ ret = ldb_parse_filtercomp(s2);
+ free(s2);
+
+ *s = p2;
+
+ return ret;
+}
+
+
+/*
+ main parser entry point. Takes a search string and returns a parse tree
+
+ expression ::= <simple> | <filter>
+*/
+struct ldb_parse_tree *ldb_parse_tree(const char *s)
+{
+ while (isspace(*s)) s++;
+
+ if (*s == '(') {
+ return ldb_parse_filter(&s);
+ }
+
+ return ldb_parse_simple(s);
+}
+
+/*
+ free a parse tree returned from ldb_parse_tree()
+*/
+void ldb_parse_tree_free(struct ldb_parse_tree *tree)
+{
+ int i;
+
+ switch (tree->operation) {
+ case LDB_OP_SIMPLE:
+ free(tree->u.simple.attr);
+ if (tree->u.simple.value.data) free(tree->u.simple.value.data);
+ break;
+
+ case LDB_OP_AND:
+ case LDB_OP_OR:
+ for (i=0;i<tree->u.list.num_elements;i++) {
+ ldb_parse_tree_free(tree->u.list.elements[i]);
+ }
+ if (tree->u.list.elements) free(tree->u.list.elements);
+ break;
+
+ case LDB_OP_NOT:
+ ldb_parse_tree_free(tree->u.not.child);
+ break;
+ }
+
+ free(tree);
+}
+
+#if TEST_PROGRAM
+/*
+ return a string representation of a parse tree
+ used for debugging
+*/
+static char *tree_string(struct ldb_parse_tree *tree)
+{
+ char *s = NULL;
+ char *s1, *s2;
+ int i;
+
+ switch (tree->operation) {
+ case LDB_OP_SIMPLE:
+ asprintf(&s, "( %s = \"%s\" )", tree->u.simple.attr,
+ (char *)tree->u.simple.value.data);
+ break;
+
+ case LDB_OP_AND:
+ case LDB_OP_OR:
+ asprintf(&s, "( %c", tree->operation==LDB_OP_AND?'&':'|');
+ if (!s) return NULL;
+
+ for (i=0;i<tree->u.list.num_elements;i++) {
+ s1 = tree_string(tree->u.list.elements[i]);
+ if (!s1) {
+ free(s);
+ return NULL;
+ }
+ asprintf(&s2, "%s %s", s, s1);
+ free(s);
+ free(s1);
+ s = s2;
+ }
+ if (!s) {
+ return NULL;
+ }
+ asprintf(&s2, "%s )", s);
+ free(s);
+ s = s2;
+ break;
+
+ case LDB_OP_NOT:
+ s1 = tree_string(tree->u.not.child);
+ asprintf(&s, "( ! %s )", s1);
+ free(s1);
+ break;
+ }
+ return s;
+}
+
+
+/*
+ print a tree
+ */
+static void print_tree(struct ldb_parse_tree *tree)
+{
+ char *s = tree_string(tree);
+ printf("%s\n", s);
+ free(s);
+}
+
+
+ int main(void)
+{
+ char line[1000];
+ int ret = 0;
+
+ while (fgets(line, sizeof(line)-1, stdin)) {
+ struct ldb_parse_tree *tree;
+
+ if (line[strlen(line)-1] == '\n') {
+ line[strlen(line)-1] = 0;
+ }
+ tree = ldb_parse_tree(line);
+ if (!tree) {
+ fprintf(stderr, "Failed to parse\n");
+ ret = 1;
+ continue;
+ }
+ print_tree(tree);
+ ldb_parse_tree_free(tree);
+ }
+
+ return ret;
+}
+#endif /* TEST_PROGRAM */
+
diff --git a/source4/lib/ldb/common/util.c b/source4/lib/ldb/common/util.c
new file mode 100644
index 0000000000..d198a1ad92
--- /dev/null
+++ b/source4/lib/ldb/common/util.c
@@ -0,0 +1,102 @@
+/*
+ ldb database library
+
+ Copyright (C) Andrew Tridgell 2004
+
+ ** NOTE! The following LGPL license applies to the ldb
+ ** library. This does NOT imply that all of Samba is released
+ ** under the LGPL
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+/*
+ * Name: ldb
+ *
+ * Component: ldb utility functions
+ *
+ * Description: miscellanous utility functions for ldb
+ *
+ * Author: Andrew Tridgell
+ */
+
+#include "includes.h"
+
+
+#define MAX_MALLOC_SIZE 0x7fffffff
+
+/*
+ realloc an array, checking for integer overflow in the array size
+*/
+void *realloc_array(void *ptr, size_t el_size, unsigned count)
+{
+ if (count == 0 ||
+ count >= MAX_MALLOC_SIZE/el_size) {
+ return NULL;
+ }
+ if (!ptr) {
+ return malloc(el_size * count);
+ }
+ return realloc(ptr, el_size * count);
+}
+
+
+/*
+ find an element in a list, using the given comparison function and
+ assuming that the list is already sorted using comp_fn
+
+ return -1 if not found, or the index of the first occurance of needle if found
+*/
+int list_find(const void *needle,
+ const void *base, size_t nmemb, size_t size, comparison_fn_t comp_fn)
+{
+ const char *base_p = base;
+ size_t min_i, max_i, test_i;
+
+ if (nmemb == 0) {
+ return -1;
+ }
+
+ min_i = 0;
+ max_i = nmemb-1;
+
+ while (min_i < max_i) {
+ size_t test_t;
+ int r;
+
+ test_i = (min_i + max_i) / 2;
+ r = comp_fn(needle, *(void **)(base_p + (size * test_i)));
+ if (r == 0) {
+ /* scan back for first element */
+ while (test_t > 0 &&
+ comp_fn(needle, *(void **)(base_p + (size * (test_i-1)))) == 0) {
+ test_i--;
+ }
+ return test_i;
+ }
+ if (r == -1) {
+ max_i = test_i - 1;
+ }
+ if (r == 1) {
+ min_i = test_i + 1;
+ }
+ }
+
+ if (comp_fn(needle, *(void **)(base_p + (size * min_i))) == 0) {
+ return min_i;
+ }
+
+ return -1;
+}