external/bsd/openldap/dist/libraries/libldap/sort.c

   1 /* sort.c -- LDAP library entry and value sort routines */
   2 /* $OpenLDAP: pkg/ldap/libraries/libldap/sort.c,v 1.27.2.4 2008/02/11 23:26:41 kurt Exp $ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 1998-2008 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16 /* Portions Copyright (c) 1994 Regents of the University of Michigan.
  17  * All rights reserved.
  18  *
  19  * Redistribution and use in source and binary forms are permitted
  20  * provided that this notice is preserved and that due credit is given
  21  * to the University of Michigan at Ann Arbor. The name of the University
  22  * may not be used to endorse or promote products derived from this
  23  * software without specific prior written permission. This software
  24  * is provided ``as is'' without express or implied warranty.
  25  */
  26
  27 #include "portable.h"
  28
  29 #include <stdio.h>
  30 #include <ac/stdlib.h>
  31
  32 #include <ac/ctype.h>
  33 #include <ac/string.h>
  34 #include <ac/time.h>
  35
  36
  37 #include "ldap-int.h"
  38
  39 struct entrything {
  40         char            **et_vals;
  41         LDAPMessage     *et_msg;
  42         int             (*et_cmp_fn) LDAP_P((const char *a, const char *b));
  43 };
  44
  45 static int      et_cmp LDAP_P(( const void *aa, const void *bb));
  46
  47
  48 int
  49 ldap_sort_strcasecmp(
  50         LDAP_CONST void *a,
  51         LDAP_CONST void *b
  52 )
  53 {
  54         return( strcasecmp( *(char *const *)a, *(char *const *)b ) );
  55 }
  56
  57 static int
  58 et_cmp(
  59         const void      *aa,
  60         const void      *bb
  61 )
  62 {
  63         int                     i, rc;
  64         const struct entrything *a = (const struct entrything *)aa;
  65         const struct entrything *b = (const struct entrything *)bb;
  66
  67         if ( a->et_vals == NULL && b->et_vals == NULL )
  68                 return( 0 );
  69         if ( a->et_vals == NULL )
  70                 return( -1 );
  71         if ( b->et_vals == NULL )
  72                 return( 1 );
  73
  74         for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
  75                 if ( (rc = a->et_cmp_fn( a->et_vals[i], b->et_vals[i] )) != 0 ) {
  76                         return( rc );
  77                 }
  78         }
  79
  80         if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
  81                 return( 0 );
  82         if ( a->et_vals[i] == NULL )
  83                 return( -1 );
  84         return( 1 );
  85 }
  86
  87 int
  88 ldap_sort_entries(
  89     LDAP        *ld,
  90     LDAPMessage **chain,
  91     LDAP_CONST char     *attr,          /* NULL => sort by DN */
  92     int         (*cmp) (LDAP_CONST  char *, LDAP_CONST char *)
  93 )
  94 {
  95         int                     i, count = 0;
  96         struct entrything       *et;
  97         LDAPMessage             *e, *ehead = NULL, *etail = NULL;
  98         LDAPMessage             *ohead = NULL, *otail = NULL;
  99         LDAPMessage             **ep;
 100
 101         assert( ld != NULL );
 102
 103         /* Separate entries from non-entries */
 104         for ( e = *chain; e; e=e->lm_chain ) {
 105                 if ( e->lm_msgtype == LDAP_RES_SEARCH_ENTRY ) {
 106                         count++;
 107                         if ( !ehead ) ehead = e;
 108                         if ( etail ) etail->lm_chain = e;
 109                         etail = e;
 110                 } else {
 111                         if ( !ohead ) ohead = e;
 112                         if ( otail ) otail->lm_chain = e;
 113                         otail = e;
 114                 }
 115         }
 116
 117         if ( count < 2 ) {
 118                 /* zero or one entries -- already sorted! */
 119                 if ( ehead ) {
 120                         etail->lm_chain = ohead;
 121                         *chain = ehead;
 122                 } else {
 123                         *chain = ohead;
 124                 }
 125                 return 0;
 126         }
 127
 128         if ( (et = (struct entrything *) LDAP_MALLOC( count *
 129             sizeof(struct entrything) )) == NULL ) {
 130                 ld->ld_errno = LDAP_NO_MEMORY;
 131                 return( -1 );
 132         }
 133
 134         e = ehead;
 135         for ( i = 0; i < count; i++ ) {
 136                 et[i].et_cmp_fn = cmp;
 137                 et[i].et_msg = e;
 138                 if ( attr == NULL ) {
 139                         char    *dn;
 140
 141                         dn = ldap_get_dn( ld, e );
 142                         et[i].et_vals = ldap_explode_dn( dn, 1 );
 143                         LDAP_FREE( dn );
 144                 } else {
 145                         et[i].et_vals = ldap_get_values( ld, e, attr );
 146                 }
 147
 148                 e = e->lm_chain;
 149         }
 150
 151         qsort( et, count, sizeof(struct entrything), et_cmp );
 152
 153         ep = chain;
 154         for ( i = 0; i < count; i++ ) {
 155                 *ep = et[i].et_msg;
 156                 ep = &(*ep)->lm_chain;
 157
 158                 LDAP_VFREE( et[i].et_vals );
 159         }
 160         *ep = ohead;
 161         (*chain)->lm_chain_tail = otail ? otail : etail;
 162
 163         LDAP_FREE( (char *) et );
 164
 165         return( 0 );
 166 }
 167
 168 int
 169 ldap_sort_values(
 170     LDAP        *ld,
 171     char        **vals,
 172     int         (*cmp) (LDAP_CONST void *, LDAP_CONST void *)
 173 )
 174 {
 175         int     nel;
 176
 177         for ( nel = 0; vals[nel] != NULL; nel++ )
 178                 ;       /* NULL */
 179
 180         qsort( vals, nel, sizeof(char *), cmp );
 181
 182         return( 0 );
 183 }