1/*
2 * Copyright (c) 2008 Apple Inc.  All Rights Reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 *
23 * Does this need to be released under the OpenLDAP License instead of, or in
24 * addition to the APSL?
25 *
26 */
27
28/*
29 * Implementation of the Red Black tree to index the
30 * ldap response messages.
31 */
32
33#ifdef LDAP_RESPONSE_RB_TREE
34
35#include "portable.h"
36
37#include <stdio.h>
38#include <ac/stdlib.h>
39#include <ac/unistd.h>
40
41#include "ldap-int.h"
42
43#include "rb.h"
44#include "rb_response.h"
45#include "ldap_rb_stats.h"
46
47
48#define RBNODE_TO_LM(n) \
49    ((LDAPMessage *)((uintptr_t)n - offsetof(LDAPMessage, lm_link)))
50
51static int ldap_resp_rbt_compare_nodes( const struct rb_node *n1,
52                                        const struct rb_node *n2 )
53{
54	const ber_int_t msgid1 = RBNODE_TO_LM(n1)->lm_msgid;
55	const ber_int_t msgid2 = RBNODE_TO_LM(n2)->lm_msgid;
56
57    if ( msgid1 < msgid2 ) {
58        return -1;
59    }
60    if ( msgid1 > msgid2 ) {
61        return 1;
62    }
63    return 0;
64}
65
66static int ldap_resp_rbt_compare_key( const struct rb_node *n,
67                                      const void *v )
68{
69	const ber_int_t msgid1 = RBNODE_TO_LM(n)->lm_msgid;
70	const ber_int_t msgid2 = *((ber_int_t*)v);
71
72    if ( msgid1 < msgid2 ) {
73        return -1;
74    }
75    if ( msgid1 > msgid2 ) {
76        return 1;
77    }
78    return 0;
79}
80
81static const struct rb_tree_ops ldap_resp_rbt_ops = {
82    .rbto_compare_nodes = ldap_resp_rbt_compare_nodes,
83    .rbto_compare_key   = ldap_resp_rbt_compare_key,
84};
85
86void ldap_resp_rbt_create( LDAP *ld )
87{
88    assert( ld != NULL );
89
90    ld->ld_rbt_responses = LDAP_CALLOC( 1, sizeof(*ld->ld_rbt_responses) );
91    assert( ld->ld_rbt_responses != NULL );
92
93    rb_tree_init( ld->ld_rbt_responses, &ldap_resp_rbt_ops );
94}
95
96void ldap_resp_rbt_free( LDAP *ld )
97{
98    LDAPMessage *lm;
99    LDAPMessage *doomed;
100
101    assert( ld != NULL );
102    assert( ld->ld_rbt_responses != NULL );
103
104    /* Free all of the response messages in the tree. */
105    lm = ldap_resp_rbt_get_first_msg( ld );
106    while ( lm ) {
107        /* Since the rb tree will re-balance when we delete, get the next
108         * message before removing it from the rb tree.
109         */
110        doomed = lm;
111        lm = ldap_resp_rbt_get_next_msg( ld, lm );
112        ldap_resp_rbt_delete_msg( ld, doomed );
113    }
114
115    /* Now that the tree is empty, free the tree itself. */
116    LDAP_FREE( ld->ld_rbt_responses );
117    ld->ld_rbt_responses = NULL;
118}
119
120void ldap_resp_rbt_insert_msg( LDAP *ld, LDAPMessage *lm )
121{
122    assert( ld != NULL );
123    assert( ld->ld_rbt_responses != NULL );
124
125    rb_tree_insert_node( ld->ld_rbt_responses, &lm->lm_link );
126
127    if ( LDAP_RB_STATS_COUNT_ENABLED() ) {
128        LDAP_RB_STATS_COUNT( ld->ld_rbt_responses->rbt_count, lm->lm_msgid, lm );
129    }
130}
131
132/* Removes the message from the rb tree & deletes the message. */
133void ldap_resp_rbt_delete_msg( LDAP *ld, LDAPMessage *lm )
134{
135    assert( ld != NULL );
136    assert( ld->ld_rbt_responses != NULL );
137    assert( lm != NULL );
138
139    rb_tree_remove_node( ld->ld_rbt_responses, &lm->lm_link );
140    ldap_msgfree( lm );
141
142   if ( LDAP_RB_STATS_COUNT_ENABLED() ) {
143        LDAP_RB_STATS_COUNT( ld->ld_rbt_responses->rbt_count, lm->lm_msgid, lm );
144    }
145}
146
147/* Removes the message from the rb tree, but does _not_ delete it. */
148void ldap_resp_rbt_unlink_msg( LDAP *ld, LDAPMessage *lm)
149{
150    assert( ld != NULL );
151    assert( ld->ld_rbt_responses != NULL );
152    assert( lm != NULL );
153
154    rb_tree_remove_node( ld->ld_rbt_responses, &lm->lm_link );
155
156    if ( LDAP_RB_STATS_COUNT_ENABLED() ) {
157        LDAP_RB_STATS_COUNT( ld->ld_rbt_responses->rbt_count, lm->lm_msgid, lm );
158    }
159}
160
161/* Removes the message from the rb tree, but inserts the next message in
162 * the first message's response chain.
163 */
164void ldap_resp_rbt_unlink_partial_msg( LDAP *ld, LDAPMessage *lm )
165{
166    LDAPMessage *nextInChain;
167
168    assert( ld != NULL );
169    assert( ld->ld_rbt_responses != NULL );
170    assert( lm != NULL );
171
172    rb_tree_remove_node( ld->ld_rbt_responses, &lm->lm_link );
173    nextInChain = lm->lm_chain;
174	nextInChain->lm_chain_tail = ( lm->lm_chain_tail != lm ) ? lm->lm_chain_tail : lm->lm_chain;
175    rb_tree_insert_node( ld->ld_rbt_responses, &nextInChain->lm_link );
176
177    lm->lm_chain = NULL;
178    lm->lm_chain_tail = NULL;
179}
180
181LDAPMessage *ldap_resp_rbt_find_msg( LDAP *ld, ber_int_t msgid )
182{
183    struct rb_node* rbn = NULL;
184    LDAPMessage* lm  = NULL;
185
186    assert( ld != NULL );
187    assert( ld->ld_rbt_responses != NULL );
188
189    rbn = rb_tree_find_node( ld->ld_rbt_responses, &msgid );
190    if ( rbn ) {
191        lm = RBNODE_TO_LM( rbn );
192    }
193
194    return lm;
195}
196
197LDAPMessage *ldap_resp_rbt_get_first_msg( LDAP *ld )
198{
199    struct rb_node *rbn;
200    LDAPMessage *lm = NULL;
201
202    assert( ld != NULL );
203    assert( ld->ld_rbt_responses != NULL );
204
205    rbn = rb_tree_iterate( ld->ld_rbt_responses, NULL, RB_DIR_RIGHT );
206    if ( rbn ) {
207        lm = RBNODE_TO_LM( rbn );
208    }
209
210    return lm;
211}
212
213LDAPMessage *ldap_resp_rbt_get_next_msg( LDAP *ld, LDAPMessage *lm )
214{
215    struct rb_node *rbn;
216    LDAPMessage *next = NULL;
217
218    assert( ld != NULL );
219    assert( ld->ld_rbt_responses != NULL );
220
221    rbn = rb_tree_iterate( ld->ld_rbt_responses, &lm->lm_link, RB_DIR_LEFT );
222    if ( rbn ) {
223        next = RBNODE_TO_LM( rbn );
224    }
225
226    return next;
227}
228
229void ldap_resp_rbt_dump( LDAP* ld )
230{
231    LDAPMessage	*lm;
232	LDAPMessage *l;
233    struct rb_node *rbn;
234
235    assert( ld != NULL );
236    assert( ld->ld_rbt_responses != NULL );
237
238	fprintf( stderr, "** ld %p Red-Black Tree Response Queue:\n", (void *)ld );
239    rbn = rb_tree_iterate( ld->ld_rbt_responses, NULL, RB_DIR_RIGHT );
240	if ( rbn == NULL ) {
241		fprintf( stderr, "   Empty\n" );
242	}
243	for ( ; rbn != NULL; rbn = rb_tree_iterate( ld->ld_rbt_responses, rbn, RB_DIR_LEFT ) )
244	{
245        lm = RBNODE_TO_LM(rbn);
246		fprintf( stderr, " * msgid %d,  type %lu\n",
247		        lm->lm_msgid,
248		        (unsigned long) lm->lm_msgtype );
249
250        l = lm->lm_chain;;
251		if ( l != NULL )
252		{
253			fprintf( stderr, "   chained responses:\n" );
254			for ( ; l != NULL; l = l->lm_chain )
255			{
256				fprintf( stderr,
257				        "  * msgid %d,  type %lu\n",
258				        l->lm_msgid,
259				        (unsigned long) l->lm_msgtype );
260			}
261		}
262	}
263}
264
265#endif /* LDAP_RESPONSE_RB_TREE */
266