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 } 184