1/* sort.c -- LDAP library entry and value sort routines */
2/* $OpenLDAP$ */
3/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 1998-2011 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
39struct entrything {
40	char		**et_vals;
41	LDAPMessage	*et_msg;
42	int 		(*et_cmp_fn) LDAP_P((const char *a, const char *b));
43};
44
45static int	et_cmp LDAP_P(( const void *aa, const void *bb));
46
47
48int
49ldap_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
57static int
58et_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
87int
88ldap_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
168int
169ldap_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