[Bug 164834] modify/replace allows multiple same valued attributes in an entry

1) Eliminated SLAPD_MODUTIL_TREE_THREASHHOLD from attr.c as well as valueset.c.
With this change, if an attribute has more than 1 value to add/replace/delete,
it creates an AVL tree to check the duplicates.
2) Replace was not checking the duplicated value at all.  Added a code to put
the attribute values into the AVL tree as being done for add and delete.

5 files changed, 113 insertions, 94 deletions

diff --git a/ldap/servers/slapd/attr.c b/ldap/servers/slapd/attr.c
index 9f8c9f96..053cfa6d 100644
--- a/ldap/servers/slapd/attr.c
+++ b/ldap/servers/slapd/attr.c
@@ -710,19 +710,12 @@ attr_add_deleted_value(Slapi_Attr *a, const Slapi_Value *v)
 }
 
 /*
- * 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
-
-/*
- * Add a value array to an attribute. If SLAPD_MODUTIL_TREE_THRESHHOLD or
- * more values are being added, we build an AVL tree of any existing
+ * Add a value array to an attribute. 
+ * If more than one values are being added, we build an AVL tree of any existing
  * values and then update that in parallel with the existing values.  This
- * is done so that we do not waste a lot of CPU time searching for duplicate
- * values.  The AVL tree is created and destroyed all within this function.
+ * AVL tree is used to detect the duplicates not only between the existing 
+ * values and to-be-added values but also among the to-be-added values.
+ * The AVL tree is created and destroyed all within this function.
  *
  * Returns
  * LDAP_SUCCESS - OK
@@ -733,28 +726,28 @@ int
 attr_add_valuearray(Slapi_Attr *a, Slapi_Value **vals, const char *dn)
 {
     int i = 0;
-	int duplicate_index = -1;
-	int was_present_null = 0;
-	int rc = LDAP_SUCCESS;
+    int numofvals = 0;
+    int duplicate_index = -1;
+    int was_present_null = 0;
+    int rc = LDAP_SUCCESS;
 
     if (valuearray_isempty(vals)) {
         /*
          * No values to add (unexpected but acceptable).
          */
         return rc;
-	}
+    }
 
     /*
      * determine whether we should use an AVL tree of values or not
      */
-    while ( i < SLAPD_MODUTIL_TREE_THRESHHOLD - 1 && vals[i] != NULL ) {
-		i++;
-	}
+    for ( i = 0; vals[i] != NULL; i++ ) ;
+    numofvals = i;
 
     /*
      * detect duplicate values
      */
-    if ( i >= SLAPD_MODUTIL_TREE_THRESHHOLD - 1 ) {
+    if ( numofvals > 1 ) {
         /*
          * Several values to add: use an AVL tree to detect duplicates.
          */
@@ -763,82 +756,85 @@ attr_add_valuearray(Slapi_Attr *a, Slapi_Value **vals, const char *dn)
                    "detect duplicate values\n", 0, 0, 0 );
 
         if (valueset_isempty(&a->a_present_values)) {
-			/* if the attribute contains no values yet, just check the
-			 * input vals array for duplicates
-			 */
+            /* if the attribute contains no values yet, just check the
+             * input vals array for duplicates
+             */
             Avlnode *vtree = NULL;
             rc= valuetree_add_valuearray(a->a_type, a->a_plugin, vals, &vtree, &duplicate_index);
             valuetree_free(&vtree);
-			was_present_null = 1;
+            was_present_null = 1;
         } else {
-			/* the attr and vals both contain values, check intersection */
+            /* the attr and vals both contain values, check intersection */
             rc= valueset_intersectswith_valuearray(&a->a_present_values, a, vals, &duplicate_index);
         }
 
     } else if ( !valueset_isempty(&a->a_present_values) ) {
         /*
-         * Small number of values to add: don't bother constructing
+         * One or no value to add: don't bother constructing
          * an AVL tree, etc. since it probably isn't worth the time.
          */
         for ( i = 0; vals[i] != NULL; ++i ) {
             if ( slapi_attr_value_find( a, slapi_value_get_berval(vals[i]) ) == 0 ) {
-				duplicate_index = i;
-	            rc = LDAP_TYPE_OR_VALUE_EXISTS;
-				break;
+                duplicate_index = i;
+                rc = LDAP_TYPE_OR_VALUE_EXISTS;
+                break;
             }
-    	}
+        }
     }
 
