X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=servers%2Fslapd%2Fback-bdb%2Fidl.c;h=e48c9ac1fc4dcd3931bf95c36f762ac48dd36a02;hb=d806b970b1b91b4db5998aec7dd5ab610fbe590b;hp=b6d0208fad1bf21105f695641d3bcaeeab2a2231;hpb=df3d8f3e30d896499540a49c9b662155909c3aaf;p=openldap

diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c
index b6d0208fad..e48c9ac1fc 100644
--- a/servers/slapd/back-bdb/idl.c
+++ b/servers/slapd/back-bdb/idl.c
@@ -2,7 +2,7 @@
 /* $OpenLDAP$ */
 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
  *
- * Copyright 2000-2005 The OpenLDAP Foundation.
+ * Copyright 2000-2012 The OpenLDAP Foundation.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -22,34 +22,28 @@
 #include "back-bdb.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 ? 1 : 0 ) )
-
-#define IDL_LRU_DELETE( bdb, e ) do { 					\
-	if ( e->idl_lru_prev != NULL ) {				\
-		e->idl_lru_prev->idl_lru_next = e->idl_lru_next; 	\
-	} else {							\
-		bdb->bi_idl_lru_head = e->idl_lru_next;			\
-	}								\
-	if ( e->idl_lru_next != NULL ) {				\
-		e->idl_lru_next->idl_lru_prev = e->idl_lru_prev;	\
-	} else {							\
-		bdb->bi_idl_lru_tail = e->idl_lru_prev;			\
-	}								\
-} while ( 0 )
-
-#define IDL_LRU_ADD( bdb, e ) do {					\
-	e->idl_lru_next = bdb->bi_idl_lru_head;				\
-	if ( e->idl_lru_next != NULL ) {				\
-		e->idl_lru_next->idl_lru_prev = (e);			\
-	}								\
-	(bdb)->bi_idl_lru_head = (e);					\
-	e->idl_lru_prev = NULL;						\
-	if ( (bdb)->bi_idl_lru_tail == NULL ) {				\
-		(bdb)->bi_idl_lru_tail = (e);				\
-	}								\
+#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) )
+
+#define IDL_LRU_DELETE( bdb, e ) do { \
+	if ( (e) == (bdb)->bi_idl_lru_head ) { \
+		if ( (e)->idl_lru_next == (bdb)->bi_idl_lru_head ) { \
+			(bdb)->bi_idl_lru_head = NULL; \
+		} else { \
+			(bdb)->bi_idl_lru_head = (e)->idl_lru_next; \
+		} \
+	} \
+	if ( (e) == (bdb)->bi_idl_lru_tail ) { \
+		if ( (e)->idl_lru_prev == (bdb)->bi_idl_lru_tail ) { \
+			assert( (bdb)->bi_idl_lru_head == NULL ); \
+			(bdb)->bi_idl_lru_tail = NULL; \
+		} else { \
+			(bdb)->bi_idl_lru_tail = (e)->idl_lru_prev; \
+		} \
+	} \
+	(e)->idl_lru_next->idl_lru_prev = (e)->idl_lru_prev; \
+	(e)->idl_lru_prev->idl_lru_next = (e)->idl_lru_next; \
 } while ( 0 )
 
 static int
@@ -114,7 +108,7 @@ unsigned bdb_idl_search( ID *ids, ID id )
 	 * if not found, returns first postion greater than id
 	 */
 	unsigned base = 0;
-	unsigned cursor = 0;
+	unsigned cursor = 1;
 	int val = 0;
 	unsigned n = ids[0];
 
@@ -123,27 +117,26 @@ unsigned bdb_idl_search( ID *ids, ID id )
 #endif
 
 	while( 0 < n ) {
-		int pivot = n >> 1;
-		cursor = base + pivot;
-		val = IDL_CMP( id, ids[cursor + 1] );
+		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 + 1;
+			base = cursor;
 			n -= pivot + 1;
 
 		} else {
-			return cursor + 1;
+			return cursor;
 		}
 	}
 	
 	if( val > 0 ) {
-		return cursor + 2;
-	} else {
-		return cursor + 1;
+		++cursor;
 	}
