Subversion Repositories pentevo

Rev

Blame | Last modification | View Log | Download | RSS feed | ?url?

  1. /* trees.c */
  2. /*****************************************************************************/
  3. /* SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only                     */
  4. /*                                                                           */
  5. /* AS-Portierung                                                             */
  6. /*                                                                           */
  7. /* Tree management                                                           */
  8. /*                                                                           */
  9. /*****************************************************************************/
  10.  
  11. #include "stdinc.h"
  12. #include <string.h>
  13. #include <ctype.h>
  14.  
  15. #include "be_le.h"
  16. #include "nls.h"
  17. #include "asmdef.h"
  18. #include "asmsub.h"
  19. #include "asmpars.h"
  20.  
  21. #include "trees.h"
  22.  
  23. Boolean BalanceTrees;
  24.  
  25. static ShortInt StrCmp(const char *s1, const char *s2, LongInt Hand1, LongInt Hand2)
  26. {
  27.   int tmp;
  28.  
  29.   tmp = (*s1) - (*s2);
  30.   if (!tmp)
  31.     tmp = strcmp(s1, s2);
  32.   if (!tmp)
  33.     tmp = Hand1 - Hand2;
  34.   if (tmp < 0)
  35.     return -1;
  36.   if (tmp > 0)
  37.     return 1;
  38.   return 0;
  39. }
  40.  
  41. void IterTree(PTree Tree, TTreeCallback Callback, void *pData)
  42. {
  43.   ChkStack();
  44.   if (Tree)
  45.   {
  46.     if (Tree->Left) IterTree(Tree->Left, Callback, pData);
  47.     Callback(Tree, pData);
  48.     if (Tree->Right) IterTree(Tree->Right, Callback, pData);
  49.   }
  50. }
  51.  
  52. static void TreeDepthIter(PTree Tree, LongInt Level, LongInt *pMin, LongInt *pMax)
  53. {
  54.   ChkStack();
  55.   if (Tree)
  56.   {
  57.     TreeDepthIter(Tree->Left, Level + 1, pMin, pMax);
  58.     TreeDepthIter(Tree->Right, Level + 1, pMin, pMax);
  59.   }
  60.   else
  61.   {
  62.     if (Level > *pMax) *pMax = Level;
  63.     if (Level < *pMin) *pMin = Level;
  64.   }
  65. }
  66.  
  67. void GetTreeDepth(PTree Tree, LongInt *pMin, LongInt *pMax)
  68. {
  69.   *pMin = MaxLongInt; *pMax = 0;
  70.   TreeDepthIter(Tree, 0, pMin, pMax);
  71. }
  72.  
  73. void DestroyTree(PTree *Tree, TTreeCallback Callback, void *pData)
  74. {
  75.   ChkStack();
  76.   if (*Tree)
  77.   {
  78.     if ((*Tree)->Left) DestroyTree(&((*Tree)->Left), Callback, pData);
  79.     if ((*Tree)->Right) DestroyTree(&((*Tree)->Right), Callback, pData);
  80.     Callback(*Tree, pData);
  81.     if ((*Tree)->Name)
  82.     {
  83.       free((*Tree)->Name); (*Tree)->Name = NULL;
  84.     }
  85.     free(*Tree); *Tree = NULL;
  86.   }
  87. }
  88.  
  89. static void DumpTreeIter(PTree Tree, LongInt Level)
  90. {
  91.   ChkStack();
  92.   if (Tree)
  93.   {
  94.     if (Tree->Left) DumpTreeIter(Tree->Left, Level + 1);
  95.     fprintf(Debug,"%*s%s\n", 6 * Level, "", Tree->Name);
  96.     if (Tree->Right) DumpTreeIter(Tree->Right, Level + 1);
  97.   }
  98. }
  99.  
  100. void DumpTree(PTree Tree)
  101. {
  102.   DumpTreeIter(Tree, 0);
  103. }
  104.  
  105. PTree SearchTree(PTree Tree, const char *Name, LongInt Attribute)
  106. {
  107.   ShortInt SErg = -1;
  108.  
  109.   while ((Tree) && (SErg != 0))
  110.   {
  111.     SErg = StrCmp(Name, Tree->Name, Attribute, Tree->Attribute);
  112.     if (SErg < 0) Tree = Tree->Left;
  113.     else if (SErg > 0) Tree = Tree->Right;
  114.   }
  115.   return Tree;
  116. }
  117.  
  118. Boolean EnterTree(PTree *PDest, PTree Neu, TTreeAdder Adder, void *pData)
  119. {
  120.   PTree Hilf, p1, p2;
  121.   Boolean Grown, Result;
  122.   ShortInt CompErg;
  123.  
  124.   /* check for stack overflow, nothing yet inserted */
  125.  
  126.   ChkStack(); Result = False;
  127.  
  128.   /* arrived at a leaf? --> simply add */
  129.  
  130.   if (*PDest == NULL)
  131.   {
  132.     (*PDest) = Neu;
  133.     (*PDest)->Balance = 0; (*PDest)->Left = NULL; (*PDest)->Right = NULL;
  134.     Adder(NULL, Neu, pData);
  135.     return True;
  136.   }
  137.  
  138.   /* go right, left, or straight? */
  139.  
  140.   CompErg = StrCmp(Neu->Name, (*PDest)->Name, Neu->Attribute, (*PDest)->Attribute);
  141.  
  142.   /* left ? */
  143.  
  144.   if (CompErg > 0)
  145.   {
  146.     Grown = EnterTree(&((*PDest)->Right), Neu, Adder, pData);
  147.     if ((BalanceTrees) && (Grown))
  148.      switch ((*PDest)->Balance)
  149.      {
  150.        case -1:
  151.          (*PDest)->Balance = 0; break;
  152.        case 0:
  153.          (*PDest)->Balance = 1; Result = True; break;
  154.        case 1:
  155.         p1 = (*PDest)->Right;
  156.         if (p1->Balance == 1)
  157.         {
  158.           (*PDest)->Right = p1->Left; p1->Left = *PDest;
  159.           (*PDest)->Balance = 0; *PDest = p1;
  160.         }
  161.         else
  162.         {
  163.           p2 = p1->Left;
  164.           p1->Left = p2->Right; p2->Right = p1;
  165.           (*PDest)->Right = p2->Left; p2->Left = *PDest;
  166.           if (p2->Balance ==  1) (*PDest)->Balance = (-1); else (*PDest)->Balance = 0;
  167.           if (p2->Balance == -1) p1      ->Balance =    1; else p1      ->Balance = 0;
  168.           *PDest = p2;
  169.         }
  170.         (*PDest)->Balance = 0;
  171.         break;
  172.      }
  173.   }
  174.  
  175.   /* right ? */
  176.  
  177.    else if (CompErg < 0)
  178.    {
  179.      Grown = EnterTree(&((*PDest)->Left), Neu, Adder, pData);
  180.      if ((BalanceTrees) && (Grown))
  181.        switch ((*PDest)->Balance)
  182.        {
  183.          case 1:
  184.            (*PDest)->Balance = 0;
  185.            break;
  186.          case 0:
  187.            (*PDest)->Balance = -1;
  188.            Result = True;
  189.            break;
  190.          case -1:
  191.            p1 = (*PDest)->Left;
  192.            if (p1->Balance == (-1))
  193.            {
  194.              (*PDest)->Left = p1->Right;
  195.              p1->Right = *PDest;
  196.              (*PDest)->Balance = 0;
  197.              *PDest = p1;
  198.            }
  199.            else
  200.            {
  201.              p2 = p1->Right;
  202.              p1->Right = p2->Left;
  203.              p2->Left = p1;
  204.              (*PDest)->Left = p2->Right;
  205.              p2->Right = *PDest;
  206.              if (p2->Balance == (-1)) (*PDest)->Balance =    1; else (*PDest)->Balance = 0;
  207.              if (p2->Balance ==    1) p1      ->Balance = (-1); else p1      ->Balance = 0;
  208.              *PDest = p2;
  209.            }
  210.            (*PDest)->Balance = 0;
  211.            break;
  212.        }
  213.    }
  214.  
  215.   /* otherwise we might replace the node */
  216.  
  217.   else
  218.   {
  219.     if (Adder(PDest, Neu, pData))
  220.     {
  221.       Neu->Left = (*PDest)->Left; Neu->Right = (*PDest)->Right;
  222.       Neu->Balance = (*PDest)->Balance;
  223.       Hilf = *PDest; *PDest = Neu;
  224.       if (Hilf->Name)
  225.       {
  226.         free(Hilf->Name); Hilf->Name = NULL;
  227.       }
  228.       free(Hilf);
  229.     }
  230.   }
  231.  
  232.   return Result;
  233. }
  234.