From 58d50a614f1b4a3fc6b60ad5f777d987263fe54f Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Wed, 31 Mar 2004 06:45:39 +0000 Subject: make a more recent snapshot of ldb available to interested people. Note that I decided to make it LGPL. ldb is not finished yet, but enough of it is there for people to get an idea of what it does, and quite a few simple tests work (This used to be commit dc6f41f9e777d37f883303ddef0d96840d80f78e) --- source4/lib/ldb/common/ldb.c | 129 ++++++++++ source4/lib/ldb/common/ldb_ldif.c | 476 +++++++++++++++++++++++++++++++++++++ source4/lib/ldb/common/ldb_parse.c | 460 +++++++++++++++++++++++++++++++++++ source4/lib/ldb/common/util.c | 102 ++++++++ 4 files changed, 1167 insertions(+) create mode 100644 source4/lib/ldb/common/ldb.c create mode 100644 source4/lib/ldb/common/ldb_ldif.c create mode 100644 source4/lib/ldb/common/ldb_parse.c create mode 100644 source4/lib/ldb/common/util.c (limited to 'source4/lib/ldb/common') 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> (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; ilength; 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;idn); + CHECK_RET; + + for (i=0;inum_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: + ::= '(' ')' + ::= | | | + ::= '&' + ::= '|' + ::= '!' + ::= | + ::= + ::= '=' | '~=' | '<=' | '>=' +*/ + +/* + 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); + +/* + ::= +*/ +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 + ::= '&' + ::= '|' + ::= | +*/ +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; +} + + +/* + ::= '!' +*/ +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 + ::= | | | +*/ +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); +} + + +/* + ::= '(' ')' +*/ +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 ::= | +*/ +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;iu.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;iu.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; +} -- cgit