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;
33 BerVarray nvals = NULL, nmods = NULL;
36 * FIXME: better do the following
38 * - count the existing values
39 * - count the new values
41 * - if the existing values are less than the new ones {
42 * - normalize all the existing values
43 * - for each new value {
45 * - check with existing
46 * - cross-check with already normalized new vals
49 * - for each new value {
51 * - cross-check with already normalized new vals
53 * - for each existing value {
55 * - check with already normalized new values
59 * The first case is good when adding a lot of new values,
60 * and significantly at first import of values (e.g. adding
61 * a new group); the latter case seems to be quite important
62 * as well, because it is likely to be the most frequently
63 * used when administering the entry. The current
64 * implementation will always normalize all the existing
65 * values before checking. If there's no duplicate, the
66 * performances should not change; they will in case of error.
69 for ( nummods = 0; mods[ nummods ].bv_val != NULL; nummods++ )
70 /* count new values */ ;
73 for ( numvals = 0; vals[ numvals ].bv_val != NULL; numvals++ )
74 /* count existing values */ ;
76 if ( numvals < nummods ) {
77 nvals = SLAP_CALLOC( numvals + 1, sizeof( struct berval ) );
80 LDAP_LOG( OPERATION, ERR,
81 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
83 Debug( LDAP_DEBUG_ANY,
84 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
89 /* normalize the existing values first */
90 for ( j = 0; vals[ j ].bv_val != NULL; j++ ) {
91 rc = value_normalize( ad, SLAP_MR_EQUALITY,
92 &vals[ j ], &nvals[ j ], text );
94 /* existing attribute values must normalize */
95 assert( rc == LDAP_SUCCESS );
97 if ( rc != LDAP_SUCCESS ) {
98 nvals[ j ].bv_val = NULL;
102 nvals[ j ].bv_val = NULL;
107 * If the existing values are less than the new values,
108 * it is more convenient to normalize all the existing
109 * values and test each new value against them first,
110 * then to other already normalized values
112 nmods = SLAP_CALLOC( nummods + 1, sizeof( struct berval ) );
113 if ( nmods == NULL ) {
115 LDAP_LOG( OPERATION, ERR,
116 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
118 Debug( LDAP_DEBUG_ANY,
119 "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
124 for ( i = 0; mods[ i ].bv_val != NULL; i++ ) {
125 rc = value_normalize( ad, SLAP_MR_EQUALITY,
126 &mods[ i ], &nmods[ i ], text );
128 if ( rc != LDAP_SUCCESS ) {
129 nmods[ i ].bv_val = NULL;
133 if ( numvals > 0 && numvals < nummods ) {
134 for ( matched = 0, j = 0; nvals[ j ].bv_val; j++ ) {
137 rc = (*mr->smr_match)( &match,
138 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
139 ad->ad_type->sat_syntax,
140 mr, &nmods[ i ], &nvals[ j ] );
141 if ( rc != LDAP_SUCCESS ) {
142 nmods[ i + 1 ].bv_val = NULL;
144 snprintf( textbuf, textlen,
145 "%s: matching rule failed",
146 ad->ad_cname.bv_val );
156 snprintf( textbuf, textlen,
157 "%s: value #%d provided more than once",
158 ad->ad_cname.bv_val, i );
159 rc = LDAP_TYPE_OR_VALUE_EXISTS;
160 nmods[ i + 1 ].bv_val = NULL;
165 if ( permissive && matched == j ) {
166 nmods[ i + 1 ].bv_val = NULL;
167 rc = LDAP_TYPE_OR_VALUE_EXISTS;
172 for ( matched = 0, j = 0; j < i; j++ ) {
175 rc = (*mr->smr_match)( &match,
176 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
177 ad->ad_type->sat_syntax,
178 mr, &nmods[ i ], &nmods[ j ] );
179 if ( rc != LDAP_SUCCESS ) {
180 nmods[ i + 1 ].bv_val = NULL;
182 snprintf( textbuf, textlen,
183 "%s: matching rule failed",
184 ad->ad_cname.bv_val );
194 snprintf( textbuf, textlen,
195 "%s: value #%d provided more than once",
196 ad->ad_cname.bv_val, j );
197 rc = LDAP_TYPE_OR_VALUE_EXISTS;
198 nmods[ i + 1 ].bv_val = NULL;
203 if ( permissive && matched == j ) {
204 nmods[ i + 1 ].bv_val = NULL;
205 rc = LDAP_TYPE_OR_VALUE_EXISTS;
209 nmods[ i ].bv_val = NULL;
212 * if new values are more than existing values, it is more
213 * convenient to normalize and check all new values first,
214 * then check each new value against existing values, which
215 * can be normalized in place
218 if ( numvals >= nummods ) {
219 for ( j = 0; vals[ j ].bv_val; j++ ) {
220 struct berval asserted;
222 rc = value_normalize( ad, SLAP_MR_EQUALITY,
223 &vals[ j ], &asserted, text );
225 if ( rc != LDAP_SUCCESS ) {
229 for ( matched = 0, i = 0; nmods[ i ].bv_val; i++ ) {
232 rc = (*mr->smr_match)( &match,
233 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
234 ad->ad_type->sat_syntax,
235 mr, &nmods[ i ], &asserted );
236 if ( rc != LDAP_SUCCESS ) {
238 snprintf( textbuf, textlen,
239 "%s: matching rule failed",
240 ad->ad_cname.bv_val );
250 snprintf( textbuf, textlen,
251 "%s: value #%d provided more than once",
252 ad->ad_cname.bv_val, j );
253 rc = LDAP_TYPE_OR_VALUE_EXISTS;
258 if ( permissive && matched == i ) {
259 rc = LDAP_TYPE_OR_VALUE_EXISTS;
267 ber_bvarray_free( nvals );
270 ber_bvarray_free( nmods );
282 char *textbuf, size_t textlen
288 MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
291 switch( mod->sm_op ) {
295 case LDAP_MOD_REPLACE:
303 a = attr_find( e->e_attrs, mod->sm_desc );
306 * With permissive set, as long as the attribute being added
307 * has the same value(s?) as the existing attribute, then the
308 * modify will succeed.
311 /* check if the values we're adding already exist */
312 if( mr == NULL || !mr->smr_match ) {
314 /* do not allow add of additional attribute
315 if no equality rule exists */
317 snprintf( textbuf, textlen,
318 "modify/%s: %s: no equality matching rule",
319 op, mod->sm_desc->ad_cname.bv_val );
320 return LDAP_INAPPROPRIATE_MATCHING;
323 for ( i = 0; mod->sm_bvalues[i].bv_val != NULL; i++ ) {
324 /* test asserted values against existing values */
326 for( matched = 0, j = 0; a->a_vals[j].bv_val != NULL; j++ ) {
327 if ( bvmatch( &mod->sm_bvalues[i],
333 /* value exists already */
335 snprintf( textbuf, textlen,
336 "modify/%s: %s: value #%i already exists",
337 op, mod->sm_desc->ad_cname.bv_val, j );
338 return LDAP_TYPE_OR_VALUE_EXISTS;
341 if ( permissive && matched == j ) {
342 /* values already exist; do nothing */
347 /* test asserted values against themselves */
348 for( j = 0; j < i; j++ ) {
349 if ( bvmatch( &mod->sm_bvalues[i],
350 &mod->sm_bvalues[j] ) ) {
352 /* value exists already */
354 snprintf( textbuf, textlen,
355 "modify/%s: %s: value #%i already exists",
356 op, mod->sm_desc->ad_cname.bv_val, j );
357 return LDAP_TYPE_OR_VALUE_EXISTS;
364 * The original code performs ( n ) normalizations
365 * and ( n * ( n - 1 ) / 2 ) matches, which hide
366 * the same number of normalizations. The new code
367 * performs the same number of normalizations ( n )
368 * and ( n * ( n - 1 ) / 2 ) mem compares, far less
369 * expensive than an entire match, if a match is
370 * equivalent to a normalization and a mem compare ...
372 * This is far more memory expensive than the previous,
373 * but it can heavily improve performances when big
374 * chunks of data are added (typical example is a group
375 * with thousands of DN-syntax members; on my system:
376 * for members of 5-RDN DNs,
378 members orig bvmatch (dirty) new
379 1000 0m38.456s 0m0.553s 0m0.608s
380 2000 2m33.341s 0m0.851s 0m1.003s
382 * Moreover, 100 groups with 10000 members each were
383 * added in 37m27.933s (an analogous LDIF file was
384 * loaded into Active Directory in 38m28.682s, BTW).
386 * Maybe we could switch to the new algorithm when
387 * the number of values overcomes a given threshold?
392 if ( mod->sm_bvalues[ 1 ].bv_val == 0 ) {
394 struct berval asserted;
397 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
398 &mod->sm_bvalues[ 0 ], &asserted, text );
400 if ( rc != LDAP_SUCCESS ) {
404 for ( matched = 0, i = 0; a->a_vals[ i ].bv_val; i++ ) {
407 rc = value_match( &match, mod->sm_desc, mr,
408 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
409 &a->a_vals[ i ], &asserted, text );
411 if( rc == LDAP_SUCCESS && match == 0 ) {
416 free( asserted.bv_val );
418 snprintf( textbuf, textlen,
419 "modify/%s: %s: value #0 already exists",
420 op, mod->sm_desc->ad_cname.bv_val, 0 );
421 return LDAP_TYPE_OR_VALUE_EXISTS;
424 if ( permissive && matched == i ) {
425 /* values already exist; do nothing */
431 rc = modify_check_duplicates( mod->sm_desc, mr,
432 a ? a->a_vals : NULL, mod->sm_bvalues,
434 text, textbuf, textlen );
436 if ( permissive && rc == LDAP_TYPE_OR_VALUE_EXISTS ) {
440 if ( rc != LDAP_SUCCESS ) {
448 if( attr_merge( e, mod->sm_desc, mod->sm_values, mod->sm_nvalues ) != 0 )
450 if( attr_merge( e, mod->sm_desc, mod->sm_bvalues ) != 0 )
453 /* this should return result of attr_merge */
455 snprintf( textbuf, textlen,
456 "modify/%s: %s: merge error",
457 op, mod->sm_desc->ad_cname.bv_val );
465 modify_delete_values(
470 char *textbuf, size_t textlen
473 int i, j, k, rc = LDAP_SUCCESS;
475 MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
476 BerVarray nvals = NULL;
480 * If permissive is set, then the non-existence of an
481 * attribute is not treated as an error.
484 /* delete the entire attribute */
485 if ( mod->sm_bvalues == NULL ) {
486 rc = attr_delete( &e->e_attrs, mod->sm_desc );
490 } else if( rc != LDAP_SUCCESS ) {
492 snprintf( textbuf, textlen,
493 "modify/delete: %s: no such attribute",
494 mod->sm_desc->ad_cname.bv_val );
495 rc = LDAP_NO_SUCH_ATTRIBUTE;
500 if( mr == NULL || !mr->smr_match ) {
501 /* disallow specific attributes from being deleted if
504 snprintf( textbuf, textlen,
505 "modify/delete: %s: no equality matching rule",
506 mod->sm_desc->ad_cname.bv_val );
507 return LDAP_INAPPROPRIATE_MATCHING;
510 /* delete specific values - find the attribute first */
511 if ( (a = attr_find( e->e_attrs, mod->sm_desc )) == NULL ) {
516 snprintf( textbuf, textlen,
517 "modify/delete: %s: no such attribute",
518 mod->sm_desc->ad_cname.bv_val );
519 return LDAP_NO_SUCH_ATTRIBUTE;
522 /* find each value to delete */
523 for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ )
524 /* count existing values */ ;
526 nvals = (BerVarray)SLAP_CALLOC( j + 1, sizeof ( struct berval ) );
527 if( nvals == NULL ) {
529 LDAP_LOG( OPERATION, ERR,
530 "modify_delete_values: SLAP_CALLOC failed", 0, 0, 0 );
532 Debug( LDAP_DEBUG_ANY,
533 "modify_delete_values: SLAP_CALLOC failed", 0, 0, 0 );
538 /* normalize existing values */
539 for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ ) {
540 rc = value_normalize( a->a_desc, SLAP_MR_EQUALITY,
541 &a->a_vals[ j ], &nvals[ j ], text );
543 if ( rc != LDAP_SUCCESS ) {
544 nvals[ j ].bv_val = NULL;
549 for ( i = 0; mod->sm_bvalues[ i ].bv_val != NULL; i++ ) {
550 struct berval asserted;
553 /* normalize the value to be deleted */
554 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
555 &mod->sm_bvalues[ i ], &asserted, text );
557 if( rc != LDAP_SUCCESS ) {
562 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
565 if ( nvals[ j ].bv_val == &dummy ) {
569 rc = (*mr->smr_match)( &match,
570 SLAP_MR_ATTRIBUTE_SYNTAX_MATCH,
571 a->a_desc->ad_type->sat_syntax,
572 mr, &nvals[ j ], &asserted );
574 if ( rc != LDAP_SUCCESS ) {
575 free( asserted.bv_val );
577 snprintf( textbuf, textlen,
578 "%s: matching rule failed",
579 mod->sm_desc->ad_cname.bv_val );
589 /* delete value and mark it as dummy */
590 free( nvals[ j ].bv_val );
591 nvals[ j ].bv_val = &dummy;
596 free( asserted.bv_val );
600 snprintf( textbuf, textlen,
601 "modify/delete: %s: no such value",
602 mod->sm_desc->ad_cname.bv_val );
603 rc = LDAP_NO_SUCH_ATTRIBUTE;
608 /* compact array skipping dummies */
609 for ( k = 0, j = 0; nvals[ k ].bv_val != NULL; j++, k++ ) {
611 /* delete and skip dummies */ ;
612 for ( ; nvals[ k ].bv_val == &dummy; k++ ) {
613 free( a->a_vals[ k ].bv_val );
617 a->a_vals[ j ] = a->a_vals[ k ];
620 if ( a->a_vals[ k ].bv_val == NULL ) {
624 a->a_vals[ j ].bv_val = NULL;
626 assert( i == k - j );
628 /* if no values remain, delete the entire attribute */
629 if ( a->a_vals[0].bv_val == NULL ) {
630 if ( attr_delete( &e->e_attrs, mod->sm_desc ) ) {
632 snprintf( textbuf, textlen,
633 "modify/delete: %s: no such attribute",
634 mod->sm_desc->ad_cname.bv_val );
635 rc = LDAP_NO_SUCH_ATTRIBUTE;
641 /* delete the remaining normalized values */
642 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
643 if ( nvals[ j ].bv_val != &dummy ) {
644 ber_memfree( nvals[ j ].bv_val );
647 ber_memfree( nvals );
654 modify_replace_values(
659 char *textbuf, size_t textlen
662 (void) attr_delete( &e->e_attrs, mod->sm_desc );
664 if ( mod->sm_bvalues ) {
665 return modify_add_values( e, mod, permissive, text, textbuf, textlen );
677 if ( mod->sm_values != NULL ) ber_bvarray_free( mod->sm_values );
678 mod->sm_values = NULL;
681 if ( mod->sm_nvalues != NULL ) ber_bvarray_free( mod->sm_nvalues );
682 mod->sm_nvalues = NULL;
685 if( freeit ) free( mod );
695 for ( ; ml != NULL; ml = next ) {
698 slap_mod_free( &ml->sml_mod, 0 );