]> git.sur5r.net Git - openldap/blob - servers/slapd/overlays/valsort.c
bfd3ca1ffb0690347076e93f8df358a9f16ff682
[openldap] / servers / slapd / overlays / valsort.c
1 /* valsort.c - sort attribute values */
2 /* $OpenLDAP$ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4  *
5  * Copyright 2005-2007 The OpenLDAP Foundation.
6  * Portions copyright 2005 Symas Corporation.
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted only as authorized by the OpenLDAP
11  * Public License.
12  *
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>.
16  */
17 /* ACKNOWLEDGEMENTS:
18  * This work was initially developed by Howard Chu for inclusion in
19  * OpenLDAP Software. This work was sponsored by Stanford University.
20  */
21
22 /*
23  * This overlay sorts the values of multi-valued attributes when returning
24  * them in a search response.
25  */
26 #include "portable.h"
27
28 #ifdef SLAPD_OVER_VALSORT
29
30 #include <stdio.h>
31
32 #include <ac/string.h>
33 #include <ac/ctype.h>
34
35 #include "slap.h"
36 #include "config.h"
37 #include "lutil.h"
38
39 #define VALSORT_ASCEND  0
40 #define VALSORT_DESCEND 1
41
42 #define VALSORT_ALPHA   2
43 #define VALSORT_NUMERIC 4
44
45 #define VALSORT_WEIGHTED        8
46
47 typedef struct valsort_info {
48         struct valsort_info *vi_next;
49         struct berval vi_dn;
50         AttributeDescription *vi_ad;
51         slap_mask_t vi_sort;
52 } valsort_info;
53
54 static int valsort_cid;
55
56 static ConfigDriver valsort_cf_func;
57
58 static ConfigTable valsort_cfats[] = {
59         { "valsort-attr", "attribute> <dn> <sort-type", 4, 5, 0, ARG_MAGIC,
60                 valsort_cf_func, "( OLcfgOvAt:5.1 NAME 'olcValSortAttr' "
61                         "DESC 'Sorting rule for attribute under given DN' "
62                         "EQUALITY caseIgnoreMatch "
63                         "SYNTAX OMsDirectoryString )", NULL, NULL },
64         { NULL }
65 };
66
67 static ConfigOCs valsort_cfocs[] = {
68         { "( OLcfgOvOc:5.1 "
69                 "NAME 'olcValSortConfig' "
70                 "DESC 'Value Sorting configuration' "
71                 "SUP olcOverlayConfig "
72                 "MUST olcValSortAttr )",
73                         Cft_Overlay, valsort_cfats },
74         { NULL }
75 };
76
77 static slap_verbmasks sorts[] = {
78         { BER_BVC("alpha-ascend"), VALSORT_ASCEND|VALSORT_ALPHA },
79         { BER_BVC("alpha-descend"), VALSORT_DESCEND|VALSORT_ALPHA },
80         { BER_BVC("numeric-ascend"), VALSORT_ASCEND|VALSORT_NUMERIC },
81         { BER_BVC("numeric-descend"), VALSORT_DESCEND|VALSORT_NUMERIC },
82         { BER_BVC("weighted"), VALSORT_WEIGHTED },
83         { BER_BVNULL, 0 }
84 };
85
86 static Syntax *syn_numericString;
87
88 static int
89 valsort_cf_func(ConfigArgs *c) {
90         slap_overinst *on = (slap_overinst *)c->bi;
91         valsort_info vitmp, *vi;
92         const char *text = NULL;
93         int i, is_numeric;
94         struct berval bv = BER_BVNULL;
95
96         if ( c->op == SLAP_CONFIG_EMIT ) {
97                 for ( vi = on->on_bi.bi_private; vi; vi = vi->vi_next ) {
98                         struct berval bv2 = BER_BVNULL, bvret;
99                         char *ptr;
100                         int len;
101                         
102                         len = vi->vi_ad->ad_cname.bv_len + 1 + vi->vi_dn.bv_len + 2;
103                         i = vi->vi_sort;
104                         if ( i & VALSORT_WEIGHTED ) {
105                                 enum_to_verb( sorts, VALSORT_WEIGHTED, &bv2 );
106                                 len += bv2.bv_len + 1;
107                                 i ^= VALSORT_WEIGHTED;
108                         }
109                         if ( i ) {
110                                 enum_to_verb( sorts, i, &bv );
111                                 len += bv.bv_len + 1;
112                         }
113                         bvret.bv_val = ch_malloc( len+1 );
114                         bvret.bv_len = len;
115
116                         ptr = lutil_strcopy( bvret.bv_val, vi->vi_ad->ad_cname.bv_val );
117                         *ptr++ = ' ';
118                         *ptr++ = '"';
119                         ptr = lutil_strcopy( ptr, vi->vi_dn.bv_val );
120                         *ptr++ = '"';
121                         if ( vi->vi_sort & VALSORT_WEIGHTED ) {
122                                 *ptr++ = ' ';
123                                 ptr = lutil_strcopy( ptr, bv2.bv_val );
124                         }
125                         if ( i ) {
126                                 *ptr++ = ' ';
127                                 strcpy( ptr, bv.bv_val );
128                         }
129                         ber_bvarray_add( &c->rvalue_vals, &bvret );
130                 }
131                 i = ( c->rvalue_vals != NULL ) ? 0 : 1;
132                 return i;
133         } else if ( c->op == LDAP_MOD_DELETE ) {
134                 if ( c->valx < 0 ) {
135                         for ( vi = on->on_bi.bi_private; vi; vi = on->on_bi.bi_private ) {
136                                 on->on_bi.bi_private = vi->vi_next;
137                                 ch_free( vi->vi_dn.bv_val );
138                                 ch_free( vi );
139                         }
140                 } else {
141                         valsort_info **prev;
142
143                         for (i=0, prev = (valsort_info **)&on->on_bi.bi_private,
144                                 vi = *prev; vi && i<c->valx;
145                                 prev = &vi->vi_next, vi = vi->vi_next, i++ );
146                         (*prev)->vi_next = vi->vi_next;
147                         ch_free( vi->vi_dn.bv_val );
148                         ch_free( vi );
149                 }
150                 return 0;
151         }
152         vitmp.vi_ad = NULL;
153         i = slap_str2ad( c->argv[1], &vitmp.vi_ad, &text );
154         if ( i ) {
155                 sprintf( c->msg, "<%s> %s", c->argv[0], text );
156                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
157                         c->log, c->msg, c->argv[1] );
158                 return(1);
159         }
160         if ( is_at_single_value( vitmp.vi_ad->ad_type )) {
161                 sprintf( c->msg, "<%s> %s is single-valued, ignoring", c->argv[0],
162                         vitmp.vi_ad->ad_cname.bv_val );
163                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
164                         c->log, c->msg, c->argv[1] );
165                 return(0);
166         }
167         is_numeric = ( vitmp.vi_ad->ad_type->sat_syntax == syn_numericString ||
168                 vitmp.vi_ad->ad_type->sat_syntax == slap_schema.si_syn_integer ) ? 1
169                 : 0;
170         ber_str2bv( c->argv[2], 0, 0, &bv );
171         i = dnNormalize( 0, NULL, NULL, &bv, &vitmp.vi_dn, NULL );
172         if ( i ) {
173                 sprintf( c->msg, "<%s> unable to normalize DN", c->argv[0] );
174                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
175                         c->log, c->msg, c->argv[2] );
176                 return(1);
177         }
178         i = verb_to_mask( c->argv[3], sorts );
179         if ( BER_BVISNULL( &sorts[i].word )) {
180                 sprintf( c->msg, "<%s> unrecognized sort type", c->argv[0] );
181                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
182                         c->log, c->msg, c->argv[3] );
183                 return(1);
184         }
185         vitmp.vi_sort = sorts[i].mask;
186         if ( sorts[i].mask == VALSORT_WEIGHTED && c->argc == 5 ) {
187                 i = verb_to_mask( c->argv[4], sorts );
188                 if ( BER_BVISNULL( &sorts[i].word )) {
189                         sprintf( c->msg, "<%s> unrecognized sort type", c->argv[0] );
190                         Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
191                                 c->log, c->msg, c->argv[4] );
192                         return(1);
193                 }
194                 vitmp.vi_sort |= sorts[i].mask;
195         }
196         if (( vitmp.vi_sort & VALSORT_NUMERIC ) && !is_numeric ) {
197                 sprintf( c->msg, "<%s> numeric sort specified for non-numeric syntax",
198                         c->argv[0] );
199                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
200                         c->log, c->msg, c->argv[1] );
201                 return(1);
202         }
203         vi = ch_malloc( sizeof(valsort_info) );
204         *vi = vitmp;
205         vi->vi_next = on->on_bi.bi_private;
206         on->on_bi.bi_private = vi;
207         return 0;
208 }
209
210 /* Use Insertion Sort algorithm on selected values */
211 static void
212 do_sort( Operation *op, Attribute *a, int beg, int num, slap_mask_t sort )
213 {
214         int i, j, gotnvals;
215         struct berval tmp, ntmp, *vals = NULL, *nvals;
216
217         gotnvals = (a->a_vals != a->a_nvals );
218
219         nvals = a->a_nvals + beg;
220         if ( gotnvals )
221                 vals = a->a_vals + beg;
222
223         if ( sort & VALSORT_NUMERIC ) {
224                 long *numbers = op->o_tmpalloc( num * sizeof(long), op->o_tmpmemctx ),
225                         idx;
226                 for (i=0; i<num; i++)
227                         numbers[i] = strtol( nvals[i].bv_val, NULL, 0 );
228
229                 for (i=1; i<num; i++) {
230                         idx = numbers[i];
231                         ntmp = nvals[i];
232                         if ( gotnvals ) tmp = vals[i];
233                         j = i;
234                         while ( j>0 ) {
235                                 int cmp = (sort & VALSORT_DESCEND) ? numbers[j-1] < idx :
236                                         numbers[j-1] > idx;
237                                 if ( !cmp ) break;
238                                 numbers[j] = numbers[j-1];
239                                 nvals[j] = nvals[j-1];
240                                 if ( gotnvals ) vals[j] = vals[j-1];
241                                 j--;
242                         }
243                         numbers[j] = idx;
244                         nvals[j] = ntmp;
245                         if ( gotnvals ) vals[j] = tmp;
246                 }
247                 op->o_tmpfree( numbers, op->o_tmpmemctx );
248         } else {
249                 for (i=1; i<num; i++) {
250                         ntmp = nvals[i];
251                         if ( gotnvals ) tmp = vals[i];
252                         j = i;
253                         while ( j>0 ) {
254                                 int cmp = strcmp( nvals[j-1].bv_val, ntmp.bv_val );
255                                 cmp = (sort & VALSORT_DESCEND) ? (cmp < 0) : (cmp > 0);
256                                 if ( !cmp ) break;
257
258                                 nvals[j] = nvals[j-1];
259                                 if ( gotnvals ) vals[j] = vals[j-1];
260                                 j--;
261                         }
262                         nvals[j] = ntmp;
263                         if ( gotnvals ) vals[j] = tmp;
264                 }
265         }
266 }
267
268 static int
269 valsort_response( Operation *op, SlapReply *rs )
270 {
271         slap_overinst *on;
272         valsort_info *vi;
273         Attribute *a;
274
275         /* If this is not a search response, or it is a syncrepl response,
276          * or the valsort control wants raw results, pass thru unmodified.
277          */
278         if ( rs->sr_type != REP_SEARCH ||
279                 ( _SCM(op->o_sync) > SLAP_CONTROL_IGNORED ) ||
280                 ( op->o_ctrlflag[valsort_cid] & SLAP_CONTROL_DATA0))
281                 return SLAP_CB_CONTINUE;
282                 
283         on = (slap_overinst *) op->o_bd->bd_info;
284         vi = on->on_bi.bi_private;
285
286         /* And we must have something configured */
287         if ( !vi ) return SLAP_CB_CONTINUE;
288
289         /* Find a rule whose baseDN matches this entry */
290         for (; vi; vi = vi->vi_next ) {
291                 int i, n;
292
293                 if ( !dnIsSuffix( &rs->sr_entry->e_nname, &vi->vi_dn ))
294                         continue;
295
296                 /* Find attr that this rule affects */
297                 a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
298                 if ( !a ) continue;
299
300                 if (( rs->sr_flags & ( REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED )) !=
301                         ( REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED )) {
302                         rs->sr_entry = entry_dup( rs->sr_entry );
303                         rs->sr_flags |= REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED;
304                         a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
305                 }
306
307                 /* count values */
308                 for ( n = 0; !BER_BVISNULL( &a->a_vals[n] ); n++ );
309
310                 if ( vi->vi_sort & VALSORT_WEIGHTED ) {
311                         int j, gotnvals;
312                         long *index = op->o_tmpalloc( n * sizeof(long), op->o_tmpmemctx );
313
314                         gotnvals = (a->a_vals != a->a_nvals );
315
316                         for (i=0; i<n; i++) {
317                                 char *ptr = ber_bvchr( &a->a_nvals[i], '{' );
318                                 char *end = NULL;
319                                 if ( !ptr ) {
320                                         Debug(LDAP_DEBUG_TRACE, "weights missing from attr %s "
321                                                 "in entry %s\n", vi->vi_ad->ad_cname.bv_val,
322                                                 rs->sr_entry->e_name.bv_val, 0 );
323                                         break;
324                                 }
325                                 index[i] = strtol( ptr+1, &end, 0 );
326                                 if ( *end != '}' ) {
327                                         Debug(LDAP_DEBUG_TRACE, "weights misformatted "
328                                                 "in entry %s\n", 
329                                                 rs->sr_entry->e_name.bv_val, 0, 0 );
330                                         break;
331                                 }
332                                 /* Strip out weights */
333                                 ptr = a->a_nvals[i].bv_val;
334                                 end++;
335                                 for (;*end;)
336                                         *ptr++ = *end++;
337                                 *ptr = '\0';
338                                 a->a_nvals[i].bv_len = ptr - a->a_nvals[i].bv_val;
339
340                                 if ( a->a_vals != a->a_nvals ) {
341                                         ptr = a->a_vals[i].bv_val;
342                                         end = ber_bvchr( &a->a_vals[i], '}' );
343                                         assert( end != NULL );
344                                         end++;
345                                         for (;*end;)
346                                                 *ptr++ = *end++;
347                                         *ptr = '\0';
348                                         a->a_vals[i].bv_len = ptr - a->a_vals[i].bv_val;
349                                 }
350                         }
351                         /* An attr was missing weights here, ignore it */
352                         if ( i<n ) {
353                                 op->o_tmpfree( index, op->o_tmpmemctx );
354                                 continue;
355                         }
356                         /* Insertion sort */
357                         for ( i=1; i<n; i++) {
358                                 long idx = index[i];
359                                 struct berval tmp = a->a_vals[i], ntmp;
360                                 if ( gotnvals ) ntmp = a->a_nvals[i];
361                                 j = i;
362                                 while (( j>0 ) && (index[j-1] > idx )) {
363                                         index[j] = index[j-1];
364                                         a->a_vals[j] = a->a_vals[j-1];
365                                         if ( gotnvals ) a->a_nvals[j] = a->a_nvals[j-1];
366                                         j--;
367                                 }
368                                 index[j] = idx;
369                                 a->a_vals[j] = tmp;
370                                 if ( gotnvals ) a->a_nvals[j] = ntmp;
371                         }
372                         /* Check for secondary sort */
373                         if ( vi->vi_sort ^ VALSORT_WEIGHTED ) {
374                                 for ( i=0; i<n;) {
375                                         for (j=i+1; j<n; j++) {
376                                                 if (index[i] != index[j])
377                                                         break;
378                                         }
379                                         if( j-i > 1 )
380                                                 do_sort( op, a, i, j-i, vi->vi_sort );
381                                         i = j;
382                                 }
383                         }
384                         op->o_tmpfree( index, op->o_tmpmemctx );
385                 } else {
386                         do_sort( op, a, 0, n, vi->vi_sort );
387                 }
388         }
389         return SLAP_CB_CONTINUE;
390 }
391
392 static int
393 valsort_add( Operation *op, SlapReply *rs )
394 {
395         slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
396         valsort_info *vi = on->on_bi.bi_private;
397
398         Attribute *a;
399         int i;
400         char *ptr, *end;
401
402         /* See if any weighted sorting applies to this entry */
403         for ( ;vi;vi=vi->vi_next ) {
404                 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
405                         continue;
406                 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
407                         continue;
408                 a = attr_find( op->ora_e->e_attrs, vi->vi_ad );
409                 if ( !a )
410                         continue;
411                 for (i=0; !BER_BVISNULL( &a->a_vals[i] ); i++) {
412                         ptr = ber_bvchr(&a->a_vals[i], '{' );
413                         if ( !ptr ) {
414                                 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
415                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
416                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
417                                         "weight missing from attribute" );
418                                 return rs->sr_err;
419                         }
420                         strtol( ptr+1, &end, 0 );
421                         if ( *end != '}' ) {
422                                 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
423                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
424                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
425                                         "weight is misformatted" );
426                                 return rs->sr_err;
427                         }
428                 }
429         }
430         return SLAP_CB_CONTINUE;
431 }
432
433 static int
434 valsort_modify( Operation *op, SlapReply *rs )
435 {
436         slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
437         valsort_info *vi = on->on_bi.bi_private;
438
439         Modifications *ml;
440         int i;
441         char *ptr, *end;
442
443         /* See if any weighted sorting applies to this entry */
444         for ( ;vi;vi=vi->vi_next ) {
445                 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
446                         continue;
447                 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
448                         continue;
449                 for (ml = op->orm_modlist; ml; ml=ml->sml_next ) {
450                         /* Must be a Delete Attr op, so no values to consider */
451                         if ( !ml->sml_values )
452                                 continue;
453                         if ( ml->sml_desc == vi->vi_ad )
454                                 break;
455                 }
456                 if ( !ml )
457                         continue;
458                 for (i=0; !BER_BVISNULL( &ml->sml_values[i] ); i++) {
459                         ptr = ber_bvchr(&ml->sml_values[i], '{' );
460                         if ( !ptr ) {
461                                 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
462                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
463                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
464                                         "weight missing from attribute" );
465                                 return rs->sr_err;
466                         }
467                         strtol( ptr+1, &end, 0 );
468                         if ( *end != '}' ) {
469                                 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
470                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
471                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
472                                         "weight is misformatted" );
473                                 return rs->sr_err;
474                         }
475                 }
476         }
477         return SLAP_CB_CONTINUE;
478 }
479
480 static int
481 valsort_db_open(
482         BackendDB *be
483 )
484 {
485         return overlay_register_control( be, LDAP_CONTROL_VALSORT );
486 }
487
488 static int
489 valsort_destroy(
490         BackendDB *be
491 )
492 {
493         slap_overinst *on = (slap_overinst *)be->bd_info;
494         valsort_info *vi = on->on_bi.bi_private, *next;
495
496         for (; vi; vi = next) {
497                 next = vi->vi_next;
498                 ch_free( vi->vi_dn.bv_val );
499                 ch_free( vi );
500         }
501
502         return 0;
503 }
504
505 static int
506 valsort_parseCtrl(
507         Operation *op,
508         SlapReply *rs,
509         LDAPControl *ctrl )
510 {
511         ber_tag_t tag;
512         BerElementBuffer berbuf;
513         BerElement *ber = (BerElement *)&berbuf;
514         ber_int_t flag = 0;
515
516         if ( ctrl->ldctl_value.bv_len == 0 ) {
517                 rs->sr_text = "valSort control value is empty (or absent)";
518                 return LDAP_PROTOCOL_ERROR;
519         }
520
521         ber_init2( ber, &ctrl->ldctl_value, 0 );
522         if (( tag = ber_scanf( ber, "{b}", &flag )) == LBER_ERROR ) {
523                 rs->sr_text = "valSort control: flag decoding error";
524                 return LDAP_PROTOCOL_ERROR;
525         }
526
527         op->o_ctrlflag[valsort_cid] = ctrl->ldctl_iscritical ?
528                 SLAP_CONTROL_CRITICAL : SLAP_CONTROL_NONCRITICAL;
529         if ( flag )
530                 op->o_ctrlflag[valsort_cid] |= SLAP_CONTROL_DATA0;
531
532         return LDAP_SUCCESS;
533 }
534
535 static slap_overinst valsort;
536
537 int valsort_initialize( void )
538 {
539         int rc;
540
541         valsort.on_bi.bi_type = "valsort";
542         valsort.on_bi.bi_db_destroy = valsort_destroy;
543         valsort.on_bi.bi_db_open = valsort_db_open;
544
545         valsort.on_bi.bi_op_add = valsort_add;
546         valsort.on_bi.bi_op_modify = valsort_modify;
547
548         valsort.on_response = valsort_response;
549
550         valsort.on_bi.bi_cf_ocs = valsort_cfocs;
551
552         rc = register_supported_control( LDAP_CONTROL_VALSORT,
553                 SLAP_CTRL_SEARCH | SLAP_CTRL_HIDE, NULL, valsort_parseCtrl,
554                 &valsort_cid );
555         if ( rc != LDAP_SUCCESS ) {
556                 fprintf( stderr, "Failed to register control %d\n", rc );
557                 return rc;
558         }
559
560         syn_numericString = syn_find( "1.3.6.1.4.1.1466.115.121.1.36" );
561
562         rc = config_register_schema( valsort_cfats, valsort_cfocs );
563         if ( rc ) return rc;
564
565         return overlay_register(&valsort);
566 }
567
568 #if SLAPD_OVER_VALSORT == SLAPD_MOD_DYNAMIC
569 int init_module( int argc, char *argv[]) {
570         return valsort_initialize();
571 }
572 #endif
573
574 #endif /* SLAPD_OVER_VALSORT */