]> git.sur5r.net Git - openldap/blob - libraries/libldap/sort.c
Merge remote-tracking branch 'origin/mdb.master'
[openldap] / libraries / libldap / sort.c
1 /* sort.c -- LDAP library entry and value sort routines */
2 /* $OpenLDAP$ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4  *
5  * Copyright 1998-2012 The OpenLDAP Foundation.
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted only as authorized by the OpenLDAP
10  * Public License.
11  *
12  * A copy of this license is available in the file LICENSE in the
13  * top-level directory of the distribution or, alternatively, at
14  * <http://www.OpenLDAP.org/license.html>.
15  */
16 /* Portions Copyright (c) 1994 Regents of the University of Michigan.
17  * All rights reserved.
18  *
19  * Redistribution and use in source and binary forms are permitted
20  * provided that this notice is preserved and that due credit is given
21  * to the University of Michigan at Ann Arbor. The name of the University
22  * may not be used to endorse or promote products derived from this
23  * software without specific prior written permission. This software
24  * is provided ``as is'' without express or implied warranty.
25  */
26
27 #include "portable.h"
28
29 #include <stdio.h>
30 #include <ac/stdlib.h>
31
32 #include <ac/ctype.h>
33 #include <ac/string.h>
34 #include <ac/time.h>
35
36
37 #include "ldap-int.h"
38
39 struct entrything {
40         char            **et_vals;
41         LDAPMessage     *et_msg;
42         int             (*et_cmp_fn) LDAP_P((const char *a, const char *b));
43 };
44
45 static int      et_cmp LDAP_P(( const void *aa, const void *bb));
46
47
48 int
49 ldap_sort_strcasecmp(
50         LDAP_CONST void *a,
51         LDAP_CONST void *b
52 )
53 {
54         return( strcasecmp( *(char *const *)a, *(char *const *)b ) );
55 }
56
57 static int
58 et_cmp(
59         const void      *aa,
60         const void      *bb
61 )
62 {
63         int                     i, rc;
64         const struct entrything *a = (const struct entrything *)aa;
65         const struct entrything *b = (const struct entrything *)bb;
66
67         if ( a->et_vals == NULL && b->et_vals == NULL )
68                 return( 0 );
69         if ( a->et_vals == NULL )
70                 return( -1 );
71         if ( b->et_vals == NULL )
72                 return( 1 );
73
74         for ( i = 0; a->et_vals[i] && b->et_vals[i]; i++ ) {
75                 if ( (rc = a->et_cmp_fn( a->et_vals[i], b->et_vals[i] )) != 0 ) {
76                         return( rc );
77                 }
78         }
79
80         if ( a->et_vals[i] == NULL && b->et_vals[i] == NULL )
81                 return( 0 );
82         if ( a->et_vals[i] == NULL )
83                 return( -1 );
84         return( 1 );
85 }
86
87 int
88 ldap_sort_entries(
89     LDAP        *ld,
90     LDAPMessage **chain,
91     LDAP_CONST char     *attr,          /* NULL => sort by DN */
92     int         (*cmp) (LDAP_CONST  char *, LDAP_CONST char *)
93 )
94 {
95         int                     i, count = 0;
96         struct entrything       *et;
97         LDAPMessage             *e, *ehead = NULL, *etail = NULL;
98         LDAPMessage             *ohead = NULL, *otail = NULL;
99         LDAPMessage             **ep;
100
101         assert( ld != NULL );
102
103         /* Separate entries from non-entries */
104         for ( e = *chain; e; e=e->lm_chain ) {
105                 if ( e->lm_msgtype == LDAP_RES_SEARCH_ENTRY ) {
106                         count++;
107                         if ( !ehead ) ehead = e;
108                         if ( etail ) etail->lm_chain = e;
109                         etail = e;
110                 } else {
111                         if ( !ohead ) ohead = e;
112                         if ( otail ) otail->lm_chain = e;
113                         otail = e;
114                 }
115         }
116
117         if ( count < 2 ) {
118                 /* zero or one entries -- already sorted! */
119                 if ( ehead ) {
120                         etail->lm_chain = ohead;
121                         *chain = ehead;
122                 } else {
123                         *chain = ohead;
124                 }
125                 return 0;
126         }
127
128         if ( (et = (struct entrything *) LDAP_MALLOC( count *
129             sizeof(struct entrything) )) == NULL ) {
130                 ld->ld_errno = LDAP_NO_MEMORY;
131                 return( -1 );
132         }
133
134         e = ehead;
135         for ( i = 0; i < count; i++ ) {
136                 et[i].et_cmp_fn = cmp;
137                 et[i].et_msg = e;
138                 if ( attr == NULL ) {
139                         char    *dn;
140
141                         dn = ldap_get_dn( ld, e );
142                         et[i].et_vals = ldap_explode_dn( dn, 1 );
143                         LDAP_FREE( dn );
144                 } else {
145                         et[i].et_vals = ldap_get_values( ld, e, attr );
146                 }
147
148                 e = e->lm_chain;
149         }
150
151         qsort( et, count, sizeof(struct entrything), et_cmp );
152
153         ep = chain;
154         for ( i = 0; i < count; i++ ) {
155                 *ep = et[i].et_msg;
156                 ep = &(*ep)->lm_chain;
157
158                 LDAP_VFREE( et[i].et_vals );
159         }
160         *ep = ohead;
161         (*chain)->lm_chain_tail = otail ? otail : etail;
162
163         LDAP_FREE( (char *) et );
164
165         return( 0 );
166 }
167
168 int
169 ldap_sort_values(
170     LDAP        *ld,
171     char        **vals,
172     int         (*cmp) (LDAP_CONST void *, LDAP_CONST void *)
173 )
174 {
175         int     nel;
176
177         for ( nel = 0; vals[nel] != NULL; nel++ )
178                 ;       /* NULL */
179
180         qsort( vals, nel, sizeof(char *), cmp );
181
182         return( 0 );
183 }