summaryrefslogtreecommitdiffstats
path: root/servers/slapd/back-mdb/idl.c
diff options
context:
space:
mode:
Diffstat (limited to 'servers/slapd/back-mdb/idl.c')
-rw-r--r--servers/slapd/back-mdb/idl.c1276
1 files changed, 1276 insertions, 0 deletions
diff --git a/servers/slapd/back-mdb/idl.c b/servers/slapd/back-mdb/idl.c
new file mode 100644
index 0000000..3b4a194
--- /dev/null
+++ b/servers/slapd/back-mdb/idl.c
@@ -0,0 +1,1276 @@
+/* idl.c - ldap id list handling routines */
+/* $OpenLDAP$ */
+/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
+ *
+ * Copyright 2000-2021 The OpenLDAP Foundation.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted only as authorized by the OpenLDAP
+ * Public License.
+ *
+ * A copy of this license is available in the file LICENSE in the
+ * top-level directory of the distribution or, alternatively, at
+ * <http://www.OpenLDAP.org/license.html>.
+ */
+
+#include "portable.h"
+
+#include <stdio.h>
+#include <ac/string.h>
+
+#include "back-mdb.h"
+#include "idl.h"
+
+#define IDL_MAX(x,y) ( (x) > (y) ? (x) : (y) )
+#define IDL_MIN(x,y) ( (x) < (y) ? (x) : (y) )
+#define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
+
+#if IDL_DEBUG > 0
+static void idl_check( ID *ids )
+{
+ if( MDB_IDL_IS_RANGE( ids ) ) {
+ assert( MDB_IDL_RANGE_FIRST(ids) <= MDB_IDL_RANGE_LAST(ids) );
+ } else {
+ ID i;
+ for( i=1; i < ids[0]; i++ ) {
+ assert( ids[i+1] > ids[i] );
+ }
+ }
+}
+
+#if IDL_DEBUG > 1
+static void idl_dump( ID *ids )
+{
+ if( MDB_IDL_IS_RANGE( ids ) ) {
+ Debug( LDAP_DEBUG_ANY,
+ "IDL: range ( %ld - %ld )\n",
+ (long) MDB_IDL_RANGE_FIRST( ids ),
+ (long) MDB_IDL_RANGE_LAST( ids ) );
+
+ } else {
+ ID i;
+ Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
+
+ for( i=1; i<=ids[0]; i++ ) {
+ if( i % 16 == 1 ) {
+ Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
+ }
+ Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i], 0, 0 );
+ }
+
+ Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
+ }
+
+ idl_check( ids );
+}
+#endif /* IDL_DEBUG > 1 */
+#endif /* IDL_DEBUG > 0 */
+
+unsigned mdb_idl_search( ID *ids, ID id )
+{
+#define IDL_BINARY_SEARCH 1
+#ifdef IDL_BINARY_SEARCH
+ /*
+ * binary search of id in ids
+ * if found, returns position of id
+ * if not found, returns first postion greater than id
+ */
+ unsigned base = 0;
+ unsigned cursor = 1;
+ int val = 0;
+ unsigned n = ids[0];
+
+#if IDL_DEBUG > 0
+ idl_check( ids );
+#endif
+
+ while( 0 < n ) {
+ unsigned pivot = n >> 1;
+ cursor = base + pivot + 1;
+ val = IDL_CMP( id, ids[cursor] );
+
+ if( val < 0 ) {
+ n = pivot;
+
+ } else if ( val > 0 ) {
+ base = cursor;
+ n -= pivot + 1;
+
+ } else {
+ return cursor;
+ }
+ }
+
+ if( val > 0 ) {
+ ++cursor;
+ }
+ return cursor;
+
+#else
+ /* (reverse) linear search */
+ int i;
+
+#if IDL_DEBUG > 0
+ idl_check( ids );
+#endif
+
+ for( i=ids[0]; i; i-- ) {
+ if( id > ids[i] ) {
+ break;
+ }
+ }
+
+ return i+1;
+#endif
+}
+
+int mdb_idl_insert( ID *ids, ID id )
+{
+ unsigned x;
+
+#if IDL_DEBUG > 1
+ Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
+ idl_dump( ids );
+#elif IDL_DEBUG > 0
+ idl_check( ids );
+#endif
+
+ if (MDB_IDL_IS_RANGE( ids )) {
+ /* if already in range, treat as a dup */
+ if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
+ return -1;
+ if (id < MDB_IDL_RANGE_FIRST(ids))
+ ids[1] = id;
+ else if (id > MDB_IDL_RANGE_LAST(ids))
+ ids[2] = id;
+ return 0;
+ }
+
+ x = mdb_idl_search( ids, id );
+ assert( x > 0 );
+
+ if( x < 1 ) {
+ /* internal error */
+ return -2;
+ }
+
+ if ( x <= ids[0] && ids[x] == id ) {
+ /* duplicate */
+ return -1;
+ }
+
+ if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
+ if( id < ids[1] ) {
+ ids[1] = id;
+ ids[2] = ids[ids[0]-1];
+ } else if ( ids[ids[0]-1] < id ) {
+ ids[2] = id;
+ } else {
+ ids[2] = ids[ids[0]-1];
+ }
+ ids[0] = NOID;
+
+ } else {
+ /* insert id */
+ AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
+ ids[x] = id;
+ }
+
+#if IDL_DEBUG > 1
+ idl_dump( ids );
+#elif IDL_DEBUG > 0
+ idl_check( ids );
+#endif
+
+ return 0;
+}
+
+static int mdb_idl_delete( ID *ids, ID id )
+{
+ unsigned x;
+
+#if IDL_DEBUG > 1
+ Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
+ idl_dump( ids );
+#elif IDL_DEBUG > 0
+ idl_check( ids );
+#endif
+
+ if (MDB_IDL_IS_RANGE( ids )) {
+ /* If deleting a range boundary, adjust */
+ if ( ids[1] == id )
+ ids[1]++;
+ else if ( ids[2] == id )
+ ids[2]--;
+ /* deleting from inside a range is a no-op */
+
+ /* If the range has collapsed, re-adjust */
+ if ( ids[1] > ids[2] )
+ ids[0] = 0;
+ else if ( ids[1] == ids[2] )
+ ids[1] = 1;
+ return 0;
+ }
+
+ x = mdb_idl_search( ids, id );
+ assert( x > 0 );
+
+ if( x <= 0 ) {
+ /* internal error */
+ return -2;
+ }
+
+ if( x > ids[0] || ids[x] != id ) {
+ /* not found */
+ return -1;
+
+ } else if ( --ids[0] == 0 ) {
+ if( x != 1 ) {
+ return -3;
+ }
+
+ } else {
+ AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
+ }
+
+#if IDL_DEBUG > 1
+ idl_dump( ids );
+#elif IDL_DEBUG > 0
+ idl_check( ids );
+#endif
+
+ return 0;
+}
+
+static char *
+mdb_show_key(
+ char *buf,
+ void *val,
+ size_t len )
+{
+ if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
+ unsigned char *c = val;
+ sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
+ return buf;
+ } else {
+ return val;
+ }
+}
+
+int
+mdb_idl_fetch_key(
+ BackendDB *be,
+ MDB_txn *txn,
+ MDB_dbi dbi,
+ MDB_val *key,
+ ID *ids,
+ MDB_cursor **saved_cursor,
+ int get_flag )
+{
+ MDB_val data, key2, *kptr;
+ MDB_cursor *cursor;
+ ID *i;
+ size_t len;
+ int rc;
+ MDB_cursor_op opflag;
+
+ char keybuf[16];
+
+ Debug( LDAP_DEBUG_ARGS,
+ "mdb_idl_fetch_key: %s\n",
+ mdb_show_key( keybuf, key->mv_data, key->mv_size ), 0, 0 );
+
+ assert( ids != NULL );
+
+ if ( saved_cursor && *saved_cursor ) {
+ opflag = MDB_NEXT;
+ } else if ( get_flag == LDAP_FILTER_GE ) {
+ opflag = MDB_SET_RANGE;
+ } else if ( get_flag == LDAP_FILTER_LE ) {
+ opflag = MDB_FIRST;
+ } else {
+ opflag = MDB_SET;
+ }
+
+ /* If we're not reusing an existing cursor, get a new one */
+ if( opflag != MDB_NEXT ) {
+ rc = mdb_cursor_open( txn, dbi, &cursor );
+ if( rc != 0 ) {
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
+ "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
+ return rc;
+ }
+ } else {
+ cursor = *saved_cursor;
+ }
+
+ /* If this is a LE lookup, save original key so we can determine
+ * when to stop. If this is a GE lookup, save the key since it
+ * will be overwritten.
+ */
+ if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
+ key2.mv_data = keybuf;
+ key2.mv_size = key->mv_size;
+ AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
+ kptr = &key2;
+ } else {
+ kptr = key;
+ }
+ len = key->mv_size;
+ rc = mdb_cursor_get( cursor, kptr, &data, opflag );
+
+ /* skip presence key on range inequality lookups */
+ while (rc == 0 && kptr->mv_size != len) {
+ rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
+ }
+ /* If we're doing a LE compare and the new key is greater than
+ * our search key, we're done
+ */
+ if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
+ key->mv_data, key->mv_size ) > 0 ) {
+ rc = MDB_NOTFOUND;
+ }
+ if (rc == 0) {
+ i = ids+1;
+ rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
+ while (rc == 0) {
+ memcpy( i, data.mv_data, data.mv_size );
+ i += data.mv_size / sizeof(ID);
+ rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
+ }
+ if ( rc == MDB_NOTFOUND ) rc = 0;
+ ids[0] = i - &ids[1];
+ /* On disk, a range is denoted by 0 in the first element */
+ if (ids[1] == 0) {
+ if (ids[0] != MDB_IDL_RANGE_SIZE) {
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
+ "range size mismatch: expected %d, got %ld\n",
+ MDB_IDL_RANGE_SIZE, ids[0], 0 );
+ mdb_cursor_close( cursor );
+ return -1;
+ }
+ MDB_IDL_RANGE( ids, ids[2], ids[3] );
+ }
+ data.mv_size = MDB_IDL_SIZEOF(ids);
+ }
+
+ if ( saved_cursor && rc == 0 ) {
+ if ( !*saved_cursor )
+ *saved_cursor = cursor;
+ }
+ else
+ mdb_cursor_close( cursor );
+
+ if( rc == MDB_NOTFOUND ) {
+ return rc;
+
+ } else if( rc != 0 ) {
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
+ "get failed: %s (%d)\n",
+ mdb_strerror(rc), rc, 0 );
+ return rc;
+
+ } else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
+ /* size not multiple of ID size */
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
+ "odd size: expected %ld multiple, got %ld\n",
+ (long) sizeof( ID ), (long) data.mv_size, 0 );
+ return -1;
+
+ } else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
+ /* size mismatch */
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
+ "get size mismatch: expected %ld, got %ld\n",
+ (long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size, 0 );
+ return -1;
+ }
+
+ return rc;
+}
+
+int
+mdb_idl_insert_keys(
+ BackendDB *be,
+ MDB_cursor *cursor,
+ struct berval *keys,
+ ID id )
+{
+ struct mdb_info *mdb = be->be_private;
+ MDB_val key, data;
+ ID lo, hi, *i;
+ char *err;
+ int rc = 0, k;
+ unsigned int flag = MDB_NODUPDATA;
+#ifndef MISALIGNED_OK
+ int kbuf[2];
+#endif
+
+ {
+ char buf[16];
+ Debug( LDAP_DEBUG_ARGS,
+ "mdb_idl_insert_keys: %lx %s\n",
+ (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
+ }
+
+ assert( id != NOID );
+
+#ifndef MISALIGNED_OK
+ if (keys[0].bv_len & ALIGNER)
+ kbuf[1] = 0;
+#endif
+ for ( k=0; keys[k].bv_val; k++ ) {
+ /* Fetch the first data item for this key, to see if it
+ * exists and if it's a range.
+ */
+#ifndef MISALIGNED_OK
+ if (keys[k].bv_len & ALIGNER) {
+ key.mv_size = sizeof(kbuf);
+ key.mv_data = kbuf;
+ memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
+ } else
+#endif
+ {
+ key.mv_size = keys[k].bv_len;
+ key.mv_data = keys[k].bv_val;
+ }
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
+ err = "c_get";
+ if ( rc == 0 ) {
+ i = data.mv_data;
+ memcpy(&lo, data.mv_data, sizeof(ID));
+ if ( lo != 0 ) {
+ /* not a range, count the number of items */
+ size_t count;
+ rc = mdb_cursor_count( cursor, &count );
+ if ( rc != 0 ) {
+ err = "c_count";
+ goto fail;
+ }
+ if ( count >= MDB_IDL_DB_MAX ) {
+ /* No room, convert to a range */
+ lo = *i;
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
+ if ( rc != 0 && rc != MDB_NOTFOUND ) {
+ err = "c_get last_dup";
+ goto fail;
+ }
+ i = data.mv_data;
+ hi = *i;
+ /* Update hi/lo if needed */
+ if ( id < lo ) {
+ lo = id;
+ } else if ( id > hi ) {
+ hi = id;
+ }
+ /* delete the old key */
+ rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
+ if ( rc != 0 ) {
+ err = "c_del dups";
+ goto fail;
+ }
+ /* Store the range */
+ data.mv_size = sizeof(ID);
+ data.mv_data = &id;
+ id = 0;
+ rc = mdb_cursor_put( cursor, &key, &data, 0 );
+ if ( rc != 0 ) {
+ err = "c_put range";
+ goto fail;
+ }
+ id = lo;
+ rc = mdb_cursor_put( cursor, &key, &data, 0 );
+ if ( rc != 0 ) {
+ err = "c_put lo";
+ goto fail;
+ }
+ id = hi;
+ rc = mdb_cursor_put( cursor, &key, &data, 0 );
+ if ( rc != 0 ) {
+ err = "c_put hi";
+ goto fail;
+ }
+ } else {
+ /* There's room, just store it */
+ if (id == mdb->mi_nextid)
+ flag |= MDB_APPENDDUP;
+ goto put1;
+ }
+ } else {
+ /* It's a range, see if we need to rewrite
+ * the boundaries
+ */
+ lo = i[1];
+ hi = i[2];
+ if ( id < lo || id > hi ) {
+ /* position on lo */
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
+ if ( rc != 0 ) {
+ err = "c_get lo";
+ goto fail;
+ }
+ if ( id > hi ) {
+ /* position on hi */
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
+ if ( rc != 0 ) {
+ err = "c_get hi";
+ goto fail;
+ }
+ }
+ data.mv_size = sizeof(ID);
+ data.mv_data = &id;
+ /* Replace the current lo/hi */
+ rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
+ if ( rc != 0 ) {
+ err = "c_put lo/hi";
+ goto fail;
+ }
+ }
+ }
+ } else if ( rc == MDB_NOTFOUND ) {
+ flag &= ~MDB_APPENDDUP;
+put1: data.mv_data = &id;
+ data.mv_size = sizeof(ID);
+ rc = mdb_cursor_put( cursor, &key, &data, flag );
+ /* Don't worry if it's already there */
+ if ( rc == MDB_KEYEXIST )
+ rc = 0;
+ if ( rc ) {
+ err = "c_put id";
+ goto fail;
+ }
+ } else {
+ /* initial c_get failed, nothing was done */
+fail:
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
+ "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
+ break;
+ }
+ }
+ return rc;
+}
+
+int
+mdb_idl_delete_keys(
+ BackendDB *be,
+ MDB_cursor *cursor,
+ struct berval *keys,
+ ID id )
+{
+ int rc = 0, k;
+ MDB_val key, data;
+ ID lo, hi, tmp, *i;
+ char *err;
+#ifndef MISALIGNED_OK
+ int kbuf[2];
+#endif
+
+ {
+ char buf[16];
+ Debug( LDAP_DEBUG_ARGS,
+ "mdb_idl_delete_keys: %lx %s\n",
+ (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
+ }
+ assert( id != NOID );
+
+#ifndef MISALIGNED_OK
+ if (keys[0].bv_len & ALIGNER)
+ kbuf[1] = 0;
+#endif
+ for ( k=0; keys[k].bv_val; k++) {
+ /* Fetch the first data item for this key, to see if it
+ * exists and if it's a range.
+ */
+#ifndef MISALIGNED_OK
+ if (keys[k].bv_len & ALIGNER) {
+ key.mv_size = sizeof(kbuf);
+ key.mv_data = kbuf;
+ memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
+ } else
+#endif
+ {
+ key.mv_size = keys[k].bv_len;
+ key.mv_data = keys[k].bv_val;
+ }
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
+ err = "c_get";
+ if ( rc == 0 ) {
+ memcpy( &tmp, data.mv_data, sizeof(ID) );
+ i = data.mv_data;
+ if ( tmp != 0 ) {
+ /* Not a range, just delete it */
+ data.mv_data = &id;
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
+ if ( rc != 0 ) {
+ err = "c_get id";
+ goto fail;
+ }
+ rc = mdb_cursor_del( cursor, 0 );
+ if ( rc != 0 ) {
+ err = "c_del id";
+ goto fail;
+ }
+ } else {
+ /* It's a range, see if we need to rewrite
+ * the boundaries
+ */
+ lo = i[1];
+ hi = i[2];
+ if ( id == lo || id == hi ) {
+ ID lo2 = lo, hi2 = hi;
+ if ( id == lo ) {
+ lo2++;
+ } else if ( id == hi ) {
+ hi2--;
+ }
+ if ( lo2 >= hi2 ) {
+ /* The range has collapsed... */
+ /* delete the range marker */
+ rc = mdb_cursor_del( cursor, 0 );
+ if ( rc != 0 ) {
+ err = "c_del dup1";
+ goto fail;
+ }
+ /* skip past deleted marker */
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
+ if ( rc != 0 ) {
+ err = "c_get dup1";
+ goto fail;
+ }
+ /* delete the requested id */
+ if ( id == hi ) {
+ /* skip lo */
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
+ if ( rc != 0 ) {
+ err = "c_get dup2";
+ goto fail;
+ }
+ }
+ rc = mdb_cursor_del( cursor, 0 );
+ if ( rc != 0 ) {
+ err = "c_del dup2";
+ goto fail;
+ }
+ } else {
+ /* position on lo */
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
+ if ( id == lo )
+ data.mv_data = &lo2;
+ else {
+ /* position on hi */
+ rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
+ data.mv_data = &hi2;
+ }
+ /* Replace the current lo/hi */
+ data.mv_size = sizeof(ID);
+ rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
+ if ( rc != 0 ) {
+ err = "c_put lo/hi";
+ goto fail;
+ }
+ }
+ }
+ }
+ } else {
+ /* initial c_get failed, nothing was done */
+fail:
+ if ( rc == MDB_NOTFOUND )
+ rc = 0;
+ if ( rc ) {
+ Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
+ "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
+ break;
+ }
+ }
+ }
+ return rc;
+}
+
+
+/*
+ * idl_intersection - return a = a intersection b
+ */
+int
+mdb_idl_intersection(
+ ID *a,
+ ID *b )
+{
+ ID ida, idb;
+ ID idmax, idmin;
+ ID cursora = 0, cursorb = 0, cursorc;
+ int swap = 0;
+
+ if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
+ a[0] = 0;
+ return 0;
+ }
+
+ idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
+ idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
+ if ( idmin > idmax ) {
+ a[0] = 0;
+ return 0;
+ } else if ( idmin == idmax ) {
+ a[0] = 1;
+ a[1] = idmin;
+ return 0;
+ }
+
+ if ( MDB_IDL_IS_RANGE( a ) ) {
+ if ( MDB_IDL_IS_RANGE(b) ) {
+ /* If both are ranges, just shrink the boundaries */
+ a[1] = idmin;
+ a[2] = idmax;
+ return 0;
+ } else {
+ /* Else swap so that b is the range, a is a list */
+ ID *tmp = a;
+ a = b;
+ b = tmp;
+ swap = 1;
+ }
+ }
+
+ /* If a range completely covers the list, the result is
+ * just the list.
+ */
+ if ( MDB_IDL_IS_RANGE( b )
+ && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_FIRST( a )
+ && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_LLAST( a ) ) {
+ goto done;
+ }
+
+ /* Fine, do the intersection one element at a time.
+ * First advance to idmin in both IDLs.
+ */
+ cursora = cursorb = idmin;
+ ida = mdb_idl_first( a, &cursora );
+ idb = mdb_idl_first( b, &cursorb );
+ cursorc = 0;
+
+ while( ida <= idmax || idb <= idmax ) {
+ if( ida == idb ) {
+ a[++cursorc] = ida;
+ ida = mdb_idl_next( a, &cursora );
+ idb = mdb_idl_next( b, &cursorb );
+ } else if ( ida < idb ) {
+ ida = mdb_idl_next( a, &cursora );
+ } else {
+ idb = mdb_idl_next( b, &cursorb );
+ }
+ }
+ a[0] = cursorc;
+done:
+ if (swap)
+ MDB_IDL_CPY( b, a );
+
+ return 0;
+}
+
+
+/*
+ * idl_union - return a = a union b
+ */
+int
+mdb_idl_union(
+ ID *a,
+ ID *b )
+{
+ ID ida, idb;
+ ID cursora = 0, cursorb = 0, cursorc;
+
+ if ( MDB_IDL_IS_ZERO( b ) ) {
+ return 0;
+ }
+
+ if ( MDB_IDL_IS_ZERO( a ) ) {
+ MDB_IDL_CPY( a, b );
+ return 0;
+ }
+
+ if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
+over: ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
+ idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
+ a[0] = NOID;
+ a[1] = ida;
+ a[2] = idb;
+ return 0;
+ }
+
+ ida = mdb_idl_first( a, &cursora );
+ idb = mdb_idl_first( b, &cursorb );
+
+ cursorc = b[0];
+
+ /* The distinct elements of a are cat'd to b */
+ while( ida != NOID || idb != NOID ) {
+ if ( ida < idb ) {
+ if( ++cursorc > MDB_IDL_UM_MAX ) {
+ goto over;
+ }
+ b[cursorc] = ida;
+ ida = mdb_idl_next( a, &cursora );
+
+ } else {
+ if ( ida == idb )
+ ida = mdb_idl_next( a, &cursora );
+ idb = mdb_idl_next( b, &cursorb );
+ }
+ }
+
+ /* b is copied back to a in sorted order */
+ a[0] = cursorc;
+ cursora = 1;
+ cursorb = 1;
+ cursorc = b[0]+1;
+ while (cursorb <= b[0] || cursorc <= a[0]) {
+ if (cursorc > a[0])
+ idb = NOID;
+ else
+ idb = b[cursorc];
+ if (cursorb <= b[0] && b[cursorb] < idb)
+ a[cursora++] = b[cursorb++];
+ else {
+ a[cursora++] = idb;
+ cursorc++;
+ }
+ }
+
+ return 0;
+}
+
+
+#if 0
+/*
+ * mdb_idl_notin - return a intersection ~b (or a minus b)
+ */
+int
+mdb_idl_notin(
+ ID *a,
+ ID *b,
+ ID *ids )
+{
+ ID ida, idb;
+ ID cursora = 0, cursorb = 0;
+
+ if( MDB_IDL_IS_ZERO( a ) ||
+ MDB_IDL_IS_ZERO( b ) ||
+ MDB_IDL_IS_RANGE( b ) )
+ {
+ MDB_IDL_CPY( ids, a );
+ return 0;
+ }
+
+ if( MDB_IDL_IS_RANGE( a ) ) {
+ MDB_IDL_CPY( ids, a );
+ return 0;
+ }
+
+ ida = mdb_idl_first( a, &cursora ),
+ idb = mdb_idl_first( b, &cursorb );
+
+ ids[0] = 0;
+
+ while( ida != NOID ) {
+ if ( idb == NOID ) {
+ /* we could shortcut this */
+ ids[++ids[0]] = ida;
+ ida = mdb_idl_next( a, &cursora );
+
+ } else if ( ida < idb ) {
+ ids[++ids[0]] = ida;
+ ida = mdb_idl_next( a, &cursora );
+
+ } else if ( ida > idb ) {
+ idb = mdb_idl_next( b, &cursorb );
+
+ } else {
+ ida = mdb_idl_next( a, &cursora );
+ idb = mdb_idl_next( b, &cursorb );
+ }
+ }
+
+ return 0;
+}
+#endif
+
+ID mdb_idl_first( ID *ids, ID *cursor )
+{
+ ID pos;
+
+ if ( ids[0] == 0 ) {
+ *cursor = NOID;
+ return NOID;
+ }
+
+ if ( MDB_IDL_IS_RANGE( ids ) ) {
+ if( *cursor < ids[1] ) {
+ *cursor = ids[1];
+ }
+ return *cursor;
+ }
+
+ if ( *cursor == 0 )
+ pos = 1;
+ else
+ pos = mdb_idl_search( ids, *cursor );
+
+ if( pos > ids[0] ) {
+ return NOID;
+ }
+
+ *cursor = pos;
+ return ids[pos];
+}
+
+ID mdb_idl_next( ID *ids, ID *cursor )
+{
+ if ( MDB_IDL_IS_RANGE( ids ) ) {
+ if( ids[2] < ++(*cursor) ) {
+ return NOID;
+ }
+ return *cursor;
+ }
+
+ if ( ++(*cursor) <= ids[0] ) {
+ return ids[*cursor];
+ }
+
+ return NOID;
+}
+
+/* Add one ID to an unsorted list. We ensure that the first element is the
+ * minimum and the last element is the maximum, for fast range compaction.
+ * this means IDLs up to length 3 are always sorted...
+ */
+int mdb_idl_append_one( ID *ids, ID id )
+{
+ if (MDB_IDL_IS_RANGE( ids )) {
+ /* if already in range, treat as a dup */
+ if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
+ return -1;
+ if (id < MDB_IDL_RANGE_FIRST(ids))
+ ids[1] = id;
+ else if (id > MDB_IDL_RANGE_LAST(ids))
+ ids[2] = id;
+ return 0;
+ }
+ if ( ids[0] ) {
+ ID tmp;
+
+ if (id < ids[1]) {
+ tmp = ids[1];
+ ids[1] = id;
+ id = tmp;
+ }
+ if ( ids[0] > 1 && id < ids[ids[0]] ) {
+ tmp = ids[ids[0]];
+ ids[ids[0]] = id;
+ id = tmp;
+ }
+ }
+ ids[0]++;
+ if ( ids[0] >= MDB_IDL_UM_MAX ) {
+ ids[0] = NOID;
+ ids[2] = id;
+ } else {
+ ids[ids[0]] = id;
+ }
+ return 0;
+}
+
+/* Append sorted list b to sorted list a. The result is unsorted but
+ * a[1] is the min of the result and a[a[0]] is the max.
+ */
+int mdb_idl_append( ID *a, ID *b )
+{
+ ID ida, idb, tmp, swap = 0;
+
+ if ( MDB_IDL_IS_ZERO( b ) ) {
+ return 0;
+ }
+
+ if ( MDB_IDL_IS_ZERO( a ) ) {
+ MDB_IDL_CPY( a, b );
+ return 0;
+ }
+
+ ida = MDB_IDL_LAST( a );
+ idb = MDB_IDL_LAST( b );
+ if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
+ a[0] + b[0] >= MDB_IDL_UM_MAX ) {
+ a[2] = IDL_MAX( ida, idb );
+ a[1] = IDL_MIN( a[1], b[1] );
+ a[0] = NOID;
+ return 0;
+ }
+
+ if ( b[0] > 1 && ida > idb ) {
+ swap = idb;
+ a[a[0]] = idb;
+ b[b[0]] = ida;
+ }
+
+ if ( b[1] < a[1] ) {
+ tmp = a[1];
+ a[1] = b[1];
+ } else {
+ tmp = b[1];
+ }
+ a[0]++;
+ a[a[0]] = tmp;
+
+ if ( b[0] > 1 ) {
+ int i = b[0] - 1;
+ AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
+ a[0] += i;
+ }
+ if ( swap ) {
+ b[b[0]] = swap;
+ }
+ return 0;
+}
+
+#if 1
+
+/* Quicksort + Insertion sort for small arrays */
+
+#define SMALL 8
+#define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp
+
+void
+mdb_idl_sort( ID *ids, ID *tmp )
+{
+ int *istack = (int *)tmp; /* Private stack, not used by caller */
+ int i,j,k,l,ir,jstack;
+ ID a, itmp;
+
+ if ( MDB_IDL_IS_RANGE( ids ))
+ return;
+
+ ir = ids[0];
+ l = 1;
+ jstack = 0;
+ for(;;) {
+ if (ir - l < SMALL) { /* Insertion sort */
+ for (j=l+1;j<=ir;j++) {
+ a = ids[j];
+ for (i=j-1;i>=1;i--) {
+ if (ids[i] <= a) break;
+ ids[i+1] = ids[i];
+ }
+ ids[i+1] = a;
+ }
+ if (jstack == 0) break;
+ ir = istack[jstack--];
+ l = istack[jstack--];
+ } else {
+ k = (l + ir) >> 1; /* Choose median of left, center, right */
+ SWAP(ids[k], ids[l+1]);
+ if (ids[l] > ids[ir]) {
+ SWAP(ids[l], ids[ir]);
+ }
+ if (ids[l+1] > ids[ir]) {
+ SWAP(ids[l+1], ids[ir]);
+ }
+ if (ids[l] > ids[l+1]) {
+ SWAP(ids[l], ids[l+1]);
+ }
+ i = l+1;
+ j = ir;
+ a = ids[l+1];
+ for(;;) {
+ do i++; while(ids[i] < a);
+ do j--; while(ids[j] > a);
+ if (j < i) break;
+ SWAP(ids[i],ids[j]);
+ }
+ ids[l+1] = ids[j];
+ ids[j] = a;
+ jstack += 2;
+ if (ir-i+1 >= j-l) {
+ istack[jstack] = ir;
+ istack[jstack-1] = i;
+ ir = j-1;
+ } else {
+ istack[jstack] = j-1;
+ istack[jstack-1] = l;
+ l = i;
+ }
+ }
+ }
+}
+
+#else
+
+/* 8 bit Radix sort + insertion sort
+ *
+ * based on code from http://www.cubic.org/docs/radix.htm
+ * with improvements by ebackes@symas.com and hyc@symas.com
+ *
+ * This code is O(n) but has a relatively high constant factor. For lists
+ * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
+ * Much faster than quicksort for lists longer than ~100. Insertion
+ * sort is actually superior for lists <50.
+ */
+
+#define BUCKETS (1<<8)
+#define SMALL 50
+
+void
+mdb_idl_sort( ID *ids, ID *tmp )
+{
+ int count, soft_limit, phase = 0, size = ids[0];
+ ID *idls[2];
+ unsigned char *maxv = (unsigned char *)&ids[size];
+
+ if ( MDB_IDL_IS_RANGE( ids ))
+ return;
+
+ /* Use insertion sort for small lists */
+ if ( size <= SMALL ) {
+ int i,j;
+ ID a;
+
+ for (j=1;j<=size;j++) {
+ a = ids[j];
+ for (i=j-1;i>=1;i--) {
+ if (ids[i] <= a) break;
+ ids[i+1] = ids[i];
+ }
+ ids[i+1] = a;
+ }
+ return;
+ }
+
+ tmp[0] = size;
+ idls[0] = ids;
+ idls[1] = tmp;
+
+#if BYTE_ORDER == BIG_ENDIAN
+ for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
+#else
+ for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
+#endif
+
+ for (
+#if BYTE_ORDER == BIG_ENDIAN
+ count = sizeof(ID)-1; count >= soft_limit; --count
+#else
+ count = 0; count <= soft_limit; ++count
+#endif
+ ) {
+ unsigned int num[BUCKETS], * np, n, sum;
+ int i;
+ ID *sp, *source, *dest;
+ unsigned char *bp, *source_start;
+
+ source = idls[phase]+1;
+ dest = idls[phase^1]+1;
+ source_start = ((unsigned char *) source) + count;
+
+ np = num;
+ for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
+
+ /* count occurences of every byte value */
+ bp = source_start;
+ for ( i = size; i > 0; --i, bp += sizeof(ID) )
+ num[*bp]++;
+
+ /* transform count into index by summing elements and storing
+ * into same array
+ */
+ sum = 0;
+ np = num;
+ for ( i = BUCKETS; i > 0; --i ) {
+ n = *np;
+ *np++ = sum;
+ sum += n;
+ }
+
+ /* fill dest with the right values in the right place */
+ bp = source_start;
+ sp = source;
+ for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
+ np = num + *bp;
+ dest[*np] = *sp++;
+ ++(*np);
+ }
+ phase ^= 1;
+ }
+
+ /* copy back from temp if needed */
+ if ( phase ) {
+ ids++; tmp++;
+ for ( count = 0; count < size; ++count )
+ *ids++ = *tmp++;
+ }
+}
+#endif /* Quick vs Radix */
+
+unsigned mdb_id2l_search( ID2L ids, ID id )
+{
+ /*
+ * binary search of id in ids
+ * if found, returns position of id
+ * if not found, returns first position greater than id
+ */
+ unsigned base = 0;
+ unsigned cursor = 1;
+ int val = 0;
+ unsigned n = ids[0].mid;
+
+ while( 0 < n ) {
+ unsigned pivot = n >> 1;
+ cursor = base + pivot + 1;
+ val = IDL_CMP( id, ids[cursor].mid );
+
+ if( val < 0 ) {
+ n = pivot;
+
+ } else if ( val > 0 ) {
+ base = cursor;
+ n -= pivot + 1;
+
+ } else {
+ return cursor;
+ }
+ }
+
+ if( val > 0 ) {
+ ++cursor;
+ }
+ return cursor;
+}
+
+int mdb_id2l_insert( ID2L ids, ID2 *id )
+{
+ unsigned x, i;
+
+ x = mdb_id2l_search( ids, id->mid );
+ assert( x > 0 );
+
+ if( x < 1 ) {
+ /* internal error */
+ return -2;
+ }
+
+ if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
+ /* duplicate */
+ return -1;
+ }
+
+ if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
+ /* too big */
+ return -2;
+
+ } else {
+ /* insert id */
+ ids[0].mid++;
+ for (i=ids[0].mid; i>x; i--)
+ ids[i] = ids[i-1];
+ ids[x] = *id;
+ }
+
+ return 0;
+}