symbol table符號表使用

在學習lex, yacc過程中,經常需要使用到符號表,用來存儲,訪問數據.
比較快捷的方法該是hash 表,
用數組也是可行的, 比較難以處理的是如何存儲名字,值.
不想多次使用malloc申請內存,構思了這樣一個方法.
先malloc一塊大內存, 然後自己管理內存,最後一次釋放.
核心就是使用sym_sbrk 實現自己的malloc函數.

void *sym_sbrk(struct sym_table_entry *s, int increment)


DEBUG_DUMP 是comm.h中的一個宏定義
#ifdef NODEBUG
#define DEBUG_DUMP(...)
#else
#define DEBUG_DUMP  trace
#endif


#define trace(...) (fprintf(stderr, "[%s %d %s] ", __FILE__, __LINE__, __func__), \
                fprintf(stderr, __VA_ARGS__), fflush(stderr))






代碼如下
sym.h
  1 #ifndef SYMBOL_TABLE_H_
  2 #define SYMBOL-TABLE_H_
  3
  4 #include
  5 #include
  6 #include
  7 #include "comm.h"
  8
  9
 10 enum sym_type {
 11   S_INT ,
 12   S_STR ,
 13   S_PTR ,
 14   S_FLOAT,
 15 } ;
 16
 17 struct   sym
 18 {
 19   int type;
 20   char *name;
 21   union {
 22     void *pdata ;
 23     int  idata ;
 24     float fdata;
 25   } ;
 26 } ;
 27
 28
 29 struct sym_table_entry
 30 {
 31     struct sym  *symlist ;
 32     int  sym_size ;
 33     int  idx ;
 34     char *sym_data ;
 35     char *lim ;
 36     char *end_data_segment  ;
 37 };
 38
 39 /*
 40     memory:   sym_table_entry | symlist | sym_data
 41
 42 */
 43
 44 struct sym_table_entry   *sym_table_alloc(int sym_size, int seg_size)
 45 {
 46          struct sym_table_entry *p;
 47          int asize  ;
 48          asize = sizeof(struct  sym) * sym_size  ;
 49
 50
 51          p = malloc(sizeof(struct sym_table_entry)+ asize + seg_size) ;
 52          p->sym_size   =  sym_size ;
 53
 54          p->symlist   =  (char *)p + sizeof(struct sym_table_entry) ;
 55          p->sym_data  =  (char *)p + sizeof(struct sym_table_entry)    + asize ;
 56
 57          p->end_data_segment    = p->sym_data ;
 58          p->idx    = 0;
 59          p->lim    =  p->sym_data + seg_size ;
 60
 61          return p;
 62 }
 63
 64 void sym_table_free(struct sym_table_entry  *p)
 65 {
 66          free(p) ;
 67 }
 68
 69
 70 void *sym_sbrk(struct sym_table_entry *s, int increment)
 71 {
 72          int m ;
 73          char *pos;
 74          if  ((s->lim - s->end_data_segment) < increment) {
 75
 76                  DEBUG_DUMP("%s\n", "sym_sbrk error");
 77                  return NULL ;
 78          }
 79
 80          pos = s-> end_data_segment ;
 81          s->end_data_segment  += increment ;
 82          return pos ;
 83 }
 84
 85 void *sym_xalloc(struct sym_table_entry *s, int size)
 86 {
 87          void *p ;
 88          p = sym_sbrk(s, size) ;
 89          if  (p == NULL) {
 90                  DEBUG_DUMP("%s\n", "alloc error");
 91                  exit(-1);
 92
 93          }
 94
 95          return p;
 96 }
 97
 98
 99 struct sym  *sym_find(struct sym_table_entry *s, const char *name)
100 {
101          int i;
102          struct sym *p;
103          for (i=0; i< s->idx; i++) {
104                  p =&(s->symlist[i]) ;
105                  if (strcmp(p->name, name) ==0) {
106                          return p;
107                  }
108
109          }
110          return NULL;
111 }
112
113 int sym_put(struct sym_table_entry *s, const char *name,  int type, void *data, int d_size)
114 {
115          int x, l;
116          struct sym *p;
117          int new = 0;
118
119          if  (s->idx >= s->sym_size) {
120                  fprintf(stderr, "%s\n", "symbol table is full");
121                  return -1;
122          }
123
124          p = sym_find(s, name) ;
125          if  (p  == NULL) {
126                  l = strlen(name) + 1 ;
127                  p = &(s->symlist[s->idx]) ;
128                  p->type = type;
129                  p->name = sym_xalloc(s, l);
130                  strcpy(p->name, name) ;
131                  new = 1;
132          } else if (p->type != type) {
133                  fprintf(stderr, "dismatch data type \n");
134                  exit(-1);
135          }
136
137
138          switch (type)  {
139          case  S_INT:
140                  p->idata = *(int *)data ;
141                  s->idx += new ;
142                  break ;
143          case  S_STR:
144                  p->pdata  = sym_xalloc(s, d_size +1) ;
145                  memcpy(p->pdata, data, d_size +1);
146                  s->idx += new ;
147                  break ;
148          case S_PTR:
149                  p->pdata = data ;
150                  s->idx += new ;
151                  break ;
152          case S_FLOAT:
153                  p->fdata = *(float *) data ;
154                  s->idx += new ;
155                  break ;
156          default:
157                  printf("error\n");
158                  exit(-1) ;
159          }
160
161          return 0;
162 }
163
164 #endif
165



做一個簡單的測試.

  1 #include
  2 #include "sym.h"
  3
  4 int test()
  5 {
  6          struct sym_table_entry *sym ;
  7          int x ;
  8          char *str ="hell world this is ";
  9          sym = sym_table_alloc(100,1024) ;
 10          x =3 ;
 11          sym_put(sym,"aaa", S_INT, &x, 4);
 12          sym_put(sym,"bbb", S_INT, &x, 4);
 13          sym_put(sym,"ccc", S_INT, &x, 4);
 14          sym_put(sym,"ccc", S_INT, &x, 4);
 15          sym_put(sym,"ee", S_STR, str, strlen(str));
 16          sym_put(sym,"ff", S_STR, str, strlen(str));
 17          printf("size:%d %s\n", sym->idx , sym_find(sym,"ff")->idata );
 18          sym_table_free(sym);
 19          return 0;
 20 }
 21
 22 int main(int argc, char *argv[])
 23 {
 24          test();
 25          exit(0);
 26 }