diff options
Diffstat (limited to 'ldap/servers/slapd/valueset.c')
| -rw-r--r-- | ldap/servers/slapd/valueset.c | 1303 |
1 files changed, 1303 insertions, 0 deletions
diff --git a/ldap/servers/slapd/valueset.c b/ldap/servers/slapd/valueset.c new file mode 100644 index 00000000..a388fc38 --- /dev/null +++ b/ldap/servers/slapd/valueset.c @@ -0,0 +1,1303 @@ +/** BEGIN COPYRIGHT BLOCK + * Copyright 2001 Sun Microsystems, Inc. + * Portions copyright 1999, 2001-2003 Netscape Communications Corporation. + * All rights reserved. + * END COPYRIGHT BLOCK **/ +/* valueset.c - routines for dealing with value sets */ + +#include "slap.h" +#include "slapi-private.h" + +/* <=========================== Berval Array ==========================> */ + +/* + * vals - The existing values. + * addval - The value to add. + * nvals - The number of existing values. + * maxvals - The number of elements in the existing values array. + */ +void +bervalarray_add_berval_fast( + struct berval ***vals, + const struct berval *addval, + int nvals, + int *maxvals +) +{ + int need = nvals + 2; + if(need>*maxvals) + { + if (*maxvals==0) + { + *maxvals = 2; + } + while ( *maxvals < need ) + { + *maxvals *= 2; + } + if(*vals==NULL) + { + *vals = (struct berval **) slapi_ch_malloc( *maxvals * sizeof(struct berval *)); + } + else + { + *vals = (struct berval **) slapi_ch_realloc( (char *) *vals, *maxvals * sizeof(struct berval *)); + } + } + (*vals)[nvals] = ber_bvdup( (struct berval *)addval ); + (*vals)[nvals+1] = NULL; +} + +/* <=========================== Value Array ==========================> */ + +/* + * vals - The existing values. + * addval - The value to add. + * nvals - The number of existing values. + * maxvals - The number of elements in the existing values array. + */ +void +valuearray_add_value_fast(Slapi_Value ***vals, + Slapi_Value *addval, + int nvals, + int *maxvals, + int exact, /* Don't create an array bigger than needed */ + int passin) /* The values are being passed in */ +{ + Slapi_Value *oneval[2]; + oneval[0]= addval; + oneval[1]= NULL; + valuearray_add_valuearray_fast(vals,oneval,nvals,1,maxvals,exact,passin); +} + +void +valuearray_add_valuearray_fast(Slapi_Value ***vals, + Slapi_Value **addvals, + int nvals, + int naddvals, + int *maxvals, + int exact, /* Don't create an array bigger than needed */ + int passin) /* The values are being passed in */ +{ + int i, j; + int allocate= 0; + int need = nvals + naddvals + 1; + if(exact) + { + /* Create an array exactly the right size. */ + if(need>*maxvals) + { + allocate= need; + } + } + else + { + if (*maxvals==0) /* empty; create with 4 by default */ + { + allocate= 4; + } + else if (need > *maxvals) + { + /* Exponentially expand the array */ + allocate= *maxvals; + + while ( allocate < need ) + { + allocate *= 2; + } + } + } + if(allocate>0) + { + if(*vals==NULL) + { + *vals = (Slapi_Value **) slapi_ch_malloc( allocate * sizeof(Slapi_Value *)); + } + else + { + *vals = (Slapi_Value **) slapi_ch_realloc( (char *) *vals, allocate * sizeof(Slapi_Value *)); + } + *maxvals= allocate; + } + for ( i = 0, j = 0; i < naddvals; i++) + { + if ( addvals[i]!=NULL ) + { + if(passin) + { + /* We consume the values */ + (*vals)[nvals + j] = addvals[i]; + } + else + { + /* We copy the values */ + (*vals)[nvals + j] = slapi_value_dup(addvals[i]); + } + j++; + } + } + (*vals)[nvals + j] = NULL; +} + +void +valuearray_add_value(Slapi_Value ***vals, const Slapi_Value *addval) +{ + Slapi_Value *oneval[2]; + oneval[0]= (Slapi_Value*)addval; + oneval[1]= NULL; + valuearray_add_valuearray(vals,oneval,0); +} + +void +valuearray_add_valuearray(Slapi_Value ***vals, Slapi_Value **addvals, PRUint32 flags) +{ + int valslen; + int addvalslen; + int maxvals; + + addvalslen= valuearray_count(addvals); + if(*vals == NULL) + { + valslen= 0; + maxvals= 0; + } + else + { + valslen= valuearray_count(*vals); + maxvals= valslen+1; + } + valuearray_add_valuearray_fast(vals,addvals,valslen,addvalslen,&maxvals,1/*Exact*/,flags & SLAPI_VALUE_FLAG_PASSIN); +} + +int +valuearray_count( Slapi_Value **va) +{ + int i=0; + if(va!=NULL) + { + while(NULL != va[i]) i++; + } + return(i); +} + +int +valuearray_isempty( Slapi_Value **va) +{ + return va==NULL || va[0]==NULL; +} + +/* + * JCM SLOW FUNCTION + * + * WARNING: Use only if you absolutley need to... + * This function mostly exists to map from the old slapi berval + * based interface to the new Slapi_Value based interfaces. + */ +int +valuearray_init_bervalarray(struct berval **bvals, Slapi_Value ***cvals) +{ + int n; + for(n=0; bvals != NULL && bvals[n] != NULL; n++); + if(n==0) + { + *cvals = NULL; + } + else + { + int i; + *cvals = (Slapi_Value **) slapi_ch_malloc((n + 1) * sizeof(Slapi_Value *)); + for(i=0;i<n;i++) + { + (*cvals)[i] = slapi_value_new_berval(bvals[i]); + } + (*cvals)[i] = NULL; + } + return n; +} + +/* + * JCM SLOW FUNCTION + * + * Use only if you absolutley need to... + * This function mostly exists to map from the old slapi berval + * based interface to the new Slapi_Value based interfaces. + */ +int +valuearray_get_bervalarray(Slapi_Value **cvals,struct berval ***bvals) +{ + int i,n; + n= valuearray_count(cvals); + if (0 == n) + { + *bvals = NULL; + } + else + { + *bvals = (struct berval **)slapi_ch_malloc((n + 1) * sizeof(struct berval *)); + for(i=0;i<n;i++) + { + (*bvals)[i] = ber_bvdup(slapi_value_get_berval(cvals[i])); + } + (*bvals)[i] = NULL; + } + return(0); +} + +void +valuearray_free(Slapi_Value ***va) +{ + if(va!=NULL && *va!=NULL) + { + int i; + for(i=0; (*va)[i]!=NULL; i++) + { + slapi_value_free(&(*va)[i]); + } + slapi_ch_free((void **)va); + *va = NULL; + } +} + +int +valuearray_next_value( Slapi_Value **va, int index, Slapi_Value **v) +{ + int r= -1; + if(va!=NULL && va[0]!=NULL) + { + r= index+1; + *v= va[r]; + if(*v==NULL) + { + r= -1; + } + } + else + { + *v= NULL; + } + return r; +} + +int +valuearray_first_value( Slapi_Value **va, Slapi_Value **v ) +{ + return valuearray_next_value( va, -1, v); +} + +/* + * Find the value and return an index number to it. + */ +int +valuearray_find(const Slapi_Attr *a, Slapi_Value **va, const Slapi_Value *v) +{ + int i= 0; + int found= -1; + while(found==-1 && va!=NULL && va[i]!=NULL) + { + if(slapi_value_compare( a, v, va[i])==0) + { + found= i; + } + else + { + i++; + } + } + return found; +} + +/* + * Shunt up the array to cover the value to remove. + */ +void +valuearray_remove_value_atindex(Slapi_Value **va, int index) +{ + if(va!=NULL && va[0]!=NULL) + { + int k; + for ( k = index + 1; va[k] != NULL; k++ ) + { + va[k - 1] = va[k]; + } + va[k - 1] = NULL; + } +} + +/* + * Find the value in the array, + * shunt up the array to cover it, + * return a ptr to the value. + */ +Slapi_Value * +valuearray_remove_value(const Slapi_Attr *a, Slapi_Value **va, const Slapi_Value *v) +{ + Slapi_Value *r= NULL; + int i= 0; + i= valuearray_find(a, va, v); + if(i!=-1) + { + r= va[i]; + valuearray_remove_value_atindex(va,i); + } + return r; +} + +/* + * Remove any values older than the CSN. + */ +int +valuearray_purge(Slapi_Value ***va, const CSN *csn) +{ + int numValues=0; + int i=0; + int nextValue=0; + + PR_ASSERT(va!=NULL && *va!=NULL); + + /* Loop over all the values freeing the old ones. */ + for(i=0; (*va)[i]; i++) + { + csnset_purge(&((*va)[i]->v_csnset),csn); + if ((*va)[i]->v_csnset == NULL) + { + slapi_value_free(&(*va)[i]); + (*va)[i] = NULL; + } + } + /* Now compact the value list. */ + numValues=i; + nextValue = 0; + i = 0; + for(i=0;i<numValues;i++) + { + while((nextValue < numValues) && (NULL == (*va)[nextValue])) + { + nextValue++; + } + if(nextValue < numValues) + { + (*va)[i] = (*va)[nextValue]; + nextValue++; + } + else + { + break; + } + } + (*va)[i] = NULL; + + /* All the values were deleted, we can discard the whole array. */ + if(NULL == (*va)[0]) + { + slapi_ch_free((void**)va); + *va= NULL; + } + + return(0); +} + +size_t +valuearray_size(Slapi_Value **va) +{ + size_t s= 0; + if(va!=NULL && va[0]!=NULL) + { + int i; + for (i = 0; va[i]; i++) + { + s += value_size(va[i]); + } + s += (i + 1) * sizeof(Slapi_Value*); + } + return s; +} + +void +valuearray_update_csn(Slapi_Value **va, CSNType t, const CSN *csn) +{ + int i; + for (i = 0; va!=NULL && va[i]; i++) + { + value_update_csn(va[i],t,csn); + } +} + +/* + * Shunt up the values to cover the empty slots. + * + * "compressed" means "contains no NULL's" + * + * Invariant for the outer loop: + * va[0..i] is compressed && + * va[n..numvalues] contains just NULL's + * + * Invariant for the inner loop: + * i<j<=k<=n && va[j..k] has been shifted left by (j-i) places && + * va[k..n] remains to be shifted left by (j-i) places + * + */ +void +valuearray_compress(Slapi_Value **va,int numvalues) +{ + int i = 0; + int n= numvalues; + while(i<n) + { + if ( va[i] != NULL ) { + i++; + } else { + int k,j; + j = i + 1; + /* Find the length of the next run of NULL's */ + while( j<n && va[j] == NULL) { j++; } + /* va[i..j] is all NULL && j<= n */ + for ( k = j; k<n; k++ ) + { + va[k - (j-i)] = va[k]; + va[k] = NULL; + } + /* va[i..n] has been shifted down by j-i places */ + n = n - (j-i); + /* + * If va[i] in now non null, then bump i, + * if not then we are done anyway (j==n) so can bump it. + */ + i++; + } + } +} + +/* <=========================== Value Array Fast ==========================> */ + +void +valuearrayfast_init(struct valuearrayfast *vaf,Slapi_Value **va) +{ + vaf->num= valuearray_count(va); + vaf->max= vaf->num; + vaf->va= va; +} + +void +valuearrayfast_done(struct valuearrayfast *vaf) +{ + if(vaf->va!=NULL) + { + int i; + for(i=0; i<vaf->num; i++) + { + slapi_value_free(&vaf->va[i]); + } + slapi_ch_free((void **)&vaf->va); + vaf->num= 0; + vaf->max= 0; + } +} + +void +valuearrayfast_add_value(struct valuearrayfast *vaf,const Slapi_Value *v) +{ + valuearray_add_value_fast(&vaf->va,(Slapi_Value *)v,vaf->num,&vaf->max,0/*Exact*/,0/*!PassIn*/); + vaf->num++; +} + +void +valuearrayfast_add_value_passin(struct valuearrayfast *vaf,Slapi_Value *v) +{ + valuearray_add_value_fast(&vaf->va,v,vaf->num,&vaf->max,0/*Exact*/,1/*PassIn*/); + vaf->num++; +} + +void +valuearrayfast_add_valuearrayfast(struct valuearrayfast *vaf,const struct valuearrayfast *vaf_add) +{ + valuearray_add_valuearray_fast(&vaf->va,vaf_add->va,vaf->num,vaf_add->num,&vaf->max,0/*Exact*/,0/*!PassIn*/); + vaf->num+= vaf_add->num; +} + +/* <=========================== ValueArrayIndexTree =======================> */ + +static int valuetree_dupvalue_disallow( caddr_t d1, caddr_t d2 ); +static int valuetree_node_cmp( caddr_t d1, caddr_t d2 ); +static int valuetree_node_free( caddr_t data ); + +/* + * structure used within AVL value trees. + */ +typedef struct valuetree_node +{ + int index; /* index into the value array */ + Slapi_Value *sval; /* the actual value */ +} valuetree_node; + +/* + * Create or update an AVL tree of values that can be used to speed up value + * lookups. We store the index keys for the values in the AVL tree so + * we can use a trivial comparison function. + * + * Returns: + * LDAP_SUCCESS on success, + * LDAP_TYPE_OR_VALUE_EXISTS if the value already exists, + * LDAP_OPERATIONS_ERROR for some unexpected failure. + * + * Sets *valuetreep to the root of the AVL tree that was created. If a + * non-zero value is returned, the tree is freed if free_on_error is non-zero + * and *valuetreep is set to NULL. + */ +int +valuetree_add_valuearray( const char *type, struct slapdplugin *pi, Slapi_Value **va, Avlnode **valuetreep, int *duplicate_index ) +{ + int rc= LDAP_SUCCESS; + + PR_ASSERT(type!=NULL); + PR_ASSERT(pi!=NULL); + PR_ASSERT(valuetreep!=NULL); + + if ( duplicate_index ) { + *duplicate_index = -1; + } + + if ( !valuearray_isempty(va) ) + { + Slapi_Value **keyvals; + /* Convert the value array into key values */ + if ( slapi_call_syntax_values2keys_sv( pi, (Slapi_Value**)va, &keyvals, LDAP_FILTER_EQUALITY ) != 0 ) /* jcm cast */ + { + LDAPDebug( LDAP_DEBUG_ANY,"slapi_call_syntax_values2keys for attribute %s failed\n", type, 0, 0 ); + rc= LDAP_OPERATIONS_ERROR; + } + else + { + int i; + valuetree_node *vaip; + for ( i = 0; rc==LDAP_SUCCESS && va[i] != NULL; ++i ) + { + if ( keyvals[i] == NULL ) + { + LDAPDebug( LDAP_DEBUG_ANY,"slapi_call_syntax_values2keys for attribute %s did not return enough key values\n", type, 0, 0 ); + rc= LDAP_OPERATIONS_ERROR; + } + else + { + vaip = (valuetree_node *)slapi_ch_malloc( sizeof( valuetree_node )); + vaip->index = i; + vaip->sval = keyvals[i]; + if (( rc = avl_insert( valuetreep, vaip, valuetree_node_cmp, valuetree_dupvalue_disallow )) != 0 ) + { + slapi_ch_free( (void **)&vaip ); + /* Value must already be in there */ + rc= LDAP_TYPE_OR_VALUE_EXISTS; + if ( duplicate_index ) { + *duplicate_index = i; + } + } + else + { + keyvals[i]= NULL; + } + } + } + valuearray_free( &keyvals ); + } + } + if(rc!=0) + { + valuetree_free( valuetreep ); + } + + return rc; +} + +int +valuetree_add_value( const char *type, struct slapdplugin *pi, const Slapi_Value *v, Avlnode **valuetreep) +{ + Slapi_Value *va[2]; + va[0]= (Slapi_Value*)v; + va[1]= NULL; + return valuetree_add_valuearray( type, pi, va, valuetreep, NULL); +} + + +/* + * + * Find value "v" using AVL tree "valuetree" + * + * returns LDAP_SUCCESS if "v" was found, LDAP_NO_SUCH_ATTRIBUTE + * if "v" was not found and LDAP_OPERATIONS_ERROR if some unexpected error occurs. + */ +static int +valuetree_find( const struct slapi_attr *a, const Slapi_Value *v, Avlnode *valuetree, int *index) +{ + const Slapi_Value *oneval[2]; + Slapi_Value **keyvals; + valuetree_node *vaip, tmpvain; + + PR_ASSERT(a!=NULL); + PR_ASSERT(a->a_plugin!=NULL); + PR_ASSERT(v!=NULL); + PR_ASSERT(valuetree!=NULL); + PR_ASSERT(index!=NULL); + + if ( a == NULL || a->a_plugin == NULL || v == NULL || valuetree == NULL ) + { + return( LDAP_OPERATIONS_ERROR ); + } + + keyvals = NULL; + oneval[0] = v; + oneval[1] = NULL; + if ( slapi_call_syntax_values2keys_sv( a->a_plugin, (Slapi_Value**)oneval, &keyvals, LDAP_FILTER_EQUALITY ) != 0 /* jcm cast */ + || keyvals == NULL + || keyvals[0] == NULL ) + { + LDAPDebug( LDAP_DEBUG_ANY, "valuetree_find_and_replace: " + "slapi_call_syntax_values2keys failed for type %s\n", + a->a_type, 0, 0 ); + return( LDAP_OPERATIONS_ERROR ); + } + + tmpvain.index = 0; + tmpvain.sval = keyvals[0]; + vaip = (valuetree_node *)avl_find( valuetree, &tmpvain, valuetree_node_cmp ); + + if ( keyvals != NULL ) + { + valuearray_free( &keyvals ); + } + + if (vaip == NULL) + { + return( LDAP_NO_SUCH_ATTRIBUTE ); + } + else + { + *index= vaip->index; + } + + return( LDAP_SUCCESS ); +} + +static int +valuetree_dupvalue_disallow( caddr_t d1, caddr_t d2 ) +{ + return( 1 ); +} + + +void +valuetree_free( Avlnode **valuetreep ) +{ + if ( valuetreep != NULL && *valuetreep != NULL ) + { + avl_free( *valuetreep, valuetree_node_free ); + *valuetreep = NULL; + } +} + + +static int +valuetree_node_free( caddr_t data ) +{ + if ( data!=NULL ) + { + valuetree_node *vaip = (valuetree_node *)data; + + slapi_value_free(&vaip->sval); + slapi_ch_free( (void **)&data ); + } + return( 0 ); +} + + +static int +valuetree_node_cmp( caddr_t d1, caddr_t d2 ) +{ + const struct berval *bv1, *bv2; + int rc; + + bv1 = slapi_value_get_berval(((valuetree_node *)d1)->sval); + bv2 = slapi_value_get_berval(((valuetree_node *)d2)->sval); + + if ( bv1->bv_len < bv2->bv_len ) { + rc = -1; + } else if ( bv1->bv_len > bv2->bv_len ) { + rc = 1; + } else { + rc = memcmp( bv1->bv_val, bv2->bv_val, bv1->bv_len ); + } + + return( rc ); +} + +/* <=========================== Value Set =======================> */ + +/* + * JCM: All of these valueset functions are just forwarded to the + * JCM: valuearray functions... waste of time. Inline them! + */ + +Slapi_ValueSet * +slapi_valueset_new() +{ + Slapi_ValueSet *vs = (Slapi_ValueSet *)slapi_ch_calloc(1,sizeof(Slapi_ValueSet)); + + if(vs) + slapi_valueset_init(vs); + + return vs; +} + +void +slapi_valueset_init(Slapi_ValueSet *vs) +{ + if(vs!=NULL) + { + vs->va= NULL; + } +} + +void +slapi_valueset_done(Slapi_ValueSet *vs) +{ + if(vs!=NULL) + { + if(vs->va!=NULL) + { + valuearray_free(&vs->va); + vs->va= NULL; + } + } +} + +void +slapi_valueset_free(Slapi_ValueSet *vs) +{ + if(vs!=NULL) + { + slapi_valueset_done(vs); + slapi_ch_free((void **)&vs); + } +} + +void +slapi_valueset_set_from_smod(Slapi_ValueSet *vs, Slapi_Mod *smod) +{ + Slapi_Value **va= NULL; + valuearray_init_bervalarray(slapi_mod_get_ldapmod_byref(smod)->mod_bvalues, &va); + valueset_set_valuearray_passin(vs, va); +} + +void +valueset_set_valuearray_byval(Slapi_ValueSet *vs, Slapi_Value **addvals) +{ + slapi_valueset_init(vs); + valueset_add_valuearray(vs,addvals); +} + +void +valueset_set_valuearray_passin(Slapi_ValueSet *vs, Slapi_Value **addvals) +{ + slapi_valueset_init(vs); + vs->va= addvals; +} + +void +slapi_valueset_set_valueset(Slapi_ValueSet *vs1, const Slapi_ValueSet *vs2) +{ + slapi_valueset_init(vs1); + valueset_add_valueset(vs1,vs2); +} + +int +slapi_valueset_first_value( Slapi_ValueSet *vs, Slapi_Value **v ) +{ + return valuearray_first_value(vs->va,v); +} + +int +slapi_valueset_next_value( Slapi_ValueSet *vs, int index, Slapi_Value **v) +{ + return valuearray_next_value(vs->va,index,v); +} + +int +slapi_valueset_count( const Slapi_ValueSet *vs) +{ + int r=0; + if (NULL != vs) + { + if(!valuearray_isempty(vs->va)) + { + r= valuearray_count(vs->va); + } + } + return r; +} + +int +valueset_isempty( const Slapi_ValueSet *vs) +{ + return valuearray_isempty(vs->va); +} + + +Slapi_Value * +slapi_valueset_find(const Slapi_Attr *a, const Slapi_ValueSet *vs, const Slapi_Value *v) +{ + Slapi_Value *r= NULL; + if(!valuearray_isempty(vs->va)) + { + int i= valuearray_find(a,vs->va,v); + if(i!=-1) + { + r= vs->va[i]; + } + } + return r; +} + +/* + * The value is found in the set, removed and returned. + * The caller is responsible for freeing the value. + */ +Slapi_Value * +valueset_remove_value(const Slapi_Attr *a, Slapi_ValueSet *vs, const Slapi_Value *v) +{ + Slapi_Value *r= NULL; + if(!valuearray_isempty(vs->va)) + { + r= valuearray_remove_value(a, vs->va, v); + } + return r; +} + +/* + * Remove any values older than the CSN. + */ +int +valueset_purge(Slapi_ValueSet *vs, const CSN *csn) +{ + int r= 0; + if(!valuearray_isempty(vs->va)) + { + r= valuearray_purge(&vs->va, csn); + } + return r; +} + +Slapi_Value ** +valueset_get_valuearray(const Slapi_ValueSet *vs) +{ + return (Slapi_Value**)vs->va; +} + +size_t +valueset_size(const Slapi_ValueSet *vs) +{ + size_t s= 0; + if(!valuearray_isempty(vs->va)) + { + s= valuearray_size(vs->va); + } + return s; +} + +/* + * The value array is passed in by value. + */ +void +valueset_add_valuearray(Slapi_ValueSet *vs, Slapi_Value **addvals) +{ + if(!valuearray_isempty(addvals)) + { + valuearray_add_valuearray(&vs->va, addvals, 0); + } +} + +void +valueset_add_valuearray_ext(Slapi_ValueSet *vs, Slapi_Value **addvals, PRUint32 flags) +{ + if(!valuearray_isempty(addvals)) + { + valuearray_add_valuearray(&vs->va, addvals, flags); + } +} + +/* + * The value is passed in by value. + */ +void +slapi_valueset_add_value(Slapi_ValueSet *vs, const Slapi_Value *addval) +{ + valuearray_add_value(&vs->va,addval); +} + +void +slapi_valueset_add_value_ext(Slapi_ValueSet *vs, Slapi_Value *addval, unsigned long flags) +{ + Slapi_Value *oneval[2]; + oneval[0]= (Slapi_Value*)addval; + oneval[1]= NULL; + valuearray_add_valuearray(&vs->va, oneval, flags); +} + +/* + * The string is passed in by value. + */ +void +valueset_add_string(Slapi_ValueSet *vs, const char *s, CSNType t, const CSN *csn) +{ + Slapi_Value v; + value_init(&v,NULL,t,csn); + slapi_value_set_string(&v,s); + valuearray_add_value(&vs->va,&v); + value_done(&v); +} + +/* + * The value set is passed in by value. + */ +void +valueset_add_valueset(Slapi_ValueSet *vs1, const Slapi_ValueSet *vs2) +{ + if (vs1 && vs2) + valueset_add_valuearray(vs1, vs2->va); +} + +void +valueset_remove_string(const Slapi_Attr *a, Slapi_ValueSet *vs, const char *s) +{ + Slapi_Value v; + value_init(&v,NULL,CSN_TYPE_NONE,NULL); + slapi_value_set_string(&v,s); + valuearray_remove_value(a,vs->va,&v); + value_done(&v); +} + +void +valueset_update_csn(Slapi_ValueSet *vs, CSNType t, const CSN *csn) +{ + if(!valuearray_isempty(vs->va)) + { + valuearray_update_csn(vs->va,t,csn); + } +} + +/* + * If we are adding or deleting SLAPD_MODUTIL_TREE_THRESHHOLD or more + * entries, we use an AVL tree to speed up searching for duplicates or + * values we are trying to delete. This threshhold is somewhat arbitrary; + * we should really take some measurements to determine an optimal number. + */ +#define SLAPD_MODUTIL_TREE_THRESHHOLD 5 +/* + * Remove an array of values from a value set. + * The removed values are passed back in an array. + * + * Returns + * LDAP_SUCCESS - OK. + * LDAP_NO_SUCH_ATTRIBUTE - A value to be deleted was not in the value set. + * LDAP_OPERATIONS_ERROR - Something very bad happened. + */ +int +valueset_remove_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value **valuestodelete, int flags, Slapi_Value ***va_out) +{ + int rc= LDAP_SUCCESS; + if(!valuearray_isempty(vs->va)) + { + int numberofvaluestodelete= valuearray_count(valuestodelete); + struct valuearrayfast vaf_out; + if ( va_out ) + { + valuearrayfast_init(&vaf_out,*va_out); + } + + /* + * determine whether we should use an AVL tree of values or not + */ + if ( numberofvaluestodelete >= SLAPD_MODUTIL_TREE_THRESHHOLD) + { + /* + * Several values to delete: first build an AVL tree that + * holds all of the existing values and use that to find + * the values we want to delete. + */ + Avlnode *vtree = NULL; + int numberofexistingvalues= slapi_valueset_count(vs); + rc= valuetree_add_valuearray( a->a_type, a->a_plugin, vs->va, &vtree, NULL ); + if ( rc!=LDAP_SUCCESS ) + { + /* + * failed while constructing AVL tree of existing + * values... something bad happened. + */ + rc= LDAP_OPERATIONS_ERROR; + } + else + { + int i; + /* + * find and mark all the values that are to be deleted + */ + for ( i = 0; rc == LDAP_SUCCESS && valuestodelete[i] != NULL; ++i ) + { + int index= 0; + rc = valuetree_find( a, valuestodelete[i], vtree, &index ); + if(rc==LDAP_SUCCESS) + { + if(vs->va[index]!=NULL) + { + /* Move the value to be removed to the out array */ + if ( va_out ) + { + if (vs->va[index]->v_csnset && (flags & SLAPI_VALUE_FLAG_PRESERVECSNSET)) + { + valuestodelete[i]->v_csnset = csnset_dup (vs->va[index]->v_csnset); + } + valuearrayfast_add_value_passin(&vaf_out,vs->va[index]); + vs->va[index] = NULL; + } + else + { + if (flags & SLAPI_VALUE_FLAG_PRESERVECSNSET) + { + valuestodelete[i]->v_csnset = vs->va[index]->v_csnset; + vs->va[index]->v_csnset = NULL; + } + slapi_value_free ( & vs->va[index] ); + } + } + else + { + /* We already deleted this value... */ + if((flags & SLAPI_VALUE_FLAG_IGNOREERROR) == 0) + { + /* ...that's an error. */ + rc= LDAP_NO_SUCH_ATTRIBUTE; + } + } + } + else + { + /* Couldn't find the value to be deleted */ + if(rc==LDAP_NO_SUCH_ATTRIBUTE && (flags & SLAPI_VALUE_FLAG_IGNOREERROR )) + { + rc= LDAP_SUCCESS; + } + } + } + valuetree_free( &vtree ); + + if ( rc != LDAP_SUCCESS ) + { + LDAPDebug( LDAP_DEBUG_ANY,"could not find value %d for attr %s (%s)\n", i-1, a->a_type, ldap_err2string( rc )); + } + else + { + /* Shunt up all the remaining values to cover the deleted ones. */ + valuearray_compress(vs->va,numberofexistingvalues); + } + } + } + else + { + /* We don't have to delete very many values, so we use brute force. */ + int i; + for ( i = 0; rc==LDAP_SUCCESS && valuestodelete[i] != NULL; ++i ) + { + Slapi_Value *found= valueset_remove_value(a, vs, valuestodelete[i]); + if(found!=NULL) + { + if ( va_out ) + { + if (found->v_csnset && (flags & SLAPI_VALUE_FLAG_PRESERVECSNSET)) + { + valuestodelete[i]->v_csnset = csnset_dup (found->v_csnset); + } + valuearrayfast_add_value_passin(&vaf_out,found); + } + else + { + if (flags & SLAPI_VALUE_FLAG_PRESERVECSNSET) + { + valuestodelete[i]->v_csnset = found->v_csnset; + found->v_csnset = NULL; + } + slapi_value_free ( & found ); + } + } + else + { + if((flags & SLAPI_VALUE_FLAG_IGNOREERROR) == 0) + { + LDAPDebug( LDAP_DEBUG_ARGS,"could not find value %d for attr %s\n", i-1, a->a_type, 0 ); + rc= LDAP_NO_SUCH_ATTRIBUTE; + } + } + } + } + if ( va_out ) + { + *va_out= vaf_out.va; + if(rc!=LDAP_SUCCESS) + { + valuearray_free(va_out); + } + } + } + return rc; +} + +/* + * Check if the set of values in the valueset and the valuearray intersect. + * + * Returns + * LDAP_SUCCESS - No intersection. + * LDAP_NO_SUCH_ATTRIBUTE - There is an intersection. + * LDAP_OPERATIONS_ERROR - There are duplicate values in the value set already. + */ +int +valueset_intersectswith_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value **values, int *duplicate_index ) +{ + int rc= LDAP_SUCCESS; + + if ( duplicate_index ) { + *duplicate_index = -1; + } + + if(valuearray_isempty(vs->va)) + { + /* No intersection */ + } + else + { + int numberofvalues= valuearray_count(values); + /* + * determine whether we should use an AVL tree of values or not + */ + if (numberofvalues==0) + { + /* No intersection */ + } + else if ( numberofvalues >= SLAPD_MODUTIL_TREE_THRESHHOLD) + { + /* + * Several values to add: use an AVL tree to detect duplicates. + */ + Avlnode *vtree = NULL; + rc= valuetree_add_valuearray( a->a_type, a->a_plugin, vs->va, &vtree, duplicate_index ); + if(rc==LDAP_OPERATIONS_ERROR) + { + /* There were already duplicate values in the value set */ + } + else + { + rc= valuetree_add_valuearray( a->a_type, a->a_plugin, values, &vtree, duplicate_index ); + /* + * Returns LDAP_OPERATIONS_ERROR if something very bad happens. + * Or LDAP_TYPE_OR_VALUE_EXISTS if a value already exists. + */ + } + valuetree_free( &vtree ); + } + else + { + /* + * Small number of values to add: don't bother constructing + * an AVL tree, etc. since it probably isn't worth the time. + * + * JCM - This is actually quite slow because the comparison function is looked up many times. + */ + int i; + for ( i = 0; rc == LDAP_SUCCESS && values[i] != NULL; ++i ) + { + if(valuearray_find(a, vs->va, values[i])!=-1) + { + rc = LDAP_TYPE_OR_VALUE_EXISTS; + *duplicate_index = i; + break; + } + } + } + } + return rc; +} + +Slapi_ValueSet * +valueset_dup(const Slapi_ValueSet *dupee) +{ + Slapi_ValueSet *duped= (Slapi_ValueSet *)slapi_ch_calloc(1,sizeof(Slapi_ValueSet)); + if (NULL!=duped) + { + valueset_add_valuearray( duped, dupee->va ); + } + return duped; +} + +/* quickly throw away any old contents of this valueset, and stick in the + * new ones. + */ +void +valueset_replace(Slapi_ValueSet *vs, Slapi_Value **vals) +{ + if(!valuearray_isempty(vs->va)) + { + slapi_valueset_done(vs); + } + vs->va = vals; +} + +/* + * Search the value set for each value to be update, + * and update the value with the CSN provided. + * Updated values are moved from the valuestoupdate + * array to the valueupdated array. + */ +void +valueset_update_csn_for_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value **valuestoupdate, CSNType t, const CSN *csn, Slapi_Value ***valuesupdated) +{ + if(!valuearray_isempty(valuestoupdate) && + !valuearray_isempty(vs->va)) + { + /* + * determine whether we should use an AVL tree of values or not + */ + struct valuearrayfast vaf_valuesupdated; + int numberofvaluestoupdate= valuearray_count(valuestoupdate); + valuearrayfast_init(&vaf_valuesupdated,*valuesupdated); + if (numberofvaluestoupdate>=SLAPD_MODUTIL_TREE_THRESHHOLD) + { + int i; + Avlnode *vtree = NULL; + int rc= valuetree_add_valuearray( a->a_type, a->a_plugin, vs->va, &vtree, NULL ); + PR_ASSERT(rc==LDAP_SUCCESS); + for (i=0;valuestoupdate[i]!=NULL;++i) + { + int index= 0; + rc = valuetree_find( a, valuestoupdate[i], vtree, &index ); + if(rc==LDAP_SUCCESS) + { + value_update_csn(vs->va[index],t,csn); + valuearrayfast_add_value_passin(&vaf_valuesupdated,valuestoupdate[i]); + valuestoupdate[i] = NULL; + } + } + valuetree_free(&vtree); + } + else + { + int i; + for (i=0;valuestoupdate[i]!=NULL;++i) + { + int index= valuearray_find(a, vs->va, valuestoupdate[i]); + if(index!=-1) + { + value_update_csn(vs->va[index],t,csn); + valuearrayfast_add_value_passin(&vaf_valuesupdated,valuestoupdate[i]); + valuestoupdate[i]= NULL; + } + } + } + valuearray_compress(valuestoupdate,numberofvaluestoupdate); + *valuesupdated= vaf_valuesupdated.va; + } +} |