From 966dbc53d8ad4c6d7e1a1ac959576b382cf9dce0 Mon Sep 17 00:00:00 2001 From: cuz Date: Wed, 22 Oct 2003 19:13:21 +0000 Subject: [PATCH] Use the new generic hash tables git-svn-id: svn://svn.cc65.org/cc65/trunk@2561 b7a2c559-68d2-44c3-8de9-860c34a00d81 --- src/ca65/filetab.c | 40 ++++++------- src/ca65/macro.c | 143 +++++++++++++++++++++++++++++---------------- 2 files changed, 114 insertions(+), 69 deletions(-) diff --git a/src/ca65/filetab.c b/src/ca65/filetab.c index bcc51ad65..05d065f32 100644 --- a/src/ca65/filetab.c +++ b/src/ca65/filetab.c @@ -55,17 +55,17 @@ -static unsigned GenHash (const void* Index); -/* Generate the hash over an index. */ +static unsigned HT_GenHash (const void* Key); +/* Generate the hash over a key. */ -static const void* GetIndex (void* Entry); -/* Given a pointer to the user entry data, return a pointer to the index */ +static const void* HT_GetKey (void* Entry); +/* Given a pointer to the user entry data, return a pointer to the key. */ -static HashNode* GetHashNode (void* Entry); +static HashNode* HT_GetHashNode (void* Entry); /* Given a pointer to the user entry data, return a pointer to the hash node */ -static int Compare (const void* Index1, const void* Index2); -/* Compare two indices for equality */ +static int HT_Compare (const void* Key1, const void* Key2); +/* Compare two keys for equality */ @@ -84,7 +84,7 @@ typedef struct FileEntry FileEntry; struct FileEntry { HashNode Node; unsigned Name; /* File name */ - unsigned Index; /* Index of entry */ + unsigned Index; /* Index of entry */ unsigned long Size; /* Size of file */ unsigned long MTime; /* Time of last modification */ }; @@ -94,10 +94,10 @@ static Collection FileTab = STATIC_COLLECTION_INITIALIZER; /* Hash table functions */ static const HashFunctions HashFunc = { - GenHash, - GetIndex, - GetHashNode, - Compare + HT_GenHash, + HT_GetKey, + HT_GetHashNode, + HT_Compare }; /* Hash table, hashed by name */ @@ -111,15 +111,15 @@ static HashTable HashTab = STATIC_HASHTABLE_INITIALIZER (HASHTAB_COUNT, &HashFun -static unsigned GenHash (const void* Index) -/* Generate the hash over an index. */ +static unsigned HT_GenHash (const void* Key) +/* Generate the hash over a key. */ { - return (*(const unsigned*)Index & HASHTAB_MASK); + return (*(const unsigned*)Key & HASHTAB_MASK); } -static const void* GetIndex (void* Entry) +static const void* HT_GetKey (void* Entry) /* Given a pointer to the user entry data, return a pointer to the index */ { return &((FileEntry*) Entry)->Name; @@ -127,7 +127,7 @@ static const void* GetIndex (void* Entry) -static HashNode* GetHashNode (void* Entry) +static HashNode* HT_GetHashNode (void* Entry) /* Given a pointer to the user entry data, return a pointer to the hash node */ { return &((FileEntry*) Entry)->Node; @@ -135,10 +135,10 @@ static HashNode* GetHashNode (void* Entry) -static int Compare (const void* Index1, const void* Index2) -/* Compare two indices for equality */ +static int HT_Compare (const void* Key1, const void* Key2) +/* Compare two keys for equality */ { - return (*(const unsigned*)Index1 == *(const unsigned*)Index2); + return (*(const unsigned*)Key1 == *(const unsigned*)Key2); } diff --git a/src/ca65/macro.c b/src/ca65/macro.c index 9a249cdec..649427770 100644 --- a/src/ca65/macro.c +++ b/src/ca65/macro.c @@ -7,9 +7,9 @@ /* */ /* */ /* (C) 1998-2003 Ullrich von Bassewitz */ -/* Wacholderweg 14 */ -/* D-70597 Stuttgart */ -/* EMail: uz@musoftware.de */ +/* Römerstrasse 52 */ +/* D-70794 Filderstadt */ +/* EMail: uz@cc65.org */ /* */ /* */ /* This software is provided 'as-is', without any expressed or implied */ @@ -39,6 +39,7 @@ /* common */ #include "check.h" #include "hashstr.h" +#include "hashtab.h" #include "xmalloc.h" /* ca65 */ @@ -53,6 +54,26 @@ +/*****************************************************************************/ +/* Forwards */ +/*****************************************************************************/ + + + +static unsigned HT_GenHash (const void* Key); +/* Generate the hash over a key. */ + +static const void* HT_GetKey (void* Entry); +/* Given a pointer to the user entry data, return a pointer to the key */ + +static HashNode* HT_GetHashNode (void* Entry); +/* Given a pointer to the user entry data, return a pointer to the hash node */ + +static int HT_Compare (const void* Key1, const void* Key2); +/* Compare two keys for equality */ + + + /*****************************************************************************/ /* Data */ /*****************************************************************************/ @@ -60,18 +81,18 @@ /* Struct that describes an identifer (macro param, local list) */ -typedef struct IdDesc_ IdDesc; -struct IdDesc_ { - IdDesc* Next; /* Linked list */ +typedef struct IdDesc IdDesc; +struct IdDesc { + IdDesc* Next; /* Linked list */ char Id [1]; /* Identifier, dynamically allocated */ }; /* Struct that describes a macro definition */ -typedef struct Macro_ Macro; -struct Macro_ { - Macro* Next; /* Next macro with same hash */ +typedef struct Macro Macro; +struct Macro { + HashNode Node; /* Hash list node */ Macro* List; /* List of all macros */ unsigned LocalCount; /* Count of local symbols */ IdDesc* Locals; /* List of local symbols */ @@ -84,25 +105,32 @@ struct Macro_ { char Name [1]; /* Macro name, dynamically allocated */ }; +/* Hash table functions */ +static const HashFunctions HashFunc = { + HT_GenHash, + HT_GetKey, + HT_GetHashNode, + HT_Compare +}; + /* Macro hash table */ -#define HASHTAB_SIZE 117 -static Macro* MacroTab [HASHTAB_SIZE]; +static HashTable MacroTab = STATIC_HASHTABLE_INITIALIZER (117, &HashFunc); /* Global macro data */ static Macro* MacroRoot = 0; /* List of all macros */ /* Structs that holds data for a macro expansion */ -typedef struct MacExp_ MacExp; -struct MacExp_ { - MacExp* Next; /* Pointer to next expansion */ - Macro* M; /* Which macro do we expand? */ - unsigned IfSP; /* .IF stack pointer at start of expansion */ +typedef struct MacExp MacExp; +struct MacExp { + MacExp* Next; /* Pointer to next expansion */ + Macro* M; /* Which macro do we expand? */ + unsigned IfSP; /* .IF stack pointer at start of expansion */ TokNode* Exp; /* Pointer to current token */ - TokNode* Final; /* Pointer to final token */ + TokNode* Final; /* Pointer to final token */ unsigned LocalStart; /* Start of counter for local symbol names */ - unsigned ParamCount; /* Number of actual parameters */ + unsigned ParamCount; /* Number of actual parameters */ TokNode** Params; /* List of actual parameters */ - TokNode* ParamExp; /* Node for expanding parameters */ + TokNode* ParamExp; /* Node for expanding parameters */ }; /* Number of active macro expansions */ @@ -116,6 +144,44 @@ static unsigned LocalName = 0; +/*****************************************************************************/ +/* Hash table functions */ +/*****************************************************************************/ + + + +static unsigned HT_GenHash (const void* Key) +/* Generate the hash over a key. */ +{ + return HashStr (Key); +} + + + +static const void* HT_GetKey (void* Entry) +/* Given a pointer to the user entry data, return a pointer to the index */ +{ + return ((Macro*) Entry)->Name; +} + + + +static HashNode* HT_GetHashNode (void* Entry) +/* Given a pointer to the user entry data, return a pointer to the hash node */ +{ + return &((Macro*) Entry)->Node; +} + + + +static int HT_Compare (const void* Key1, const void* Key2) +/* Compare two keys for equality */ +{ + return (strcmp (Key1, Key2) == 0); +} + + + /*****************************************************************************/ /* Code */ /*****************************************************************************/ @@ -140,7 +206,7 @@ static IdDesc* NewIdDesc (const char* Id) -static Macro* NewMacro (const char* Name, unsigned HashVal, unsigned char Style) +static Macro* NewMacro (const char* Name, unsigned char Style) /* Generate a new macro entry, initialize and return it */ { /* Allocate memory */ @@ -148,6 +214,7 @@ static Macro* NewMacro (const char* Name, unsigned HashVal, unsigned char Style) Macro* M = xmalloc (sizeof (Macro) + Len); /* Initialize the macro struct */ + InitHashNode (&M->Node, M); M->LocalCount = 0; M->Locals = 0; M->ParamCount = 0; @@ -156,16 +223,14 @@ static Macro* NewMacro (const char* Name, unsigned HashVal, unsigned char Style) M->TokRoot = 0; M->TokLast = 0; M->Style = Style; - memcpy (M->Name, Name, Len); - M->Name [Len] = '\0'; + memcpy (M->Name, Name, Len+1); /* Insert the macro into the global macro list */ M->List = MacroRoot; MacroRoot = M; /* Insert the macro into the hash table */ - M->Next = MacroTab [HashVal]; - MacroTab [HashVal] = M; + HT_Insert (&MacroTab, &M->Node); /* Return the new macro struct */ return M; @@ -250,28 +315,11 @@ static void MacSkipDef (unsigned Style) -static Macro* MacFind (const char* Name, unsigned HashVal) -/* Search for a macro in the hash table */ -{ - /* Search for the identifier */ - Macro* M = MacroTab [HashVal]; - while (M) { - if (strcmp (Name, M->Name) == 0) { - return M; - } - M = M->Next; - } - return 0; -} - - - void MacDef (unsigned Style) /* Parse a macro definition */ { Macro* M; TokNode* T; - unsigned HashVal; int HaveParams; /* We expect a macro name here */ @@ -281,11 +329,8 @@ void MacDef (unsigned Style) return; } - /* Generate the hash value */ - HashVal = HashStr (SVal) % HASHTAB_SIZE; - /* Did we already define that macro? */ - if (MacFind (SVal, HashVal) != 0) { + if (HT_Find (&MacroTab, SVal) != 0) { /* Macro is already defined */ Error (ERR_SYM_ALREADY_DEFINED, SVal); /* Skip tokens until we reach the final .endmacro */ @@ -294,7 +339,7 @@ void MacDef (unsigned Style) } /* Define the macro */ - M = NewMacro (SVal, HashVal, Style); + M = NewMacro (SVal, Style); /* Switch to raw token mode and skip the macro name */ EnterRawTokenMode (); @@ -738,7 +783,7 @@ void MacExpandStart (void) /* Start expanding the macro in SVal */ { /* Search for the macro */ - Macro* M = MacFind (SVal, HashStr (SVal) % HASHTAB_SIZE); + Macro* M = HT_FindEntry (&MacroTab, SVal); CHECK (M != 0); /* Call the apropriate subroutine */ @@ -766,7 +811,7 @@ void MacAbort (void) int IsMacro (const char* Name) /* Return true if the given name is the name of a macro */ { - return MacFind (Name, HashStr (Name) % HASHTAB_SIZE) != 0; + return (HT_Find (&MacroTab, Name) != 0); } @@ -774,7 +819,7 @@ int IsMacro (const char* Name) int IsDefine (const char* Name) /* Return true if the given name is the name of a define style macro */ { - Macro* M = MacFind (Name, HashStr (Name) % HASHTAB_SIZE); + Macro* M = HT_FindEntry (&MacroTab, Name); return (M != 0 && M->Style == MAC_STYLE_DEFINE); } -- 2.39.5