git.sur5r.net Git - openldap/blob - 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 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 ConfigDriver valsort_cf_func;
  55
  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 },
  62         { NULL }
  63 };
  64
  65 static ConfigOCs valsort_cfocs[] = {
  66         { "( OLcfgOvOc:5.1 "
  67                 "NAME 'olcValSortConfig' "
  68                 "DESC 'Value Sorting configuration' "
  69                 "SUP olcOverlayConfig "
  70                 "MUST olcValSortAttr )",
  71                         Cft_Overlay, valsort_cfats },
  72         { NULL }
  73 };
  74
  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 },
  81         { BER_BVNULL, 0 }
  82 };
  83
  84 static int
  85 valsort_cf_func(ConfigArgs *c) {
  86         slap_overinst *on = (slap_overinst *)c->bi;
  87         valsort_info vitmp, *vi;
  88         const char *text = NULL;
  89         int i;
  90         struct berval bv;
  91
  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;
  95                         char *ptr;
  96                         int len;
  97
  98                         len = vi->vi_ad->ad_cname.bv_len + 1 + vi->vi_dn.bv_len + 3;
  99                         i = vi->vi_sort;
 100                         if ( i & VALSORT_WEIGHTED ) {
 101                                 enum_to_verb( sorts, VALSORT_WEIGHTED, &bv2 );
 102                                 len += bv2.bv_len + 1;
 103                                 i ^= VALSORT_WEIGHTED;
 104                         }
 105                         enum_to_verb( sorts, i, &bv );
 106                         len += bv.bv_len;
 107                         bvret.bv_val = ch_malloc( len+1 );
 108                         bvret.bv_len = len;
 109
 110                         ptr = lutil_strcopy( bvret.bv_val, vi->vi_ad->ad_cname.bv_val );
 111                         *ptr++ = ' ';
 112                         *ptr++ = '"';
 113                         ptr = lutil_strcopy( ptr, vi->vi_dn.bv_val );
 114                         *ptr++ = '"';
 115                         *ptr++ = ' ';
 116                         if ( vi->vi_sort & VALSORT_WEIGHTED ) {
 117                                 ptr = lutil_strcopy( ptr, bv2.bv_val );
 118                                 *ptr++ = ' ';
 119                         }
 120                         strcpy( ptr, bv.bv_val );
 121                         ber_bvarray_add( &c->rvalue_vals, &bvret );
 122                 }
 123                 i = ( c->rvalue_vals != NULL ) ? 0 : 1;
 124                 return i;
 125         } else if ( c->op == LDAP_MOD_DELETE ) {
 126                 if ( c->valx < 0 ) {
 127                         for ( vi = on->on_bi.bi_private; vi; vi = c->be->be_private ) {
 128                                 on->on_bi.bi_private = vi->vi_next;
 129                                 ch_free( vi->vi_dn.bv_val );
 130                                 ch_free( vi );
 131                         }
 132                 } else {
 133                         valsort_info **prev;
 134
 135                         for (i=0, prev = (valsort_info **)&on->on_bi.bi_private,
 136                                 vi = *prev; vi && i<c->valx;
 137                                 prev = &vi->vi_next, vi = vi->vi_next, i++ );
 138                         (*prev)->vi_next = vi->vi_next;
 139                         ch_free( vi->vi_dn.bv_val );
 140                         ch_free( vi );
 141                 }
 142                 return 0;
 143         }
 144         vitmp.vi_ad = NULL;
 145         i = slap_str2ad( c->argv[1], &vitmp.vi_ad, &text );
 146         if ( i ) {
 147                 sprintf( c->msg, "<%s> %s", c->argv[0], text );
 148                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
 149                         c->log, c->msg, c->argv[1] );
 150                 return(1);
 151         }
 152         ber_str2bv( c->argv[2], 0, 0, &bv );
 153         i = dnNormalize( 0, NULL, NULL, &bv, &vitmp.vi_dn, NULL );
 154         if ( i ) {
 155                 sprintf( c->msg, "<%s> unable to normalize DN", c->argv[0] );
 156                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
 157                         c->log, c->msg, c->argv[2] );
 158                 return(1);
 159         }
 160         i = verb_to_mask( c->argv[3], sorts );
 161         if ( BER_BVISNULL( &sorts[i].word )) {
 162                 sprintf( c->msg, "<%s> unrecognized sort type", c->argv[0] );
 163                 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
 164                         c->log, c->msg, c->argv[3] );
 165                 return(1);
 166         }
 167         vitmp.vi_sort = sorts[i].mask;
 168         if ( sorts[i].mask == VALSORT_WEIGHTED && c->argc == 5 ) {
 169                 i = verb_to_mask( c->argv[4], sorts );
 170                 if ( BER_BVISNULL( &sorts[i].word )) {
 171                         sprintf( c->msg, "<%s> unrecognized sort type", c->argv[0] );
 172                         Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
 173                                 c->log, c->msg, c->argv[4] );
 174                         return(1);
 175                 }
 176                 vitmp.vi_sort |= sorts[i].mask;
 177         }
 178         vi = ch_malloc( sizeof(valsort_info) );
 179         *vi = vitmp;
 180         vi->vi_next = on->on_bi.bi_private;
 181         on->on_bi.bi_private = vi;
 182         return 0;
 183 }
 184
 185 /* Use Insertion Sort algorithm on selected values */
 186 static void
 187 do_sort( Operation *op, Attribute *a, int beg, int num, slap_mask_t sort )
 188 {
 189         int i, j, gotnvals;
 190         struct berval tmp, ntmp, *vals, *nvals;
 191
 192         gotnvals = (a->a_vals != a->a_nvals );
 193
 194         nvals = a->a_nvals + beg;
 195         if ( gotnvals )
 196                 vals = a->a_vals + beg;
 197
 198         if ( sort & VALSORT_NUMERIC ) {
 199                 long *numbers = op->o_tmpalloc( num * sizeof(long), op->o_tmpmemctx ),
 200                         idx;
 201                 for (i=0; i<num; i++)
 202                         numbers[i] = strtol( nvals[i].bv_val, NULL, 0 );
 203
 204                 for (i=1; i<num; i++) {
 205                         idx = numbers[i];
 206                         ntmp = nvals[i];
 207                         if ( gotnvals ) tmp = vals[i];
 208                         j = i;
 209                         while ( j>0 ) {
 210                                 int cmp = (sort & VALSORT_DESCEND) ? numbers[j-1] < idx :
 211                                         numbers[j-1] > idx;
 212                                 if ( !cmp ) break;
 213                                 numbers[j] = numbers[j-1];
 214                                 nvals[j] = nvals[j-1];
 215                                 if ( gotnvals ) vals[j] = vals[j-1];
 216                                 j--;
 217                         }
 218                         numbers[j] = idx;
 219                         nvals[j] = ntmp;
 220                         if ( gotnvals ) vals[j] = tmp;
 221                 }
 222                 op->o_tmpfree( numbers, op->o_tmpmemctx );
 223         } else {
 224                 for (i=1; i<num; i++) {
 225                         ntmp = nvals[i];
 226                         if ( gotnvals ) tmp = vals[i];
 227                         j = i;
 228                         while ( j>0 ) {
 229                                 int cmp = strcmp( nvals[j-1].bv_val, ntmp.bv_val );
 230                                 cmp = (sort & VALSORT_DESCEND) ? (cmp < 0) : (cmp > 0);
 231                                 if ( !cmp ) break;
 232
 233                                 nvals[j] = nvals[j-1];
 234                                 if ( gotnvals ) vals[j] = vals[j-1];
 235                                 j--;
 236                         }
 237                         nvals[j] = ntmp;
 238                         if ( gotnvals ) vals[j] = tmp;
 239                 }
 240         }
 241 }
 242
 243 static int
 244 valsort_response( Operation *op, SlapReply *rs )
 245 {
 246         slap_overinst *on;
 247         valsort_info *vi;
 248         Attribute *a;
 249
 250         /* We only want search responses */
 251         if ( rs->sr_type != REP_SEARCH ) return SLAP_CB_CONTINUE;
 252
 253         on = (slap_overinst *) op->o_bd->bd_info;
 254         vi = on->on_bi.bi_private;
 255
 256         /* And we must have something configured */
 257         if ( !vi ) return SLAP_CB_CONTINUE;
 258
 259         /* Find a rule whose baseDN matches this entry */
 260         for (; vi; vi = vi->vi_next ) {
 261                 int i, n;
 262
 263                 if ( !dnIsSuffix( &rs->sr_entry->e_nname, &vi->vi_dn ))
 264                         continue;
 265
 266                 /* Find attr that this rule affects */
 267                 a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
 268                 if ( !a ) continue;
 269
 270                 if (( rs->sr_flags & ( REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED )) !=
 271                         ( REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED )) {
 272                         rs->sr_entry = entry_dup( rs->sr_entry );
 273                         rs->sr_flags |= REP_ENTRY_MODIFIABLE|REP_ENTRY_MUSTBEFREED;
 274                         a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
 275                 }
 276
 277                 /* count values */
 278                 for ( n = 0; !BER_BVISNULL( &a->a_vals[n] ); n++ );
 279
 280                 if ( vi->vi_sort & VALSORT_WEIGHTED ) {
 281                         int j, gotnvals;
 282                         long *index = op->o_tmpalloc( n * sizeof(long), op->o_tmpmemctx );
 283
 284                         gotnvals = (a->a_vals != a->a_nvals );
 285
 286                         for (i=0; i<n; i++) {
 287                                 char *ptr = strchr( a->a_nvals[i].bv_val, '{' );
 288                                 char *end = NULL;
 289                                 if ( !ptr ) {
 290                                         Debug(LDAP_DEBUG_TRACE, "weights missing from attr %s "
 291                                                 "in entry %s\n", vi->vi_ad->ad_cname.bv_val,
 292                                                 rs->sr_entry->e_name.bv_val, 0 );
 293                                         break;
 294                                 }
 295                                 index[i] = strtol( ptr+1, &end, 0 );
 296                                 if ( *end != '}' ) {
 297                                         Debug(LDAP_DEBUG_TRACE, "weights misformatted "
 298                                                 "in entry %s\n",
 299                                                 rs->sr_entry->e_name.bv_val, 0, 0 );
 300                                         break;
 301                                 }
 302                                 /* Strip out weights */
 303                                 ptr = a->a_nvals[i].bv_val;
 304                                 end++;
 305                                 for (;*end;)
 306                                         *ptr++ = *end++;
 307                                 *ptr = '\0';
 308                                 a->a_nvals[i].bv_len = ptr - a->a_nvals[i].bv_val;
 309
 310                                 if ( a->a_vals != a->a_nvals ) {
 311                                         ptr = a->a_vals[i].bv_val;
 312                                         end = strchr( ptr, '}' ) + 1;
 313                                         for (;*end;)
 314                                                 *ptr++ = *end++;
 315                                         *ptr = '\0';
 316                                         a->a_vals[i].bv_len = ptr - a->a_vals[i].bv_val;
 317                                 }
 318                         }
 319                         /* An attr was missing weights here, ignore it */
 320                         if ( i<n ) {
 321                                 op->o_tmpfree( index, op->o_tmpmemctx );
 322                                 continue;
 323                         }
 324                         /* Insertion sort */
 325                         for ( i=1; i<n; i++) {
 326                                 long idx = index[i];
 327                                 struct berval tmp = a->a_vals[i], ntmp;
 328                                 if ( gotnvals ) ntmp = a->a_nvals[i];
 329                                 j = i;
 330                                 while (( j>0 ) && (index[j-1] > idx )) {
 331                                         index[j] = index[j-1];
 332                                         a->a_vals[j] = a->a_vals[j-1];
 333                                         if ( gotnvals ) a->a_nvals[j] = a->a_nvals[j-1];
 334                                         j--;
 335                                 }
 336                                 index[j] = idx;
 337                                 a->a_vals[j] = tmp;
 338                                 if ( gotnvals ) a->a_nvals[j] = ntmp;
 339                         }
 340                         /* Check for secondary sort */
 341                         if ( vi->vi_sort ^ VALSORT_WEIGHTED ) {
 342                                 for ( i=0; i<n;) {
 343                                         for (j=i+1; j<n; j++) {
 344                                                 if (index[i] != index[j])
 345                                                         break;
 346                                         }
 347                                         if( j-i > 1 )
 348                                                 do_sort( op, a, i, j-i, vi->vi_sort );
 349                                         i = j;
 350                                 }
 351                         }
 352                         op->o_tmpfree( index, op->o_tmpmemctx );
 353                 } else {
 354                         do_sort( op, a, 0, n, vi->vi_sort );
 355                 }
 356         }
 357         return SLAP_CB_CONTINUE;
 358 }
 359
 360 static int
 361 valsort_add( Operation *op, SlapReply *rs )
 362 {
 363         slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
 364         valsort_info *vi = on->on_bi.bi_private;
 365
 366         Attribute *a;
 367         int i;
 368         char *ptr, *end;
 369
 370         /* See if any weighted sorting applies to this entry */
 371         for ( ;vi;vi=vi->vi_next ) {
 372                 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
 373                         continue;
 374                 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
 375                         continue;
 376                 a = attr_find( op->ora_e->e_attrs, vi->vi_ad );
 377                 if ( !a )
 378                         continue;
 379                 for (i=0; !BER_BVISNULL( &a->a_vals[i] ); i++) {
 380                         ptr = strchr(a->a_vals[i].bv_val, '{' );
 381                         if ( !ptr ) {
 382                                 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
 383                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
 384                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
 385                                         "weight missing from attribute" );
 386                                 return rs->sr_err;
 387                         }
 388                         strtol( ptr+1, &end, 0 );
 389                         if ( *end != '}' ) {
 390                                 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
 391                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
 392                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
 393                                         "weight is misformatted" );
 394                                 return rs->sr_err;
 395                         }
 396                 }
 397         }
 398         return SLAP_CB_CONTINUE;
 399 }
 400
 401 static int
 402 valsort_modify( Operation *op, SlapReply *rs )
 403 {
 404         slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
 405         valsort_info *vi = on->on_bi.bi_private;
 406
 407         Modifications *ml;
 408         int i;
 409         char *ptr, *end;
 410
 411         /* See if any weighted sorting applies to this entry */
 412         for ( ;vi;vi=vi->vi_next ) {
 413                 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
 414                         continue;
 415                 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
 416                         continue;
 417                 for (ml = op->orm_modlist; ml; ml=ml->sml_next ) {
 418                         if ( ml->sml_desc == vi->vi_ad )
 419                                 break;
 420                 }
 421                 if ( !ml )
 422                         continue;
 423                 for (i=0; !BER_BVISNULL( &ml->sml_values[i] ); i++) {
 424                         ptr = strchr(ml->sml_values[i].bv_val, '{' );
 425                         if ( !ptr ) {
 426                                 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
 427                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
 428                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
 429                                         "weight missing from attribute" );
 430                                 return rs->sr_err;
 431                         }
 432                         strtol( ptr+1, &end, 0 );
 433                         if ( *end != '}' ) {
 434                                 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
 435                                         vi->vi_ad->ad_cname.bv_val, 0, 0);
 436                                 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
 437                                         "weight is misformatted" );
 438                                 return rs->sr_err;
 439                         }
 440                 }
 441         }
 442         return SLAP_CB_CONTINUE;
 443 }
 444
 445 static int
 446 valsort_destroy(
 447         BackendDB *be
 448 )
 449 {
 450         slap_overinst *on = (slap_overinst *)be->bd_info;
 451         valsort_info *vi = on->on_bi.bi_private, *next;
 452
 453         for (; vi; vi = next) {
 454                 next = vi->vi_next;
 455                 ch_free( vi->vi_dn.bv_val );
 456                 ch_free( vi );
 457         }
 458
 459         return 0;
 460 }
 461
 462 static slap_overinst valsort;
 463
 464 int valsort_init()
 465 {
 466         int i, rc;
 467
 468         valsort.on_bi.bi_type = "valsort";
 469         valsort.on_bi.bi_db_destroy = valsort_destroy;
 470
 471         valsort.on_bi.bi_op_add = valsort_add;
 472         valsort.on_bi.bi_op_modify = valsort_modify;
 473
 474         valsort.on_response = valsort_response;
 475
 476         valsort.on_bi.bi_cf_ocs = valsort_cfocs;
 477
 478         rc = config_register_schema( valsort_cfats, valsort_cfocs );
 479         if ( rc ) return rc;
 480
 481         return overlay_register(&valsort);
 482 }
 483
 484 #if SLAPD_OVER_VALSORT == SLAPD_MOD_DYNAMIC
 485 int init_module( int argc, char *argv[]) {
 486         return valsort_init();
 487 }
 488 #endif
 489
 490 #endif /* SLAPD_OVER_VALSORT */