From d2179d885ff588df4f73ee27ae363df9a493b9f3 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Mon, 24 Sep 2007 05:02:31 +0000 Subject: [PATCH] Use attr_valfind instead of value_find_ex to optimize lookups --- servers/slapd/aci.c | 5 ++--- servers/slapd/acl.c | 5 ++--- servers/slapd/attr.c | 25 ++++++++++++++++++------- servers/slapd/back-bdb/compare.c | 4 ++-- servers/slapd/back-monitor/compare.c | 4 ++-- servers/slapd/back-sql/compare.c | 5 ++--- servers/slapd/backend.c | 4 ++-- servers/slapd/bconfig.c | 1 + servers/slapd/compare.c | 4 ++-- servers/slapd/filterentry.c | 23 +++++++++++++++++++++++ servers/slapd/overlays/dynlist.c | 8 ++++---- servers/slapd/overlays/syncprov.c | 4 ++-- servers/slapd/schema_check.c | 4 ++-- servers/slapd/slap.h | 5 +++++ servers/slapd/slapi/slapi_utils.c | 19 +++---------------- servers/slapd/syncrepl.c | 6 +++--- 16 files changed, 75 insertions(+), 51 deletions(-) diff --git a/servers/slapd/aci.c b/servers/slapd/aci.c index ac786ace75..0acf6c108f 100644 --- a/servers/slapd/aci.c +++ b/servers/slapd/aci.c @@ -592,11 +592,10 @@ aci_mask( at != NULL; at = attrs_find( at->a_next, ad ) ) { - if ( value_find_ex( ad, + if ( attr_valfind( at, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - at->a_nvals, - &op->o_ndn, op->o_tmpmemctx ) == 0 ) + &op->o_ndn, NULL, op->o_tmpmemctx ) == 0 ) { rc = 1; break; diff --git a/servers/slapd/acl.c b/servers/slapd/acl.c index 8e9057ec68..adcfc15084 100644 --- a/servers/slapd/acl.c +++ b/servers/slapd/acl.c @@ -974,11 +974,10 @@ acl_mask_dnattr( at != NULL; at = attrs_find( at->a_next, bdn->a_at ) ) { - if ( value_find_ex( bdn->a_at, + if ( attr_valfind( at, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - at->a_nvals, - &bv, op->o_tmpmemctx ) == 0 ) + &bv, NULL, op->o_tmpmemctx ) == 0 ) { /* found it */ match = 1; diff --git a/servers/slapd/attr.c b/servers/slapd/attr.c index 7112358c1e..e66b65a841 100644 --- a/servers/slapd/attr.c +++ b/servers/slapd/attr.c @@ -211,6 +211,7 @@ attrs_free( Attribute *a ) static void attr_dup2( Attribute *tmp, Attribute *a ) { + tmp->a_flags = a->a_flags & SLAP_ATTR_PERSISTENT_FLAGS; if ( a->a_vals != NULL ) { int i; @@ -290,11 +291,16 @@ attr_valfind( void *ctx ) { struct berval nval = BER_BVNULL, *cval; - MatchingRule *mr = a->a_desc->ad_type->sat_equality; + MatchingRule *mr; const char *text; int match = -1, rc; unsigned i; + if ( flags & SLAP_MR_ORDERING ) + mr = a->a_desc->ad_type->sat_ordering; + else + mr = a->a_desc->ad_type->sat_equality; + if( !SLAP_IS_MR_ASSERTED_VALUE_NORMALIZED_MATCH( flags ) && mr->smr_normalize ) { @@ -319,15 +325,19 @@ attr_valfind( while ( 0 < n ) { unsigned pivot = n >> 1; i = base + pivot; + if ( i >= a->a_numvals ) { + i = a->a_numvals - 1; + break; + } rc = value_match( &match, a->a_desc, mr, flags, &a->a_nvals[i], cval, &text ); if ( rc == LDAP_SUCCESS && match == 0 ) break; n = pivot; - if ( match > 0 ) + if ( match < 0 ) base = i+1; } - if ( match > 0 ) + if ( match < 0 ) i++; } else { /* Linear search */ @@ -340,7 +350,8 @@ attr_valfind( break; } } - *slot = i; + if ( slot ) + *slot = i; if ( match ) rc = LDAP_NO_SUCH_ATTRIBUTE; if ( nval.bv_val ) @@ -395,14 +406,14 @@ attr_valadd( rc = LDAP_TYPE_OR_VALUE_EXISTS; return rc; } - for ( j = a->a_numvals; j > slot; j-- ) { + for ( j = a->a_numvals; j >= slot; j-- ) { a->a_vals[j+1] = a->a_vals[j]; if ( nvals ) a->a_nvals[j+1] = a->a_nvals[j]; } - ber_dupbv( &a->a_nvals[j], &v2[i] ); + ber_dupbv( &a->a_nvals[slot], &v2[i] ); if ( nvals ) - ber_dupbv( &a->a_vals[j], &vals[i] ); + ber_dupbv( &a->a_vals[slot], &vals[i] ); a->a_numvals++; } BER_BVZERO( &a->a_vals[a->a_numvals] ); diff --git a/servers/slapd/back-bdb/compare.c b/servers/slapd/back-bdb/compare.c index 972071314c..538d1da61a 100644 --- a/servers/slapd/back-bdb/compare.c +++ b/servers/slapd/back-bdb/compare.c @@ -158,10 +158,10 @@ dn2entry_retry: { rs->sr_err = LDAP_COMPARE_FALSE; - if ( value_find_ex( op->oq_compare.rs_ava->aa_desc, + if ( attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, &op->oq_compare.rs_ava->aa_value, + &op->oq_compare.rs_ava->aa_value, NULL, op->o_tmpmemctx ) == 0 ) { rs->sr_err = LDAP_COMPARE_TRUE; diff --git a/servers/slapd/back-monitor/compare.c b/servers/slapd/back-monitor/compare.c index 3a8df66624..9cac645bc9 100644 --- a/servers/slapd/back-monitor/compare.c +++ b/servers/slapd/back-monitor/compare.c @@ -71,10 +71,10 @@ monitor_back_compare( Operation *op, SlapReply *rs ) a = attrs_find( a->a_next, op->oq_compare.rs_ava->aa_desc )) { rs->sr_err = LDAP_COMPARE_FALSE; - if ( value_find_ex( op->oq_compare.rs_ava->aa_desc, + if ( attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, &op->oq_compare.rs_ava->aa_value, + &op->oq_compare.rs_ava->aa_value, NULL, op->o_tmpmemctx ) == 0 ) { rs->sr_err = LDAP_COMPARE_TRUE; diff --git a/servers/slapd/back-sql/compare.c b/servers/slapd/back-sql/compare.c index 24fe2e9fb1..403e82c3e5 100644 --- a/servers/slapd/back-sql/compare.c +++ b/servers/slapd/back-sql/compare.c @@ -131,11 +131,10 @@ backsql_compare( Operation *op, SlapReply *rs ) a = attrs_find( a->a_next, op->oq_compare.rs_ava->aa_desc ) ) { rs->sr_err = LDAP_COMPARE_FALSE; - if ( value_find_ex( op->oq_compare.rs_ava->aa_desc, + if ( attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, - &op->oq_compare.rs_ava->aa_value, + &op->oq_compare.rs_ava->aa_value, NULL, op->o_tmpmemctx ) == 0 ) { rs->sr_err = LDAP_COMPARE_TRUE; diff --git a/servers/slapd/backend.c b/servers/slapd/backend.c index eb766d349d..3eb2a679d4 100644 --- a/servers/slapd/backend.c +++ b/servers/slapd/backend.c @@ -1501,10 +1501,10 @@ loopit: op->o_bd = b2; } else { - rc = value_find_ex( group_at, + rc = attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, op_ndn, op->o_tmpmemctx ); + op_ndn, NULL, op->o_tmpmemctx ); if ( rc == LDAP_NO_SUCH_ATTRIBUTE ) { rc = LDAP_COMPARE_FALSE; } diff --git a/servers/slapd/bconfig.c b/servers/slapd/bconfig.c index d83ac37520..7576a2c2f7 100644 --- a/servers/slapd/bconfig.c +++ b/servers/slapd/bconfig.c @@ -1525,6 +1525,7 @@ sortval_reject: } svtail = sv; } + sv->al_next = NULL; for ( sv = svnew; sv; sv = sv->al_next ) sv->al_desc->ad_type->sat_flags |= SLAP_AT_SORTED_VAL; for ( sv = sortVals; sv && sv->al_next; sv = sv->al_next ); diff --git a/servers/slapd/compare.c b/servers/slapd/compare.c index eaee0c0e9b..1af6ba0b6a 100644 --- a/servers/slapd/compare.c +++ b/servers/slapd/compare.c @@ -384,10 +384,10 @@ static int compare_entry( break; } - if ( value_find_ex( ava->aa_desc, + if ( attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, &ava->aa_value, op->o_tmpmemctx ) == 0 ) + &ava->aa_value, NULL, op->o_tmpmemctx ) == 0 ) { rc = LDAP_COMPARE_TRUE; break; diff --git a/servers/slapd/filterentry.c b/servers/slapd/filterentry.c index 7d5fabfbc3..ba53221d9d 100644 --- a/servers/slapd/filterentry.c +++ b/servers/slapd/filterentry.c @@ -657,6 +657,29 @@ test_ava_filter( continue; } + if ( a->a_flags & SLAP_ATTR_SORTED_VALS ) { + unsigned slot; + rc = attr_valfind( a, use | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH | + SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH, + &ava->aa_value, &slot, NULL ); + if ( rc == LDAP_SUCCESS ) + return LDAP_COMPARE_TRUE; + if ( rc == LDAP_NO_SUCH_ATTRIBUTE ) { + /* If insertion point is not the end of the list, there was + * at least one value greater than the assertion. + */ + if ( type == LDAP_FILTER_GE && slot < a->a_numvals ) + return LDAP_COMPARE_TRUE; + /* Likewise, if insertion point is not the head of the list, + * there was at least one value less than the assertion. + */ + if ( type == LDAP_FILTER_LE && slot > 0 ) + return LDAP_COMPARE_TRUE; + return LDAP_COMPARE_FALSE; + } + return rc; + } + #ifdef LDAP_COMP_MATCH if ( nibble_mem_allocator && ava->aa_cf && !a->a_comp_data ) { /* Component Matching */ diff --git a/servers/slapd/overlays/dynlist.c b/servers/slapd/overlays/dynlist.c index 1b58fe4bef..ef75f01167 100644 --- a/servers/slapd/overlays/dynlist.c +++ b/servers/slapd/overlays/dynlist.c @@ -92,10 +92,10 @@ dynlist_is_dynlist_next( Operation *op, SlapReply *rs, dynlist_info_t *old_dli ) } for ( ; dli; dli = dli->dli_next ) { - if ( value_find_ex( slap_schema.si_ad_objectClass, + if ( attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, &dli->dli_oc->soc_cname, + &dli->dli_oc->soc_cname, NULL, op->o_tmpmemctx ) == 0 ) { return dli; @@ -723,10 +723,10 @@ done:; /* if we're here, we got a match... */ rs->sr_err = LDAP_COMPARE_FALSE; - if ( value_find_ex( op->orc_ava->aa_desc, + if ( attr_valfind( a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a->a_nvals, &op->orc_ava->aa_value, op->o_tmpmemctx ) == 0 ) + &op->orc_ava->aa_value, NULL, op->o_tmpmemctx ) == 0 ) { rs->sr_err = LDAP_COMPARE_TRUE; break; diff --git a/servers/slapd/overlays/syncprov.c b/servers/slapd/overlays/syncprov.c index 3cdcbf0c78..9cae2c53dc 100644 --- a/servers/slapd/overlays/syncprov.c +++ b/servers/slapd/overlays/syncprov.c @@ -1680,10 +1680,10 @@ syncprov_op_compare( Operation *op, SlapReply *rs ) rs->sr_err = LDAP_COMPARE_FALSE; - if ( value_find_ex( op->oq_compare.rs_ava->aa_desc, + if ( attr_valfind( &a, SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH, - a.a_nvals, &op->oq_compare.rs_ava->aa_value, op->o_tmpmemctx ) == 0 ) + &op->oq_compare.rs_ava->aa_value, NULL, op->o_tmpmemctx ) == 0 ) { rs->sr_err = LDAP_COMPARE_TRUE; } diff --git a/servers/slapd/schema_check.c b/servers/slapd/schema_check.c index a5860d7dc9..4c0d376249 100644 --- a/servers/slapd/schema_check.c +++ b/servers/slapd/schema_check.c @@ -856,9 +856,9 @@ entry_naming_check( break; } - rc = value_find_ex( desc, SLAP_MR_VALUE_OF_ASSERTION_SYNTAX| + rc = attr_valfind( attr, SLAP_MR_VALUE_OF_ASSERTION_SYNTAX| SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH, - attr->a_nvals, &ava->la_value, NULL ); + &ava->la_value, NULL, NULL ); if( rc != 0 ) { switch( rc ) { diff --git a/servers/slapd/slap.h b/servers/slapd/slap.h index bbcc3437b8..65319e1a6e 100644 --- a/servers/slapd/slap.h +++ b/servers/slapd/slap.h @@ -1131,6 +1131,11 @@ struct Attribute { #define SLAP_ATTR_DONT_FREE_DATA 0x4U #define SLAP_ATTR_DONT_FREE_VALS 0x8U #define SLAP_ATTR_SORTED_VALS 0x10U /* values are sorted */ + +/* These flags persist across an attr_dup() */ +#define SLAP_ATTR_PERSISTENT_FLAGS \ + SLAP_ATTR_SORTED_VALS + Attribute *a_next; #ifdef LDAP_COMP_MATCH ComponentData *a_comp_data; /* component values */ diff --git a/servers/slapd/slapi/slapi_utils.c b/servers/slapd/slapi/slapi_utils.c index 446fd80f4c..6c37e3b7f4 100644 --- a/servers/slapd/slapi/slapi_utils.c +++ b/servers/slapd/slapi/slapi_utils.c @@ -2152,28 +2152,15 @@ int slapi_attr_value_cmp( const Slapi_Attr *a, const struct berval *v1, const st int slapi_attr_value_find( const Slapi_Attr *a, struct berval *v ) { - MatchingRule *mr; - struct berval *bv; - int j; - const char *text; int rc; int ret; if ( a ->a_vals == NULL ) { return -1; } - mr = a->a_desc->ad_type->sat_equality; - for ( bv = a->a_vals, j = 0; bv->bv_val != NULL; bv++, j++ ) { - rc = value_match( &ret, a->a_desc, mr, - SLAP_MR_VALUE_OF_ASSERTION_SYNTAX, bv, v, &text ); - if ( rc != LDAP_SUCCESS ) { - return -1; - } - if ( ret == 0 ) { - return 0; - } - } - return -1; + rc = attr_valfind( (Attribute *)a, SLAP_MR_VALUE_OF_ASSERTION_SYNTAX, v, + NULL, NULL ); + return rc == 0 ? 0 : -1; } int slapi_attr_type_cmp( const char *t1, const char *t2, int opt ) diff --git a/servers/slapd/syncrepl.c b/servers/slapd/syncrepl.c index ea94e4e279..a657088bed 100644 --- a/servers/slapd/syncrepl.c +++ b/servers/slapd/syncrepl.c @@ -2858,11 +2858,11 @@ dn_callback( oldRDN.bv_len -= oldVal.bv_len + 2; slap_bv2ad( &oldRDN, &ad, &rs->sr_text ); a = attr_find( dni->new_entry->e_attrs, ad ); - if ( !a || value_find_ex( ad, + if ( !a || attr_valfind( a, SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH | SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH | - SLAP_MR_VALUE_OF_SYNTAX, a->a_nvals, - &oldVal, op->o_tmpmemctx ) != LDAP_SUCCESS ) + SLAP_MR_VALUE_OF_SYNTAX, + &oldVal, NULL, op->o_tmpmemctx ) != LDAP_SUCCESS ) { dni->delOldRDN = 1; } -- 2.39.5