Home | History | Annotate | Line # | Download | only in libldap 
      1 /*	$NetBSD: sort.c,v 1.4 2025/09/05 21:16:21 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-2024 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.4 2025/09/05 21:16:21 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 
     44 struct entrything {
     45 	char		**et_vals;
     46 	LDAPMessage	*et_msg;
     47 	int 		(*et_cmp_fn) LDAP_P((const char *a, const char *b));
     48 };
     49 
     50 static int	et_cmp LDAP_P(( const void *aa, const void *bb));
     51 
     52 
     53 int
     54 ldap_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 
     62 static int
     63 et_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 
     92 int
     93 ldap_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 
    173 int
    174 ldap_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