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