1 /* $NetBSD: sort.c,v 1.3 2021/08/14 16:14:56 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-2021 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.3 2021/08/14 16:14:56 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
ldap_sort_strcasecmp(LDAP_CONST void * a,LDAP_CONST void * b)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
et_cmp(const void * aa,const void * bb)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
ldap_sort_entries(LDAP * ld,LDAPMessage ** chain,LDAP_CONST char * attr,int (* cmp)(LDAP_CONST char *,LDAP_CONST char *))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
ldap_sort_values(LDAP * ld,char ** vals,int (* cmp)(LDAP_CONST void *,LDAP_CONST void *))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