From ee9623ad0f6d45cb509d3bfb34181125cdb37d1a Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Sat, 25 Nov 2006 10:58:45 +0000 Subject: [PATCH] Use quicksort in slap_mods_check for finding duplicates. Currently enabled, preserving original order of input. See ifdefs to alter the behavior: SLAP_MODS_CHECK_QUICKSORT, PRESERVE_ORDER --- servers/slapd/modify.c | 154 ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 153 insertions(+), 1 deletion(-) diff --git a/servers/slapd/modify.c b/servers/slapd/modify.c index bab4bb0ffd..cb91b3015e 100644 --- a/servers/slapd/modify.c +++ b/servers/slapd/modify.c @@ -729,6 +729,8 @@ int slap_mods_check( /* check for duplicates, but ignore Deletes. */ if( nvals > 1 && ml->sml_op != LDAP_MOD_DELETE ) { +#define SLAP_MODS_CHECK_QUICKSORT +#ifndef SLAP_MODS_CHECK_QUICKSORT int i, j, rc, match; MatchingRule *mr = ad->ad_type->sat_equality; @@ -760,8 +762,158 @@ int slap_mods_check( } } } +#else /* SLAP_MODS_CHECK_QUICKSORT */ + +/* Quicksort + Insertion sort for small arrays */ + +#define SMALL 8 +#define SWAP(a,b,tmp) tmp=(a);(a)=(b);(b)=tmp +#define COMP(a,b) match=0; rc = ordered_value_match( &match, \ + ml->sml_desc, mr, SLAP_MR_EQUALITY \ + | SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX \ + | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH \ + | SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH, \ + &(a), &(b), text ); + + MatchingRule *mr = ad->ad_type->sat_equality; + int istack[sizeof(int)*16]; + int i,j,k,l,ir,jstack, rc, match, *ix, itmp; + struct berval a, *cv; + +/* If PRESERVE_ORDER is defined only the index array is sorted; the + * actual values are left in their incoming order. Otherwise, the + * only reason to keep the index array is to identify the offending + * value when duplicates are found. + */ +#define PRESERVE_ORDER +#ifndef PRESERVE_ORDER + struct berval va, *v, *nv, bvtmp; + +#define IX(x) x +#define EXCH(x,y) SWAP(ix[x],ix[y],itmp); SWAP(cv[x],cv[y],bvtmp); \ + if (nv) {SWAP(v[x],v[y],bvtmp);} +#define SETA(x) itmp = ix[x]; a = cv[x]; if (nv) va=v[x] +#define GETA(x) ix[x] = itmp; cv[x] = a; if (nv) v[x]=va +#define SET(x,y) ix[x] = ix[y]; cv[x] = cv[y]; if (nv) v[x]=v[y] + + v = ml->sml_values; + nv = ml->sml_nvalues; + +#else /* PRESERVE_ORDER */ + +#define IX(x) ix[x] +#define EXCH(x,y) SWAP(ix[x],ix[y],itmp) +#define SETA(x) itmp = ix[x]; a = cv[itmp] +#define GETA(x) ix[x] = itmp; +#define SET(x,y) ix[x] = ix[y] + +#endif /* PRESERVE_ORDER */ + + cv = ml->sml_nvalues ? ml->sml_nvalues : ml->sml_values; + + /* record indices to preserve input ordering */ + ix = slap_sl_malloc( nvals * sizeof(int), ctx ); + for (i=0; i=0;i--) { + COMP(cv[IX(i)], a); + if ( match <= 0 ) + break; + SET(i+1,i); + } + GETA(i+1); + if ( match == 0 ) goto done; + } + if ( jstack == 0 ) break; + if ( match == 0 ) break; + ir = istack[jstack--]; + l = istack[jstack--]; + } else { + k = (l + ir) >> 1; /* Choose median of left, center, right */ + EXCH(k, l+1); + COMP( cv[IX(l)], cv[IX(ir)] ); + if ( match > 0 ) { + EXCH(l, ir); + } else if ( match == 0 ) { + i = ir; + break; + } + COMP( cv[IX(l+1)], cv[IX(ir)] ); + if ( match > 0 ) { + EXCH(l+1, ir); + } else if ( match == 0 ) { + i = ir; + break; + } + COMP( cv[IX(l)], cv[IX(l+1)] ); + if ( match > 0 ) { + EXCH(l, l+1); + } else if ( match == 0 ) { + i = l; + break; + } + i = l+1; + j = ir; + a = cv[IX(i)]; + for(;;) { + do { + i++; + COMP( cv[IX(i)], a ); + } while( match < 0 ); + while( match > 0 ) { + j--; + COMP( cv[IX(j)], a ); + } + if (j < i) { + match = 1; + break; + } + if ( match == 0 ) { + i = l+1; + break; + } + EXCH(i,j); + } + if ( match == 0 ) + break; + EXCH(l+1,j); + jstack += 2; + if (ir-i+1 >= j) { + istack[jstack] = ir; + istack[jstack-1] = i; + ir = j; + } else { + istack[jstack] = j; + istack[jstack-1] = l; + l = i; + } + } + } +done: + j = ix[i]; + slap_sl_free( ix, ctx ); + + if ( rc != LDAP_SUCCESS ) { + return rc; + } else if ( match == 0 ) { + /* value exists already */ + snprintf( textbuf, textlen, + "%s: value #%d provided more than once", + ml->sml_desc->ad_cname.bv_val, j ); + *text = textbuf; + return LDAP_TYPE_OR_VALUE_EXISTS; + } +#endif /* SLAP_MODS_CHECK_QUICKSORT */ } - } } -- 2.39.5