Back to index

openldap  2.4.31
sort.c
Go to the documentation of this file.
00001 /* sort.c -- LDAP library entry and value sort routines */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 1998-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 /* Portions Copyright (c) 1994 Regents of the University of Michigan.
00017  * All rights reserved.
00018  *
00019  * Redistribution and use in source and binary forms are permitted
00020  * provided that this notice is preserved and that due credit is given
00021  * to the University of Michigan at Ann Arbor. The name of the University
00022  * may not be used to endorse or promote products derived from this
00023  * software without specific prior written permission. This software
00024  * is provided ``as is'' without express or implied warranty.
00025  */
00026 
00027 #include "portable.h"
00028 
00029 #include <stdio.h>
00030 #include <ac/stdlib.h>
00031 
00032 #include <ac/ctype.h>
00033 #include <ac/string.h>
00034 #include <ac/time.h>
00035 
00036 
00037 #include "ldap-int.h"
00038 
00039 struct entrything {
00040        char          **et_vals;
00041        LDAPMessage   *et_msg;
00042        int           (*et_cmp_fn) LDAP_P((const char *a, const char *b));
00043 };
00044 
00045 static int    et_cmp LDAP_P(( const void *aa, const void *bb));
00046 
00047 
00048 int
00049 ldap_sort_strcasecmp(
00050        LDAP_CONST void      *a,
00051        LDAP_CONST void      *b
00052 )
00053 {
00054        return( strcasecmp( *(char *const *)a, *(char *const *)b ) );
00055 }
00056 
00057 static int
00058 et_cmp(
00059        const void    *aa,
00060        const void    *bb
00061 )
00062 {
00063        int                  i, rc;
00064        const struct entrything     *a = (const struct entrything *)aa;
00065        const struct entrything     *b = (const struct entrything *)bb;
00066 
00067        if ( a->et_vals == NULL && b->et_vals == NULL )
00068               return( 0 );
00069        if ( a->et_vals == NULL )
00070               return( -1 );
00071        if ( b->et_vals == NULL )
00072               return( 1 );
00073 
00074        for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
00075               if ( (rc = a->et_cmp_fn( a->et_vals[i], b->et_vals[i] )) != 0 ) {
00076                      return( rc );
00077               }
00078        }
00079 
00080        if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
00081               return( 0 );
00082        if ( a->et_vals[i] == NULL )
00083               return( -1 );
00084        return( 1 );
00085 }
00086 
00087 int
00088 ldap_sort_entries(
00089     LDAP      *ld,
00090     LDAPMessage      **chain,
00091     LDAP_CONST char  *attr,        /* NULL => sort by DN */
00092     int              (*cmp) (LDAP_CONST  char *, LDAP_CONST char *)
00093 )
00094 {
00095        int                  i, count = 0;
00096        struct entrything    *et;
00097        LDAPMessage          *e, *ehead = NULL, *etail = NULL;
00098        LDAPMessage          *ohead = NULL, *otail = NULL;
00099        LDAPMessage          **ep;
00100 
00101        assert( ld != NULL );
00102 
00103        /* Separate entries from non-entries */
00104        for ( e = *chain; e; e=e->lm_chain ) {
00105               if ( e->lm_msgtype == LDAP_RES_SEARCH_ENTRY ) {
00106                      count++;
00107                      if ( !ehead ) ehead = e;
00108                      if ( etail ) etail->lm_chain = e;
00109                      etail = e;
00110               } else {
00111                      if ( !ohead ) ohead = e;
00112                      if ( otail ) otail->lm_chain = e;
00113                      otail = e;
00114               }
00115        }
00116 
00117        if ( count < 2 ) {
00118               /* zero or one entries -- already sorted! */
00119               if ( ehead ) {
00120                      etail->lm_chain = ohead;
00121                      *chain = ehead;
00122               } else {
00123                      *chain = ohead;
00124               }
00125               return 0;
00126        }
00127 
00128        if ( (et = (struct entrything *) LDAP_MALLOC( count *
00129            sizeof(struct entrything) )) == NULL ) {
00130               ld->ld_errno = LDAP_NO_MEMORY;
00131               return( -1 );
00132        }
00133 
00134        e = ehead;
00135        for ( i = 0; i < count; i++ ) {
00136               et[i].et_cmp_fn = cmp;
00137               et[i].et_msg = e;
00138               if ( attr == NULL ) {
00139                      char   *dn;
00140 
00141                      dn = ldap_get_dn( ld, e );
00142                      et[i].et_vals = ldap_explode_dn( dn, 1 );
00143                      LDAP_FREE( dn );
00144               } else {
00145                      et[i].et_vals = ldap_get_values( ld, e, attr );
00146               }
00147 
00148               e = e->lm_chain;
00149        }
00150 
00151        qsort( et, count, sizeof(struct entrything), et_cmp );
00152 
00153        ep = chain;
00154        for ( i = 0; i < count; i++ ) {
00155               *ep = et[i].et_msg;
00156               ep = &(*ep)->lm_chain;
00157 
00158               LDAP_VFREE( et[i].et_vals );
00159        }
00160        *ep = ohead;
00161        (*chain)->lm_chain_tail = otail ? otail : etail;
00162 
00163        LDAP_FREE( (char *) et );
00164 
00165        return( 0 );
00166 }
00167 
00168 int
00169 ldap_sort_values(
00170     LDAP      *ld,
00171     char      **vals,
00172     int              (*cmp) (LDAP_CONST void *, LDAP_CONST void *)
00173 )
00174 {
00175        int    nel;
00176 
00177        for ( nel = 0; vals[nel] != NULL; nel++ )
00178               ;      /* NULL */
00179 
00180        qsort( vals, nel, sizeof(char *), cmp );
00181 
00182        return( 0 );
00183 }