-	/*
-	 * add values if no duplicates detected
-	 */
+    /*
+     * add values if no duplicates detected
+     */
     if(rc==LDAP_SUCCESS) {
-		valueset_add_valuearray( &a->a_present_values, vals );
-	}
+        valueset_add_valuearray( &a->a_present_values, vals );
+    }
 
-	/* In the case of duplicate value, rc == LDAP_TYPE_OR_VALUE_EXISTS or
-	 * LDAP_OPERATIONS_ERROR
-	 */
-	else if ( duplicate_index >= 0 ) {
-		char avdbuf[BUFSIZ];
-		char bvvalcopy[BUFSIZ];
-		char *duplicate_string = "null or non-ASCII";
-
-		i = 0;
-		while ( (unsigned int)i < vals[duplicate_index]->bv.bv_len &&
-				i < BUFSIZ - 1 &&
-				vals[duplicate_index]->bv.bv_val[i] &&
-				isascii ( vals[duplicate_index]->bv.bv_val[i] )) {
-			i++;
-		}
+    /* In the case of duplicate value, rc == LDAP_TYPE_OR_VALUE_EXISTS or
+     * LDAP_OPERATIONS_ERROR
+     */
+    else if ( duplicate_index >= 0 ) {
+        char avdbuf[BUFSIZ];
+        char bvvalcopy[BUFSIZ];
+        char *duplicate_string = "null or non-ASCII";
+
+        i = 0;
+        while ( (unsigned int)i < vals[duplicate_index]->bv.bv_len &&
+                i < BUFSIZ - 1 &&
+                vals[duplicate_index]->bv.bv_val[i] &&
+                isascii ( vals[duplicate_index]->bv.bv_val[i] )) {
+            i++;
+        }
 
-		if ( i ) {
-			if ( vals[duplicate_index]->bv.bv_val[i] == 0 ) {
-				duplicate_string = vals[duplicate_index]->bv.bv_val;
-			}
-			else {
-				strncpy ( &bvvalcopy[0], vals[duplicate_index]->bv.bv_val, i );
-				bvvalcopy[i] = '\0';
-				duplicate_string = bvvalcopy;
-			}
-		}
+        if ( i ) {
+            if ( vals[duplicate_index]->bv.bv_val[i] == 0 ) {
+                duplicate_string = vals[duplicate_index]->bv.bv_val;
+            }
+            else {
+                strncpy ( &bvvalcopy[0], vals[duplicate_index]->bv.bv_val, i );
+                bvvalcopy[i] = '\0';
+                duplicate_string = bvvalcopy;
+            }
+        }
 
-		slapi_log_error( SLAPI_LOG_FATAL, NULL, "add value \"%s\" to "
-					"attribute type \"%s\" in entry \"%s\" failed: %s\n", 
-					duplicate_string,
-					a->a_type,
-					dn ? escape_string(dn,avdbuf) : "<null>", 
-					(was_present_null ? "duplicate new value" : "value exists"));
-	}
+        slapi_log_error( SLAPI_LOG_FATAL, NULL, "add value \"%s\" to "
+                "attribute type \"%s\" in entry \"%s\" failed: %s\n", 
+                duplicate_string,
+                a->a_type,
+                dn ? escape_string(dn,avdbuf) : "<null>", 
+                (was_present_null ? "duplicate new value" : "value exists"));
+    }
     return( rc );
 }
 
 /* quickly toss an attribute's values and replace them with new ones
  * (used by attrlist_replace_fast)
+ * Returns
+ * LDAP_SUCCESS - OK
+ * LDAP_OPERATIONS_ERROR - Existing duplicates in attribute.
  */
-void attr_replace(Slapi_Attr *a, Slapi_Value **vals)
+int attr_replace(Slapi_Attr *a, Slapi_Value **vals)
 {
-    valueset_replace(&a->a_present_values, vals);
+    return valueset_replace(a, &a->a_present_values, vals);
 }
 
 int 
