17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * The contents of this file are subject to the Netscape Public
37c478bd9Sstevel@tonic-gate * License Version 1.1 (the "License"); you may not use this file
47c478bd9Sstevel@tonic-gate * except in compliance with the License. You may obtain a copy of
57c478bd9Sstevel@tonic-gate * the License at http://www.mozilla.org/NPL/
67c478bd9Sstevel@tonic-gate *
77c478bd9Sstevel@tonic-gate * Software distributed under the License is distributed on an "AS
87c478bd9Sstevel@tonic-gate * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
97c478bd9Sstevel@tonic-gate * implied. See the License for the specific language governing
107c478bd9Sstevel@tonic-gate * rights and limitations under the License.
117c478bd9Sstevel@tonic-gate *
127c478bd9Sstevel@tonic-gate * The Original Code is Mozilla Communicator client code, released
137c478bd9Sstevel@tonic-gate * March 31, 1998.
147c478bd9Sstevel@tonic-gate *
157c478bd9Sstevel@tonic-gate * The Initial Developer of the Original Code is Netscape
167c478bd9Sstevel@tonic-gate * Communications Corporation. Portions created by Netscape are
177c478bd9Sstevel@tonic-gate * Copyright (C) 1998-1999 Netscape Communications Corporation. All
187c478bd9Sstevel@tonic-gate * Rights Reserved.
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * Contributor(s):
217c478bd9Sstevel@tonic-gate */
227c478bd9Sstevel@tonic-gate /*
237c478bd9Sstevel@tonic-gate * Copyright (c) 1994 Regents of the University of Michigan.
247c478bd9Sstevel@tonic-gate * All rights reserved.
257c478bd9Sstevel@tonic-gate *
267c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms are permitted
277c478bd9Sstevel@tonic-gate * provided that this notice is preserved and that due credit is given
287c478bd9Sstevel@tonic-gate * to the University of Michigan at Ann Arbor. The name of the University
297c478bd9Sstevel@tonic-gate * may not be used to endorse or promote products derived from this
307c478bd9Sstevel@tonic-gate * software without specific prior written permission. This software
317c478bd9Sstevel@tonic-gate * is provided ``as is'' without express or implied warranty.
327c478bd9Sstevel@tonic-gate */
337c478bd9Sstevel@tonic-gate /*
347c478bd9Sstevel@tonic-gate * sort.c: LDAP library entry and value sort routines
357c478bd9Sstevel@tonic-gate */
367c478bd9Sstevel@tonic-gate
377c478bd9Sstevel@tonic-gate #include "ldap-int.h"
387c478bd9Sstevel@tonic-gate
397c478bd9Sstevel@tonic-gate /* This xp_qsort fixes a memory problem (ABR) on Solaris for the client.
407c478bd9Sstevel@tonic-gate * Server is welcome to use it too, but I wasn't sure if it
417c478bd9Sstevel@tonic-gate * would be ok to use XP code here. -slamm
427c478bd9Sstevel@tonic-gate *
437c478bd9Sstevel@tonic-gate * We don't want to require use of libxp when linking with libldap, so
447c478bd9Sstevel@tonic-gate * I'll leave use of xp_qsort as a MOZILLA_CLIENT-only thing for now. --mcs
457c478bd9Sstevel@tonic-gate */
467c478bd9Sstevel@tonic-gate #if defined(MOZILLA_CLIENT) && defined(SOLARIS)
477c478bd9Sstevel@tonic-gate #include "xp_qsort.h"
487c478bd9Sstevel@tonic-gate #else
497c478bd9Sstevel@tonic-gate #define XP_QSORT qsort
507c478bd9Sstevel@tonic-gate #endif
517c478bd9Sstevel@tonic-gate
527c478bd9Sstevel@tonic-gate typedef struct keycmp {
537c478bd9Sstevel@tonic-gate void *kc_arg;
547c478bd9Sstevel@tonic-gate LDAP_KEYCMP_CALLBACK *kc_cmp;
557c478bd9Sstevel@tonic-gate } keycmp_t;
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate typedef struct keything {
587c478bd9Sstevel@tonic-gate keycmp_t *kt_cmp;
597c478bd9Sstevel@tonic-gate const struct berval *kt_key;
607c478bd9Sstevel@tonic-gate LDAPMessage *kt_msg;
617c478bd9Sstevel@tonic-gate } keything_t;
627c478bd9Sstevel@tonic-gate
637c478bd9Sstevel@tonic-gate static int LDAP_C LDAP_CALLBACK
ldapi_keycmp(const void * Lv,const void * Rv)647c478bd9Sstevel@tonic-gate ldapi_keycmp( const void *Lv, const void *Rv )
657c478bd9Sstevel@tonic-gate {
667c478bd9Sstevel@tonic-gate auto keything_t **L = (keything_t**)Lv;
677c478bd9Sstevel@tonic-gate auto keything_t **R = (keything_t**)Rv;
687c478bd9Sstevel@tonic-gate auto keycmp_t *cmp = (*L)->kt_cmp;
697c478bd9Sstevel@tonic-gate return cmp->kc_cmp( cmp->kc_arg, (*L)->kt_key, (*R)->kt_key );
707c478bd9Sstevel@tonic-gate }
717c478bd9Sstevel@tonic-gate
727c478bd9Sstevel@tonic-gate int
737c478bd9Sstevel@tonic-gate LDAP_CALL
ldap_keysort_entries(LDAP * ld,LDAPMessage ** chain,void * arg,LDAP_KEYGEN_CALLBACK * gen,LDAP_KEYCMP_CALLBACK * cmp,LDAP_KEYFREE_CALLBACK * fre)747c478bd9Sstevel@tonic-gate ldap_keysort_entries(
757c478bd9Sstevel@tonic-gate LDAP *ld,
767c478bd9Sstevel@tonic-gate LDAPMessage **chain,
777c478bd9Sstevel@tonic-gate void *arg,
787c478bd9Sstevel@tonic-gate LDAP_KEYGEN_CALLBACK *gen,
797c478bd9Sstevel@tonic-gate LDAP_KEYCMP_CALLBACK *cmp,
807c478bd9Sstevel@tonic-gate LDAP_KEYFREE_CALLBACK *fre)
817c478bd9Sstevel@tonic-gate {
827c478bd9Sstevel@tonic-gate size_t count, i;
837c478bd9Sstevel@tonic-gate keycmp_t kc = {0};
847c478bd9Sstevel@tonic-gate keything_t **kt;
857c478bd9Sstevel@tonic-gate LDAPMessage *e, *last;
867c478bd9Sstevel@tonic-gate LDAPMessage **ep;
877c478bd9Sstevel@tonic-gate
887c478bd9Sstevel@tonic-gate if ( !NSLDAPI_VALID_LDAP_POINTER( ld )
897c478bd9Sstevel@tonic-gate || chain == NULL || cmp == NULL ) {
907c478bd9Sstevel@tonic-gate return( LDAP_PARAM_ERROR );
917c478bd9Sstevel@tonic-gate }
927c478bd9Sstevel@tonic-gate
937c478bd9Sstevel@tonic-gate count = ldap_count_entries( ld, *chain );
947c478bd9Sstevel@tonic-gate
957c478bd9Sstevel@tonic-gate kt = (keything_t**)NSLDAPI_MALLOC( count * (sizeof(keything_t*) + sizeof(keything_t)) );
967c478bd9Sstevel@tonic-gate if ( kt == NULL ) {
977c478bd9Sstevel@tonic-gate LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
987c478bd9Sstevel@tonic-gate return( -1 );
997c478bd9Sstevel@tonic-gate }
1007c478bd9Sstevel@tonic-gate for ( i = 0; i < count; i++ ) {
1017c478bd9Sstevel@tonic-gate kt[i] = i + (keything_t*)(kt + count);
1027c478bd9Sstevel@tonic-gate }
1037c478bd9Sstevel@tonic-gate kc.kc_arg = arg;
1047c478bd9Sstevel@tonic-gate kc.kc_cmp = cmp;
1057c478bd9Sstevel@tonic-gate
1067c478bd9Sstevel@tonic-gate for ( e = *chain, i = 0; i < count; i++, e = e->lm_chain ) {
1077c478bd9Sstevel@tonic-gate kt[i]->kt_msg = e;
1087c478bd9Sstevel@tonic-gate kt[i]->kt_cmp = &kc;
1097c478bd9Sstevel@tonic-gate kt[i]->kt_key = gen( arg, ld, e );
1107c478bd9Sstevel@tonic-gate if ( kt[i]->kt_key == NULL ) {
1117c478bd9Sstevel@tonic-gate if ( fre ) while ( i-- > 0 ) fre( arg, kt[i]->kt_key );
1127c478bd9Sstevel@tonic-gate NSLDAPI_FREE( (char*)kt );
1137c478bd9Sstevel@tonic-gate LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
1147c478bd9Sstevel@tonic-gate return( -1 );
1157c478bd9Sstevel@tonic-gate }
1167c478bd9Sstevel@tonic-gate }
1177c478bd9Sstevel@tonic-gate last = e;
1187c478bd9Sstevel@tonic-gate
1197c478bd9Sstevel@tonic-gate XP_QSORT( (void*)kt, count, (size_t)sizeof(keything_t*), ldapi_keycmp );
120*55fea89dSDan Cross
1217c478bd9Sstevel@tonic-gate ep = chain;
1227c478bd9Sstevel@tonic-gate for ( i = 0; i < count; i++ ) {
1237c478bd9Sstevel@tonic-gate *ep = kt[i]->kt_msg;
1247c478bd9Sstevel@tonic-gate ep = &(*ep)->lm_chain;
1257c478bd9Sstevel@tonic-gate if ( fre ) fre( arg, kt[i]->kt_key );
1267c478bd9Sstevel@tonic-gate }
1277c478bd9Sstevel@tonic-gate *ep = last;
1287c478bd9Sstevel@tonic-gate NSLDAPI_FREE( (char*)kt );
1297c478bd9Sstevel@tonic-gate return( 0 );
1307c478bd9Sstevel@tonic-gate }
1317c478bd9Sstevel@tonic-gate
1327c478bd9Sstevel@tonic-gate
1337c478bd9Sstevel@tonic-gate struct entrything {
1347c478bd9Sstevel@tonic-gate char **et_vals;
1357c478bd9Sstevel@tonic-gate LDAPMessage *et_msg;
1367c478bd9Sstevel@tonic-gate };
1377c478bd9Sstevel@tonic-gate
1387c478bd9Sstevel@tonic-gate typedef int (LDAP_C LDAP_CALLBACK LDAP_CHARCMP_CALLBACK)(char*, char*);
139*55fea89dSDan Cross typedef int (LDAP_C LDAP_CALLBACK LDAP_VOIDCMP_CALLBACK)(const void*,
1407c478bd9Sstevel@tonic-gate const void*);
1417c478bd9Sstevel@tonic-gate
1427c478bd9Sstevel@tonic-gate static LDAP_CHARCMP_CALLBACK *et_cmp_fn;
1437c478bd9Sstevel@tonic-gate static LDAP_VOIDCMP_CALLBACK et_cmp;
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate int
1467c478bd9Sstevel@tonic-gate LDAP_C
1477c478bd9Sstevel@tonic-gate LDAP_CALLBACK
ldap_sort_strcasecmp(const char ** a,const char ** b)1487c478bd9Sstevel@tonic-gate ldap_sort_strcasecmp(
1497c478bd9Sstevel@tonic-gate const char **a,
1507c478bd9Sstevel@tonic-gate const char **b
1517c478bd9Sstevel@tonic-gate )
1527c478bd9Sstevel@tonic-gate {
1537c478bd9Sstevel@tonic-gate /* XXXceb
154*55fea89dSDan Cross * I am not 100% sure this is the way this should be handled.
1557c478bd9Sstevel@tonic-gate * For now we will return a 0 on invalid.
1561307500aSToomas Soome */
1571307500aSToomas Soome if (NULL == a || NULL == b)
1581307500aSToomas Soome return (0);
1597c478bd9Sstevel@tonic-gate return( strcasecmp( (char *)*a, (char *)*b ) );
1607c478bd9Sstevel@tonic-gate }
1617c478bd9Sstevel@tonic-gate
1627c478bd9Sstevel@tonic-gate static int
1637c478bd9Sstevel@tonic-gate LDAP_C
1647c478bd9Sstevel@tonic-gate LDAP_CALLBACK
et_cmp(const void * aa,const void * bb)1657c478bd9Sstevel@tonic-gate et_cmp(
1667c478bd9Sstevel@tonic-gate const void *aa,
1677c478bd9Sstevel@tonic-gate const void *bb
1687c478bd9Sstevel@tonic-gate )
1697c478bd9Sstevel@tonic-gate {
1707c478bd9Sstevel@tonic-gate int i, rc;
1717c478bd9Sstevel@tonic-gate struct entrything *a = (struct entrything *)aa;
1727c478bd9Sstevel@tonic-gate struct entrything *b = (struct entrything *)bb;
1737c478bd9Sstevel@tonic-gate
1747c478bd9Sstevel@tonic-gate if ( a->et_vals == NULL && b->et_vals == NULL )
1757c478bd9Sstevel@tonic-gate return( 0 );
1767c478bd9Sstevel@tonic-gate if ( a->et_vals == NULL )
1777c478bd9Sstevel@tonic-gate return( -1 );
1787c478bd9Sstevel@tonic-gate if ( b->et_vals == NULL )
1797c478bd9Sstevel@tonic-gate return( 1 );
1807c478bd9Sstevel@tonic-gate
1817c478bd9Sstevel@tonic-gate for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
1827c478bd9Sstevel@tonic-gate if ( (rc = (*et_cmp_fn)( a->et_vals[i], b->et_vals[i] ))
1837c478bd9Sstevel@tonic-gate != 0 ) {
1847c478bd9Sstevel@tonic-gate return( rc );
1857c478bd9Sstevel@tonic-gate }
1867c478bd9Sstevel@tonic-gate }
1877c478bd9Sstevel@tonic-gate
1887c478bd9Sstevel@tonic-gate if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
1897c478bd9Sstevel@tonic-gate return( 0 );
1907c478bd9Sstevel@tonic-gate if ( a->et_vals[i] == NULL )
1917c478bd9Sstevel@tonic-gate return( -1 );
1927c478bd9Sstevel@tonic-gate return( 1 );
1937c478bd9Sstevel@tonic-gate }
1947c478bd9Sstevel@tonic-gate
1957c478bd9Sstevel@tonic-gate int
1967c478bd9Sstevel@tonic-gate LDAP_CALL
ldap_multisort_entries(LDAP * ld,LDAPMessage ** chain,char ** attr,LDAP_CMP_CALLBACK * cmp)1977c478bd9Sstevel@tonic-gate ldap_multisort_entries(
1987c478bd9Sstevel@tonic-gate LDAP *ld,
1997c478bd9Sstevel@tonic-gate LDAPMessage **chain,
2007c478bd9Sstevel@tonic-gate char **attr, /* NULL => sort by DN */
2017c478bd9Sstevel@tonic-gate LDAP_CMP_CALLBACK *cmp
2027c478bd9Sstevel@tonic-gate )
2037c478bd9Sstevel@tonic-gate {
2047c478bd9Sstevel@tonic-gate int i, count;
2057c478bd9Sstevel@tonic-gate struct entrything *et;
2067c478bd9Sstevel@tonic-gate LDAPMessage *e, *last;
2077c478bd9Sstevel@tonic-gate LDAPMessage **ep;
2087c478bd9Sstevel@tonic-gate
2097c478bd9Sstevel@tonic-gate if ( !NSLDAPI_VALID_LDAP_POINTER( ld )
2107c478bd9Sstevel@tonic-gate || chain == NULL || cmp == NULL ) {
2117c478bd9Sstevel@tonic-gate return( LDAP_PARAM_ERROR );
2127c478bd9Sstevel@tonic-gate }
2137c478bd9Sstevel@tonic-gate
2147c478bd9Sstevel@tonic-gate count = ldap_count_entries( ld, *chain );
2157c478bd9Sstevel@tonic-gate
2167c478bd9Sstevel@tonic-gate if ( (et = (struct entrything *)NSLDAPI_MALLOC( count *
2177c478bd9Sstevel@tonic-gate sizeof(struct entrything) )) == NULL ) {
2187c478bd9Sstevel@tonic-gate LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL, NULL );
2197c478bd9Sstevel@tonic-gate return( -1 );
2207c478bd9Sstevel@tonic-gate }
2217c478bd9Sstevel@tonic-gate
2227c478bd9Sstevel@tonic-gate e = *chain;
2237c478bd9Sstevel@tonic-gate for ( i = 0; i < count; i++ ) {
2247c478bd9Sstevel@tonic-gate et[i].et_msg = e;
2257c478bd9Sstevel@tonic-gate et[i].et_vals = NULL;
2267c478bd9Sstevel@tonic-gate if ( attr == NULL ) {
2277c478bd9Sstevel@tonic-gate char *dn;
2287c478bd9Sstevel@tonic-gate
2297c478bd9Sstevel@tonic-gate dn = ldap_get_dn( ld, e );
2307c478bd9Sstevel@tonic-gate et[i].et_vals = ldap_explode_dn( dn, 1 );
2317c478bd9Sstevel@tonic-gate NSLDAPI_FREE( dn );
2327c478bd9Sstevel@tonic-gate } else {
2337c478bd9Sstevel@tonic-gate int attrcnt;
2347c478bd9Sstevel@tonic-gate char **vals;
2357c478bd9Sstevel@tonic-gate
2367c478bd9Sstevel@tonic-gate for ( attrcnt = 0; attr[attrcnt] != NULL; attrcnt++ ) {
2377c478bd9Sstevel@tonic-gate vals = ldap_get_values( ld, e, attr[attrcnt] );
2387c478bd9Sstevel@tonic-gate if ( ldap_charray_merge( &(et[i].et_vals), vals )
2397c478bd9Sstevel@tonic-gate != 0 ) {
2407c478bd9Sstevel@tonic-gate int j;
2417c478bd9Sstevel@tonic-gate
2427c478bd9Sstevel@tonic-gate /* XXX risky: ldap_value_free( vals ); */
2437c478bd9Sstevel@tonic-gate for ( j = 0; j <= i; j++ )
2447c478bd9Sstevel@tonic-gate ldap_value_free( et[j].et_vals );
2457c478bd9Sstevel@tonic-gate NSLDAPI_FREE( (char *) et );
246*55fea89dSDan Cross LDAP_SET_LDERRNO( ld, LDAP_NO_MEMORY, NULL,
2477c478bd9Sstevel@tonic-gate NULL );
2487c478bd9Sstevel@tonic-gate return( -1 );
2497c478bd9Sstevel@tonic-gate }
2507c478bd9Sstevel@tonic-gate if ( vals != NULL ) {
2517c478bd9Sstevel@tonic-gate NSLDAPI_FREE( (char *)vals );
2527c478bd9Sstevel@tonic-gate }
2537c478bd9Sstevel@tonic-gate }
2547c478bd9Sstevel@tonic-gate }
2557c478bd9Sstevel@tonic-gate
2567c478bd9Sstevel@tonic-gate e = e->lm_chain;
2577c478bd9Sstevel@tonic-gate }
2587c478bd9Sstevel@tonic-gate last = e;
2597c478bd9Sstevel@tonic-gate
2607c478bd9Sstevel@tonic-gate et_cmp_fn = (LDAP_CHARCMP_CALLBACK *)cmp;
2617c478bd9Sstevel@tonic-gate XP_QSORT( (void *) et, (size_t) count,
2627c478bd9Sstevel@tonic-gate (size_t) sizeof(struct entrything), et_cmp );
2637c478bd9Sstevel@tonic-gate
2647c478bd9Sstevel@tonic-gate ep = chain;
2657c478bd9Sstevel@tonic-gate for ( i = 0; i < count; i++ ) {
2667c478bd9Sstevel@tonic-gate *ep = et[i].et_msg;
2677c478bd9Sstevel@tonic-gate ep = &(*ep)->lm_chain;
2687c478bd9Sstevel@tonic-gate
2697c478bd9Sstevel@tonic-gate ldap_value_free( et[i].et_vals );
2707c478bd9Sstevel@tonic-gate }
2717c478bd9Sstevel@tonic-gate *ep = last;
2727c478bd9Sstevel@tonic-gate NSLDAPI_FREE( (char *) et );
2737c478bd9Sstevel@tonic-gate
2747c478bd9Sstevel@tonic-gate return( 0 );
2757c478bd9Sstevel@tonic-gate }
2767c478bd9Sstevel@tonic-gate
2777c478bd9Sstevel@tonic-gate int
2787c478bd9Sstevel@tonic-gate LDAP_CALL
ldap_sort_entries(LDAP * ld,LDAPMessage ** chain,char * attr,LDAP_CMP_CALLBACK * cmp)2797c478bd9Sstevel@tonic-gate ldap_sort_entries(
2807c478bd9Sstevel@tonic-gate LDAP *ld,
2817c478bd9Sstevel@tonic-gate LDAPMessage **chain,
2827c478bd9Sstevel@tonic-gate char *attr, /* NULL => sort by DN */
2837c478bd9Sstevel@tonic-gate LDAP_CMP_CALLBACK *cmp
2847c478bd9Sstevel@tonic-gate )
2857c478bd9Sstevel@tonic-gate {
2867c478bd9Sstevel@tonic-gate char *attrs[2];
2877c478bd9Sstevel@tonic-gate
2887c478bd9Sstevel@tonic-gate attrs[0] = attr;
2897c478bd9Sstevel@tonic-gate attrs[1] = NULL;
2907c478bd9Sstevel@tonic-gate return( ldap_multisort_entries( ld, chain, attr ? attrs : NULL, cmp ) );
2917c478bd9Sstevel@tonic-gate }
2927c478bd9Sstevel@tonic-gate
2937c478bd9Sstevel@tonic-gate int
2947c478bd9Sstevel@tonic-gate LDAP_CALL
ldap_sort_values(LDAP * ld,char ** vals,LDAP_VALCMP_CALLBACK * cmp)2957c478bd9Sstevel@tonic-gate ldap_sort_values(
2967c478bd9Sstevel@tonic-gate LDAP *ld,
2977c478bd9Sstevel@tonic-gate char **vals,
2987c478bd9Sstevel@tonic-gate LDAP_VALCMP_CALLBACK *cmp
2997c478bd9Sstevel@tonic-gate )
3007c478bd9Sstevel@tonic-gate {
3017c478bd9Sstevel@tonic-gate int nel;
3027c478bd9Sstevel@tonic-gate
3037c478bd9Sstevel@tonic-gate if ( !NSLDAPI_VALID_LDAP_POINTER( ld ) || cmp == NULL ) {
3047c478bd9Sstevel@tonic-gate return( LDAP_PARAM_ERROR );
3057c478bd9Sstevel@tonic-gate }
3067c478bd9Sstevel@tonic-gate
307*55fea89dSDan Cross if ( NULL == vals)
3087c478bd9Sstevel@tonic-gate {
3097c478bd9Sstevel@tonic-gate LDAP_SET_LDERRNO( ld, LDAP_PARAM_ERROR, NULL, NULL );
3107c478bd9Sstevel@tonic-gate return( LDAP_PARAM_ERROR );
3117c478bd9Sstevel@tonic-gate }
3127c478bd9Sstevel@tonic-gate for ( nel = 0; vals[nel] != NULL; nel++ )
3137c478bd9Sstevel@tonic-gate ; /* NULL */
3147c478bd9Sstevel@tonic-gate
3157c478bd9Sstevel@tonic-gate XP_QSORT( vals, nel, sizeof(char *), (LDAP_VOIDCMP_CALLBACK *)cmp );
3167c478bd9Sstevel@tonic-gate
3177c478bd9Sstevel@tonic-gate return( LDAP_SUCCESS );
3187c478bd9Sstevel@tonic-gate }
319