Subversion Repositories pentevo

Rev

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

  1. /* asmitree.c */
  2. /*****************************************************************************/
  3. /* SPDX-License-Identifier: GPL-2.0-only OR GPL-3.0-only                     */
  4. /*                                                                           */
  5. /* AS-Portierung                                                             */
  6. /*                                                                           */
  7. /* Opcode-Abfrage als Binaerbaum                                             */
  8. /*                                                                           */
  9. /* Historie: 30.10.1996 Grundsteinlegung                                     */
  10. /*            8.10.1997 Hash-Tabelle                                         */
  11. /*            6.12.1998 dynamisches Kopieren der Namen                       */
  12. /*                                                                           */
  13. /*****************************************************************************/
  14.  
  15. #include "stdinc.h"
  16. #include <string.h>
  17.  
  18. #include "chunks.h"
  19. #include "strutil.h"
  20. #include "asmdef.h"
  21. #include "asmsub.h"
  22.  
  23. #include "asmitree.h"
  24.  
  25. /*---------------------------------------------------------------------------*/
  26.  
  27. static Boolean AddSingle(PInstTreeNode *Node, char *NName, InstProc NProc, Word NIndex)
  28. {
  29.   PInstTreeNode p1, p2;
  30.   Boolean Result = False;
  31.  
  32.   ChkStack();
  33.  
  34.   if (!*Node)
  35.   {
  36.     *Node = (PInstTreeNode) malloc(sizeof(TInstTreeNode));
  37.     (*Node)->Left = NULL;
  38.     (*Node)->Right = NULL;
  39.     (*Node)->Proc = NProc;
  40.     (*Node)->Index = NIndex;
  41.     (*Node)->Balance = 0;
  42.     (*Node)->Name = as_strdup(NName);
  43.     Result = True;
  44.   }
  45.   else if (strcmp(NName, (*Node)->Name) < 0)
  46.   {
  47.     if (AddSingle(&((*Node)->Left), NName, NProc, NIndex))
  48.       switch ((*Node)->Balance)
  49.       {
  50.         case 1:
  51.           (*Node)->Balance = 0;
  52.           break;
  53.         case 0:
  54.           (*Node)->Balance = -1;
  55.           Result = True;
  56.           break;
  57.         case -1:
  58.           p1 = (*Node)->Left;
  59.           if (p1->Balance == -1)
  60.           {
  61.             (*Node)->Left = p1->Right;
  62.             p1->Right = (*Node);
  63.             (*Node)->Balance = 0;
  64.             *Node = p1;
  65.           }
  66.          else
  67.          {
  68.            p2 = p1->Right;
  69.            p1->Right = p2->Left;
  70.            p2->Left = p1;
  71.            (*Node)->Left = p2->Right;
  72.            p2->Right = (*Node);
  73.            (*Node)->Balance = (p2->Balance == -1) ? 1 : 0;
  74.            p1->Balance = (p2->Balance == 1) ? -1 : 0;
  75.            *Node = p2;
  76.          }
  77.          (*Node)->Balance = 0;
  78.          break;
  79.      }
  80.   }
  81.   else
  82.   {
  83.     if (AddSingle(&((*Node)->Right), NName, NProc, NIndex))
  84.       switch ((*Node)->Balance)
  85.       {
  86.         case -1:
  87.           (*Node)->Balance = 0;
  88.           break;
  89.         case 0:
  90.           (*Node)->Balance = 1;
  91.           Result = True;
  92.           break;
  93.         case 1:
  94.           p1 = (*Node)->Right;
  95.           if (p1->Balance == 1)
  96.           {
  97.             (*Node)->Right = p1->Left;
  98.             p1->Left = (*Node);
  99.             (*Node)->Balance = 0;
  100.             *Node = p1;
  101.           }
  102.           else
  103.           {
  104.             p2 = p1->Left;
  105.             p1->Left = p2->Right;
  106.             p2->Right = p1;
  107.             (*Node)->Right = p2->Left;
  108.             p2->Left = (*Node);
  109.             (*Node)->Balance = (p2->Balance == 1) ? -1 : 0;
  110.             p1->Balance = (p2->Balance == -1) ? 1 : 0;
  111.             *Node = p2;
  112.           }
  113.           (*Node)->Balance = 0;
  114.           break;
  115.       }
  116.   }
  117.   return Result;
  118. }
  119.  
  120. void AddInstTree(PInstTreeNode *Root, char *NName, InstProc NProc, Word NIndex)
  121. {
  122.   AddSingle(Root, NName, NProc, NIndex);
  123. }
  124.  
  125. static void ClearSingle(PInstTreeNode *Node)
  126. {
  127.   ChkStack();
  128.  
  129.   if (*Node)
  130.   {
  131.     free((*Node)->Name);
  132.     ClearSingle(&((*Node)->Left));
  133.     ClearSingle(&((*Node)->Right));
  134.     free(*Node);
  135.     *Node = NULL;
  136.   }
  137. }
  138.  
  139. void ClearInstTree(PInstTreeNode *Root)
  140. {
  141.   ClearSingle(Root);
  142. }
  143.  
  144. Boolean SearchInstTree(PInstTreeNode Root, char *OpPart)
  145. {
  146.   while (Root)
  147.   {
  148.     int cmp_res = strcmp(OpPart, Root->Name);
  149.     if (!cmp_res)
  150.       break;
  151.     Root = (cmp_res < 0) ? Root->Left : Root->Right;
  152.   }
  153.  
  154.   if (!Root)
  155.     return False;
  156.   else
  157.   {
  158.     Root->Proc(Root->Index);
  159.     return True;
  160.   }
  161. }
  162.  
  163. static void PNode(PInstTreeNode Node, Word Lev)
  164. {
  165.   ChkStack();
  166.   if (Node)
  167.   {
  168.     PNode(Node->Left, Lev + 1);
  169.     printf("%*s %s %p %p %d\n", 5 * Lev, "", Node->Name, (void*)Node->Left, (void*)Node->Right, Node->Balance);
  170.     PNode(Node->Right, Lev + 1);
  171.   }
  172. }
  173.  
  174. void PrintInstTree(PInstTreeNode Root)
  175. {
  176.   PNode(Root, 0);
  177. }
  178.  
  179. /*----------------------------------------------------------------------------*/
  180.  
  181. static int GetKey(const char *Name, LongWord TableSize)
  182. {
  183.   register unsigned char *p;
  184.   LongWord tmp = 0;
  185.  
  186.   for (p = (unsigned char *)Name; *p != '\0'; p++)
  187.     tmp = (tmp << 2) + ((LongWord)*p);
  188.   return tmp % TableSize;
  189. }
  190.  
  191. PInstTable CreateInstTable(int TableSize)
  192. {
  193.   int z;
  194.   PInstTableEntry tmp;
  195.   PInstTable tab;
  196.  
  197.   tmp = (PInstTableEntry) malloc(sizeof(TInstTableEntry) * TableSize);
  198.   for (z = 0; z < TableSize; z++)
  199.     tmp[z].Name = NULL;
  200.   tab = (PInstTable) malloc(sizeof(TInstTable));
  201.   tab->Fill = 0;
  202.   tab->Size = TableSize;
  203.   tab->Entries = tmp;
  204.   tab->Dynamic = FALSE;
  205.   return tab;
  206. }
  207.  
  208. /*!------------------------------------------------------------------------
  209.  * \fn     inst_fnc_table_create(int table_size)
  210.  * \brief  create new instance of function table
  211.  * \param  table_size max. # of entries in table
  212.  * \return * to table
  213.  * ------------------------------------------------------------------------ */
  214.  
  215. inst_fnc_table_t *inst_fnc_table_create(int table_size)
  216. {
  217.   int z;
  218.   inst_fnc_table_entry_t *p_entries = NULL;
  219.   inst_fnc_table_t *p_ret = NULL;
  220.  
  221.   p_entries = (inst_fnc_table_entry_t*)calloc(table_size, sizeof(*p_entries));
  222.   if (!p_entries)
  223.     goto func_exit;
  224.   for (z = 0; z < table_size; z++)
  225.     p_entries[z].p_name = NULL;
  226.  
  227.   p_ret = (inst_fnc_table_t*) calloc(1, sizeof(*p_ret));
  228.   if (!p_ret)
  229.     goto func_exit;
  230.   p_ret->fill = 0;
  231.   p_ret->size = table_size;
  232.   p_ret->p_entries = p_entries; p_entries = NULL;
  233.   p_ret->dynamic = False;
  234.  
  235. func_exit:
  236.   if (p_entries)
  237.     free(p_entries);
  238.   return p_ret;
  239. }
  240.  
  241. void SetDynamicInstTable(PInstTable Table)
  242. {
  243.   Table->Dynamic = TRUE;
  244. }
  245.  
  246. void DestroyInstTable(PInstTable tab)
  247. {
  248.   int z;
  249.  
  250.   if (tab->Dynamic)
  251.     for (z = 0; z < tab->Size; z++)
  252.       free(tab->Entries[z].Name);
  253.  
  254.   free(tab->Entries);
  255.   free(tab);
  256. }
  257.  
  258. void AddInstTable(PInstTable tab, const char *Name, Word Index, InstProc Proc)
  259. {
  260.   LongWord h0 = GetKey(Name, tab->Size), z = 0;
  261.  
  262.   /* mindestens ein freies Element lassen, damit der Sucher garantiert terminiert */
  263.  
  264.   if (tab->Size - 1 <= tab->Fill)
  265.   {
  266.     fprintf(stderr, "\nhash table overflow\n");
  267.     exit(255);
  268.   }
  269.   while (1)
  270.   {
  271.     if (!tab->Entries[h0].Name)
  272.     {
  273.       tab->Entries[h0].Name = (tab->Dynamic) ? as_strdup(Name) : (char*)Name;
  274.       tab->Entries[h0].Proc = Proc;
  275.       tab->Entries[h0].Index = Index;
  276.       tab->Entries[h0].Coll = z;
  277.       tab->Fill++;
  278.       return;
  279.     }
  280.     if (!strcmp(tab->Entries[h0].Name, Name))
  281.     {
  282.       printf("%s double in table\n", Name);
  283.       exit(255);
  284.     }
  285.     z++;
  286.     if ((LongInt)(++h0) == tab->Size)
  287.       h0 = 0;
  288.   }
  289. }
  290.  
  291. /*!------------------------------------------------------------------------
  292.  * \fn     inst_fnc_table_add(inst_fnc_table_t *p_table, const char *p_name, Word index, inst_fnc_t fnc)
  293.  * \brief  augment table by one entry
  294.  * \param  p_table table to add to
  295.  * \param  p_name name of instruction
  296.  * \param  index callback argument
  297.  * \param  fnc callback itself
  298.  * ------------------------------------------------------------------------ */
  299.  
  300. void inst_fnc_table_add(inst_fnc_table_t *p_table, const char *p_name, Word index, inst_fnc_t fnc)
  301. {
  302.   LongWord tab_index = GetKey(p_name, p_table->size), num_coll = 0;
  303.  
  304.   /* mindestens ein freies Element lassen, damit der Sucher garantiert terminiert */
  305.  
  306.   if (p_table->size - 1 <= p_table->fill)
  307.   {
  308.     fprintf(stderr, "\nhash table overflow\n");
  309.     exit(255);
  310.   }
  311.   while (1)
  312.   {
  313.     if (!p_table->p_entries[tab_index].p_name)
  314.     {
  315.       p_table->p_entries[tab_index].p_name = (p_table->dynamic) ? as_strdup(p_name) : (char*)p_name;
  316.       p_table->p_entries[tab_index].fnc = fnc;
  317.       p_table->p_entries[tab_index].index = index;
  318.       p_table->p_entries[tab_index].coll = num_coll;
  319.       p_table->fill++;
  320.       return;
  321.     }
  322.     if (!strcmp(p_table->p_entries[tab_index].p_name, p_name))
  323.     {
  324.       printf("%s double in table\n", p_name);
  325.       exit(255);
  326.     }
  327.     num_coll++;
  328.     if ((LongInt)(++tab_index) == p_table->size)
  329.       tab_index = 0;
  330.   }
  331. }
  332.  
  333. void RemoveInstTable(PInstTable tab, const char *Name)
  334. {
  335.   LongWord h0 = GetKey(Name, tab->Size);
  336.  
  337.   while (1)
  338.   {
  339.     if (!tab->Entries[h0].Name)
  340.       return;
  341.     else if (!strcmp(tab->Entries[h0].Name, Name))
  342.     {
  343.       tab->Entries[h0].Name = NULL;
  344.       tab->Entries[h0].Proc = NULL;
  345.       tab->Fill--;
  346.       return;
  347.     }
  348.     if ((LongInt)(++h0) == tab->Size)
  349.       h0 = 0;
  350.   }
  351. }
  352.  
  353. Boolean LookupInstTable(PInstTable tab, const char *Name)
  354. {
  355.   LongWord h0 = GetKey(Name, tab->Size);
  356.  
  357.   while (1)
  358.   {
  359.     if (!tab->Entries[h0].Name)
  360.       return False;
  361.     else if (!strcmp(tab->Entries[h0].Name, Name))
  362.     {
  363.       tab->Entries[h0].Proc(tab->Entries[h0].Index);
  364.       return True;
  365.     }
  366.     if ((LongInt)(++h0) == tab->Size)
  367.       h0 = 0;
  368.   }
  369. }
  370.  
  371. /*!------------------------------------------------------------------------
  372.  * \fn     inst_fnc_table_lookup(const inst_fnc_table_t *p_table, const char *p_name)
  373.  * \brief  look up & execute instruction callback
  374.  * \param  p_table table with functions
  375.  * \param  p_name instruction name
  376.  * \return True if callback was found and executed
  377.  * ------------------------------------------------------------------------ */
  378.  
  379. Boolean inst_fnc_table_lookup(const inst_fnc_table_t *p_table, const char *p_name)
  380. {
  381.   LongWord index = GetKey(p_name, p_table->size);
  382.  
  383.   while (1)
  384.   {
  385.     if (!p_table->p_entries[index].p_name)
  386.       return False;
  387.     else if (!strcmp(p_table->p_entries[index].p_name, p_name))
  388.       return p_table->p_entries[index].fnc(p_table->p_entries[index].index);
  389.     if ((LongInt)(++index) == p_table->size)
  390.       index = 0;
  391.   }
  392. }
  393.  
  394. void PrintInstTable(FILE *stream, PInstTable tab)
  395. {
  396.   int z;
  397.  
  398.   for (z = 0; z < tab->Size; z++)
  399.     if (tab->Entries[z].Name)
  400.       fprintf(stream, "[%3d]: %-10s Index %4d Coll %2d\n", z,
  401.              tab->Entries[z].Name, tab->Entries[z].Index, tab->Entries[z].Coll);
  402. }
  403.  
  404. /*----------------------------------------------------------------------------*/
  405.  
  406. void asmitree_init(void)
  407. {
  408. }
  409.