release/src-rt-6.x.4708/linux/linux-2.6.36/net/ipv4/netfilter/tree_map.h

   1 /*
   2  * Copyright © 2008 by Eric Bishop <eric@gargoyle-router.com>
   3  *
   4  * This work 'as-is' we provide.
   5  * No warranty, express or implied.
   6  * We've done our best,
   7  * to debug and test.
   8  * Liability for damages denied.
   9  *
  10  * Permission is granted hereby,
  11  * to copy, share, and modify.
  12  * Use as is fit,
  13  * free or for profit.
  14  * On this notice these rights rely.
  15  *
  16  *
  17  *
  18  *  Note that unlike other portions of Gargoyle this code
  19  *  does not fall under the GPL, but the rather whimsical
  20  *  'Poetic License' above.
  21  *
  22  *  Basically, this library contains a bunch of utilities
  23  *  that I find useful.  I'm sure other libraries exist
  24  *  that are just as good or better, but I like these tools
  25  *  because I personally wrote them, so I know their quirks.
  26  *  (i.e. I know where the bodies are buried).  I want to
  27  *  make sure that I can re-use these utilities for whatever
  28  *  code I may want to write in the future be it
  29  *  proprietary or open-source, so I've put them under
  30  *  a very, very permissive license.
  31  *
  32  *  If you find this code useful, use it.  If not, don't.
  33  *  I really don't care.
  34  *
  35  */
  36
  37
  38 #if __KERNEL__
  39         #define malloc(foo)     kmalloc(foo,GFP_ATOMIC)
  40         #define free(foo)       kfree(foo)
  41         #define printf(format,args...)  printk(format,##args)
  42
  43         /* kernel strdup */
  44         static inline char *kernel_strdup(const char *str);
  45         static inline char *kernel_strdup(const char *str)
  46         {
  47                 char *tmp;
  48                 long int s;
  49                 s=strlen(str) + 1;
  50                 tmp = kmalloc(s, GFP_ATOMIC);
  51                 if (tmp != NULL)
  52                 {
  53                         memcpy(tmp, str, s);
  54                 }
  55                 return tmp;
  56         }
  57         #define strdup kernel_strdup
  58
  59 #endif
  60
  61
  62
  63 /* tree_map structs / prototypes */
  64 typedef struct long_tree_map_node
  65 {
  66         unsigned long key;
  67         void* value;
  68
  69         signed char balance;
  70         struct long_tree_map_node* left;
  71         struct long_tree_map_node* right;
  72 } long_map_node;
  73
  74 typedef struct
  75 {
  76         long_map_node* root;
  77         unsigned long num_elements;
  78
  79 }long_map;
  80
  81 typedef struct
  82 {
  83         long_map lm;
  84         unsigned char store_keys;
  85         unsigned long num_elements;
  86
  87 }string_map;
  88
  89
  90
  91 /* long map functions */
  92 long_map* initialize_long_map(void);
  93 void* get_long_map_element(long_map* map, unsigned long key);
  94 void* get_smallest_long_map_element(long_map* map, unsigned long* smallest_key);
  95 void* get_largest_long_map_element(long_map* map, unsigned long* largest_key);
  96 void* remove_smallest_long_map_element(long_map* map, unsigned long* smallest_key);
  97 void* remove_largest_long_map_element(long_map* map, unsigned long* largest_key);
  98 void* set_long_map_element(long_map* map, unsigned long key, void* value);
  99 void* remove_long_map_element(long_map* map, unsigned long key);
 100 unsigned long* get_sorted_long_map_keys(long_map* map, unsigned long* num_keys_returned);
 101 void** get_sorted_long_map_values(long_map* map, unsigned long* num_values_returned);
 102 void** destroy_long_map(long_map* map, int destruction_type, unsigned long* num_destroyed);
 103 void apply_to_every_long_map_value(long_map* map, void (*apply_func)(unsigned long key, void* value));
 104
 105 /* string map functions */
 106 string_map* initialize_string_map(unsigned char store_keys);
 107 void* get_string_map_element(string_map* map, const char* key);
 108 void* set_string_map_element(string_map* map, const char* key, void* value);
 109 void* remove_string_map_element(string_map* map, const char* key);
 110 char** get_string_map_keys(string_map* map, unsigned long* num_keys_returned);
 111 void** get_string_map_values(string_map* map, unsigned long* num_values_returned);
 112 void** destroy_string_map(string_map* map, int destruction_type, unsigned long* num_destroyed);
 113 void apply_to_every_string_map_value(string_map* map, void (*apply_func)(char* key, void* value));
 114
 115
 116 /*
 117  * three different ways to deal with values when data structure is destroyed
 118  */
 119 #define DESTROY_MODE_RETURN_VALUES      20
 120 #define DESTROY_MODE_FREE_VALUES        21
 121 #define DESTROY_MODE_IGNORE_VALUES      22
 122
 123
 124 /*
 125  * for convenience & backwards compatibility alias _string_map_ functions to
 126  *  _map_ functions since string map is used more often than long map
 127  */
 128 #define initialize_map          initialize_string_map
 129 #define set_map_element         set_string_map_element
 130 #define get_map_element         get_string_map_element
 131 #define remove_map_element      remove_string_map_element
 132 #define get_map_keys            get_string_map_keys
 133 #define get_map_values          get_string_map_values
 134 #define destroy_map             destroy_string_map
 135
 136
 137 /* internal utility structures/ functions */
 138 typedef struct stack_node_struct
 139 {
 140         long_map_node** node_ptr;
 141         signed char direction;
 142         struct stack_node_struct* previous;
 143 } stack_node;
 144
 145 static void free_stack(stack_node* stack);
 146 static void** destroy_long_map_values(long_map* map, int destruction_type, unsigned long* num_destroyed);
 147 static void apply_to_every_long_map_node(long_map_node* node, void (*apply_func)(unsigned long key, void* value));
 148 static void apply_to_every_string_map_node(long_map_node* node, unsigned char has_key, void (*apply_func)(char* key, void* value));
 149 static void get_sorted_node_keys(long_map_node* node, unsigned long* key_list, unsigned long* next_key_index, int depth);
 150 static void get_sorted_node_values(long_map_node* node, void** value_list, unsigned long* next_value_index, int depth);
 151 static signed char rebalance (long_map_node** n, signed char direction, signed char update_op);
 152 static void rotate_right (long_map_node** parent);
 153 static void rotate_left (long_map_node** parent);
 154
 155 /* internal for string map */
 156 typedef struct
 157 {
 158         char* key;
 159         void* value;
 160 } string_map_key_value;
 161 static unsigned long sdbm_string_hash(const char *key);
 162
 163
 164
 165
 166 /***************************************************
 167  * For testing only
 168  ***************************************************/
 169 /*
 170 void print_list(stack_node *l);
 171
 172 void print_list(stack_node *l)
 173 {
 174         if(l != NULL)
 175         {
 176                 printf(" list key = %ld, dir=%d, \n", (*(l->node_ptr))->key, l->direction);
 177                 print_list(l->previous);
 178         }
 179 }
 180 */
 181 /******************************************************
 182  * End testing Code
 183  *******************************************************/
 184
 185
 186
 187
 188 /***************************************************
 189  * string_map function definitions
 190  ***************************************************/
 191
 192 string_map* initialize_string_map(unsigned char store_keys)
 193 {
 194         string_map* map = (string_map*)malloc(sizeof(string_map));
 195         if(map != NULL)
 196         {
 197                 map->store_keys = store_keys;
 198                 map->lm.root = NULL;
 199                 map->lm.num_elements = 0;
 200                 map->num_elements = map->lm.num_elements;
 201         }
 202         return map;
 203 }
 204
 205 void* get_string_map_element(string_map* map, const char* key)
 206 {
 207         unsigned long hashed_key = sdbm_string_hash(key);
 208         void* return_value =  get_long_map_element( &(map->lm), hashed_key);
 209         if(return_value != NULL && map->store_keys)
 210         {
 211                 string_map_key_value* r = (string_map_key_value*)return_value;
 212                 return_value = r->value;
 213         }
 214         map->num_elements = map->lm.num_elements;
 215         return return_value;
 216 }
 217
 218 void* set_string_map_element(string_map* map, const char* key, void* value)
 219 {
 220         unsigned long hashed_key = sdbm_string_hash(key);
 221         void* return_value = NULL;
 222         if(map->store_keys)
 223         {
 224                 string_map_key_value* kv = (string_map_key_value*)malloc(sizeof(string_map_key_value));
 225                 if(kv == NULL) /* deal with malloc failure */
 226                 {
 227                         return NULL;
 228                 }
 229                 kv->key = strdup(key);
 230                 if(kv->key == NULL) /* deal with malloc failure */
 231                 {
 232                         free(kv);
 233                         return NULL;
 234                 }
 235                 kv->value = value;
 236                 return_value = set_long_map_element(  &(map->lm), hashed_key, kv);
 237                 if(return_value != NULL)
 238                 {
 239                         string_map_key_value* r = (string_map_key_value*)return_value;
 240                         return_value = r->value;
 241                         free(r->key);
 242                         free(r);
 243                 }
 244         }
 245         else
 246         {
 247                 return_value = set_long_map_element( &(map->lm), hashed_key, value);
 248         }
 249         map->num_elements = map->lm.num_elements;
 250         return return_value;
 251 }
 252
 253 void* remove_string_map_element(string_map* map, const char* key)
 254 {
 255         unsigned long hashed_key = sdbm_string_hash(key);
 256         void* return_value =  remove_long_map_element( &(map->lm), hashed_key);
 257
 258         if(return_value != NULL && map->store_keys)
 259         {
 260                 string_map_key_value* r = (string_map_key_value*)return_value;
 261                 return_value = r->value;
 262                 free(r->key);
 263                 free(r);
 264         }
 265         map->num_elements = map->lm.num_elements;
 266         return return_value;
 267 }
 268
 269 char** get_string_map_keys(string_map* map, unsigned long* num_keys_returned)
 270 {
 271         char** str_keys;
 272         str_keys = (char**)malloc((map->num_elements+1)*sizeof(char*));
 273         if(str_keys == NULL) /* deal with malloc failure */
 274         {
 275                 return NULL;
 276         }
 277         str_keys[0] = NULL;
 278         *num_keys_returned = 0;
 279         if(map->store_keys && map->num_elements > 0)
 280         {
 281                 unsigned long list_length;
 282                 void** long_values = get_sorted_long_map_values( &(map->lm),  &list_length);
 283                 unsigned long key_index;
 284                 /*list_length will be 0 on malloc failure in get_sorted_long_map_values, so this code shouldn't seg fault if that happens */
 285                 for(key_index = 0; key_index < list_length; key_index++)
 286                 {
 287                         str_keys[key_index] = strdup( ((string_map_key_value*)(long_values[key_index]))->key);
 288                         if(str_keys[key_index] == NULL) /* deal with malloc failure */
 289                         {
 290                                 //just return the incomplete list (hey, it's null terminated...)
 291                                 free(long_values);
 292                                 return str_keys;
 293                         }
 294                         *num_keys_returned = *num_keys_returned + 1;
 295                 }
 296                 str_keys[list_length] = NULL;
 297                 free(long_values);
 298         }
 299         return str_keys;
 300 }
 301
 302
 303 void** get_string_map_values(string_map* map, unsigned long* num_values_returned)
 304 {
 305         void** values = NULL;
 306         if(map != NULL)
 307         {
 308                 values = get_sorted_long_map_values ( &(map->lm), num_values_returned );
 309         }
 310         return values;
 311 }
 312
 313
 314 void** destroy_string_map(string_map* map, int destruction_type, unsigned long* num_destroyed)
 315 {
 316         void** return_values = NULL;
 317         if(map != NULL)
 318         {
 319                 if(map->store_keys)
 320                 {
 321                         void** kvs = destroy_long_map_values( &(map->lm), DESTROY_MODE_RETURN_VALUES, num_destroyed );
 322                         unsigned long kv_index = 0;
 323                         for(kv_index=0; kv_index < *num_destroyed; kv_index++)
 324                         {
 325                                 string_map_key_value* kv = (string_map_key_value*)kvs[kv_index];
 326                                 void* value = kv->value;
 327
 328                                 free(kv->key);
 329                                 free(kv);
 330                                 if(destruction_type == DESTROY_MODE_FREE_VALUES)
 331                                 {
 332                                         free(value);
 333                                 }
 334                                 if(destruction_type == DESTROY_MODE_RETURN_VALUES)
 335                                 {
 336                                         kvs[kv_index] = value;
 337                                 }
 338                         }
 339                         if(destruction_type == DESTROY_MODE_RETURN_VALUES)
 340                         {
 341                                 return_values = kvs;
 342                         }
 343                         else
 344                         {
 345                                 free(kvs);
 346                         }
 347                 }
 348                 else
 349                 {
 350                         return_values = destroy_long_map_values( &(map->lm), destruction_type, num_destroyed );
 351                 }
 352                 free(map);
 353         }
 354         return return_values;
 355 }
 356
 357
 358
 359
 360 /***************************************************
 361  * long_map function definitions
 362  ***************************************************/
 363
 364 long_map* initialize_long_map(void)
 365 {
 366         long_map* map = (long_map*)malloc(sizeof(long_map));
 367         if(map != NULL) /* test for malloc failure */
 368         {
 369                 map->root = NULL;
 370                 map->num_elements = 0;
 371         }
 372         return map;
 373 }
 374
 375 void* get_long_map_element(long_map* map, unsigned long key)
 376 {
 377         void* value = NULL;
 378
 379         if(map->root != NULL)
 380         {
 381                 long_map_node* parent_node = map->root;
 382                 long_map_node* next_node;
 383                 while( key != parent_node->key && (next_node = (long_map_node *)(key < parent_node->key ? parent_node->left : parent_node->right))  != NULL)
 384                 {
 385                         parent_node = next_node;
 386                 }
 387                 if(parent_node->key == key)
 388                 {
 389                         value = parent_node->value;
 390                 }
 391         }
 392         return value;
 393 }
 394
 395 void* get_smallest_long_map_element(long_map* map, unsigned long* smallest_key)
 396 {
 397         void* value = NULL;
 398         if(map->root != NULL)
 399         {
 400                 long_map_node* next_node = map->root;
 401                 while( next_node->left != NULL)
 402                 {
 403                         next_node = next_node->left;
 404                 }
 405                 value = next_node->value;
 406                 *smallest_key = next_node->key;
 407         }
 408         return value;
 409 }
 410
 411 void* get_largest_long_map_element(long_map* map, unsigned long* largest_key)
 412 {
 413         void* value = NULL;
 414         if(map->root != NULL)
 415         {
 416                 long_map_node* next_node = map->root;
 417                 while( next_node->right != NULL)
 418                 {
 419                         next_node = next_node->right;
 420                 }
 421                 value = next_node->value;
 422                 *largest_key = next_node->key;
 423         }
 424         return value;
 425 }
 426
 427 void* remove_smallest_long_map_element(long_map* map, unsigned long* smallest_key)
 428 {
 429         get_smallest_long_map_element(map, smallest_key);
 430         return remove_long_map_element(map, *smallest_key);
 431 }
 432
 433 void* remove_largest_long_map_element(long_map* map, unsigned long* largest_key)
 434 {
 435         get_largest_long_map_element(map, largest_key);
 436         return remove_long_map_element(map, *largest_key);
 437 }
 438
 439
 440 /* if replacement performed, returns replaced value, otherwise null */
 441 void* set_long_map_element(long_map* map, unsigned long key, void* value)
 442 {
 443         stack_node* parent_list = NULL;
 444         void* old_value = NULL;
 445         int old_value_found = 0;
 446
 447         long_map_node* parent_node;
 448         long_map_node* next_node;
 449         stack_node* next_parent;
 450         stack_node* previous_parent;
 451         signed char new_balance;
 452
 453
 454         long_map_node* new_node = (long_map_node*)malloc(sizeof(long_map_node));
 455         if(new_node == NULL)
 456         {
 457                 return NULL;
 458         }
 459         new_node->value = value;
 460         new_node->key = key;
 461         new_node->left = NULL;
 462         new_node->right = NULL;
 463         new_node->balance = 0;
 464
 465
 466
 467         if(map->root == NULL)
 468         {
 469                 map->root = new_node;
 470         }
 471         else
 472         {
 473                 parent_node = map->root;
 474
 475                 next_parent = (stack_node*)malloc(sizeof(stack_node));
 476                 if(next_parent == NULL) /* deal with malloc failure */
 477                 {
 478                         free(new_node);
 479                         return NULL; /* won't insert but won't seg fault */
 480                 }
 481                 next_parent->node_ptr =  &(map->root);
 482                 next_parent->previous = parent_list;
 483                 parent_list = next_parent;
 484
 485                 while( key != parent_node->key && (next_node = (key < parent_node->key ? parent_node->left : parent_node->right) )  != NULL)
 486                 {
 487                         next_parent = (stack_node*)malloc(sizeof(stack_node));
 488                         if(next_parent == NULL) /* deal with malloc failure */
 489                         {
 490                                 /* free previous stack nodes to prevent memory leak */
 491                                 free_stack(parent_list);
 492                                 free(new_node);
 493                                 return NULL;
 494                         }
 495                         next_parent->node_ptr = key < parent_node->key ? &(parent_node->left) : &(parent_node->right);
 496                         next_parent->previous = parent_list;
 497                         next_parent->previous->direction = key < parent_node->key ? -1 : 1;
 498                         parent_list = next_parent;
 499
 500                         parent_node = next_node;
 501                 }
 502
 503
 504                 if(key == parent_node->key)
 505                 {
 506                         old_value = parent_node->value;
 507                         old_value_found = 1;
 508                         parent_node->value = value;
 509                         free(new_node);
 510                         /* we merely replaced a node, no need to rebalance */
 511                 }
 512                 else
 513                 {
 514                         if(key < parent_node->key)
 515                         {
 516                                 parent_node->left = (void*)new_node;
 517                                 parent_list->direction = -1;
 518                         }
 519                         else
 520                         {
 521                                 parent_node->right = (void*)new_node;
 522                                 parent_list->direction = 1;
 523                         }
 524
 525
 526                         /* we inserted a node, rebalance */
 527                         previous_parent = parent_list;
 528                         new_balance  = 1; /* initial value is not used, but must not be 0 for initial loop condition */
 529
 530
 531                         while(previous_parent != NULL && new_balance != 0)
 532                         {
 533                                 new_balance = rebalance(previous_parent->node_ptr, previous_parent->direction, 1);
 534                                 previous_parent = previous_parent->previous;
 535                         }
 536                 }
 537         }
 538
 539         free_stack(parent_list);
 540
 541         if(old_value_found == 0)
 542         {
 543                 map->num_elements = map->num_elements + 1;
 544         }
 545
 546         return old_value;
 547 }
 548
 549
 550 void* remove_long_map_element(long_map* map, unsigned long key)
 551 {
 552
 553         void* value = NULL;
 554
 555         long_map_node* root_node = map->root;
 556         stack_node* parent_list = NULL;
 557
 558
 559         long_map_node* remove_parent;
 560         long_map_node* remove_node;
 561         long_map_node* next_node;
 562
 563         long_map_node* replacement;
 564         long_map_node* replacement_parent;
 565         long_map_node* replacement_next;
 566
 567         stack_node* next_parent;
 568         stack_node* previous_parent;
 569         stack_node* replacement_stack_node;
 570
 571
 572         signed char new_balance;
 573
 574
 575
 576         if(root_node != NULL)
 577         {
 578                 remove_parent = root_node;
 579                 remove_node = key < remove_parent->key ? remove_parent->left : remove_parent->right;
 580
 581                 if(remove_node != NULL && key != remove_parent->key)
 582                 {
 583                         next_parent = (stack_node*)malloc(sizeof(stack_node));
 584                         if(next_parent == NULL) /* deal with malloc failure */
 585                         {
 586                                 return NULL;
 587                         }
 588                         next_parent->node_ptr =  &(map->root);
 589                         next_parent->previous = parent_list;
 590                         parent_list = next_parent;
 591                         while( key != remove_node->key && (next_node = (key < remove_node->key ? remove_node->left : remove_node->right))  != NULL)
 592                         {
 593                                 next_parent = (stack_node*)malloc(sizeof(stack_node));
 594                                 if(next_parent == NULL) /* deal with malloc failure */
 595                                 {
 596                                         /* free previous stack nodes to prevent memory leak */
 597                                         free_stack(parent_list);
 598                                         return NULL;
 599                                 }
 600                                 next_parent->node_ptr = key < remove_parent->key ? &(remove_parent->left) : &(remove_parent->right);
 601                                 next_parent->previous = parent_list;
 602                                 next_parent->previous->direction = key < remove_parent->key ? -1 : 1;
 603                                 parent_list = next_parent;
 604
 605
 606                                 remove_parent = remove_node;
 607                                 remove_node = next_node;
 608                         }
 609                         parent_list->direction = key < remove_parent-> key ? -1 : 1;
 610                 }
 611                 else
 612                 {
 613                         remove_node = remove_parent;
 614                 }
 615
 616
 617                 if(key == remove_node->key)
 618                 {
 619
 620                         /* find replacement for node we are deleting */
 621                         if( remove_node->right == NULL )
 622                         {
 623                                 replacement = remove_node->left;
 624                         }
 625                         else if( remove_node->right->left == NULL)
 626                         {
 627
 628                                 replacement = remove_node->right;
 629                                 replacement->left = remove_node->left;
 630                                 replacement->balance = remove_node->balance;
 631
 632                                 /* put pointer to replacement node into list for balance update */
 633                                 replacement_stack_node = (stack_node*)malloc(sizeof(stack_node));
 634                                 if(replacement_stack_node == NULL) /* deal with malloc failure */
 635                                 {
 636                                         /* free previous stack nodes to prevent memory leak */
 637                                         free_stack(parent_list);
 638                                         return NULL;
 639                                 }
 640                                 replacement_stack_node->previous = parent_list;
 641                                 replacement_stack_node->direction = 1; /* replacement is from right */
 642                                 if(remove_node == remove_parent) /* special case for root node */
 643                                 {
 644                                         replacement_stack_node->node_ptr = &(map->root);
 645                                 }
 646                                 else
 647                                 {
 648                                         replacement_stack_node->node_ptr = key < remove_parent-> key ? &(remove_parent->left) : &(remove_parent->right);
 649                                 }
 650                                 parent_list = replacement_stack_node;
 651
 652                         }
 653                         else
 654                         {
 655                                 /* put pointer to replacement node into list for balance update */
 656                                 replacement_stack_node = (stack_node*)malloc(sizeof(stack_node));
 657                                 if(replacement_stack_node == NULL) /* deal with malloc failure */
 658                                 {
 659                                         /* free previous stack nodes to prevent memory leak */
 660                                         free_stack(parent_list);
 661                                         return NULL;
 662                                 }
 663
 664                                 replacement_stack_node->previous = parent_list;
 665                                 replacement_stack_node->direction = 1; /* we always look for replacement on right */
 666                                 if(remove_node == remove_parent) /* special case for root node */
 667                                 {
 668                                         replacement_stack_node->node_ptr = &(map->root);
 669                                 }
 670                                 else
 671                                 {
 672                                         replacement_stack_node->node_ptr = key < remove_parent-> key ? &(remove_parent->left) : &(remove_parent->right);
 673                                 }
 674
 675                                 parent_list = replacement_stack_node;
 676
 677
 678                                 /*
 679                                  * put pointer to replacement node->right into list for balance update
 680                                  * this node will have to be updated with the proper pointer
 681                                  * after we have identified the replacement
 682                                  */
 683                                 replacement_stack_node = (stack_node*)malloc(sizeof(stack_node));
 684                                 if(replacement_stack_node == NULL) /* deal with malloc failure */
 685                                 {
 686                                         /* free previous stack nodes to prevent memory leak */
 687                                         free_stack(parent_list);
 688                                         return NULL;
 689                                 }
 690
 691                                 replacement_stack_node->previous = parent_list;
 692                                 replacement_stack_node->direction = -1; /* we always look for replacement to left of this node */
 693                                 parent_list = replacement_stack_node;
 694
 695                                 /* find smallest node on right (large) side of tree */
 696                                 replacement_parent = remove_node->right;
 697                                 replacement = replacement_parent->left;
 698
 699                                 while((replacement_next = replacement->left)  != NULL)
 700                                 {
 701                                         next_parent = (stack_node*)malloc(sizeof(stack_node));
 702                                         if(next_parent == NULL) /* deal with malloc failure */
 703                                         {
 704                                                 /* free previous stack nodes to prevent memory leak */
 705                                                 free_stack(parent_list);
 706                                                 return NULL;
 707                                         }
 708
 709                                         next_parent->node_ptr = &(replacement_parent->left);
 710                                         next_parent->previous = parent_list;
 711                                         next_parent->direction = -1; /* we always go left */
 712                                         parent_list = next_parent;
 713
 714                                         replacement_parent = replacement;
 715                                         replacement = replacement_next;
 716
 717                                 }
 718
 719                                 replacement_parent->left = replacement->right;
 720
 721                                 replacement->left = remove_node->left;
 722                                 replacement->right = remove_node->right;
 723                                 replacement->balance = remove_node->balance;
 724                                 replacement_stack_node->node_ptr = &(replacement->right);
 725                         }
 726
 727                         /* insert replacement at proper location in tree */
 728                         if(remove_node == remove_parent)
 729                         {
 730                                 map->root = replacement;
 731                         }
 732                         else
 733                         {
 734                                 remove_parent->left = remove_node == remove_parent->left ? replacement : remove_parent->left;
 735                                 remove_parent->right = remove_node == remove_parent->right ? replacement : remove_parent->right;
 736                         }
 737
 738
 739                         /* rebalance tree */
 740                         previous_parent = parent_list;
 741                         new_balance = 0;
 742                         while(previous_parent != NULL && new_balance == 0)
 743                         {
 744                                 new_balance = rebalance(previous_parent->node_ptr, previous_parent->direction, -1);
 745                                 previous_parent = previous_parent->previous;
 746                         }
 747
 748
 749
 750
 751                         /*
 752                          * since we found a value to remove, decrease number of elements in map
 753                          *  set return value to the deleted node's value and free the node
 754                          */
 755                         map->num_elements = map->num_elements - 1;
 756                         value = remove_node->value;
 757                         free(remove_node);
 758                 }
 759         }
 760
 761         free_stack(parent_list);
 762
 763         return value;
 764 }
 765
 766
 767 /* note: returned keys are dynamically allocated, you need to free them! */
 768 unsigned long* get_sorted_long_map_keys(long_map* map, unsigned long* num_keys_returned)
 769 {
 770         unsigned long* key_list = (unsigned long*)malloc((map->num_elements)*sizeof(unsigned long));
 771         unsigned long next_key_index;
 772         if(key_list == NULL)
 773         {
 774                 *num_keys_returned = 0;
 775                 return NULL;
 776         }
 777         next_key_index = 0;
 778         get_sorted_node_keys(map->root, key_list, &next_key_index, 0);
 779
 780         *num_keys_returned = map->num_elements;
 781
 782         return key_list;
 783 }
 784
 785
 786 void** get_sorted_long_map_values(long_map* map, unsigned long* num_values_returned)
 787 {
 788         void** value_list = (void**)malloc((map->num_elements+1)*sizeof(void*));
 789         unsigned long next_value_index;
 790
 791         if(value_list == NULL)
 792         {
 793                 *num_values_returned = 0;
 794                 return NULL;
 795         }
 796         next_value_index = 0;
 797         get_sorted_node_values(map->root, value_list, &next_value_index, 0);
 798         value_list[map->num_elements] = NULL; /* since we're dealing with pointers make list null terminated */
 799
 800         *num_values_returned = map->num_elements;
 801         return value_list;
 802
 803 }
 804
 805
 806
 807 void** destroy_long_map(long_map* map, int destruction_type, unsigned long* num_destroyed)
 808 {
 809         void** return_values = destroy_long_map_values(map, destruction_type, num_destroyed);
 810         free(map);
 811         return return_values;
 812 }
 813
 814
 815
 816 void apply_to_every_long_map_value(long_map* map, void (*apply_func)(unsigned long key, void* value))
 817 {
 818         apply_to_every_long_map_node(map->root, apply_func);
 819 }
 820 void apply_to_every_string_map_value(string_map* map, void (*apply_func)(char* key, void* value))
 821 {
 822         apply_to_every_string_map_node( (map->lm).root, map->store_keys, apply_func);
 823 }
 824
 825
 826 /***************************************************
 827  * internal utility function definitions
 828  ***************************************************/
 829 static void free_stack(stack_node* stack)
 830 {
 831         while(stack != NULL)
 832         {
 833                 stack_node* prev_node = stack;
 834                 stack = prev_node->previous;
 835                 free(prev_node);
 836         }
 837
 838 }
 839
 840 static void** destroy_long_map_values(long_map* map, int destruction_type, unsigned long* num_destroyed)
 841 {
 842         void** return_values = NULL;
 843         unsigned long return_index = 0;
 844
 845         *num_destroyed = 0;
 846
 847         if(destruction_type == DESTROY_MODE_RETURN_VALUES)
 848         {
 849                 return_values = (void**)malloc((map->num_elements+1)*sizeof(void*));
 850                 if(return_values == NULL) /* deal with malloc failure */
 851                 {
 852                         destruction_type = DESTROY_MODE_IGNORE_VALUES; /* could cause memory leak, but there's no other way to be sure we won't seg fault */
 853                 }
 854                 else
 855                 {
 856                         return_values[map->num_elements] = NULL;
 857                 }
 858         }
 859         while(map->num_elements > 0)
 860         {
 861                 unsigned long smallest_key;
 862                 void* removed_value = remove_smallest_long_map_element(map, &smallest_key);
 863                 if(destruction_type == DESTROY_MODE_RETURN_VALUES)
 864                 {
 865                         return_values[return_index] = removed_value;
 866                 }
 867                 if(destruction_type == DESTROY_MODE_FREE_VALUES)
 868                 {
 869                         free(removed_value);
 870                 }
 871                 return_index++;
 872                 *num_destroyed = *num_destroyed + 1;
 873         }
 874         return return_values;
 875 }
 876
 877 static void apply_to_every_long_map_node(long_map_node* node, void (*apply_func)(unsigned long key, void* value))
 878 {
 879         if(node != NULL)
 880         {
 881                 apply_to_every_long_map_node(node->left,  apply_func);
 882
 883                 apply_func(node->key, node->value);
 884
 885                 apply_to_every_long_map_node(node->right, apply_func);
 886         }
 887 }
 888 static void apply_to_every_string_map_node(long_map_node* node, unsigned char has_key, void (*apply_func)(char* key, void* value))
 889 {
 890         if(node != NULL)
 891         {
 892                 apply_to_every_string_map_node(node->left, has_key,  apply_func);
 893
 894                 if(has_key)
 895                 {
 896                         string_map_key_value* kv = (string_map_key_value*)(node->value);
 897                         apply_func(kv->key, kv->value);
 898                 }
 899                 else
 900                 {
 901                         apply_func(NULL, node->value);
 902                 }
 903                 apply_to_every_string_map_node(node->right, has_key, apply_func);
 904         }
 905 }
 906
 907
 908
 909 static void get_sorted_node_keys(long_map_node* node, unsigned long* key_list, unsigned long* next_key_index, int depth)
 910 {
 911         if(node != NULL)
 912         {
 913                 get_sorted_node_keys(node->left, key_list, next_key_index, depth+1);
 914
 915                 key_list[ *next_key_index ] = node->key;
 916                 (*next_key_index)++;
 917
 918                 get_sorted_node_keys(node->right, key_list, next_key_index, depth+1);
 919         }
 920 }
 921
 922 static void get_sorted_node_values(long_map_node* node, void** value_list, unsigned long* next_value_index, int depth)
 923 {
 924         if(node != NULL)
 925         {
 926                 get_sorted_node_values(node->left, value_list, next_value_index, depth+1);
 927
 928                 value_list[ *next_value_index ] = node->value;
 929                 (*next_value_index)++;
 930
 931                 get_sorted_node_values(node->right, value_list, next_value_index, depth+1);
 932         }
 933 }
 934
 935
 936
 937 /*
 938  * direction = -1 indicates left subtree updated, direction = 1 for right subtree
 939  * update_op = -1 indicates delete node, update_op = 1 for insert node
 940  */
 941 static signed char rebalance (long_map_node** n, signed char direction, signed char update_op)
 942 {
 943         /*
 944         printf( "original: key = %ld, balance = %d, update_op=%d, direction=%d\n", (*n)->key, (*n)->balance, update_op, direction);
 945         */
 946
 947         (*n)->balance = (*n)->balance + (update_op*direction);
 948
 949         if( (*n)->balance <  -1)
 950         {
 951                 if((*n)->left->balance < 0)
 952                 {
 953                         rotate_right(n);
 954                         (*n)->right->balance = 0;
 955                         (*n)->balance = 0;
 956                 }
 957                 else if((*n)->left->balance == 0)
 958                 {
 959                         rotate_right(n);
 960                         (*n)->right->balance = -1;
 961                         (*n)->balance = 1;
 962                 }
 963                 else if((*n)->left->balance > 0)
 964                 {
 965                         rotate_left( &((*n)->left) );
 966                         rotate_right(n);
 967                         /*
 968                         if( (*n)->balance < 0 )
 969                         {
 970                                 (*n)->left->balance = 0;
 971                                 (*n)->right->balance = 1;
 972                         }
 973                         else if( (*n)->balance == 0 )
 974                         {
 975                                 (*n)->left->balance = 0;
 976                                 (*n)->right->balance = 0;
 977                         }
 978                         else if( (*n)->balance > 0 )
 979                         {
 980                                 (*n)->left->balance = -1;
 981                                 (*n)->right->balance = 0;
 982                         }
 983                         */
 984                         (*n)->left->balance  = (*n)->balance > 0 ? -1 : 0;
 985                         (*n)->right->balance = (*n)->balance < 0 ?  1 : 0;
 986                         (*n)->balance = 0;
 987                 }
 988         }
 989         if( (*n)->balance >  1)
 990         {
 991                 if((*n)->right->balance > 0)
 992                 {
 993                         rotate_left(n);
 994                         (*n)->left->balance = 0;
 995                         (*n)->balance = 0;
 996                 }
 997                 else if ((*n)->right->balance == 0)
 998                 {
 999                         rotate_left(n);
1000                         (*n)->left->balance = 1;
1001                         (*n)->balance = -1;
1002                 }
1003                 else if((*n)->right->balance < 0)
1004                 {
1005                         rotate_right( &((*n)->right) );
1006                         rotate_left(n);
1007                         /*
1008                         if( (*n)->balance < 0 )
1009                         {
1010                                 (*n)->left->balance = 0;
1011                                 (*n)->right->balance = 1;
1012                         }
1013                         else if( (*n)->balance == 0 )
1014                         {
1015                                 (*n)->left->balance = 0;
1016                                 (*n)->right->balance = 0;
1017                         }
1018                         else if( (*n)->balance > 0 )
1019                         {
1020                                 (*n)->left->balance = -1;
1021                                 (*n)->right->balance = 0;
1022                         }
1023                         */
1024                         (*n)->left->balance   = (*n)->balance > 0 ? -1 : 0;
1025                         (*n)->right->balance  = (*n)->balance < 0 ?  1 : 0;
1026                         (*n)->balance = 0;
1027                 }
1028         }
1029
1030         /*
1031         printf( "key = %ld, balance = %d\n", (*n)->key, (*n)->balance);
1032         */
1033
1034         return (*n)->balance;
1035 }
1036
1037
1038 static void rotate_right (long_map_node** parent)
1039 {
1040         long_map_node* old_parent = *parent;
1041         long_map_node* pivot = old_parent->left;
1042         old_parent->left = pivot->right;
1043         pivot->right  = old_parent;
1044
1045         *parent = pivot;
1046 }
1047
1048 static void rotate_left (long_map_node** parent)
1049 {
1050         long_map_node* old_parent = *parent;
1051         long_map_node* pivot = old_parent->right;
1052         old_parent->right = pivot->left;
1053         pivot->left  = old_parent;
1054
1055         *parent = pivot;
1056 }
1057
1058
1059
1060 /***************************************************************************
1061  * This algorithm was created for the sdbm database library (a public-domain
1062  * reimplementation of ndbm) and seems to work relatively well in
1063  * scrambling bits
1064  *
1065  *
1066  * This code was derived from code found at:
1067  * http://www.cse.yorku.ca/~oz/hash.html
1068  ***************************************************************************/
1069 static unsigned long sdbm_string_hash(const char *key)
1070 {
1071         unsigned long hashed_key = 0;
1072
1073         int index = 0;
1074         unsigned int nextch;
1075         while(key[index] != '\0')
1076         {
1077                 nextch = key[index];
1078                 hashed_key = nextch + (hashed_key << 6) + (hashed_key << 16) - hashed_key;
1079                 index++;
1080         }
1081         return hashed_key;
1082 }
1083
1084