1 /* valsort.c - sort attribute values */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 2005 The OpenLDAP Foundation.
6 * Portions copyright 2005 Symas Corporation.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted only as authorized by the OpenLDAP
13 * A copy of this license is available in the file LICENSE in the
14 * top-level directory of the distribution or, alternatively, at
15 * <http://www.OpenLDAP.org/license.html>.
18 * This work was initially developed by Howard Chu for inclusion in
19 * OpenLDAP Software. This work was sponsored by Stanford University.
23 * This overlay sorts the values of multi-valued attributes when returning
24 * them in a search response.
28 #ifdef SLAPD_OVER_VALSORT
32 #include <ac/string.h>
39 #define VALSORT_ASCEND 0
40 #define VALSORT_DESCEND 1
42 #define VALSORT_ALPHA 2
43 #define VALSORT_NUMERIC 4
45 #define VALSORT_WEIGHTED 8
47 typedef struct valsort_info {
48 struct valsort_info *vi_next;
50 AttributeDescription *vi_ad;
54 static ConfigDriver valsort_cf_func;
56 static ConfigTable valsort_cfats[] = {
57 { "valsort-attr", "attribute> <dn> <sort-type", 4, 5, 0, ARG_MAGIC,
58 valsort_cf_func, "( OLcfgOvAt:5.1 NAME 'olcValSortAttr' "
59 "DESC 'Sorting rule for attribute under given DN' "
60 "EQUALITY caseIgnoreMatch "
61 "SYNTAX OMsDirectoryString )", NULL, NULL },
65 static ConfigOCs valsort_cfocs[] = {
67 "NAME 'olcValSortConfig' "
68 "DESC 'Value Sorting configuration' "
69 "SUP olcOverlayConfig "
70 "MUST olcValSortAttr )",
71 Cft_Overlay, valsort_cfats },
75 static slap_verbmasks sorts[] = {
76 { BER_BVC("alpha-ascend"), VALSORT_ASCEND|VALSORT_ALPHA },
77 { BER_BVC("alpha-descend"), VALSORT_DESCEND|VALSORT_ALPHA },
78 { BER_BVC("numeric-ascend"), VALSORT_ASCEND|VALSORT_NUMERIC },
79 { BER_BVC("numeric-ascend"), VALSORT_DESCEND|VALSORT_NUMERIC },
80 { BER_BVC("weighted"), VALSORT_WEIGHTED },
85 valsort_cf_func(ConfigArgs *c) {
86 slap_overinst *on = (slap_overinst *)c->bi;
87 valsort_info vitmp, *vi;
88 const char *text = NULL;
90 struct berval bv = BER_BVNULL;
92 if ( c->op == SLAP_CONFIG_EMIT ) {
93 for ( vi = on->on_bi.bi_private; vi; vi = vi->vi_next ) {
94 struct berval bv2 = BER_BVNULL, bvret;
98 len = vi->vi_ad->ad_cname.bv_len + 1 + vi->vi_dn.bv_len + 3;
100 if ( i & VALSORT_WEIGHTED ) {
101 enum_to_verb( sorts, VALSORT_WEIGHTED, &bv2 );
102 len += bv2.bv_len + 1;
103 i ^= VALSORT_WEIGHTED;
106 enum_to_verb( sorts, i, &bv );
108 bvret.bv_val = ch_malloc( len+1 );
111 ptr = lutil_strcopy( bvret.bv_val, vi->vi_ad->ad_cname.bv_val );
114 ptr = lutil_strcopy( ptr, vi->vi_dn.bv_val );
116 if ( vi->vi_sort & VALSORT_WEIGHTED ) {
118 ptr = lutil_strcopy( ptr, bv2.bv_val );
120 if ( !BER_BVISNULL( &bv )) {
122 strcpy( ptr, bv.bv_val );
124 ber_bvarray_add( &c->rvalue_vals, &bvret );
126 i = ( c->rvalue_vals != NULL ) ? 0 : 1;
128 } else if ( c->op == LDAP_MOD_DELETE ) {
130 for ( vi = on->on_bi.bi_private; vi; vi = c->be->be_private ) {
131 on->on_bi.bi_private = vi->vi_next;
132 ch_free( vi->vi_dn.bv_val );
138 for (i=0, prev = (valsort_info **)&on->on_bi.bi_private,
139 vi = *prev; vi && i<c->valx;
140 prev = &vi->vi_next, vi = vi->vi_next, i++ );
141 (*prev)->vi_next = vi->vi_next;
142 ch_free( vi->vi_dn.bv_val );
148 i = slap_str2ad( c->argv[1], &vitmp.vi_ad, &text );
150 sprintf( c->msg, "<%s> %s", c->argv[0], text );
151 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
152 c->log, c->msg, c->argv[1] );
155 if ( is_at_single_value( vitmp.vi_ad->ad_type )) {
156 sprintf( c->msg, "<%s> %s is single-valued, ignoring", c->argv[0],
157 vitmp.vi_ad->ad_cname.bv_val );
158 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
159 c->log, c->msg, c->argv[1] );
162 ber_str2bv( c->argv[2], 0, 0, &bv );
163 i = dnNormalize( 0, NULL, NULL, &bv, &vitmp.vi_dn, NULL );
165 sprintf( c->msg, "<%s> unable to normalize DN", c->argv[0] );
166 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
167 c->log, c->msg, c->argv[2] );
170 i = verb_to_mask( c->argv[3], sorts );
171 if ( BER_BVISNULL( &sorts[i].word )) {
172 sprintf( c->msg, "<%s> unrecognized sort type", c->argv[0] );
173 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
174 c->log, c->msg, c->argv[3] );
177 vitmp.vi_sort = sorts[i].mask;
178 if ( sorts[i].mask == VALSORT_WEIGHTED && c->argc == 5 ) {
179 i = verb_to_mask( c->argv[4], sorts );
180 if ( BER_BVISNULL( &sorts[i].word )) {
181 sprintf( c->msg, "<%s> unrecognized sort type", c->argv[0] );
182 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
183 c->log, c->msg, c->argv[4] );
186 vitmp.vi_sort |= sorts[i].mask;
188 vi = ch_malloc( sizeof(valsort_info) );
190 vi->vi_next = on->on_bi.bi_private;
191 on->on_bi.bi_private = vi;
195 /* Use Insertion Sort algorithm on selected values */
197 do_sort( Operation *op, Attribute *a, int beg, int num, slap_mask_t sort )
200 struct berval tmp, ntmp, *vals, *nvals;
202 gotnvals = (a->a_vals != a->a_nvals );
204 nvals = a->a_nvals + beg;
206 vals = a->a_vals + beg;
208 if ( sort & VALSORT_NUMERIC ) {
209 long *numbers = op->o_tmpalloc( num * sizeof(long), op->o_tmpmemctx ),
211 for (i=0; i<num; i++)
212 numbers[i] = strtol( nvals[i].bv_val, NULL, 0 );
214 for (i=1; i<num; i++) {
217 if ( gotnvals ) tmp = vals[i];
220 int cmp = (sort & VALSORT_DESCEND) ? numbers[j-1] < idx :
223 numbers[j] = numbers[j-1];
224 nvals[j] = nvals[j-1];
225 if ( gotnvals ) vals[j] = vals[j-1];
230 if ( gotnvals ) vals[j] = tmp;
232 op->o_tmpfree( numbers, op->o_tmpmemctx );
234 for (i=1; i<num; i++) {
236 if ( gotnvals ) tmp = vals[i];
239 int cmp = strcmp( nvals[j-1].bv_val, ntmp.bv_val );
240 cmp = (sort & VALSORT_DESCEND) ? (cmp < 0) : (cmp > 0);
243 nvals[j] = nvals[j-1];
244 if ( gotnvals ) vals[j] = vals[j-1];
248 if ( gotnvals ) vals[j] = tmp;
254 valsort_response( Operation *op, SlapReply *rs )
260 /* We only want search responses */
261 if ( rs->sr_type != REP_SEARCH ) return SLAP_CB_CONTINUE;
263 on = (slap_overinst *) op->o_bd->bd_info;
264 vi = on->on_bi.bi_private;
266 /* And we must have something configured */
267 if ( !vi ) return SLAP_CB_CONTINUE;
269 /* Find a rule whose baseDN matches this entry */
270 for (; vi; vi = vi->vi_next ) {
273 if ( !dnIsSuffix( &rs->sr_entry->e_nname, &vi->vi_dn ))
276 /* Find attr that this rule affects */
277 a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
280 if (( rs->sr_flags & ( REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED )) !=
281 ( REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED )) {
282 rs->sr_entry = entry_dup( rs->sr_entry );
283 rs->sr_flags |= REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED;
284 a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
288 for ( n = 0; !BER_BVISNULL( &a->a_vals[n] ); n++ );
290 if ( vi->vi_sort & VALSORT_WEIGHTED ) {
292 long *index = op->o_tmpalloc( n * sizeof(long), op->o_tmpmemctx );
294 gotnvals = (a->a_vals != a->a_nvals );
296 for (i=0; i<n; i++) {
297 char *ptr = strchr( a->a_nvals[i].bv_val, '{' );
300 Debug(LDAP_DEBUG_TRACE, "weights missing from attr %s "
301 "in entry %s\n", vi->vi_ad->ad_cname.bv_val,
302 rs->sr_entry->e_name.bv_val, 0 );
305 index[i] = strtol( ptr+1, &end, 0 );
307 Debug(LDAP_DEBUG_TRACE, "weights misformatted "
309 rs->sr_entry->e_name.bv_val, 0, 0 );
312 /* Strip out weights */
313 ptr = a->a_nvals[i].bv_val;
318 a->a_nvals[i].bv_len = ptr - a->a_nvals[i].bv_val;
320 if ( a->a_vals != a->a_nvals ) {
321 ptr = a->a_vals[i].bv_val;
322 end = strchr( ptr, '}' ) + 1;
326 a->a_vals[i].bv_len = ptr - a->a_vals[i].bv_val;
329 /* An attr was missing weights here, ignore it */
331 op->o_tmpfree( index, op->o_tmpmemctx );
335 for ( i=1; i<n; i++) {
337 struct berval tmp = a->a_vals[i], ntmp;
338 if ( gotnvals ) ntmp = a->a_nvals[i];
340 while (( j>0 ) && (index[j-1] > idx )) {
341 index[j] = index[j-1];
342 a->a_vals[j] = a->a_vals[j-1];
343 if ( gotnvals ) a->a_nvals[j] = a->a_nvals[j-1];
348 if ( gotnvals ) a->a_nvals[j] = ntmp;
350 /* Check for secondary sort */
351 if ( vi->vi_sort ^ VALSORT_WEIGHTED ) {
353 for (j=i+1; j<n; j++) {
354 if (index[i] != index[j])
358 do_sort( op, a, i, j-i, vi->vi_sort );
362 op->o_tmpfree( index, op->o_tmpmemctx );
364 do_sort( op, a, 0, n, vi->vi_sort );
367 return SLAP_CB_CONTINUE;
371 valsort_add( Operation *op, SlapReply *rs )
373 slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
374 valsort_info *vi = on->on_bi.bi_private;
380 /* See if any weighted sorting applies to this entry */
381 for ( ;vi;vi=vi->vi_next ) {
382 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
384 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
386 a = attr_find( op->ora_e->e_attrs, vi->vi_ad );
389 for (i=0; !BER_BVISNULL( &a->a_vals[i] ); i++) {
390 ptr = strchr(a->a_vals[i].bv_val, '{' );
392 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
393 vi->vi_ad->ad_cname.bv_val, 0, 0);
394 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
395 "weight missing from attribute" );
398 strtol( ptr+1, &end, 0 );
400 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
401 vi->vi_ad->ad_cname.bv_val, 0, 0);
402 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
403 "weight is misformatted" );
408 return SLAP_CB_CONTINUE;
412 valsort_modify( Operation *op, SlapReply *rs )
414 slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
415 valsort_info *vi = on->on_bi.bi_private;
421 /* See if any weighted sorting applies to this entry */
422 for ( ;vi;vi=vi->vi_next ) {
423 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
425 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
427 for (ml = op->orm_modlist; ml; ml=ml->sml_next ) {
428 if ( ml->sml_desc == vi->vi_ad )
433 for (i=0; !BER_BVISNULL( &ml->sml_values[i] ); i++) {
434 ptr = strchr(ml->sml_values[i].bv_val, '{' );
436 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
437 vi->vi_ad->ad_cname.bv_val, 0, 0);
438 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
439 "weight missing from attribute" );
442 strtol( ptr+1, &end, 0 );
444 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
445 vi->vi_ad->ad_cname.bv_val, 0, 0);
446 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
447 "weight is misformatted" );
452 return SLAP_CB_CONTINUE;
460 slap_overinst *on = (slap_overinst *)be->bd_info;
461 valsort_info *vi = on->on_bi.bi_private, *next;
463 for (; vi; vi = next) {
465 ch_free( vi->vi_dn.bv_val );
472 static slap_overinst valsort;
478 valsort.on_bi.bi_type = "valsort";
479 valsort.on_bi.bi_db_destroy = valsort_destroy;
481 valsort.on_bi.bi_op_add = valsort_add;
482 valsort.on_bi.bi_op_modify = valsort_modify;
484 valsort.on_response = valsort_response;
486 valsort.on_bi.bi_cf_ocs = valsort_cfocs;
488 rc = config_register_schema( valsort_cfats, valsort_cfocs );
491 return overlay_register(&valsort);
494 #if SLAPD_OVER_VALSORT == SLAPD_MOD_DYNAMIC
495 int init_module( int argc, char *argv[]) {
496 return valsort_init();
500 #endif /* SLAPD_OVER_VALSORT */