Changeset 1665


Ignore:
Timestamp:
Nov 7, 2011, 3:22:00 PM (6 years ago)
Author:
vla24
Message:

SymbolTable?: Update symtab library for dictionary div2 delimiter. Fixed some compile errors for log grouping

Location:
trunk/symtab
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/symtab/bitstream_hash_table.cpp

    r1518 r1665  
    88
    99BitStreamHashTable::BitStreamHashTable()
    10     :g_tableSize(DEFAULT_TABLE_SIZE)
     10    :m_tableSize(DEFAULT_TABLE_SIZE)
    1111{
    12     g_table = allocateHashTable(g_tableSize);
     12    m_table = allocateHashTable(m_tableSize);
    1313}
    1414
    1515BitStreamHashTable::~BitStreamHashTable()
    1616{
    17     deallocateHashTable(g_tableSize, g_table);
     17    deallocateHashTable(m_tableSize, m_table);
    1818}
    1919
     
    2121unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
    2222{
    23     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     23    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    2424
    2525    // Look up the value in the chain
    26     for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    27 #if DEBUG_BHT
     26    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
     27#if DEBUm_BHT
    2828        printf ("Check symbol: %s\n", chain->key);
    2929#endif
    3030        if( simd_compare ((unsigned char*)chain->key, (unsigned char*)name, L) )
    3131        {
    32 #if DEBUG_BHT
     32#if DEBUm_BHT
    3333            printf ("Found GID: %i\n", chain->GID);
    3434#endif
     
    3737    }
    3838
    39 #if DEBUG_BHT
     39#if DEBUm_BHT
    4040    printf ("Not Found GID: %i\n", 0);
    4141#endif
     
    4545void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid)
    4646{
    47     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     47    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    4848
    4949    // If it was not found, add it
    50     CHAIN* next = g_table[bucket];
     50    CHAIN* next = m_table[bucket];
    5151    unsigned int chainlgth = chainLength(next);
    5252    if (chainlgth == MAX_CHAIN)
     
    5454        //current chain length is maximum, expand the table
    5555        expandHashTable();
    56         bucket = getBucket(hashvalue, g_tableSize);
    57         next = g_table[bucket];
     56        bucket = getBucket(hashvalue, m_tableSize);
     57        next = m_table[bucket];
    5858    }
    5959    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
     
    6262    curr->hashvalue = hashvalue;
    6363    curr->GID = gid;
    64     g_table[bucket] = curr;
     64    m_table[bucket] = curr;
    6565
    66 #if DEBUG_BHT
    67     printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
     66#if DEBUm_BHT
     67    printf ("Given GID: %i | Stored GID: %i\n", gid, m_table[hash]->GID);
    6868#endif
    6969}
     
    7171void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
    7272{
    73     unsigned int bucket = getBucket(hashvalue, g_tableSize);
     73    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    7474
    7575    // If it was not found, add it
    76     CHAIN* next = g_table[bucket];
     76    CHAIN* next = m_table[bucket];
    7777    unsigned int chainlgth = chainLength(next);
    7878    if (chainlgth == MAX_CHAIN)
     
    8080        //current chain length is maximum, expand the table
    8181        expandHashTable();
    82         bucket = getBucket(hashvalue, g_tableSize);
    83         next = g_table[bucket];
     82        bucket = getBucket(hashvalue, m_tableSize);
     83        next = m_table[bucket];
    8484    }
    8585    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
     
    8989    curr->GID = gid;
    9090    curr->lgth = lgth;
    91     g_table[bucket] = curr;
     91    m_table[bucket] = curr;
    9292
    93 #if DEBUG_BHT
    94     printf ("Given GID: %i | Stored GID: %i\n", gid, g_table[hash]->GID);
     93#if DEBUm_BHT
     94    printf ("Given GID: %i | Stored GID: %i\n", gid, m_table[hash]->GID);
    9595#endif
    9696}
     
    101101    CHAIN** tempTable = allocateHashTable(tempTableSize);
    102102
    103     for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
     103    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
    104104    {
    105         CHAIN* curr = g_table[bucket];
    106         g_table[bucket] = NULL;
     105        CHAIN* curr = m_table[bucket];
     106        m_table[bucket] = NULL;
    107107
    108108        while (curr != NULL)
     
    121121    }
    122122
    123     // Deallocate g_table
    124     deallocateHashTable(g_tableSize, g_table);
     123    // Deallocate m_table
     124    deallocateHashTable(m_tableSize, m_table);
    125125
    126     // Reassign g_table
    127     g_table = tempTable;
    128     g_tableSize = tempTableSize;
     126    // Reassign m_table
     127    m_table = tempTable;
     128    m_tableSize = tempTableSize;
    129129}
    130130
    131131void BitStreamHashTable::Print_Symbol_Table_Distribution()
    132132{
    133     for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
     133    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
    134134    {
    135         int items = chainLength(g_table[bucket]);
     135        int items = chainLength(m_table[bucket]);
    136136        if (items >= 1)
    137137        {
  • trunk/symtab/bitstream_hash_table.h

    r1518 r1665  
    1818#define BITSTREAM_HASH_TABLE_H
    1919
    20 #define DEBUG_BHT 0
     20#define DEBUm_BHT 0
    2121
    2222#define DEFAULT_TABLE_SIZE 256
     
    5151
    5252protected:
    53     CHAIN ** g_table;
    54     unsigned int g_tableSize;
    55     inline unsigned int getBucket(const int hashvalue, unsigned int g_tableSize);
     53    CHAIN ** m_table;
     54    unsigned int m_tableSize;
     55    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize);
    5656
    5757private:
     
    7474{
    7575    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
    76     memset(table, 0, g_tableSize*sizeof(CHAIN*));
     76    memset(table, 0, m_tableSize*sizeof(CHAIN*));
    7777    return table;
    7878}
     
    8989inline unsigned int BitStreamHashTable::nextTableSize()
    9090{
    91     return g_tableSize << 1; // double the size
     91    return m_tableSize << 1; // double the size
    9292}
    9393
  • trunk/symtab/bitstream_log_hash_table.h

    r1653 r1665  
    4545{
    4646    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    47     unsigned int chainlgth = m_table->size(bucket);
    4847
    49     // Look up the value in the chain
    50     for(unsigned int i = 0; i < chainlgth; i++) {
    51         CHAIN chain = m_table->get(bucket, i);
     48    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    5249#if DEBUG_BHT
    5350        printf ("Check symbol: %s\n", chain.key);
    5451#endif
    55         if( log_equal_compare_1 ((unsigned char*)chain.key, (unsigned char*)name) )
     52        if( log_equal_compare_1 ((unsigned char*)chain->key, (unsigned char*)name) )
    5653        {
    5754#if DEBUG_BHT
    58             printf ("Found GID: %i\n", chain.GID);
     55            printf ("Found GID: %i\n", chain->GID);
    5956#endif
    60             return chain.GID;
     57            return chain->GID;
    6158        }
    6259    }
     
    7168{
    7269    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    73     unsigned int chainlgth = m_table->size(bucket);
    7470
    75     // Look up the value in the chain
    76     for(unsigned int i = 0; i < chainlgth; i++) {
    77         CHAIN chain = m_table->get(bucket, i);
     71    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    7872#if DEBUG_BHT
    7973        printf ("Check symbol: %s\n", chain.key);
    8074#endif
    81         if( log_equal_compare_2 ((unsigned char*)chain.key, (unsigned char*)name) )
     75        if( log_equal_compare_2 ((unsigned char*)chain->key, (unsigned char*)name) )
    8276        {
    8377#if DEBUG_BHT
    84             printf ("Found GID: %i\n", chain.GID);
     78            printf ("Found GID: %i\n", chain->GID);
    8579#endif
    86             return chain.GID;
     80            return chain->GID;
    8781        }
    8882    }
     
    9892{
    9993    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    100     unsigned int chainlgth = m_table->size(bucket);
    10194
    102     // Look up the value in the chain
    103     for(unsigned int i = 0; i < chainlgth; i++) {
    104         CHAIN chain = m_table->get(bucket, i);
     95    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    10596#if DEBUG_BHT
    10697        printf ("Check symbol: %s\n", chain.key);
     
    10899
    109100#ifdef USE_MASK_COMPARE
    110         if( log_equal_compare_4 ((unsigned char*)chain.key, (unsigned char*)name, L) )
     101        if( log_equal_compare_4 ((unsigned char*)chain->key, (unsigned char*)name, L) )
    111102        {
    112103#else
    113         if( overlap_compare<uint16_t>((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
     104        if( overlap_compare<uint16_t>((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    114105        {
    115106#endif
    116107#if DEBUG_BHT
    117             printf ("Found GID: %i\n", chain.GID);
     108            printf ("Found GID: %i\n", chain->GID);
    118109#endif
    119             return chain.GID;
     110            return chain->GID;
    120111        }
    121112    }
     
    131122{
    132123    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    133     unsigned int chainlgth = m_table->size(bucket);
    134124
    135     // Look up the value in the chain
    136     for(unsigned int i = 0; i < chainlgth; i++) {
    137         CHAIN chain = m_table->get(bucket, i);
     125    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    138126#if DEBUG_BHT
    139         printf ("Check symbol: %s\n", chain.key);
     127        printf ("Check symbol: %s\n", chain->key);
    140128#endif
    141         if( overlap_compare<uint32_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
     129        if( overlap_compare<uint32_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    142130        {
    143131#if DEBUG_BHT
    144132            printf ("Found GID: %i\n", chain.GID);
    145133#endif
    146             return chain.GID;
     134            return chain->GID;
    147135        }
    148136    }
     
    158146{
    159147    unsigned int bucket = getBucket(hashvalue, m_tableSize);
    160     unsigned int chainlgth = m_table->size(bucket);
    161148
    162     // Look up the value in the chain
    163     for(unsigned int i = 0; i < chainlgth; i++) {
    164         CHAIN chain = m_table->get(bucket, i);
     149    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
    165150#if DEBUG_BHT
    166151        printf ("Check symbol: %s\n", chain.key);
    167152#endif
    168         if( overlap_compare<uint64_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) )
     153        if( overlap_compare<uint64_t> ((unsigned char*)chain->key, (unsigned char*)name, chain->lgth, L) )
    169154        {
    170155#if DEBUG_BHT
    171             printf ("Found GID: %i\n", chain.GID);
     156            printf ("Found GID: %i\n", chain->GID);
    172157#endif
    173             return chain.GID;
     158            return chain->GID;
    174159        }
    175160    }
  • trunk/symtab/pbgs_div_symbol_table.h

    r1653 r1665  
    1010#ifndef PBGS_DIV_SYMBOL_TABLE_H
    1111#define PBGS_DIV_SYMBOL_TABLE_H
    12 
     12//#define XML_PARSER    // Defines this macro if this symbol table is going to be used as
     13                        // a part of an XML parser.
    1314#define DEBUG_PBGS_DIV 0
    14 
    15 // Define either one of grouping functions
    16 //#define USE_LENGTH_SORT       // f(L) = L
    17 //#define USE_LOG_SORT          // f(L) = ceil (log(L))
    18 #define USE_DIV_SORT            // f(L) = floor ((L+1)/2)
    1915
    2016#define TOTAL_GROUPS 10
     
    2723#include "ls_symbol_table_compare.h"
    2824#include "ls_symbol_table_util.h"
     25#include "pbgs_utilities.h"
    2926
    3027#if DEBUG_PBGS_DIV
     
    3229using namespace std;
    3330#endif
    34                            //0     1     2    3     4    5    6    7
    35 static char delimiters[] = {' ', '\0', '\0', ';', '\0', '=', '>', '/'};
    3631
    3732class PBGSDivSymbolTable
     
    5550
    5651    inline int getGroup(int L);
    57     inline bool isDelimiter(const char c);
    5852
    5953    template <int L> inline char* Store_Name(const char* name);
     
    124118
    125119        //Check if the last character is a delimiter
    126         if (isDelimiter(name[L-1]))
     120#ifdef XMLWF
     121        if (isXMLDelimiter(name[L-1]))
     122#else
     123        if (isGeneralDelimiter(name[L-1]))
     124#endif
    127125        {
    128126            //Do another lookup for name with L = L-1
     
    187185}
    188186
    189 
    190 inline bool PBGSDivSymbolTable::isDelimiter(const char c)
    191 {
    192     return c == delimiters[(unsigned int) c & 0x7];
    193 }
    194 
    195187inline int PBGSDivSymbolTable::getGroup(int L)
    196188{
  • trunk/symtab/pbgs_utilities.h

    r1653 r1665  
    198198}
    199199
     200//                           0     1     2    3     4    5    6    7
     201static char XMLdelimiters[] = {' ', '\0', '\0', ';', '\0', '=', '>', '/'};
     202
     203static inline bool isXMLDelimiter(const char c)
     204{
     205    return c == XMLdelimiters[(unsigned int) c & 0x7];
     206}
     207
     208static inline bool isGeneralDelimiter(const char c)
     209{
     210    return !(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9'));
     211}
     212
    200213#endif /* PBGS_DIV_UTILITIES_H_ */
Note: See TracChangeset for help on using the changeset viewer.