diff options
Diffstat (limited to 'servers/slapd/back-mdb/idl.c')
| -rw-r--r-- | servers/slapd/back-mdb/idl.c | 1255 |
1 files changed, 1255 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..b297ec8 --- /dev/null +++ b/servers/slapd/back-mdb/idl.c @@ -0,0 +1,1255 @@ +/* idl.c - ldap id list handling routines */ +/* $OpenLDAP$ */ +/* This work is part of OpenLDAP Software <http://www.openldap.org/>. + * + * Copyright 2000-2018 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... */ + rc = mdb_cursor_del( cursor, MDB_NODUPDATA ); + if ( rc != 0 ) { + err = "c_del dup"; + 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; +} |