Back to index

lightning-sunbird  0.9+nobinonly
sort.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is Mozilla Communicator client code, released
00015  * March 31, 1998.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998-1999
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 /*
00038  * Copyright (c) 1994 Regents of the University of Michigan.
00039  * All rights reserved.
00040  *
00041  * Redistribution and use in source and binary forms are permitted
00042  * provided that this notice is preserved and that due credit is given
00043  * to the University of Michigan at Ann Arbor. The name of the University
00044  * may not be used to endorse or promote products derived from this
00045  * software without specific prior written permission. This software
00046  * is provided ``as is'' without express or implied warranty.
00047  */
00048 /*
00049  * sort.c:  LDAP library entry and value sort routines
00050  */
00051 
00052 #include "ldap-int.h"
00053 
00054 /* This xp_qsort fixes a memory problem (ABR) on Solaris for the client.
00055  * Server is welcome to use it too, but I wasn't sure if it
00056  * would be ok to use XP code here.  -slamm
00057  *
00058  * We don't want to require use of libxp when linking with libldap, so
00059  * I'll leave use of xp_qsort as a MOZILLA_CLIENT-only thing for now. --mcs
00060  */
00061 #if defined(MOZILLA_CLIENT) && defined(SOLARIS)
00062 #include "xp_qsort.h"
00063 #else
00064 #define XP_QSORT qsort
00065 #endif
00066 
00067 typedef struct keycmp {
00068     void                 *kc_arg;
00069     LDAP_KEYCMP_CALLBACK *kc_cmp;
00070 } keycmp_t;
00071 
00072 typedef struct keything {
00073     keycmp_t            *kt_cmp;
00074     const struct berval *kt_key;
00075     LDAPMessage         *kt_msg;
00076 } keything_t;
00077 
00078 static int LDAP_C LDAP_CALLBACK
00079 ldapi_keycmp( const void *Lv, const void *Rv )
00080 {
00081     auto keything_t **L = (keything_t**)Lv;
00082     auto keything_t **R = (keything_t**)Rv;
00083     auto keycmp_t *cmp = (*L)->kt_cmp;
00084     return cmp->kc_cmp( cmp->kc_arg, (*L)->kt_key, (*R)->kt_key );
00085 }
00086 
00087 int
00088 LDAP_CALL
00089 ldap_keysort_entries(
00090     LDAP        *ld,
00091     LDAPMessage **chain,
00092     void                  *arg,
00093     LDAP_KEYGEN_CALLBACK  *gen,
00094     LDAP_KEYCMP_CALLBACK  *cmp,
00095     LDAP_KEYFREE_CALLBACK *fre)
00096 {
00097        size_t        count, i;
00098        keycmp_t      kc = {0};
00099        keything_t    **kt;
00100        LDAPMessage   *e, *last;
00101        LDAPMessage   **ep;
00102 
00103        if ( !NSLDAPI_VALID_LDAP_POINTER( ld )
00104            || chain == NULL || cmp == NULL ) {
00105               return( LDAP_PARAM_ERROR );
00106        }
00107 
00108        count = ldap_count_entries( ld, *chain );
00109 
00110        kt = (keything_t**)NSLDAPI_MALLOC( count * (sizeof(keything_t*) + sizeof(keything_t)) );
00111        if ( kt == NULL ) {
00112               LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
00113               return( -1 );
00114        }
00115        for ( i = 0; i < count; i++ ) {
00116               kt[i] = i + (keything_t*)(kt + count);
00117        }
00118        kc.kc_arg = arg;
00119        kc.kc_cmp = cmp;
00120 
00121        for ( e = *chain, i = 0; i < count; i++, e = e->lm_chain ) {
00122               kt[i]->kt_msg = e;
00123               kt[i]->kt_cmp = &kc;
00124               kt[i]->kt_key = gen( arg, ld, e );
00125               if ( kt[i]->kt_key == NULL ) {
00126                      if ( fre ) while ( i-- > 0 ) fre( arg, kt[i]->kt_key );
00127                      NSLDAPI_FREE( (char*)kt );
00128                      LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
00129                      return( -1 );
00130               }
00131        }
00132        last = e;
00133 
00134        XP_QSORT( (void*)kt, count, (size_t)sizeof(keything_t*), ldapi_keycmp );
00135     
00136        ep = chain;
00137        for ( i = 0; i < count; i++ ) {
00138               *ep = kt[i]->kt_msg;
00139               ep = &(*ep)->lm_chain;
00140               if ( fre ) fre( arg, kt[i]->kt_key );
00141        }
00142        *ep = last;
00143        NSLDAPI_FREE( (char*)kt );
00144        return( 0 );
00145 }
00146 
00147 
00148 struct entrything {
00149        char          **et_vals;
00150        LDAPMessage   *et_msg;
00151 };
00152 
00153 typedef int (LDAP_C LDAP_CALLBACK LDAP_CHARCMP_CALLBACK)(char*, char*);
00154 typedef int (LDAP_C LDAP_CALLBACK LDAP_VOIDCMP_CALLBACK)(const void*, 
00155        const void*);
00156 
00157 static LDAP_CHARCMP_CALLBACK *et_cmp_fn;
00158 static LDAP_VOIDCMP_CALLBACK et_cmp;
00159 
00160 int
00161 LDAP_C
00162 LDAP_CALLBACK
00163 ldap_sort_strcasecmp(
00164     const char       **a,
00165     const char       **b
00166 )
00167 {
00168     /* XXXceb
00169      * I am not 100% sure this is the way this should be handled.  
00170      * For now we will return a 0 on invalid.
00171      */    
00172     if (NULL == a || NULL == b)
00173         return (0);
00174        return( strcasecmp( (char *)*a, (char *)*b ) );
00175 }
00176 
00177 static int
00178 LDAP_C
00179 LDAP_CALLBACK
00180 et_cmp(
00181     const void       *aa,
00182     const void       *bb
00183 )
00184 {
00185        int                  i, rc;
00186        struct entrything    *a = (struct entrything *)aa;
00187        struct entrything    *b = (struct entrything *)bb;
00188 
00189        if ( a->et_vals == NULL && b->et_vals == NULL )
00190               return( 0 );
00191        if ( a->et_vals == NULL )
00192               return( -1 );
00193        if ( b->et_vals == NULL )
00194               return( 1 );
00195 
00196        for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
00197               if ( (rc = (*et_cmp_fn)( a->et_vals[i], b->et_vals[i] ))
00198                   != 0 ) {
00199                      return( rc );
00200               }
00201        }
00202 
00203        if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
00204               return( 0 );
00205        if ( a->et_vals[i] == NULL )
00206               return( -1 );
00207        return( 1 );
00208 }
00209 
00210 int
00211 LDAP_CALL
00212 ldap_multisort_entries(
00213     LDAP      *ld,
00214     LDAPMessage      **chain,
00215     char      **attr,              /* NULL => sort by DN */
00216     LDAP_CMP_CALLBACK *cmp
00217 )
00218 {
00219        int                  i, count;
00220        struct entrything    *et;
00221        LDAPMessage          *e, *last;
00222        LDAPMessage          **ep;
00223 
00224        if ( !NSLDAPI_VALID_LDAP_POINTER( ld )
00225            || chain == NULL || cmp == NULL ) {
00226               return( LDAP_PARAM_ERROR );
00227        }
00228 
00229        count = ldap_count_entries( ld, *chain );
00230 
00231        if ( (et = (struct entrything *)NSLDAPI_MALLOC( count *
00232            sizeof(struct entrything) )) == NULL ) {
00233               LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
00234               return( -1 );
00235        }
00236 
00237        e = *chain;
00238        for ( i = 0; i < count; i++ ) {
00239               et[i].et_msg = e;
00240               et[i].et_vals = NULL;
00241               if ( attr == NULL ) {
00242                      char   *dn;
00243 
00244                      dn = ldap_get_dn( ld, e );
00245                      et[i].et_vals = ldap_explode_dn( dn, 1 );
00246                      NSLDAPI_FREE( dn );
00247               } else {
00248                      int    attrcnt;
00249                      char   **vals;
00250 
00251                      for ( attrcnt = 0; attr[attrcnt] != NULL; attrcnt++ ) {
00252                          vals = ldap_get_values( ld, e, attr[attrcnt] );
00253                          if ( ldap_charray_merge( &(et[i].et_vals), vals )
00254                             != 0 ) {
00255                             int    j;
00256 
00257                             /* XXX risky: ldap_value_free( vals ); */
00258                             for ( j = 0; j <= i; j++ )
00259                                 ldap_value_free( et[j].et_vals );
00260                             NSLDAPI_FREE( (char *) et );
00261                             LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, 
00262                                 NULL );
00263                             return( -1 );
00264                          }
00265                          if ( vals != NULL ) {
00266                             NSLDAPI_FREE( (char *)vals );
00267                          }
00268                      }
00269               }
00270 
00271               e = e->lm_chain;
00272        }
00273        last = e;
00274 
00275        et_cmp_fn = (LDAP_CHARCMP_CALLBACK *)cmp;
00276        XP_QSORT( (void *) et, (size_t) count,
00277               (size_t) sizeof(struct entrything), et_cmp );
00278 
00279        ep = chain;
00280        for ( i = 0; i < count; i++ ) {
00281               *ep = et[i].et_msg;
00282               ep = &(*ep)->lm_chain;
00283 
00284               ldap_value_free( et[i].et_vals );
00285        }
00286        *ep = last;
00287        NSLDAPI_FREE( (char *) et );
00288 
00289        return( 0 );
00290 }
00291 
00292 int
00293 LDAP_CALL
00294 ldap_sort_entries(
00295     LDAP      *ld,
00296     LDAPMessage      **chain,
00297     char      *attr,        /* NULL => sort by DN */
00298     LDAP_CMP_CALLBACK *cmp
00299 )
00300 {
00301        char   *attrs[2];
00302 
00303        attrs[0] = attr;
00304        attrs[1] = NULL;
00305        return( ldap_multisort_entries( ld, chain, attr ? attrs : NULL, cmp ) );
00306 }
00307 
00308 int
00309 LDAP_CALL
00310 ldap_sort_values(
00311     LDAP      *ld,
00312     char      **vals,
00313     LDAP_VALCMP_CALLBACK *cmp
00314 )
00315 {
00316        int    nel;
00317 
00318        if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cmp == NULL ) {
00319               return( LDAP_PARAM_ERROR );
00320        }
00321 
00322     if ( NULL == vals) 
00323     {
00324               LDAP_SET_LDERRNO( ld, LDAP_PARAM_ERROR, NULL, NULL );
00325               return( LDAP_PARAM_ERROR );
00326        }
00327        for ( nel = 0; vals[nel] != NULL; nel++ )
00328               ;      /* NULL */
00329 
00330        XP_QSORT( vals, nel, sizeof(char *), (LDAP_VOIDCMP_CALLBACK *)cmp );
00331 
00332        return( LDAP_SUCCESS );
00333 }