src/tree.c

   1 /* the Music Player Daemon (MPD)
   2  * Copyright (C) 2006-2007 by Warren Dukes (warren.dukes@gmail.com)
   3  * This project's homepage is: http://www.musicpd.org
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19 #include "tree.h"
  20 #include "utils.h"
  21
  22 #include <assert.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #ifndef CHILDREN_PER_NODE
  27 #define CHILDREN_PER_NODE 25
  28 #endif
  29
  30 #define DATA_PER_NODE (CHILDREN_PER_NODE-1)
  31
  32 #if CHILDREN_PER_NODE > 7
  33 #define USE_BINARY_SEARCH 1
  34 #endif
  35
  36
  37 /************************* DATA STRUCTURES **********************************/
  38
  39 struct _TreeNode
  40 {
  41         TreeKeyData keyData[DATA_PER_NODE];
  42         struct _TreeNode * parent;
  43         short parentPos;
  44         struct _TreeNode * children[CHILDREN_PER_NODE];
  45         short count;
  46 };
  47
  48 struct _Tree
  49 {
  50         TreeCompareKeyFunction compareKey;
  51         TreeFreeFunction freeKey;
  52         TreeFreeFunction freeData;
  53         TreeNode * rootNode;
  54         int size;
  55 };
  56
  57 /************************* STATIC METHODS ***********************************/
  58
  59 static
  60 TreeNode *
  61 _MakeNode(void)
  62 {
  63         TreeNode * ret = xmalloc(sizeof(TreeNode));
  64         memset(ret, 0, sizeof(TreeNode));
  65         return ret;
  66 }
  67
  68 static
  69 void
  70 _ClearKeyData(TreeKeyData * keyData)
  71 {
  72         memset(keyData, 0, sizeof(TreeKeyData));
  73 }
  74
  75 static
  76 int
  77 _FindPosition(Tree * tree, TreeNode * node, void * key, int * pos)
  78 {
  79 #ifdef USE_BINARY_SEARCH
  80         int low = 0;
  81         int high = node->count;
  82         int cmp = -1;
  83
  84         while (high > low)
  85         {
  86                 int cur = (high + low) >> 1;
  87                 cmp = tree->compareKey(key, node->keyData[cur].key);
  88                 if (cmp > 0)
  89                 {
  90                         low = cur+1;
  91                 }
  92                 else if (cmp < 0)
  93                 {
  94                         high = cur;
  95                 }
  96                 else
  97                 {
  98                         low = cur;
  99                         break;
 100                 }
 101         }
 102
 103         *pos = low;
 104         return (cmp == 0);
 105 #else
 106         int i = 0;
 107         int cmp = -1;
 108         for (;
 109              i < node->count &&
 110              (cmp = tree->compareKey(key, node->keyData[i].key)) > 0;
 111              i++);
 112         *pos = i;
 113         return (cmp == 0);
 114 #endif
 115 }
 116
 117 static
 118 int
 119 _Find(TreeIterator * iter, void * key)
 120 {
 121         while (1)
 122         {
 123                 if (_FindPosition(iter->tree, iter->node, key, &iter->which))
 124                 {
 125                         iter->which++;
 126                         return 1;
 127                 }
 128
 129                 if (iter->node->children[iter->which])
 130                 {
 131                         iter->node = iter->node->children[iter->which];
 132                 }
 133                 else
 134                 {
 135                         return 0;
 136                 }
 137         }
 138 }
 139
 140 static void _SetIteratorToRoot(Tree * tree, TreeIterator * iter)
 141 {
 142         iter->tree = tree;
 143         iter->node = tree->rootNode;
 144         iter->which = 0;
 145 }
 146
 147 static
 148 TreeNode *
 149 _SplitNode(TreeNode * node)
 150 {
 151         TreeNode *newNode = _MakeNode();
 152         int i = DATA_PER_NODE/2;
 153         int j = 0;
 154
 155         assert(node->count == DATA_PER_NODE);
 156
 157         for (; i < DATA_PER_NODE; i++, j++)
 158         {
 159                 newNode->keyData[j] = node->keyData[i];
 160                 newNode->children[j+1] = node->children[i+1];
 161                 if (newNode->children[j+1])
 162                 {
 163                         newNode->children[j+1]->parent = newNode;
 164                         newNode->children[j+1]->parentPos = j+1;
 165                 }
 166                 _ClearKeyData(&(node->keyData[i]));
 167                 node->children[i+1] = NULL;
 168         }
 169         newNode->count = (DATA_PER_NODE-DATA_PER_NODE/2);
 170         node->count -= (DATA_PER_NODE-DATA_PER_NODE/2);
 171
 172         return newNode;
 173 }
 174
 175 static
 176 void
 177 _InsertNodeAndData(Tree * tree,
 178                    TreeNode * node,
 179                    int pos,
 180                    TreeNode * newNode,
 181                    TreeKeyData keyData)
 182 {
 183         int j = node->count;
 184
 185         assert(node->count < DATA_PER_NODE);
 186
 187         for (; j > pos; j--)
 188         {
 189                 node->keyData[j] = node->keyData[j-1];
 190                 node->children[j+1] = node->children[j];
 191                 if (node->children[j+1])
 192                 {
 193                         node->children[j+1]->parentPos = j+1;
 194                 }
 195         }
 196
 197         node->keyData[pos] = keyData;
 198         node->count++;
 199
 200         node->children[pos+1] = newNode;
 201         if (newNode)
 202         {
 203                 newNode->parent = node;
 204                 newNode->parentPos = pos+1;
 205         }
 206 }
 207
 208 static
 209 TreeKeyData
 210 _AddDataToSplitNodes(Tree * tree,
 211                      TreeNode * lessNode,
 212                      TreeNode * moreNode,
 213                      int pos,
 214                      TreeNode * newNode,
 215                      TreeKeyData keyData)
 216 {
 217         TreeKeyData retKeyData;
 218
 219         assert(moreNode->children[0] == NULL);
 220
 221         if (pos <= lessNode->count)
 222         {
 223                 _InsertNodeAndData(tree, lessNode, pos, newNode, keyData);
 224                 lessNode->count--;
 225                 retKeyData = lessNode->keyData[lessNode->count];
 226                 _ClearKeyData(&(lessNode->keyData[lessNode->count]));
 227                 moreNode->children[0] =
 228                         lessNode->children[lessNode->count+1];
 229                 if (moreNode->children[0])
 230                 {
 231                         moreNode->children[0]->parent = moreNode;
 232                         moreNode->children[0]->parentPos = 0;
 233                 }
 234                 lessNode->children[lessNode->count+1] = NULL;
 235         }
 236         else
 237         {
 238                 int j;
 239
 240                 pos -= lessNode->count;
 241                 retKeyData = moreNode->keyData[0];
 242                 assert(!moreNode->children[0]);
 243
 244                 for (j = 0; j < pos; j++)
 245                 {
 246                         moreNode->keyData[j] = moreNode->keyData[j+1];
 247                         moreNode->children[j] = moreNode->children[j+1];
 248                         if (moreNode->children[j])
 249                         {
 250                                 moreNode->children[j]->parentPos = j;
 251                         }
 252                 }
 253
 254                 moreNode->keyData[pos-1] = keyData;
 255                 moreNode->children[pos] = newNode;
 256                 if (newNode)
 257                 {
 258                         newNode->parent = moreNode;
 259                         newNode->parentPos = pos;
 260                 }
 261         }
 262
 263         return retKeyData;
 264 }
 265
 266 static
 267 void
 268 _InsertAt(TreeIterator * iter, TreeKeyData keyData)
 269 {
 270         TreeNode * node = iter->node;
 271         TreeNode * insertNode = NULL;
 272         int pos = iter->which;
 273
 274         while (node != NULL)
 275         {
 276                 /* see if there's any NULL data in the current node */
 277                 if (node->count == DATA_PER_NODE)
 278                 {
 279                         /* no open data slots, split this node! */
 280                         TreeNode * newNode = _SplitNode(node);
 281
 282                         /* insert data in split nodes */
 283                         keyData = _AddDataToSplitNodes(iter->tree,
 284                                                        node,
 285                                                        newNode,
 286                                                        pos,
 287                                                        insertNode,
 288                                                        keyData);
 289
 290                         if (node->parent == NULL)
 291                         {
 292                                 assert(node == iter->tree->rootNode);
 293                                 iter->tree->rootNode = _MakeNode();
 294                                 iter->tree->rootNode->children[0] = node;
 295                                 node->parent = iter->tree->rootNode;
 296                                 node->parentPos = 0;
 297                                 iter->tree->rootNode->children[1] = newNode;
 298                                 newNode->parent = iter->tree->rootNode;
 299                                 newNode->parentPos = 1;
 300                                 iter->tree->rootNode->keyData[0] = keyData;
 301                                 iter->tree->rootNode->count = 1;
 302                                 return;
 303                         }
 304
 305                         pos = node->parentPos;
 306                         node = node->parent;
 307                         insertNode = newNode;
 308                 }
 309                 else
 310                 {
 311                         /* insert the data and newNode */
 312                         _InsertNodeAndData(iter->tree,
 313                                            node,
 314                                            pos,
 315                                            insertNode,
 316                                            keyData);
 317                         return;
 318                 }
 319         }
 320 }
 321
 322 static
 323 void
 324 _MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
 325 {
 326         int i = 0;
 327         int j = lessNode->count;
 328
 329         assert((lessNode->count + moreNode->count) <= DATA_PER_NODE);
 330         assert(lessNode->children[j] == NULL);
 331
 332         for(; i < moreNode->count; i++,j++)
 333         {
 334                 assert(!lessNode->children[j]);
 335                 lessNode->keyData[j] = moreNode->keyData[i];
 336                 lessNode->children[j] = moreNode->children[i];
 337                 if (lessNode->children[j])
 338                 {
 339                         lessNode->children[j]->parent = lessNode;
 340                         lessNode->children[j]->parentPos = j;
 341                 }
 342         }
 343         lessNode->children[j] = moreNode->children[i];
 344         if (lessNode->children[j])
 345         {
 346                 lessNode->children[j]->parent = lessNode;
 347                 lessNode->children[j]->parentPos = j;
 348         }
 349         lessNode->count += i;
 350
 351         free(moreNode);
 352 }
 353
 354 static void _DeleteAt(TreeIterator * iter)
 355 {
 356         TreeNode * node = iter->node;
 357         int pos = iter->which - 1;
 358         TreeKeyData * keyData = &(node->keyData[pos]);
 359         TreeKeyData keyDataToFree = *keyData;
 360         int i;
 361
 362         {
 363                 /* find the least greater than data to fill the whole! */
 364                 if (node->children[pos+1])
 365                 {
 366                         TreeNode * child = node->children[++pos];
 367                         while (child->children[0])
 368                         {
 369                                 pos = 0;
 370                                 child = child->children[0];
 371                         }
 372
 373                         *keyData = child->keyData[0];
 374                         keyData = &(child->keyData[0]);
 375                         node = child;
 376                 }
 377                 /* or the greatest lesser than data to fill the whole! */
 378                 else if (node->children[pos])
 379                 {
 380                         TreeNode * child = node->children[pos];
 381                         while (child->children[child->count])
 382                         {
 383                                 pos = child->count;
 384                                 child = child->children[child->count];
 385                         }
 386
 387                         *keyData = child->keyData[child->count-1];
 388                         keyData = &(child->keyData[child->count-1]);
 389                         node = child;
 390                 }
 391                 else
 392                 {
 393                         pos = node->parentPos;
 394                 }
 395         }
 396
 397         /* move data nodes over, we're at a leaf node, so we can ignore
 398            children */
 399         i = keyData - node->keyData;
 400         for (; i < node->count-1; i++)
 401         {
 402                 node->keyData[i] = node->keyData[i+1];
 403         }
 404         _ClearKeyData(&(node->keyData[--node->count]));
 405
 406         /* merge the nodes from the bottom up which have too few data */
 407         while (node->count < (DATA_PER_NODE/2))
 408         {
 409                 /* if we're not the root */
 410                 if (node->parent)
 411                 {
 412                         TreeNode ** child = &(node->parent->children[pos]);
 413                         assert(node->parent->children[pos] == node);
 414
 415                         /* check siblings for extra data */
 416                         if (pos < node->parent->count &&
 417                             (*(child+1))->count > (DATA_PER_NODE/2))
 418                         {
 419                                 child++;
 420                                 node->keyData[node->count++] =
 421                                         node->parent->keyData[pos];
 422                                 node->children[node->count] =
 423                                         (*child)->children[0];
 424                                 if (node->children[node->count])
 425                                 {
 426                                         node->children[node->count]->
 427                                                 parent = node;
 428                                         node->children[node->count]->
 429                                                 parentPos = node->count;
 430                                 }
 431                                 node->parent->keyData[pos] =
 432                                         (*child)->keyData[0];
 433                                 i = 0;
 434                                 for(; i < (*child)->count-1; i++)
 435                                 {
 436                                         (*child)->keyData[i] =
 437                                                 (*child)->keyData[i+1];
 438                                         (*child)->children[i] =
 439                                                 (*child)->children[i+1];
 440                                         if ((*child)->children[i])
 441                                         {
 442                                                 (*child)->children[i]->
 443                                                         parentPos = i;
 444                                         }
 445                                 }
 446                                 (*child)->children[i] = (*child)->children[i+1];
 447                                 if ((*child)->children[i])
 448                                 {
 449                                         (*child)->children[i]->parentPos = i;
 450                                 }
 451                                 (*child)->children[i+1] =NULL;
 452                                 _ClearKeyData(&((*child)->keyData[i]));
 453                                 (*child)->count--;
 454                         }
 455                         else if (pos > 0 &&
 456                                  (*(child-1))->count>(DATA_PER_NODE/2))
 457                         {
 458                                 child--;
 459                                 i = node->count++;
 460                                 for(; i > 0; i--)
 461                                 {
 462                                         node->keyData[i] = node->keyData[i-1];
 463                                         node->children[i+1] = node->children[i];
 464                                         if (node->children[i+1])
 465                                         {
 466                                                 node->children[i+1]->parentPos =
 467                                                         i+1;
 468                                         }
 469                                 }
 470                                 node->children[1] = node->children[0];
 471                                 if (node->children[1])
 472                                 {
 473                                         node->children[1]->parentPos = 1;
 474                                 }
 475                                 node->keyData[0] = node->parent->keyData[pos-1];
 476                                 node->children[0] =
 477                                         (*child)->children[(*child)->count];
 478                                 if (node->children[0])
 479                                 {
 480                                         node->children[0]->parent = node;
 481                                         node->children[0]->parentPos = 0;
 482                                 }
 483                                 node->parent->keyData[pos-1] =
 484                                         (*child)->keyData[(*child)->count-1];
 485                                 (*child)->children[(*child)->count--] =
 486                                         NULL;
 487                                 _ClearKeyData(
 488                                         &((*child)->keyData[(*child)->count]));
 489                         }
 490                         /* merge with one of our siblings */
 491                         else
 492                         {
 493                                 if (pos < node->parent->count)
 494                                 {
 495                                         child++;
 496                                         assert(*child);
 497
 498                                         node->keyData[node->count++] =
 499                                                 node->parent->keyData[pos];
 500
 501                                         _MergeNodes(node, *child);
 502                                 }
 503                                 else
 504                                 {
 505                                         assert(pos > 0);
 506                                         child--;
 507                                         assert(*child);
 508                                         pos--;
 509
 510                                         (*child)->keyData[(*child)->count++] =
 511                                                 node->parent->keyData[pos];
 512
 513                                         _MergeNodes(*child, node);
 514                                         node = *child;
 515                                 }
 516
 517                                 i = pos;
 518                                 for(; i < node->parent->count-1; i++)
 519                                 {
 520                                         node->parent->keyData[i] =
 521                                                 node->parent->keyData[i+1];
 522                                         node->parent->children[i+1] =
 523                                                 node->parent->children[i+2];
 524                                         if (node->parent->children[i+1])
 525                                         {
 526                                                 node->parent->children[i+1]->
 527                                                         parentPos = i+1;
 528                                         }
 529                                 }
 530                                 _ClearKeyData(&(node->parent->keyData[i]));
 531                                 node->parent->children[i+1] = NULL;
 532                                 node->parent->count--;
 533
 534                                 node = node->parent;
 535                                 pos = node->parentPos;
 536                         }
 537                 }
 538                 /* this is a root node */
 539                 else
 540                 {
 541                         if (node->count == 0)
 542                         {
 543                                 if (node->children[0])
 544                                 {
 545                                         node->children[0]->parent = NULL;
 546                                         node->children[0]->parentPos = 0;
 547                                 }
 548
 549                                 iter->tree->rootNode = node->children[0];
 550
 551                                 free(node);
 552                         }
 553
 554                         break;
 555                 }
 556         }
 557
 558         if (iter->tree->freeKey)
 559         {
 560                 iter->tree->freeData(keyDataToFree.key);
 561         }
 562         if (iter->tree->freeData)
 563         {
 564                 iter->tree->freeData(keyDataToFree.data);
 565         }
 566 }
 567
 568 /************************* PUBLIC METHODS ***********************************/
 569
 570 Tree *
 571 MakeTree(TreeCompareKeyFunction compareKey,
 572          TreeFreeFunction freeKey,
 573          TreeFreeFunction freeData)
 574 {
 575         Tree * ret = xmalloc(sizeof(Tree));
 576         ret->compareKey = compareKey;
 577         ret->freeKey = freeKey;
 578         ret->freeData = freeData;
 579         ret->rootNode = _MakeNode();
 580         ret->size = 0;
 581         return ret;
 582 }
 583
 584 void
 585 FreeTree(Tree * tree)
 586 {
 587         assert(tree->rootNode == NULL);
 588         free(tree);
 589 }
 590
 591 int
 592 GetTreeSize(Tree * tree)
 593 {
 594         return tree->size;
 595 }
 596
 597 void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter)
 598 {
 599         _SetIteratorToRoot(tree, iter);
 600         IncrementTreeIterator(iter);
 601 }
 602
 603 int IsTreeIteratorAtEnd(const TreeIterator * iter)
 604 {
 605         return (iter->node == NULL);
 606 }
 607
 608 void IncrementTreeIterator(TreeIterator * iter)
 609 {
 610         while(iter->node)
 611         {
 612                 if (iter->node->children[iter->which])
 613                 {
 614                         iter->node = iter->node->children[iter->which];
 615                         iter->which = 0;
 616                 }
 617                 else
 618                 {
 619                         iter->which++;
 620                 }
 621
 622                 while (iter->node && iter->which > iter->node->count)
 623                 {
 624                         iter->which = iter->node->parentPos + 1;
 625                         iter->node = iter->node->parent;
 626                 }
 627
 628                 if (iter->node &&
 629                     iter->which > 0 && iter->which <= iter->node->count)
 630                 {
 631                         return;
 632                 }
 633         }
 634 }
 635
 636 TreeKeyData
 637 GetTreeKeyData(TreeIterator * iter)
 638 {
 639         assert(iter->node &&
 640                iter->which > 0 &&
 641                iter->which <= iter->node->count);
 642         return iter->node->keyData[iter->which-1];
 643 }
 644
 645 int
 646 InsertInTree(Tree * tree, void * key, void * data)
 647 {
 648         TreeKeyData keyData;
 649         TreeIterator iter;
 650
 651         _SetIteratorToRoot(tree, &iter);
 652
 653         if (_Find(&iter, key))
 654         {
 655                 return 0;
 656         }
 657
 658         keyData.key = key;
 659         keyData.data = data;
 660         _InsertAt(&iter, keyData);
 661         tree->size++;
 662
 663         return 1;
 664 }
 665
 666 int
 667 RemoveFromTreeByKey(Tree * tree, void * key)
 668 {
 669         TreeIterator iter;
 670         _SetIteratorToRoot(tree, &iter);
 671
 672         if (_Find(&iter, key))
 673         {
 674                 _DeleteAt(&iter);
 675                 tree->size--;
 676                 return 1;
 677         }
 678
 679         return 0;
 680 }
 681
 682 void
 683 RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter)
 684 {
 685         _DeleteAt(iter);
 686         tree->size--;
 687 }
 688
 689 int
 690 FindInTree(Tree * tree, void * key, TreeIterator * iter)
 691 {
 692         TreeIterator i;
 693
 694         if (iter == NULL)
 695         {
 696                 iter = &i;
 697         }
 698
 699         _SetIteratorToRoot(tree, iter);
 700         if (_Find(iter, key))
 701         {
 702                 return 1;
 703         }
 704
 705         return 0;
 706 }