+	return cursor;
 
 #else
 	/* (reverse) linear search */
@@ -176,11 +169,11 @@ int bdb_idl_insert( ID *ids, ID id )
 
 	if (BDB_IDL_IS_RANGE( ids )) {
 		/* if already in range, treat as a dup */
-		if (id >= BDB_IDL_FIRST(ids) && id <= BDB_IDL_LAST(ids))
+		if (id >= BDB_IDL_RANGE_FIRST(ids) && id <= BDB_IDL_RANGE_LAST(ids))
 			return -1;
-		if (id < BDB_IDL_FIRST(ids))
+		if (id < BDB_IDL_RANGE_FIRST(ids))
 			ids[1] = id;
-		else if (id > BDB_IDL_LAST(ids))
+		else if (id > BDB_IDL_RANGE_LAST(ids))
 			ids[2] = id;
 		return 0;
 	}
@@ -224,10 +217,9 @@ int bdb_idl_insert( ID *ids, ID id )
 	return 0;
 }
 
-#if 0	/* unused */
-static int idl_delete( ID *ids, ID id )
+int bdb_idl_delete( ID *ids, ID id )
 {
-	unsigned x = bdb_idl_search( ids, id );
+	unsigned x;
 
 #if IDL_DEBUG > 1
 	Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
@@ -236,6 +228,23 @@ static int idl_delete( ID *ids, ID id )
 	idl_check( ids );
 #endif
 
+	if (BDB_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 = bdb_idl_search( ids, id );
 	assert( x > 0 );
 
 	if( x <= 0 ) {
@@ -264,7 +273,6 @@ static int idl_delete( ID *ids, ID id )
 
 	return 0;
 }
-#endif	/* unused */
 
 static char *
 bdb_show_key(
@@ -302,10 +310,7 @@ bdb_idl_cache_get(
 	if ( matched_idl_entry != NULL ) {
 		if ( matched_idl_entry->idl && ids )
 			BDB_IDL_CPY( ids, matched_idl_entry->idl );
-		ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
-		IDL_LRU_DELETE( bdb, matched_idl_entry );
-		IDL_LRU_ADD( bdb, matched_idl_entry );
-		ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
+		matched_idl_entry->idl_flags |= CACHE_ENTRY_REFERENCED;
 		if ( matched_idl_entry->idl )
 			rc = LDAP_SUCCESS;
 		else
@@ -325,21 +330,22 @@ bdb_idl_cache_put(
 	int			rc )
 {
 	bdb_idl_cache_entry_t idl_tmp;
-	bdb_idl_cache_entry_t *ee;
+	bdb_idl_cache_entry_t *ee, *eprev;
+
+	if ( rc == DB_NOTFOUND || BDB_IDL_IS_ZERO( ids ))
+		return;
 
 	DBT2bv( key, &idl_tmp.kstr );
 
 	ee = (bdb_idl_cache_entry_t *) ch_malloc(
 		sizeof( bdb_idl_cache_entry_t ) );
 	ee->db = db;
-	if ( rc == DB_NOTFOUND) {
-		ee->idl = NULL;
-	} else {
-		ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
-		BDB_IDL_CPY( ee->idl, ids );
-	}
+	ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
+	BDB_IDL_CPY( ee->idl, ids );
+
 	ee->idl_lru_prev = NULL;
 	ee->idl_lru_next = NULL;
+	ee->idl_flags = 0;
 	ber_dupbv( &ee->kstr, &idl_tmp.kstr );
 	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
 	if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
@@ -352,11 +358,34 @@ bdb_idl_cache_put(
 		return;
 	}
 	ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
-	IDL_LRU_ADD( bdb, ee );
-	if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) {
-		int i = 0;
-		while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) {
-			ee = bdb->bi_idl_lru_tail;
+	/* LRU_ADD */
+	if ( bdb->bi_idl_lru_head ) {
+		assert( bdb->bi_idl_lru_tail != NULL );
+		assert( bdb->bi_idl_lru_head->idl_lru_prev != NULL );
+		assert( bdb->bi_idl_lru_head->idl_lru_next != NULL );
+
+		ee->idl_lru_next = bdb->bi_idl_lru_head;
+		ee->idl_lru_prev = bdb->bi_idl_lru_head->idl_lru_prev;
+		bdb->bi_idl_lru_head->idl_lru_prev->idl_lru_next = ee;
+		bdb->bi_idl_lru_head->idl_lru_prev = ee;
+	} else {
+		ee->idl_lru_next = ee->idl_lru_prev = ee;
+		bdb->bi_idl_lru_tail = ee;
+	}
+	bdb->bi_idl_lru_head = ee;
+
+	if ( bdb->bi_idl_cache_size >= bdb->bi_idl_cache_max_size ) {
+		int i;
+		eprev = bdb->bi_idl_lru_tail;
+		for ( i = 0; (ee = eprev) != NULL && i < 10; i++ ) {
+			eprev = ee->idl_lru_prev;
+			if ( eprev == ee ) {
+				eprev = NULL;
+			}
+			if ( ee->idl_flags & CACHE_ENTRY_REFERENCED ) {
+				ee->idl_flags ^= CACHE_ENTRY_REFERENCED;
+				continue;
+			}
 			if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
 				    bdb_idl_entry_cmp ) == NULL ) {
 				Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: "
@@ -370,8 +399,11 @@ bdb_idl_cache_put(
 			ch_free( ee->idl );
 			ch_free( ee );
 		}
+		bdb->bi_idl_lru_tail = eprev;
+		assert( bdb->bi_idl_lru_tail != NULL
+			|| bdb->bi_idl_lru_head == NULL );
 	}
-
+	bdb->bi_idl_cache_size++;
 	ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
 	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
 }
@@ -407,11 +439,69 @@ bdb_idl_cache_del(
 	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
 }
 
+void
+bdb_idl_cache_add_id(
+	struct bdb_info	*bdb,
+	DB			*db,
+	DBT			*key,
+	ID			id )
+{
+	bdb_idl_cache_entry_t *cache_entry, idl_tmp;
+	DBT2bv( key, &idl_tmp.kstr );
+	idl_tmp.db = db;
+	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
+	cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
+				      bdb_idl_entry_cmp );
+	if ( cache_entry != NULL ) {
+		if ( !BDB_IDL_IS_RANGE( cache_entry->idl ) &&
+			cache_entry->idl[0] < BDB_IDL_DB_MAX ) {
+			size_t s = BDB_IDL_SIZEOF( cache_entry->idl ) + sizeof(ID);
+			cache_entry->idl = ch_realloc( cache_entry->idl, s );
+		}
+		bdb_idl_insert( cache_entry->idl, id );
+	}
+	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
+}
+
+void
+bdb_idl_cache_del_id(
+	struct bdb_info	*bdb,
+	DB			*db,
+	DBT			*key,
+	ID			id )
+{
+	bdb_idl_cache_entry_t *cache_entry, idl_tmp;
+	DBT2bv( key, &idl_tmp.kstr );
+	idl_tmp.db = db;
+	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
+	cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
+				      bdb_idl_entry_cmp );
+	if ( cache_entry != NULL ) {
+		bdb_idl_delete( cache_entry->idl, id );
+		if ( cache_entry->idl[0] == 0 ) {
+			if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) cache_entry,
+						bdb_idl_entry_cmp ) == NULL ) {
+				Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
+					"AVL delete failed\n",
+					0, 0, 0 );
+			}
+			--bdb->bi_idl_cache_size;
+			ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
+			IDL_LRU_DELETE( bdb, cache_entry );
+			ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
+			free( cache_entry->kstr.bv_val );
+			free( cache_entry->idl );
+			free( cache_entry );
+		}
+	}
+	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
+}
+
 int
 bdb_idl_fetch_key(
 	BackendDB	*be,
 	DB			*db,
-	DB_TXN		*tid,
+	DB_TXN		*txn,
 	DBT			*key,
 	ID			*ids,
 	DBC                     **saved_cursor,
@@ -484,7 +574,7 @@ bdb_idl_fetch_key(
 
 	/* If we're not reusing an existing cursor, get a new one */
 	if( opflag != DB_NEXT ) {
-		rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
+		rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 		if( rc != 0 ) {
 			Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 				"cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
@@ -623,10 +713,6 @@ bdb_idl_insert_key(
 
 	assert( id != NOID );
 
-	if ( bdb->bi_idl_cache_size ) {
-		bdb_idl_cache_del( bdb, db, key );
-	}
-
 	DBTzero( &data );
 	data.size = sizeof( ID );
 	data.ulen = data.size;
@@ -799,6 +885,12 @@ fail:
 		cursor->c_close( cursor );
 		return rc;
 	}
+	/* If key was added (didn't already exist) and using IDL cache,
+	 * update key in IDL cache.
+	 */
+	if ( !rc && bdb->bi_idl_cache_max_size ) {
+		bdb_idl_cache_add_id( bdb, db, key, id );
+	}
 	rc = cursor->c_close( cursor );
 	if( rc != 0 ) {
 		Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
@@ -831,7 +923,7 @@ bdb_idl_delete_key(
 	}
 	assert( id != NOID );
 
-	if ( bdb->bi_idl_cache_max_size ) {
+	if ( bdb->bi_idl_cache_size ) {
 		bdb_idl_cache_del( bdb, db, key );
 	}
 
@@ -997,8 +1089,8 @@ bdb_idl_intersection(
 	 * turn it into a range.
 	 */
 	if ( BDB_IDL_IS_RANGE( b )
-		&& BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
-		&& BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
+		&& BDB_IDL_RANGE_FIRST( b ) <= BDB_IDL_RANGE_FIRST( a )
+		&& BDB_IDL_RANGE_LAST( b ) >= BDB_IDL_RANGE_LAST( a ) ) {
 		if (idmax - idmin + 1 == a[0])
 		{
 			a[0] = NOID;
@@ -1207,3 +1299,279 @@ ID bdb_idl_next( ID *ids, ID *cursor )
 	return NOID;
 }
 
+#ifdef BDB_HIER
+
+/* 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 bdb_idl_append_one( ID *ids, ID id )
+{
+	if (BDB_IDL_IS_RANGE( ids )) {
+		/* if already in range, treat as a dup */
+		if (id >= BDB_IDL_RANGE_FIRST(ids) && id <= BDB_IDL_RANGE_LAST(ids))
+			return -1;
+		if (id < BDB_IDL_RANGE_FIRST(ids))
+			ids[1] = id;
+		else if (id > BDB_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] >= BDB_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 bdb_idl_append( ID *a, ID *b )
+{
+	ID ida, idb, tmp, swap = 0;
+
+	if ( BDB_IDL_IS_ZERO( b ) ) {
+		return 0;
+	}
+
+	if ( BDB_IDL_IS_ZERO( a ) ) {
+		BDB_IDL_CPY( a, b );
+		return 0;
+	}
+
+	if ( b[0] == 1 ) {
+		return bdb_idl_append_one( a, BDB_IDL_FIRST( b ));
+	}
+
+	ida = BDB_IDL_LAST( a );
+	idb = BDB_IDL_LAST( b );
+	if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
+		a[0] + b[0] >= BDB_IDL_UM_MAX ) {
+		a[2] = IDL_MAX( ida, idb );
+		a[1] = IDL_MIN( a[1], b[1] );
+		a[0] = NOID;
+		return 0;
+	}
+
+	if ( 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;
+
+	{
+		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
+bdb_idl_sort( ID *ids, ID *tmp )
+{
+	int *istack = (int *)tmp;
+	int i,j,k,l,ir,jstack;
+	ID a, itmp;
+
+	if ( BDB_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-1) {
+				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 mbackes@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
+bdb_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 ( BDB_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 */
+
+#endif	/* BDB_HIER */