diff --git a/ldap/servers/slapd/attrlist.c b/ldap/servers/slapd/attrlist.c
index 8fd89fcb..eacdb3d4 100644
--- a/ldap/servers/slapd/attrlist.c
+++ b/ldap/servers/slapd/attrlist.c
@@ -268,18 +268,24 @@ attrlist_delete(Slapi_Attr **attrs, const char *type)
 
 /*
  * attrlist_replace - replace the attribute value(s) with this value(s)
+ *
+ * Returns
+ * LDAP_SUCCESS - OK (including the attr not found)
+ * LDAP_OPERATIONS_ERROR - Existing duplicates in attribute.
  */
-void attrlist_replace(Slapi_Attr **alist, const char *type, struct berval **vals)
+int attrlist_replace(Slapi_Attr **alist, const char *type, struct berval **vals)
 {
     Slapi_Attr **a = NULL;
     Slapi_Value **values = NULL;
+    int rc = LDAP_SUCCESS;
 
     if (vals == NULL || vals[0] == NULL) {
         (void)attrlist_delete(alist, type);
     } else {
         attrlist_find_or_create(alist, type, &a);
         valuearray_init_bervalarray(vals, &values);
-        attr_replace(*a, values);
+        rc = attr_replace(*a, values);
     }
+    return rc;
 }
 
diff --git a/ldap/servers/slapd/entry.c b/ldap/servers/slapd/entry.c
index bf89542c..cd5010b6 100644
--- a/ldap/servers/slapd/entry.c
+++ b/ldap/servers/slapd/entry.c
@@ -2792,8 +2792,7 @@ entry_replace_values(
     struct berval	**vals
 )
 {
-        attrlist_replace( &e->e_attrs, type, vals );
-        return 0;
+    return attrlist_replace( &e->e_attrs, type, vals );
 }
 
 int
diff --git a/ldap/servers/slapd/proto-slap.h b/ldap/servers/slapd/proto-slap.h
index 5f37b920..a40dd3cd 100644
--- a/ldap/servers/slapd/proto-slap.h
+++ b/ldap/servers/slapd/proto-slap.h
@@ -61,7 +61,7 @@ void do_add( Slapi_PBlock *pb );
  */
 void attr_done(Slapi_Attr *a);
 int attr_add_valuearray(Slapi_Attr *a, Slapi_Value **vals, const char *dn);
-void attr_replace(Slapi_Attr *a, Slapi_Value **vals);
+int attr_replace(Slapi_Attr *a, Slapi_Value **vals);
 int attr_check_onoff ( const char *attr_name, char *value, long minval, long maxval, char *errorbuf );
 int attr_check_minmax ( const char *attr_name, char *value, long minval, long maxval, char *errorbuf );
 
@@ -80,7 +80,7 @@ Slapi_Attr *attrlist_remove(Slapi_Attr **attrs, const char *type);
 void attrlist_add(Slapi_Attr **attrs, Slapi_Attr *a);
 int attrlist_count_subtypes(Slapi_Attr *a, const char *type);
 Slapi_Attr *attrlist_find_ex( Slapi_Attr *a, const char *type, int *type_name_disposition, char** actual_type_name, void **hint );
-void attrlist_replace(Slapi_Attr **alist, const char *type, struct berval **vals);
+int attrlist_replace(Slapi_Attr **alist, const char *type, struct berval **vals);
 
 /*
  * attrsyntax.c
@@ -158,7 +158,7 @@ void valueset_add_valueset(Slapi_ValueSet *vs1, const Slapi_ValueSet *vs2);
 int valueset_intersectswith_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value **values, int *duplicate_index);
 Slapi_ValueSet *valueset_dup(const Slapi_ValueSet *dupee);
 void valueset_remove_string(const Slapi_Attr *a, Slapi_ValueSet *vs, const char *s);
-void valueset_replace(Slapi_ValueSet *vs, Slapi_Value **vals);
+int valueset_replace(Slapi_Attr *a, Slapi_ValueSet *vs, Slapi_Value **vals);
 void valueset_update_csn_for_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value **valuestoupdate, CSNType t, const CSN *csn, Slapi_Value ***valuesupdated);
 void valueset_set_valuearray_byval(Slapi_ValueSet *vs, Slapi_Value **addvals);
 void valueset_set_valuearray_passin(Slapi_ValueSet *vs, Slapi_Value **addvals);
diff --git a/ldap/servers/slapd/valueset.c b/ldap/servers/slapd/valueset.c
index a65cbdd2..653591dc 100644
--- a/ldap/servers/slapd/valueset.c
+++ b/ldap/servers/slapd/valueset.c
@@ -1015,13 +1015,6 @@ valueset_update_csn(Slapi_ValueSet *vs, CSNType t, const CSN *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.
  *
@@ -1044,9 +1037,10 @@ valueset_remove_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value
 		}
 
 		/*
-		 * determine whether we should use an AVL tree of values or not
+		 * If there are more then one values, build an AVL tree to check
+		 * the duplicated values.
 		 */
