Changeset 59e450c65c2885ee922061f292965817dc713d66

Show
Ignore:
Timestamp:
08/06/09 06:40:19 (3 years ago)
Author:
Philip Herron <herron.philip@…>
Parents:
7153655a73260d072e02aa583e2f4294cdda31f5
Children:
ba029258d080b283d5f177522a2c61ea35f387ed
git-committer:
Philip Herron <herron.philip@googlemail.com> / 2009-08-06T06:40:19Z+0100
Message:

On branch master

Working hash tables based off git-core :) thanks!

modified: COPYRIGHT
modified: src/crulesParser.y
modified: src/gc.c
modified: src/hashTable.c
modified: src/symbols.h
modified: src/util.c

Files:
6 modified

Legend:

Unmodified
Added
Removed

  • COPYRIGHT

    rdcf9f50 r59e450c  
    55Contact us (see: AUTHORS) and we'll add you. 
    66 
    7 Philip Herron 
     7Original Developer: 
     8 
     9         * Philip Herron - herron.philip@googlemail.com 
    810 
    911Permission is hereby granted, free of charge, to any person obtaining a copy of 

  • src/crulesParser.y

    ra270d0b r59e450c  
    3737_SYM_STACK_ *_BLK_STK_PTR_= NULL; 
    3838 
     39/* Declare the tables */ 
     40extern struct hash_table *_func_table_; 
     41extern struct hash_table *_rule_table_; 
     42//Variable table stack 
     43extern struct hash_tbl_stk *stk_table; 
     44 
    3945//to prototype to get rid of gcc warnings... 
    4046extern int yylex( ); 

  • src/gc.c

    r7153655 r59e450c  
    3333#include <sys/types.h> 
    3434 
    35 #include <pthread.h> 
    36  
    3735#include "crules.h" 
    3836#include "symbols.h" 
    3937 
    4038/* Declare the tables */ 
    41 extern _hash_table_ *_func_table_; 
    42 extern _hash_table_ *_rule_table_; 
     39extern struct hash_table *_func_table_; 
     40extern struct hash_table *_rule_table_; 
    4341//Variable table stack 
    4442extern struct hash_tbl_stk *stk_table; 
    4543 
    46 static void freesymbol( struct symtab *sym ); 
     44static void free_symbol( struct symtab *sym ); 
     45 
     46/* Invoke the GC to search for garbage flags in symbol tables */ 
     47int invoke_gc() 
     48{ 
     49  error("Not implemented yet!\n\n"); 
     50  return ERROR; 
     51} 
     52 
     53/*Cleanup the program for exit!*/ 
     54int cleanup( ) 
     55{ 
     56  error("Not implemented yet!\n\n"); 
     57  return ERROR; 
     58} 
     59 
     60/*Push any symbols into the garbage table*/ 
     61void push_garbage( struct symtab **sym ) 
     62{ 
     63  error("Not implemented yet!\n\n"); 
     64} 
     65 
     66static 
     67void free_symbol( struct symtab *sym ) 
     68{ 
     69  error("not implemented yet!\n\n"); 
     70  xfree( sym ); 
     71} 
     72 
     73void free_hash_stk_node( struct hash_tbl_stk* node ) 
     74{ 
     75  //.. 
     76} 
    4777 
    4878/** 
    4979 *\param stack the stack you want to free 
    5080 **/ 
    51 void freeStack( _SYM_STACK_** stack ) 
     81void free_stack( _SYM_STACK_** stack ) 
    5282{ 
    5383  _SYM_STACK_* curr= (*stack); 
    … …  
    5888      if( curr ) 
    5989        { 
    60           freesymbol( curr->symbol ); 
     90          free_symbol( curr->symbol ); 
    6191          xfree( curr ); 
    6292        } 
    … …  
    70100 *\return returns macro SUCCESS or ERROR from crules.h 
    71101 **/ 
    72 int freeList( _SYM_LIST_ **node ) 
     102int free_list( _SYM_LIST_ **node ) 
    73103{ 
    74104  if( *node ) 
    … …  
    99129} 
    100130 
    101 /* Invoke the GC to search for garbage flags in symbol tables */ 
    102 int invoke_gc() 
     131void free_hash_table( struct hash_table *table ) 
    103132{ 
    104   error("Not implemented yet!\n\n"); 
    105   return ERROR; 
     133  if( table->array ) 
     134    { 
     135      //go through the array and free symbols 
     136      uint32_t i; 
     137      struct hash_entry *array= table->array; 
     138      for( i=0; i<table->size; ++i ) 
     139        { 
     140          struct symtab *sym=  array[i].symbol; 
     141          if( sym ) 
     142            free_symbol(sym); 
     143        } 
     144      xfree(table->array); 
     145      table->array = NULL; 
     146      table->size = 0; 
     147      table->nr = 0; 
     148    } 
     149  else 
     150    { 
     151      error("Warning: null hash table!\n\n"); 
     152    } 
    106153} 
    107  
    108 /*Cleanup the program for exit!*/ 
    109 int cleanup( ) 
    110 { 
    111   error("Not implemented yet!\n\n"); 
    112   return ERROR; 
    113 } 
    114  
    115 /*Push any symbols into the garbage table*/ 
    116 void push_garbage( struct symtab **sym ) 
    117 { 
    118   error("Not implemented yet!\n\n"); 
    119 } 
    120  
    121 static 
    122 void freesymbol( struct symtab *sym ) 
    123 { 
    124   error("not implemented yet!\n\n"); 
    125   xfree( sym ); 
    126 } 
    127  
    128 void pushStkTable_garbage( struct hash_tbl_stk* node ) 
    129 { 
    130   //.. 
    131 } 

  • src/hashTable.c

    r7153655 r59e450c  
    22 * hashTable.c -> Part of Crules Programming language 
    33 * hashTable implementation used for a many different things 
     4 * 
     5 * Based of hash.c from Git-core! 
    46 * 
    57 * Crules is the legal property of its developers. Please refer to the 
    … …  
    3739#include "symbols.h" 
    3840 
     41//threshold size alloctor to scale faster 
     42#define threshold_alloc(x) (((x)+16)*3/2) 
     43 
    3944/* Declare the tables */ 
    40 _hash_table_ *_func_table_; 
    41 _hash_table_ *_rule_table_; 
     45struct hash_table *_func_table_; 
     46struct hash_table *_rule_table_; 
    4247//Variable table stack 
    4348struct hash_tbl_stk *stk_table; 
     49 
     50static void grow_hash_table( struct hash_table* table ); 
    4451 
    4552/** 
    … …  
    5158 *    http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function 
    5259 **/ 
    53 uint32_t hash( unsigned char *str ) 
     60uint32_t hash( const char *str ) 
    5461{ 
    5562  uint32_t hash= 0x811C9DC5, i; 
    56   for( i=0; i<strlen(str); ++i ) 
     63  while( *str != '\0' ) 
    5764    { 
    58       uint8_t oct= str[i]; 
    59       hash^= oct; 
     65      hash^= (uint8_t) *str; 
    6066      hash= hash*(0x1000193); 
     67      *str++; 
    6168    } 
    6269  return hash; 
    … …  
    7582**/ 
    7683 
    77 struct hash_tbl_stk* const_tbl_stk_node( ) 
     84struct hash_entry* 
     85lookup_table( struct hash_table *table, 
     86              uint32_t hash ) 
    7887{ 
    79   return NULL; 
     88  if( table->array ) 
     89    { 
     90      uint32_t size= table->size, nr= hash%size; 
     91      printf("nr == %i\n", nr); 
     92      struct hash_entry *array= table->array; 
     93 
     94      while( array[nr].symbol ) 
     95        { 
     96          printf("Pass, nr = %i\n", nr); 
     97          if (array[nr].hash == hash) 
     98            break; 
     99          nr++; 
     100          if (nr >= size) 
     101            nr = 0; 
     102        } 
     103      return array+nr; 
     104    } 
     105  else 
     106    { 
     107      fatal("FATAL: looking up null table!\n\n"); 
     108      return NULL; 
     109    } 
    80110} 
    81111 
    82 bool search_table_glb( const char* identifier, 
    83                        uint8_t table ) 
     112struct symtab** insert_hash( uint32_t hash, struct symtab* sym, 
     113                             struct hash_table *table ) 
    84114{ 
    85   return false; 
     115  uint32_t nr= table->nr; 
     116  if( nr >= table->size/2 ) 
     117    grow_hash_table( table ); 
     118 
     119  struct hash_entry *entry= lookup_table(table, hash); 
     120  if( entry->symbol ) 
     121    return &entry->symbol; 
     122  else 
     123    { 
     124      entry->symbol = sym; 
     125      entry->hash = hash; 
     126      table->nr++; 
     127      return NULL; 
     128    } 
    86129} 
    87130 
    88 struct symtab* get_symbol_glb( const char* identifier, 
    89                                uint8_t table ) 
     131static 
     132void grow_hash_table(struct hash_table* table ) 
    90133{ 
    91   return NULL; 
     134  uint32_t prev_size= table->size, size= 0, i= 0; 
     135  struct hash_entry *prev_array= table->array, *array; 
     136 
     137  size= threshold_alloc( prev_size ); 
     138  array= (struct hash_entry*) 
     139    xcalloc( size, sizeof(struct hash_entry) ); 
     140 
     141  //reset nr 
     142  table->nr = 0; 
     143  table->size= size; 
     144  table->array= array; 
     145 
     146  for ( i= 0; i<prev_size; i++ ) 
     147    { 
     148      uint32_t hash= prev_array[i].hash; 
     149      struct symtab *sym= prev_array[i].symbol; 
     150 
     151      if ( sym ) 
     152        insert_hash(hash, sym, table); 
     153    } 
     154 
     155  if( prev_array ) 
     156    xfree(prev_array); 
    92157} 
    93  
    94 bool search_table( const char* identifier, 
    95                    _hash_table_ *table ) 
    96 { 
    97   return false; 
    98 } 
    99  
    100 struct symtab* get_symbol( const char* identifier, 
    101                            _hash_table_ *table ) 
    102 { 
    103   return NULL; 
    104 } 
    105  
    106 void push_symbol( struct symtab* sym, 
    107                   _hash_table_ *table ) 
    108 { 
    109 } 
    110  
    111 struct hash_tbl_stk* 
    112 pop_stk_table( struct hash_tbl_stk *tbl_stk ) 
    113 { 
    114   return NULL; 
    115 } 

  • src/symbols.h

    r7153655 r59e450c  
    6868#define _STK_TYPE_       7 
    6969 
     70/* === === === === === === */ 
     71//table defines 
     72#define _FUNC_TBL_       111 
     73#define _RULE_TBL_       222 
     74 
    7075/* This is the list type */ 
    7176struct list_sym_node { 
    … …  
    111116typedef struct symstack _SYM_STACK_; 
    112117 
    113 struct hash_tbl_entry { 
    114   unsigned long hash; 
     118struct hash_entry { 
     119  uint32_t hash; 
    115120  struct symtab *symbol; 
    116121} __attribute__((aligned)); 
    117 typedef struct hash_tbl_entry _hash_table_; 
     122 
     123struct hash_table { 
     124  uint32_t size, nr; 
     125  struct hash_entry *array; 
     126} __attribute__((aligned)); 
    118127 
    119128struct hash_tbl_stk { 
    120129  uint32_t size; 
    121   struct hash_tbl_entry *table; 
     130  struct hash_tbl *table; 
    122131  struct hash_tbl_stk *next; 
    123132} __attribute__((aligned)); 
    … …  
    127136extern struct symstack* pop( _SYM_STACK_** stack ); 
    128137extern void push( _SYM_STACK_** stack, struct symtab *sym ); 
    129 extern void freeStack( _SYM_STACK_** stack ); 
     138extern void free_stack( _SYM_STACK_** stack ); 
    130139 
    131140/* hashTable.c */ 
    132141//32-bit hash function 
    133 extern uint32_t hash( unsigned char *str ); 
    134 extern struct hash_tbl_stk* const_tbl_stk_node( ); 
     142extern uint32_t hash( const char *str ); 
     143extern struct symtab** insert_hash( uint32_t hash, struct symtab* sym, 
     144                                    struct hash_table *table ); 
     145extern struct hash_entry* lookup_table( struct hash_table *table, 
     146                                            uint32_t hash ); 
    135147 
    136 extern bool search_table_glb( const char* identifier, 
    137                               uint8_t table ); 
    138 extern struct symtab* get_symbol_glb( const char* identifier, 
    139                                       uint8_t table ); 
     148static inline void init_hash_table( struct hash_table *table ) 
     149{ 
     150  table->size= 0; 
     151  table->nr= 0; 
     152  table->array= NULL; 
     153} 
    140154 
    141 extern bool search_table( const char* identifier, 
    142                           _hash_table_ *table ); 
    143 extern struct symtab* get_symbol( const char* identifier, 
    144                            _hash_table_ *table ); 
    145 extern void push_symbol( struct symtab* sym, 
    146                          _hash_table_ *table ); 
    147 extern struct hash_tbl_stk* pop_stk_table( struct hash_tbl_stk *tbl_stk ); 
    148155 
    149156/* listType.c */ 
    … …  
    153160extern _SYM_LIST_* constructListNode( ); 
    154161extern void deleteListItem( uint32_t point, _SYM_LIST_** node ); 
     162int free_list( _SYM_LIST_ **node ); 
    155163 
    156164/* symTab.c */ 
     165//... 
    157166 
    158167#endif //__SYMBOLS_H_ 

  • src/util.c

    r7153655 r59e450c  
    3434#include "symbols.h" 
    3535 
    36 #define _DEFAULT_TBL_SIZE_ 64 
    37  
    3836/* Declare the tables */ 
    39 extern _hash_table_ *_func_table_; 
    40 extern _hash_table_ *_rule_table_; 
     37extern struct hash_table _func_table_; 
     38extern struct hash_table _rule_table_; 
    4139//Variable table stack 
    4240extern struct hash_tbl_stk *stk_table; 
    … …  
    4846int init_tables( ) 
    4947{ 
    50   _func_table_= (_hash_table_*) 
    51     xcalloc( _DEFAULT_TBL_SIZE_, sizeof(_hash_table_) ); 
    52   _rule_table_= (_hash_table_*) 
    53     xcalloc( _DEFAULT_TBL_SIZE_, sizeof(_hash_table_) ); 
    54  
    55   //stk_table=  
     48  init_hash_table( &_func_table_ ); 
     49  init_hash_table( &_rule_table_ ); 
     50  //... 
    5651 
    5752  return SUCCESS;