2 * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
3 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
6 * Copyright (c) 1995 Regents of the University of Michigan.
9 * Redistribution and use in source and binary forms are permitted
10 * provided that this notice is preserved and that due credit is given
11 * to the University of Michigan at Ann Arbor. The name of the University
12 * may not be used to endorse or promote products derived from this
13 * software without specific prior written permission. This software
14 * is provided ``as is'' without express or implied warranty.
22 modify_check_duplicates(
23 AttributeDescription *ad,
29 char *textbuf, size_t textlen )
31 int i, j, numvals = 0, nummods,
32 rc = LDAP_SUCCESS, matched;
34 /* needs major reworking */
36 BerVarray nvals = NULL, nmods = NULL;
39 * FIXME: better do the following
41 * - count the existing values
42 * - count the new values
44 * - if the existing values are less than the new ones {
45 * - normalize all the existing values
46 * - for each new value {
48 * - check with existing
49 * - cross-check with already normalized new vals
52 * - for each new value {
54 * - cross-check with already normalized new vals
56 * - for each existing value {
58 * - check with already normalized new values
62 * The first case is good when adding a lot of new values,
63 * and significantly at first import of values (e.g. adding
64 * a new group); the latter case seems to be quite important
65 * as well, because it is likely to be the most frequently
66 * used when administering the entry. The current
67 * implementation will always normalize all the existing
68 * values before checking. If there's no duplicate, the
69 * performances should not change; they will in case of error.
72 for ( nummods = 0; mods[ nummods ].bv_val != NULL; nummods++ )
73 /* count new values */ ;
76 for ( numvals = 0; vals[ numvals ].bv_val != NULL; numvals++ )
77 /* count existing values */ ;
79 if ( numvals < nummods ) {
80 nvals = SLAP_CALLOC( numvals + 1, sizeof( struct berval ) );
83 LDAP_LOG( OPERATION, ERR,
84 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
86 Debug( LDAP_DEBUG_ANY,
87 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
92 /* normalize the existing values first */
93 for ( j = 0; vals[ j ].bv_val != NULL; j++ ) {
94 rc = value_normalize( ad, SLAP_MR_EQUALITY,
95 &vals[ j ], &nvals[ j ], text );
97 /* existing attribute values must normalize */
98 assert( rc == LDAP_SUCCESS );
100 if ( rc != LDAP_SUCCESS ) {
101 nvals[ j ].bv_val = NULL;
105 nvals[ j ].bv_val = NULL;
110 * If the existing values are less than the new values,
111 * it is more convenient to normalize all the existing
112 * values and test each new value against them first,
113 * then to other already normalized values
115 nmods = SLAP_CALLOC( nummods + 1, sizeof( struct berval ) );
116 if ( nmods == NULL ) {
118 LDAP_LOG( OPERATION, ERR,
119 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
121 Debug( LDAP_DEBUG_ANY,
122 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
127 for ( i=0; mods[i].bv_val != NULL; i++ ) {
128 rc = value_normalize( ad, SLAP_MR_EQUALITY,
129 &mods[i], &nmods[i], text );
131 if ( rc != LDAP_SUCCESS ) {
132 nmods[i].bv_val = NULL;
136 if ( numvals > 0 && numvals < nummods ) {
137 for ( matched=0, j=0; nvals[j].bv_val; j++ ) {
140 rc = (*mr->smr_match)( &match,
141 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
142 ad->ad_type->sat_syntax,
143 mr, &nmods[ i ], &nvals[ j ] );
145 if ( rc != LDAP_SUCCESS ) {
146 nmods[ i + 1 ].bv_val = NULL;
148 snprintf( textbuf, textlen,
149 "%s: matching rule failed",
150 ad->ad_cname.bv_val );
160 snprintf( textbuf, textlen,
161 "%s: value #%d provided more than once",
162 ad->ad_cname.bv_val, i );
163 rc = LDAP_TYPE_OR_VALUE_EXISTS;
164 nmods[ i + 1 ].bv_val = NULL;
169 if ( permissive && matched == j ) {
170 nmods[ i + 1 ].bv_val = NULL;
171 rc = LDAP_TYPE_OR_VALUE_EXISTS;
176 for ( matched = 0, j = 0; j < i; j++ ) {
179 rc = (*mr->smr_match)( &match,
180 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
181 ad->ad_type->sat_syntax,
182 mr, &nmods[ i ], &nmods[ j ] );
183 if ( rc != LDAP_SUCCESS ) {
184 nmods[ i + 1 ].bv_val = NULL;
186 snprintf( textbuf, textlen,
187 "%s: matching rule failed",
188 ad->ad_cname.bv_val );
198 snprintf( textbuf, textlen,
199 "%s: value #%d provided more than once",
200 ad->ad_cname.bv_val, j );
201 rc = LDAP_TYPE_OR_VALUE_EXISTS;
202 nmods[ i + 1 ].bv_val = NULL;
207 if ( permissive && matched == j ) {
208 nmods[ i + 1 ].bv_val = NULL;
209 rc = LDAP_TYPE_OR_VALUE_EXISTS;
213 nmods[ i ].bv_val = NULL;
216 * if new values are more than existing values, it is more
217 * convenient to normalize and check all new values first,
218 * then check each new value against existing values, which
219 * can be normalized in place
222 if ( numvals >= nummods ) {
223 for ( j = 0; vals[ j ].bv_val; j++ ) {
224 struct berval asserted;
226 rc = value_normalize( ad, SLAP_MR_EQUALITY,
227 &vals[ j ], &asserted, text );
229 if ( rc != LDAP_SUCCESS ) {
233 for ( matched = 0, i = 0; nmods[ i ].bv_val; i++ ) {
236 rc = (*mr->smr_match)( &match,
237 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
238 ad->ad_type->sat_syntax,
239 mr, &nmods[ i ], &asserted );
240 if ( rc != LDAP_SUCCESS ) {
242 snprintf( textbuf, textlen,
243 "%s: matching rule failed",
244 ad->ad_cname.bv_val );
254 snprintf( textbuf, textlen,
255 "%s: value #%d provided more than once",
256 ad->ad_cname.bv_val, j );
257 rc = LDAP_TYPE_OR_VALUE_EXISTS;
262 if ( permissive && matched == i ) {
263 rc = LDAP_TYPE_OR_VALUE_EXISTS;
271 ber_bvarray_free( nvals );
274 ber_bvarray_free( nmods );
287 char *textbuf, size_t textlen
293 MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
296 switch( mod->sm_op ) {
300 case LDAP_MOD_REPLACE:
308 a = attr_find( e->e_attrs, mod->sm_desc );
311 * With permissive set, as long as the attribute being added
312 * has the same value(s?) as the existing attribute, then the
313 * modify will succeed.
316 /* check if the values we're adding already exist */
317 if( mr == NULL || !mr->smr_match ) {
319 /* we should have no normalized values as there is no equality rule */
320 /* assert( mod->sm_nvalues[0].bv_val == NULL); */
324 /* do not allow add of additional attribute
325 if no equality rule exists */
327 snprintf( textbuf, textlen,
328 "modify/%s: %s: no equality matching rule",
329 op, mod->sm_desc->ad_cname.bv_val );
330 return LDAP_INAPPROPRIATE_MATCHING;
333 for ( i = 0; mod->sm_bvalues[i].bv_val != NULL; i++ ) {
334 /* test asserted values against existing values */
337 /* we should have no normalized values as there
338 is no equality rule */
339 assert( a->a_nvals == NULL);
341 for( matched = 0, j = 0; a->a_vals[j].bv_val != NULL; j++ ) {
342 if ( bvmatch( &mod->sm_bvalues[i], &a->a_vals[j] ) ) {
347 /* value exists already */
349 snprintf( textbuf, textlen,
350 "modify/%s: %s: value #%i already exists",
351 op, mod->sm_desc->ad_cname.bv_val, j );
352 return LDAP_TYPE_OR_VALUE_EXISTS;
355 if ( permissive && matched == j ) {
356 /* values already exist; do nothing */
361 /* test asserted values against themselves */
362 for( j = 0; j < i; j++ ) {
363 if ( bvmatch( &mod->sm_bvalues[i], &mod->sm_bvalues[j] ) ) {
364 /* value exists already */
366 snprintf( textbuf, textlen,
367 "modify/%s: %s: value #%i already exists",
368 op, mod->sm_desc->ad_cname.bv_val, j );
369 return LDAP_TYPE_OR_VALUE_EXISTS;
376 /* no normalization is done in this routine nor
377 * in the matching routines called by this routine.
378 * values are now normalized once on input to the
379 * server (whether from LDAP or from the underlying
381 * This should outperform the old code. No numbers
386 * The original code performs ( n ) normalizations
387 * and ( n * ( n - 1 ) / 2 ) matches, which hide
388 * the same number of normalizations. The new code
389 * performs the same number of normalizations ( n )
390 * and ( n * ( n - 1 ) / 2 ) mem compares, far less
391 * expensive than an entire match, if a match is
392 * equivalent to a normalization and a mem compare ...
394 * This is far more memory expensive than the previous,
395 * but it can heavily improve performances when big
396 * chunks of data are added (typical example is a group
397 * with thousands of DN-syntax members; on my system:
398 * for members of 5-RDN DNs,
400 members orig bvmatch (dirty) new
401 1000 0m38.456s 0m0.553s 0m0.608s
402 2000 2m33.341s 0m0.851s 0m1.003s
404 * Moreover, 100 groups with 10000 members each were
405 * added in 37m27.933s (an analogous LDIF file was
406 * loaded into Active Directory in 38m28.682s, BTW).
408 * Maybe we could switch to the new algorithm when
409 * the number of values overcomes a given threshold?
415 if ( mod->sm_bvalues[1].bv_val == 0 ) {
419 struct berval asserted;
420 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
421 &mod->sm_bvalues[ 0 ], &asserted, text );
422 if ( rc != LDAP_SUCCESS ) {
427 for ( matched = 0, i = 0; a->a_vals[ i ].bv_val; i++ ) {
431 if( mod->sm_nvalues ) {
432 rc = value_match( &match, mod->sm_desc, mr,
434 | SLAP_MR_VALUE_OF_ASSERTION_SYNTAX
435 | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH
436 | SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH,
442 rc = value_match( &match, mod->sm_desc, mr,
444 | SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
451 rc = value_match( &match, mod->sm_desc, mr,
452 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
458 if( rc == LDAP_SUCCESS && match == 0 ) {
464 free( asserted.bv_val );
467 snprintf( textbuf, textlen,
468 "modify/%s: %s: value #0 already exists",
469 op, mod->sm_desc->ad_cname.bv_val, 0 );
470 return LDAP_TYPE_OR_VALUE_EXISTS;
474 free( asserted.bv_val );
476 if ( permissive && matched == i ) {
477 /* values already exist; do nothing */
483 rc = modify_check_duplicates( mod->sm_desc, mr,
484 a ? a->a_vals : NULL, mod->sm_bvalues,
485 permissive, text, textbuf, textlen );
487 if ( permissive && rc == LDAP_TYPE_OR_VALUE_EXISTS ) {
491 if ( rc != LDAP_SUCCESS ) {
499 if( attr_merge( e, mod->sm_desc, mod->sm_values, mod->sm_nvalues ) != 0 )
501 if( attr_merge( e, mod->sm_desc, mod->sm_bvalues ) != 0 )
504 /* this should return result of attr_merge */
506 snprintf( textbuf, textlen,
507 "modify/%s: %s: merge error",
508 op, mod->sm_desc->ad_cname.bv_val );
516 modify_delete_values(
521 char *textbuf, size_t textlen
524 int i, j, k, rc = LDAP_SUCCESS;
526 MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
528 BerVarray nvals = NULL;
533 * If permissive is set, then the non-existence of an
534 * attribute is not treated as an error.
537 /* delete the entire attribute */
538 if ( mod->sm_bvalues == NULL ) {
539 rc = attr_delete( &e->e_attrs, mod->sm_desc );
543 } else if( rc != LDAP_SUCCESS ) {
545 snprintf( textbuf, textlen,
546 "modify/delete: %s: no such attribute",
547 mod->sm_desc->ad_cname.bv_val );
548 rc = LDAP_NO_SUCH_ATTRIBUTE;
553 if( mr == NULL || !mr->smr_match ) {
554 /* disallow specific attributes from being deleted if
557 snprintf( textbuf, textlen,
558 "modify/delete: %s: no equality matching rule",
559 mod->sm_desc->ad_cname.bv_val );
560 return LDAP_INAPPROPRIATE_MATCHING;
563 /* delete specific values - find the attribute first */
564 if ( (a = attr_find( e->e_attrs, mod->sm_desc )) == NULL ) {
569 snprintf( textbuf, textlen,
570 "modify/delete: %s: no such attribute",
571 mod->sm_desc->ad_cname.bv_val );
572 return LDAP_NO_SUCH_ATTRIBUTE;
576 /* find each value to delete */
577 for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ )
578 /* count existing values */ ;
580 nvals = (BerVarray)SLAP_CALLOC( j + 1, sizeof ( struct berval ) );
581 if( nvals == NULL ) {
583 LDAP_LOG( OPERATION, ERR,
584 "modify_delete_values: SLAP_CALLOC failed", 0, 0, 0 );
586 Debug( LDAP_DEBUG_ANY,
587 "modify_delete_values: SLAP_CALLOC failed", 0, 0, 0 );
592 /* normalize existing values */
593 for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ ) {
594 rc = value_normalize( a->a_desc, SLAP_MR_EQUALITY,
595 &a->a_vals[ j ], &nvals[ j ], text );
597 if ( rc != LDAP_SUCCESS ) {
598 nvals[ j ].bv_val = NULL;
604 for ( i = 0; mod->sm_values[i].bv_val != NULL; i++ ) {
607 struct berval asserted;
609 /* normalize the value to be deleted */
610 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
611 &mod->sm_bvalues[ i ], &asserted, text );
613 if( rc != LDAP_SUCCESS ) {
618 for ( j = 0; nvals[ j ].bv_val != NULL; j++ )
620 for ( j = 0; a->a_vals[j].bv_val != NULL; j++ )
626 if ( nvals[j].bv_val == &dummy ) {
632 if( mod->sm_nvalues ) {
633 assert( a->a_nvals );
634 rc = (*mr->smr_match)( &match,
635 SLAP_MR_VALUE_OF_ASSERTION_SYNTAX
636 | SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH
637 | SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH,
638 a->a_desc->ad_type->sat_syntax,
640 &mod->sm_nvalues[i] );
642 assert( a->a_nvals == NULL );
643 rc = (*mr->smr_match)( &match,
644 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
645 a->a_desc->ad_type->sat_syntax,
647 &mod->sm_values[i] );
650 rc = (*mr->smr_match)( &match,
651 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
652 a->a_desc->ad_type->sat_syntax,
657 if ( rc != LDAP_SUCCESS ) {
659 free( asserted.bv_val );
662 snprintf( textbuf, textlen,
663 "%s: matching rule failed",
664 mod->sm_desc->ad_cname.bv_val );
674 /* delete value and mark it as dummy */
676 free( a->a_vals[j].bv_val );
677 a->a_vals[j].bv_val = &dummy;
679 free( a->a_nvals[j].bv_val );
680 a->a_nvals[j].bv_val = &dummy;
683 free( nvals[ j ].bv_val );
684 nvals[ j ].bv_val = &dummy;
691 free( asserted.bv_val );
696 snprintf( textbuf, textlen,
697 "modify/delete: %s: no such value",
698 mod->sm_desc->ad_cname.bv_val );
699 rc = LDAP_NO_SUCH_ATTRIBUTE;
704 /* compact array skipping dummies */
706 for ( k = 0, j = 0; a->a_vals[k].bv_val != NULL; k++ )
708 for ( k = 0, j = 0; nvals[k].bv_val != NULL; j++, k++ )
713 if( a->a_vals[k].bv_val == &dummy ) {
714 assert( a->a_nvals == NULL || a->a_nvals[k].bv_val == &dummy );
718 /* delete and skip dummies */ ;
719 for ( ; nvals[ k ].bv_val == &dummy; k++ ) {
720 free( a->a_vals[ k ].bv_val );
724 a->a_vals[ j ] = a->a_vals[ k ];
727 a->a_nvals[ j ] = a->a_nvals[ k ];
733 if ( a->a_vals[ k ].bv_val == NULL ) {
741 a->a_vals[j].bv_val = NULL;
743 if (a->a_nvals) a->a_nvals[j].bv_val = NULL;
746 assert( i == k - j );
749 /* if no values remain, delete the entire attribute */
750 if ( a->a_vals[0].bv_val == NULL ) {
751 if ( attr_delete( &e->e_attrs, mod->sm_desc ) ) {
753 snprintf( textbuf, textlen,
754 "modify/delete: %s: no such attribute",
755 mod->sm_desc->ad_cname.bv_val );
756 rc = LDAP_NO_SUCH_ATTRIBUTE;
763 /* delete the remaining normalized values */
764 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
765 if ( nvals[ j ].bv_val != &dummy ) {
766 ber_memfree( nvals[ j ].bv_val );
769 ber_memfree( nvals );
777 modify_replace_values(
782 char *textbuf, size_t textlen
785 (void) attr_delete( &e->e_attrs, mod->sm_desc );
787 if ( mod->sm_bvalues ) {
788 return modify_add_values( e, mod, permissive, text, textbuf, textlen );
800 if ( mod->sm_values != NULL ) ber_bvarray_free( mod->sm_values );
801 mod->sm_values = NULL;
804 if ( mod->sm_nvalues != NULL ) ber_bvarray_free( mod->sm_nvalues );
805 mod->sm_nvalues = NULL;
808 if( freeit ) free( mod );
818 for ( ; ml != NULL; ml = next ) {
821 slap_mod_free( &ml->sml_mod, 0 );