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