From 47f6aec61e65afd66bea096887f1cd550b55946e Mon Sep 17 00:00:00 2001 From: Hallvard Furuseth Date: Tue, 13 Sep 2011 09:39:28 +0200 Subject: [PATCH] back-bdb/back-mdb IDL cleanup. Parenthesize macros. Microoptimize IDL search. Use RANGE_ when IDL is known to be a range. --- servers/slapd/back-bdb/idl.c | 40 ++++++++++++------------ servers/slapd/back-bdb/idl.h | 6 ++-- servers/slapd/back-mdb/idl.c | 59 +++++++++++++++++------------------- servers/slapd/back-mdb/idl.h | 6 ++-- 4 files changed, 53 insertions(+), 58 deletions(-) diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c index 853a88c3dd..3a4e95efbf 100644 --- a/servers/slapd/back-bdb/idl.c +++ b/servers/slapd/back-bdb/idl.c @@ -22,10 +22,9 @@ #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_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 ) { \ @@ -109,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]; @@ -118,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 */ @@ -171,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; } @@ -1091,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; @@ -1311,11 +1309,11 @@ 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_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; } diff --git a/servers/slapd/back-bdb/idl.h b/servers/slapd/back-bdb/idl.h index bd3e4587a0..44c8fa9259 100644 --- a/servers/slapd/back-bdb/idl.h +++ b/servers/slapd/back-bdb/idl.h @@ -61,12 +61,12 @@ #define BDB_IDL_ID( bdb, ids, id ) BDB_IDL_RANGE( ids, id, ((bdb)->bi_lastid) ) #define BDB_IDL_ALL( bdb, ids ) BDB_IDL_RANGE( ids, 1, ((bdb)->bi_lastid) ) -#define BDB_IDL_FIRST( ids ) ( ids[1] ) +#define BDB_IDL_FIRST( ids ) ( (ids)[1] ) #define BDB_IDL_LAST( ids ) ( BDB_IDL_IS_RANGE(ids) \ - ? ids[2] : ids[ids[0]] ) + ? (ids)[2] : (ids)[(ids)[0]] ) #define BDB_IDL_N( ids ) ( BDB_IDL_IS_RANGE(ids) \ - ? (ids[2]-ids[1])+1 : ids[0] ) + ? ((ids)[2]-(ids)[1])+1 : (ids)[0] ) LDAP_BEGIN_DECL LDAP_END_DECL diff --git a/servers/slapd/back-mdb/idl.c b/servers/slapd/back-mdb/idl.c index eee40be51f..67d77bd5bf 100644 --- a/servers/slapd/back-mdb/idl.c +++ b/servers/slapd/back-mdb/idl.c @@ -22,10 +22,9 @@ #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 ) ) +#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 ) @@ -78,7 +77,7 @@ unsigned mdb_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]; @@ -87,27 +86,26 @@ unsigned mdb_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 */ @@ -140,11 +138,11 @@ int mdb_idl_insert( ID *ids, ID id ) if (MDB_IDL_IS_RANGE( ids )) { /* if already in range, treat as a dup */ - if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids)) + if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids)) return -1; - if (id < MDB_IDL_FIRST(ids)) + if (id < MDB_IDL_RANGE_FIRST(ids)) ids[1] = id; - else if (id > MDB_IDL_LAST(ids)) + else if (id > MDB_IDL_RANGE_LAST(ids)) ids[2] = id; return 0; } @@ -670,8 +668,8 @@ mdb_idl_intersection( * turn it into a range. */ if ( MDB_IDL_IS_RANGE( b ) - && MDB_IDL_FIRST( b ) <= MDB_IDL_FIRST( a ) - && MDB_IDL_LAST( b ) >= MDB_IDL_LAST( a ) ) { + && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_RANGE_FIRST( a ) + && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_RANGE_LAST( a ) ) { if (idmax - idmin + 1 == a[0]) { a[0] = NOID; @@ -888,11 +886,11 @@ 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_FIRST(ids) && id <= MDB_IDL_LAST(ids)) + if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids)) return -1; - if (id < MDB_IDL_FIRST(ids)) + if (id < MDB_IDL_RANGE_FIRST(ids)) ids[1] = id; - else if (id > MDB_IDL_LAST(ids)) + else if (id > MDB_IDL_RANGE_LAST(ids)) ids[2] = id; return 0; } @@ -982,7 +980,7 @@ int mdb_idl_append( ID *a, ID *b ) void mdb_idl_sort( ID *ids, ID *tmp ) { - int *istack = (int *)tmp; + int *istack = (int *)tmp; /* Private stack, not used by caller */ int i,j,k,l,ir,jstack; ID a, itmp; @@ -1157,32 +1155,31 @@ unsigned mdb_id2l_search( ID2L ids, ID id ) * if not found, returns first position greater than id */ unsigned base = 0; - unsigned cursor = 0; + unsigned cursor = 1; int val = 0; unsigned n = ids[0].mid; while( 0 < n ) { - int pivot = n >> 1; - cursor = base + pivot; - val = IDL_CMP( id, ids[cursor + 1].mid ); + 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 + 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; } int mdb_id2l_insert( ID2L ids, ID2 *id ) diff --git a/servers/slapd/back-mdb/idl.h b/servers/slapd/back-mdb/idl.h index 1b4232564c..bbb79dbb96 100644 --- a/servers/slapd/back-mdb/idl.h +++ b/servers/slapd/back-mdb/idl.h @@ -61,12 +61,12 @@ #define MDB_IDL_ID( mdb, ids, id ) MDB_IDL_RANGE( ids, id, NOID ) #define MDB_IDL_ALL( ids ) MDB_IDL_RANGE( ids, 1, NOID ) -#define MDB_IDL_FIRST( ids ) ( ids[1] ) +#define MDB_IDL_FIRST( ids ) ( (ids)[1] ) #define MDB_IDL_LAST( ids ) ( MDB_IDL_IS_RANGE(ids) \ - ? ids[2] : ids[ids[0]] ) + ? (ids)[2] : (ids)[(ids)[0]] ) #define MDB_IDL_N( ids ) ( MDB_IDL_IS_RANGE(ids) \ - ? (ids[2]-ids[1])+1 : ids[0] ) + ? ((ids)[2]-(ids)[1])+1 : (ids)[0] ) /** An ID2 is an ID/value pair. */ -- 2.39.5