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