sort.c revision 1.1.1.2
1193323Sed/* $NetBSD: sort.c,v 1.1.1.2 2010/03/08 02:14:20 lukem Exp $ */ 2193323Sed 3193323Sed/* sort.c -- LDAP library entry and value sort routines */ 4193323Sed/* OpenLDAP: pkg/ldap/libraries/libldap/sort.c,v 1.27.2.5 2009/01/22 00:00:55 kurt Exp */ 5193323Sed/* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6193323Sed * 7193323Sed * Copyright 1998-2009 The OpenLDAP Foundation. 8193323Sed * All rights reserved. 9193323Sed * 10193323Sed * Redistribution and use in source and binary forms, with or without 11193323Sed * modification, are permitted only as authorized by the OpenLDAP 12193323Sed * Public License. 13193323Sed * 14193323Sed * A copy of this license is available in the file LICENSE in the 15193323Sed * top-level directory of the distribution or, alternatively, at 16193323Sed * <http://www.OpenLDAP.org/license.html>. 17193323Sed */ 18193323Sed/* Portions Copyright (c) 1994 Regents of the University of Michigan. 19218893Sdim * All rights reserved. 20193323Sed * 21198090Srdivacky * Redistribution and use in source and binary forms are permitted 22198090Srdivacky * provided that this notice is preserved and that due credit is given 23193323Sed * to the University of Michigan at Ann Arbor. The name of the University 24193323Sed * may not be used to endorse or promote products derived from this 25193323Sed * software without specific prior written permission. This software 26193323Sed * is provided ``as is'' without express or implied warranty. 27193323Sed */ 28193323Sed 29193323Sed#include "portable.h" 30193323Sed 31193323Sed#include <stdio.h> 32193323Sed#include <ac/stdlib.h> 33193323Sed 34193323Sed#include <ac/ctype.h> 35193323Sed#include <ac/string.h> 36193323Sed#include <ac/time.h> 37193323Sed 38193323Sed 39193323Sed#include "ldap-int.h" 40193323Sed 41193323Sedstruct entrything { 42193323Sed char **et_vals; 43193323Sed LDAPMessage *et_msg; 44193323Sed int (*et_cmp_fn) LDAP_P((const char *a, const char *b)); 45193323Sed}; 46193323Sed 47193323Sedstatic int et_cmp LDAP_P(( const void *aa, const void *bb)); 48193323Sed 49193323Sed 50193323Sedint 51193323Sedldap_sort_strcasecmp( 52193323Sed LDAP_CONST void *a, 53193323Sed LDAP_CONST void *b 54193323Sed) 55193323Sed{ 56193323Sed return( strcasecmp( *(char *const *)a, *(char *const *)b ) ); 57193323Sed} 58193323Sed 59193323Sedstatic int 60193323Sedet_cmp( 61193323Sed const void *aa, 62193323Sed const void *bb 63193323Sed) 64193323Sed{ 65193323Sed int i, rc; 66193323Sed const struct entrything *a = (const struct entrything *)aa; 67193323Sed const struct entrything *b = (const struct entrything *)bb; 68193323Sed 69193323Sed if ( a->et_vals == NULL && b->et_vals == NULL ) 70193323Sed return( 0 ); 71193323Sed if ( a->et_vals == NULL ) 72193323Sed return( -1 ); 73193323Sed if ( b->et_vals == NULL ) 74193323Sed return( 1 ); 75193323Sed 76193323Sed for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) { 77193323Sed if ( (rc = a->et_cmp_fn( a->et_vals[i], b->et_vals[i] )) != 0 ) { 78193323Sed return( rc ); 79193323Sed } 80193323Sed } 81193323Sed 82193323Sed if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL ) 83193323Sed return( 0 ); 84193323Sed if ( a->et_vals[i] == NULL ) 85193323Sed return( -1 ); 86193323Sed return( 1 ); 87193323Sed} 88193323Sed 89193323Sedint 90224145Sdimldap_sort_entries( 91193323Sed LDAP *ld, 92193323Sed LDAPMessage **chain, 93193323Sed LDAP_CONST char *attr, /* NULL => sort by DN */ 94193323Sed int (*cmp) (LDAP_CONST char *, LDAP_CONST char *) 95193323Sed) 96193323Sed{ 97193323Sed int i, count = 0; 98193323Sed struct entrything *et; 99193323Sed LDAPMessage *e, *ehead = NULL, *etail = NULL; 100193323Sed LDAPMessage *ohead = NULL, *otail = NULL; 101193323Sed LDAPMessage **ep; 102193323Sed 103193323Sed assert( ld != NULL ); 104193323Sed 105193323Sed /* Separate entries from non-entries */ 106193323Sed for ( e = *chain; e; e=e->lm_chain ) { 107193323Sed if ( e->lm_msgtype == LDAP_RES_SEARCH_ENTRY ) { 108193323Sed count++; 109193323Sed if ( !ehead ) ehead = e; 110193323Sed if ( etail ) etail->lm_chain = e; 111193323Sed etail = e; 112193323Sed } else { 113193323Sed if ( !ohead ) ohead = e; 114193323Sed if ( otail ) otail->lm_chain = e; 115193323Sed otail = e; 116193323Sed } 117193323Sed } 118193323Sed 119193323Sed if ( count < 2 ) { 120193323Sed /* zero or one entries -- already sorted! */ 121193323Sed if ( ehead ) { 122193323Sed etail->lm_chain = ohead; 123193323Sed *chain = ehead; 124193323Sed } else { 125193323Sed *chain = ohead; 126193323Sed } 127193323Sed return 0; 128193323Sed } 129193323Sed 130193323Sed if ( (et = (struct entrything *) LDAP_MALLOC( count * 131193323Sed sizeof(struct entrything) )) == NULL ) { 132193323Sed ld->ld_errno = LDAP_NO_MEMORY; 133193323Sed return( -1 ); 134193323Sed } 135193323Sed 136193323Sed e = ehead; 137193323Sed for ( i = 0; i < count; i++ ) { 138193323Sed et[i].et_cmp_fn = cmp; 139193323Sed et[i].et_msg = e; 140193323Sed if ( attr == NULL ) { 141193323Sed char *dn; 142193323Sed 143193323Sed dn = ldap_get_dn( ld, e ); 144193323Sed et[i].et_vals = ldap_explode_dn( dn, 1 ); 145193323Sed LDAP_FREE( dn ); 146193323Sed } else { 147193323Sed et[i].et_vals = ldap_get_values( ld, e, attr ); 148193323Sed } 149193323Sed 150193323Sed e = e->lm_chain; 151193323Sed } 152193323Sed 153193323Sed qsort( et, count, sizeof(struct entrything), et_cmp ); 154193323Sed 155193323Sed ep = chain; 156193323Sed for ( i = 0; i < count; i++ ) { 157193323Sed *ep = et[i].et_msg; 158193323Sed ep = &(*ep)->lm_chain; 159193323Sed 160193323Sed LDAP_VFREE( et[i].et_vals ); 161193323Sed } 162193323Sed *ep = ohead; 163193323Sed (*chain)->lm_chain_tail = otail ? otail : etail; 164193323Sed 165193323Sed LDAP_FREE( (char *) et ); 166193323Sed 167193323Sed return( 0 ); 168193323Sed} 169193323Sed 170193323Sedint 171193323Sedldap_sort_values( 172193323Sed LDAP *ld, 173193323Sed char **vals, 174193323Sed int (*cmp) (LDAP_CONST void *, LDAP_CONST void *) 175193323Sed) 176193323Sed{ 177193323Sed int nel; 178193323Sed 179193323Sed for ( nel = 0; vals[nel] != NULL; nel++ ) 180193323Sed ; /* NULL */ 181193323Sed 182193323Sed qsort( vals, nel, sizeof(char *), cmp ); 183193323Sed 184193323Sed return( 0 ); 185193323Sed} 186193323Sed