git.sur5r.net Git - cc65/blob - src/cc65/casenode.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                casenode.c                                 */
   4 /*                                                                           */
   5 /*        Node for the tree that is generated for a switch statement         */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2001      Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@cc65.org                                                 */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include <limits.h>
  37
  38 /* common */
  39 #include "coll.h"
  40 #include "xmalloc.h"
  41
  42 /* cc65 */
  43 #include "asmlabel.h"
  44 #include "error.h"
  45 #include "casenode.h"
  46
  47
  48
  49 /*****************************************************************************/
  50 /*                                   Code                                    */
  51 /*****************************************************************************/
  52
  53
  54
  55 CaseNode* NewCaseNode (unsigned char Value)
  56 /* Create and initialize a new CaseNode */
  57 {
  58     /* Allocate memory */
  59     CaseNode* N = xmalloc (sizeof (CaseNode));
  60
  61     /* Initialize the fields */
  62     N->Value = Value;
  63     N->Label = 0;
  64     N->Nodes = 0;
  65
  66     /* Return the new node */
  67     return N;
  68 }
  69
  70
  71
  72 void FreeCaseNode (CaseNode* N)
  73 /* Delete a case node plus all sub nodes */
  74 {
  75     if (N->Nodes) {
  76         FreeCaseNodeColl (N->Nodes);
  77     }
  78     xfree (N);
  79 }
  80
  81
  82
  83 void FreeCaseNodeColl (Collection* Nodes)
  84 /* Free a collection of case nodes */
  85 {
  86     unsigned I;
  87     for (I = 0; I < CollCount (Nodes); ++I) {
  88         FreeCaseNode (CollAtUnchecked (Nodes, I));
  89     }
  90     FreeCollection (Nodes);
  91 }
  92
  93
  94
  95 int SearchCaseNode (const Collection* Nodes, unsigned char Key, int* Index)
  96 /* Search for a node in the given collection. If the node has been found,
  97  * set Index to the index of the node and return true. If the node was not
  98  * found, set Index the the insertion position of the node and return
  99  * false.
 100  */
 101 {
 102     /* Do a binary search */
 103     int First = 0;
 104     int Last = CollCount (Nodes) - 1;
 105     int S = 0;
 106
 107     while (First <= Last) {
 108
 109         /* Set current to mid of range */
 110         int Current = (Last + First) / 2;
 111
 112         /* Get the entry from this position */
 113         const CaseNode* N = CollConstAt (Nodes, Current);
 114
 115         /* Compare the values */
 116         if (N->Value < Key) {
 117             First = Current + 1;
 118         } else {
 119             Last = Current - 1;
 120             if (N->Value == Key) {
 121                 /* Found. We cannot have duplicates, so end the search here. */
 122                 S = 1;
 123                 First = Current;
 124             }
 125         }
 126
 127     }
 128
 129     *Index = First;
 130     return S;
 131 }
 132
 133
 134
 135 unsigned InsertCaseValue (Collection* Nodes, unsigned long Val, unsigned Depth)
 136 /* Insert a new case value into a CaseNode tree with the given depth. Return
 137  * the code label for the value.
 138  */
 139 {
 140     CaseNode* N = 0;
 141     unsigned CaseLabel = GetLocalLabel ();  /* Code label */
 142
 143     while (Depth--) {
 144
 145         int Index;
 146
 147         /* Get the key */
 148         unsigned char Key = (Val >> (Depth * CHAR_BIT)) & 0xFF;
 149
 150         /* Search for the node in the collection */
 151         if (SearchCaseNode (Nodes, Key, &Index) == 0) {
 152
 153             /* Node not found - insert one */
 154             N = NewCaseNode (Key);
 155             CollInsert (Nodes, N, Index);
 156
 157             /* If this is not the last round, create the collection for
 158              * the subnodes, otherwise get a label for the code.
 159              */
 160             if (Depth > 0) {
 161                 N->Nodes = NewCollection ();
 162             } else {
 163                 N->Label = CaseLabel;
 164             }
 165
 166         } else {
 167             /* Node found, get it */
 168             N = CollAt (Nodes, Index);
 169
 170             /* If this is the last round and we found a node, we have a
 171              * duplicate case label in a switch.
 172              */
 173             if (Depth == 0) {
 174                 Error ("Duplicate case label");
 175             }
 176         }
 177
 178         /* Get the collection from the node for the next round. */
 179         Nodes = N->Nodes;
 180     }
 181
 182     /* Return the label of the node we found/created */
 183     return CaseLabel;
 184 }