sort.c revision 1.1.1.7 
1/*	$NetBSD: sort.c,v 1.1.1.7 2019/08/08 13:31:15 christos Exp $	*/
2
3/* sort.c -- LDAP library entry and value sort routines */
4/* $OpenLDAP$ */
5/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 1998-2019 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 <sys/cdefs.h>
30__RCSID("$NetBSD: sort.c,v 1.1.1.7 2019/08/08 13:31:15 christos Exp $");
31
32#include "portable.h"
33
34#include <stdio.h>
35#include <ac/stdlib.h>
36
37#include <ac/ctype.h>
38#include <ac/string.h>
39#include <ac/time.h>
40
41
42#include "ldap-int.h"
43
44struct entrything {
45	char		**et_vals;
46	LDAPMessage	*et_msg;
47	int 		(*et_cmp_fn) LDAP_P((const char *a, const char *b));
48};
49
50static int	et_cmp LDAP_P(( const void *aa, const void *bb));
51
52
53int
54ldap_sort_strcasecmp(
55	LDAP_CONST void	*a,
56	LDAP_CONST void	*b
57)
58{
59	return( strcasecmp( *(char *const *)a, *(char *const *)b ) );
60}
61
62static int
63et_cmp(
64	const void	*aa,
65	const void	*bb
66)
67{
68	int			i, rc;
69	const struct entrything	*a = (const struct entrything *)aa;
70	const struct entrything	*b = (const struct entrything *)bb;
71
72	if ( a->et_vals == NULL && b->et_vals == NULL )
73		return( 0 );
74	if ( a->et_vals == NULL )
75		return( -1 );
76	if ( b->et_vals == NULL )
77		return( 1 );
78
79	for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
80		if ( (rc = a->et_cmp_fn( a->et_vals[i], b->et_vals[i] )) != 0 ) {
81			return( rc );
82		}
83	}
84
85	if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
86		return( 0 );
87	if ( a->et_vals[i] == NULL )
88		return( -1 );
89	return( 1 );
90}
91
92int
93ldap_sort_entries(
94    LDAP	*ld,
95    LDAPMessage	**chain,
96    LDAP_CONST char	*attr,		/* NULL => sort by DN */
97    int		(*cmp) (LDAP_CONST  char *, LDAP_CONST char *)
98)
99{
100	int			i, count = 0;
101	struct entrything	*et;
102	LDAPMessage		*e, *ehead = NULL, *etail = NULL;
103	LDAPMessage		*ohead = NULL, *otail = NULL;
104	LDAPMessage		**ep;
105
106	assert( ld != NULL );
107
108	/* Separate entries from non-entries */
109	for ( e = *chain; e; e=e->lm_chain ) {
110		if ( e->lm_msgtype == LDAP_RES_SEARCH_ENTRY ) {
111			count++;
112			if ( !ehead ) ehead = e;
113			if ( etail ) etail->lm_chain = e;
114			etail = e;
115		} else {
116			if ( !ohead ) ohead = e;
117			if ( otail ) otail->lm_chain = e;
118			otail = e;
119		}
120	}
121
122	if ( count < 2 ) {
123		/* zero or one entries -- already sorted! */
124		if ( ehead ) {
125			etail->lm_chain = ohead;
126			*chain = ehead;
127		} else {
128			*chain = ohead;
129		}
130		return 0;
131	}
132
133	if ( (et = (struct entrything *) LDAP_MALLOC( count *
134	    sizeof(struct entrything) )) == NULL ) {
135		ld->ld_errno = LDAP_NO_MEMORY;
136		return( -1 );
137	}
138
139	e = ehead;
140	for ( i = 0; i < count; i++ ) {
141		et[i].et_cmp_fn = cmp;
142		et[i].et_msg = e;
143		if ( attr == NULL ) {
144			char	*dn;
145
146			dn = ldap_get_dn( ld, e );
147			et[i].et_vals = ldap_explode_dn( dn, 1 );
148			LDAP_FREE( dn );
149		} else {
150			et[i].et_vals = ldap_get_values( ld, e, attr );
151		}
152
153		e = e->lm_chain;
154	}
155
156	qsort( et, count, sizeof(struct entrything), et_cmp );
157
158	ep = chain;
159	for ( i = 0; i < count; i++ ) {
160		*ep = et[i].et_msg;
161		ep = &(*ep)->lm_chain;
162
163		LDAP_VFREE( et[i].et_vals );
164	}
165	*ep = ohead;
166	(*chain)->lm_chain_tail = otail ? otail : etail;
167
168	LDAP_FREE( (char *) et );
169
170	return( 0 );
171}
172
173int
174ldap_sort_values(
175    LDAP	*ld,
176    char	**vals,
177    int		(*cmp) (LDAP_CONST void *, LDAP_CONST void *)
178)
179{
180	int	nel;
181
182	for ( nel = 0; vals[nel] != NULL; nel++ )
183		;	/* NULL */
184
185	qsort( vals, nel, sizeof(char *), cmp );
186
187	return( 0 );
188}
189