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