X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=servers%2Fslapd%2Fback-bdb%2Fidl.c;h=ff85ecee5cdbe683e8bf819ea54f4011bc23717a;hb=5c6976518b2d31112bf5f35ed459b22e5713afff;hp=c29d9228ce1200c8c082c619125a8cf0a8353b31;hpb=3429c5a566c7fe4e532f4e7de62c9289e0609525;p=openldap

diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c
index c29d9228ce..ff85ecee5c 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-2008 The OpenLDAP Foundation.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -27,29 +27,24 @@
 
 #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_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
@@ -226,7 +221,7 @@ int bdb_idl_insert( ID *ids, ID id )
 
 static 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 );
@@ -235,6 +230,23 @@ static int bdb_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 ) {
@@ -300,10 +312,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
@@ -323,21 +332,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 || BDB_IDL_IS_ZERO( ids )) {
-		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,
@@ -350,11 +360,34 @@ bdb_idl_cache_put(
 		return;
 	}
 	ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
-	IDL_LRU_ADD( bdb, ee );
+	/* 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 = 0;
-		while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) {
-			ee = bdb->bi_idl_lru_tail;
+		int i;
+		ee = bdb->bi_idl_lru_tail;
+		for ( i = 0; ee != NULL && i < 10; i++, ee = eprev ) {
+			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: "
@@ -368,8 +401,10 @@ 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 );
 	}
-
 	ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
 	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
 }
@@ -456,8 +491,7 @@ bdb_idl_cache_del_id(
 			IDL_LRU_DELETE( bdb, cache_entry );
 			ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
 			free( cache_entry->kstr.bv_val );
-			if ( cache_entry->idl )
-				free( cache_entry->idl );
+			free( cache_entry->idl );
 			free( cache_entry );
 		}
 	}
@@ -468,7 +502,7 @@ int
 bdb_idl_fetch_key(
 	BackendDB	*be,
 	DB			*db,
-	DB_TXN		*tid,
+	DB_TXN		*txn,
 	DBT			*key,
 	ID			*ids,
 	DBC                     **saved_cursor,
@@ -541,7 +575,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 );
@@ -680,10 +714,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;
@@ -856,6 +886,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: "
@@ -888,7 +924,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 );
 	}
 
@@ -1358,7 +1394,7 @@ int bdb_idl_append( ID *a, ID *b )
 	return 0;
 }
 
-#if 0
+#if 1
 
 /* Quicksort + Insertion sort for small arrays */