-		if ( numberofvaluestodelete >= SLAPD_MODUTIL_TREE_THRESHHOLD)
+		if ( numberofvaluestodelete > 1 )
 		{
 			/*
 			 * Several values to delete: first build an AVL tree that
@@ -1132,7 +1126,7 @@ valueset_remove_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slapi_Value
 		}
 		else
 		{
-			/* We don't have to delete very many values, so we use brute force. */
+			/* We delete one or no value, so we use brute force. */
 			int i;
 			for ( i = 0; rc==LDAP_SUCCESS && valuestodelete[i] != NULL; ++i )
 			{
@@ -1210,7 +1204,7 @@ valueset_intersectswith_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slap
 		{
 			/* No intersection */
 		}
-		else if ( numberofvalues >= SLAPD_MODUTIL_TREE_THRESHHOLD)
+		else if ( numberofvalues > 1 )
 		{
 			/*
 			 * Several values to add: use an AVL tree to detect duplicates.
@@ -1234,7 +1228,7 @@ valueset_intersectswith_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slap
 		else
 		{
 			/*
-			 * Small number of values to add: don't bother constructing
+			 * One value 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.
@@ -1267,15 +1261,39 @@ valueset_dup(const Slapi_ValueSet *dupee)
 
 /* quickly throw away any old contents of this valueset, and stick in the
  * new ones.
+ *
+ * return value: LDAP_SUCCESS - OK
+ *             : LDAP_OPERATIONS_ERROR - duplicated values given
  */
-void 
-valueset_replace(Slapi_ValueSet *vs, Slapi_Value **vals)
+int
+valueset_replace(Slapi_Attr *a, Slapi_ValueSet *vs, Slapi_Value **valstoreplace)
 {
+    int rc = LDAP_SUCCESS;
+    int numberofvalstoreplace= valuearray_count(valstoreplace);
     if(!valuearray_isempty(vs->va))
-	{
+    {
         slapi_valueset_done(vs);
-	}
-    vs->va = vals;
+    }
+    /* verify the given values are not duplicated.
+       if replacing with one value, no need to check.  just replace it.
+     */
+    if (numberofvalstoreplace > 1)
+    {
+        Avlnode *vtree = NULL;
+        rc = valuetree_add_valuearray( a->a_type, a->a_plugin, valstoreplace, &vtree, NULL );
+        valuetree_free(&vtree);
+        if ( LDAP_SUCCESS != rc )
+        {
+            /* There were already duplicate values in the value set */
+            rc = LDAP_OPERATIONS_ERROR;
+        }
+    }
+
+    if ( rc == LDAP_SUCCESS )
+    {
+        vs->va = valstoreplace;
+    }
+    return rc;
 }
 
 /*
@@ -1296,7 +1314,7 @@ valueset_update_csn_for_valuearray(Slapi_ValueSet *vs, const Slapi_Attr *a, Slap
 		struct valuearrayfast vaf_valuesupdated;
 		int numberofvaluestoupdate= valuearray_count(valuestoupdate);
 		valuearrayfast_init(&vaf_valuesupdated,*valuesupdated);
-		if (numberofvaluestoupdate>=SLAPD_MODUTIL_TREE_THRESHHOLD)
+		if (numberofvaluestoupdate > 1) /* multiple values to update */
 		{
 			int i;
 			Avlnode	*vtree = NULL;