/* $NetBSD: idl.c,v 1.1.1.3.6.1 2019/08/10 06:17:18 martin Exp $ */ /* idl.c - ldap id list handling routines */ /* $OpenLDAP$ */ /* This work is part of OpenLDAP Software . * * Copyright 2000-2019 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 * . */ #include __RCSID("$NetBSD: idl.c,v 1.1.1.3.6.1 2019/08/10 06:17:18 martin Exp $"); #include "portable.h" #include #include #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; }