xref: /illumos-gate/usr/src/lib/libldap5/sources/ldap/common/sort.c (revision 55fea89dcaa64928bed4327112404dcb3e07b79f)
1 /*
2  * The contents of this file are subject to the Netscape Public
3  * License Version 1.1 (the "License"); you may not use this file
4  * except in compliance with the License. You may obtain a copy of
5  * the License at http://www.mozilla.org/NPL/
6  *
7  * Software distributed under the License is distributed on an "AS
8  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
9  * implied. See the License for the specific language governing
10  * rights and limitations under the License.
11  *
12  * The Original Code is Mozilla Communicator client code, released
13  * March 31, 1998.
14  *
15  * The Initial Developer of the Original Code is Netscape
16  * Communications Corporation. Portions created by Netscape are
17  * Copyright (C) 1998-1999 Netscape Communications Corporation. All
18  * Rights Reserved.
19  *
20  * Contributor(s):
21  */
22 /*
23  * Copyright (c) 1994 Regents of the University of Michigan.
24  * All rights reserved.
25  *
26  * Redistribution and use in source and binary forms are permitted
27  * provided that this notice is preserved and that due credit is given
28  * to the University of Michigan at Ann Arbor. The name of the University
29  * may not be used to endorse or promote products derived from this
30  * software without specific prior written permission. This software
31  * is provided ``as is'' without express or implied warranty.
32  */
33 /*
34  * sort.c:  LDAP library entry and value sort routines
35  */
36 
37 #include "ldap-int.h"
38 
39 /* This xp_qsort fixes a memory problem (ABR) on Solaris for the client.
40  * Server is welcome to use it too, but I wasn't sure if it
41  * would be ok to use XP code here.  -slamm
42  *
43  * We don't want to require use of libxp when linking with libldap, so
44  * I'll leave use of xp_qsort as a MOZILLA_CLIENT-only thing for now. --mcs
45  */
46 #if defined(MOZILLA_CLIENT) && defined(SOLARIS)
47 #include "xp_qsort.h"
48 #else
49 #define XP_QSORT qsort
50 #endif
51 
52 typedef struct keycmp {
53     void                 *kc_arg;
54     LDAP_KEYCMP_CALLBACK *kc_cmp;
55 } keycmp_t;
56 
57 typedef struct keything {
58     keycmp_t            *kt_cmp;
59     const struct berval *kt_key;
60     LDAPMessage         *kt_msg;
61 } keything_t;
62 
63 static int LDAP_C LDAP_CALLBACK
ldapi_keycmp(const void * Lv,const void * Rv)64 ldapi_keycmp( const void *Lv, const void *Rv )
65 {
66     auto keything_t **L = (keything_t**)Lv;
67     auto keything_t **R = (keything_t**)Rv;
68     auto keycmp_t *cmp = (*L)->kt_cmp;
69     return cmp->kc_cmp( cmp->kc_arg, (*L)->kt_key, (*R)->kt_key );
70 }
71 
72 int
73 LDAP_CALL
ldap_keysort_entries(LDAP * ld,LDAPMessage ** chain,void * arg,LDAP_KEYGEN_CALLBACK * gen,LDAP_KEYCMP_CALLBACK * cmp,LDAP_KEYFREE_CALLBACK * fre)74 ldap_keysort_entries(
75     LDAP        *ld,
76     LDAPMessage **chain,
77     void                  *arg,
78     LDAP_KEYGEN_CALLBACK  *gen,
79     LDAP_KEYCMP_CALLBACK  *cmp,
80     LDAP_KEYFREE_CALLBACK *fre)
81 {
82 	size_t		count, i;
83 	keycmp_t	kc = {0};
84 	keything_t	**kt;
85 	LDAPMessage	*e, *last;
86 	LDAPMessage	**ep;
87 
88 	if ( !NSLDAPI_VALID_LDAP_POINTER( ld )
89 	    || chain == NULL || cmp == NULL ) {
90 		return( LDAP_PARAM_ERROR );
91 	}
92 
93 	count = ldap_count_entries( ld, *chain );
94 
95 	kt = (keything_t**)NSLDAPI_MALLOC( count * (sizeof(keything_t*) + sizeof(keything_t)) );
96 	if ( kt == NULL ) {
97 		LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
98 		return( -1 );
99 	}
100 	for ( i = 0; i < count; i++ ) {
101 		kt[i] = i + (keything_t*)(kt + count);
102 	}
103 	kc.kc_arg = arg;
104 	kc.kc_cmp = cmp;
105 
106 	for ( e = *chain, i = 0; i < count; i++, e = e->lm_chain ) {
107 		kt[i]->kt_msg = e;
108 		kt[i]->kt_cmp = &kc;
109 		kt[i]->kt_key = gen( arg, ld, e );
110 		if ( kt[i]->kt_key == NULL ) {
111 			if ( fre ) while ( i-- > 0 ) fre( arg, kt[i]->kt_key );
112 			NSLDAPI_FREE( (char*)kt );
113 			LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
114 			return( -1 );
115 		}
116 	}
117 	last = e;
118 
119 	XP_QSORT( (void*)kt, count, (size_t)sizeof(keything_t*), ldapi_keycmp );
120 
121 	ep = chain;
122 	for ( i = 0; i < count; i++ ) {
123 		*ep = kt[i]->kt_msg;
124 		ep = &(*ep)->lm_chain;
125 		if ( fre ) fre( arg, kt[i]->kt_key );
126 	}
127 	*ep = last;
128 	NSLDAPI_FREE( (char*)kt );
129 	return( 0 );
130 }
131 
132 
133 struct entrything {
134 	char		**et_vals;
135 	LDAPMessage	*et_msg;
136 };
137 
138 typedef int (LDAP_C LDAP_CALLBACK LDAP_CHARCMP_CALLBACK)(char*, char*);
139 typedef int (LDAP_C LDAP_CALLBACK LDAP_VOIDCMP_CALLBACK)(const void*,
140 	const void*);
141 
142 static LDAP_CHARCMP_CALLBACK *et_cmp_fn;
143 static LDAP_VOIDCMP_CALLBACK et_cmp;
144 
145 int
146 LDAP_C
147 LDAP_CALLBACK
ldap_sort_strcasecmp(const char ** a,const char ** b)148 ldap_sort_strcasecmp(
149     const char	**a,
150     const char	**b
151 )
152 {
153     /* XXXceb
154      * I am not 100% sure this is the way this should be handled.
155      * For now we will return a 0 on invalid.
156      */
157 	if (NULL == a || NULL == b)
158 		return (0);
159 	return( strcasecmp( (char *)*a, (char *)*b ) );
160 }
161 
162 static int
163 LDAP_C
164 LDAP_CALLBACK
et_cmp(const void * aa,const void * bb)165 et_cmp(
166     const void	*aa,
167     const void	*bb
168 )
169 {
170 	int			i, rc;
171 	struct entrything	*a = (struct entrything *)aa;
172 	struct entrything	*b = (struct entrything *)bb;
173 
174 	if ( a->et_vals == NULL && b->et_vals == NULL )
175 		return( 0 );
176 	if ( a->et_vals == NULL )
177 		return( -1 );
178 	if ( b->et_vals == NULL )
179 		return( 1 );
180 
181 	for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
182 		if ( (rc = (*et_cmp_fn)( a->et_vals[i], b->et_vals[i] ))
183 		    != 0 ) {
184 			return( rc );
185 		}
186 	}
187 
188 	if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
189 		return( 0 );
190 	if ( a->et_vals[i] == NULL )
191 		return( -1 );
192 	return( 1 );
193 }
194 
195 int
196 LDAP_CALL
ldap_multisort_entries(LDAP * ld,LDAPMessage ** chain,char ** attr,LDAP_CMP_CALLBACK * cmp)197 ldap_multisort_entries(
198     LDAP	*ld,
199     LDAPMessage	**chain,
200     char	**attr,		/* NULL => sort by DN */
201     LDAP_CMP_CALLBACK *cmp
202 )
203 {
204 	int			i, count;
205 	struct entrything	*et;
206 	LDAPMessage		*e, *last;
207 	LDAPMessage		**ep;
208 
209 	if ( !NSLDAPI_VALID_LDAP_POINTER( ld )
210 	    || chain == NULL || cmp == NULL ) {
211 		return( LDAP_PARAM_ERROR );
212 	}
213 
214 	count = ldap_count_entries( ld, *chain );
215 
216 	if ( (et = (struct entrything *)NSLDAPI_MALLOC( count *
217 	    sizeof(struct entrything) )) == NULL ) {
218 		LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
219 		return( -1 );
220 	}
221 
222 	e = *chain;
223 	for ( i = 0; i < count; i++ ) {
224 		et[i].et_msg = e;
225 		et[i].et_vals = NULL;
226 		if ( attr == NULL ) {
227 			char	*dn;
228 
229 			dn = ldap_get_dn( ld, e );
230 			et[i].et_vals = ldap_explode_dn( dn, 1 );
231 			NSLDAPI_FREE( dn );
232 		} else {
233 			int	attrcnt;
234 			char	**vals;
235 
236 			for ( attrcnt = 0; attr[attrcnt] != NULL; attrcnt++ ) {
237 			    vals = ldap_get_values( ld, e, attr[attrcnt] );
238 			    if ( ldap_charray_merge( &(et[i].et_vals), vals )
239 				!= 0 ) {
240 				int	j;
241 
242 				/* XXX risky: ldap_value_free( vals ); */
243 				for ( j = 0; j <= i; j++ )
244 				    ldap_value_free( et[j].et_vals );
245 				NSLDAPI_FREE( (char *) et );
246 				LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL,
247 				    NULL );
248 				return( -1 );
249 			    }
250 			    if ( vals != NULL ) {
251 				NSLDAPI_FREE( (char *)vals );
252 			    }
253 			}
254 		}
255 
256 		e = e->lm_chain;
257 	}
258 	last = e;
259 
260 	et_cmp_fn = (LDAP_CHARCMP_CALLBACK *)cmp;
261 	XP_QSORT( (void *) et, (size_t) count,
262 		(size_t) sizeof(struct entrything), et_cmp );
263 
264 	ep = chain;
265 	for ( i = 0; i < count; i++ ) {
266 		*ep = et[i].et_msg;
267 		ep = &(*ep)->lm_chain;
268 
269 		ldap_value_free( et[i].et_vals );
270 	}
271 	*ep = last;
272 	NSLDAPI_FREE( (char *) et );
273 
274 	return( 0 );
275 }
276 
277 int
278 LDAP_CALL
ldap_sort_entries(LDAP * ld,LDAPMessage ** chain,char * attr,LDAP_CMP_CALLBACK * cmp)279 ldap_sort_entries(
280     LDAP	*ld,
281     LDAPMessage	**chain,
282     char	*attr,		/* NULL => sort by DN */
283     LDAP_CMP_CALLBACK *cmp
284 )
285 {
286 	char	*attrs[2];
287 
288 	attrs[0] = attr;
289 	attrs[1] = NULL;
290 	return( ldap_multisort_entries( ld, chain, attr ? attrs : NULL, cmp ) );
291 }
292 
293 int
294 LDAP_CALL
ldap_sort_values(LDAP * ld,char ** vals,LDAP_VALCMP_CALLBACK * cmp)295 ldap_sort_values(
296     LDAP	*ld,
297     char	**vals,
298     LDAP_VALCMP_CALLBACK *cmp
299 )
300 {
301 	int	nel;
302 
303 	if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cmp == NULL ) {
304 		return( LDAP_PARAM_ERROR );
305 	}
306 
307     if ( NULL == vals)
308     {
309 		LDAP_SET_LDERRNO( ld, LDAP_PARAM_ERROR, NULL, NULL );
310 		return( LDAP_PARAM_ERROR );
311 	}
312 	for ( nel = 0; vals[nel] != NULL; nel++ )
313 		;	/* NULL */
314 
315 	XP_QSORT( vals, nel, sizeof(char *), (LDAP_VOIDCMP_CALLBACK *)cmp );
316 
317 	return( LDAP_SUCCESS );
318 }
319