The Data Structures


typedef struct symbol {
    char* name; /**< the name of the symbol */
    int   addr; /**< symbol's address in the LC3 memory */
} symbol_t;

typedef struct sym_table sym_table_t;

struct sym_table {
  int      size;        /**< size of hash table                          */
  node_t** hash_table;  /**< array of head of linked list for this index */
  char**   addr_table;  /**< look up symbols by addr (optional)          */
};

typedef struct node {
  struct node* next;     /**< linked list of symbols at same index */
  int          hash;     /**< hash value - makes searching faster  */
  symbol_t     symbol;   /**< the data the user is interested in   */
} node_t;

Graphical View of the Data Structures


    sym_table_t
   +------------+       
   | size       |         (array of node_t*)
   | hash_table | ----------> +------+
   | addr_table | ---+      0 | head | ---> NULL (some lists are empty, why?)
   +------------+    |        | head |
                     |        | head |        node_t
                     |        | head | ---> +--------+        node_t
                     |        | ...  |      | next   | ---> +--------+
                     | size-1 |      |      | hash   |      | next   | --> NULL
                     |        +------+      +--------+      | hash   |
                     |                      | symbol |      +--------+
                     |   "someLabel\0" <--- |   name |      | symbol |
                     |                      |   addr |  +-->|   name |
                     |                      +--------+  |   |   addr |
                     |                      +--------+  |   +--------+
                     |                                  |   +--------+
                     |                                  |
                     |                                  |
                     |                                  |
                     |                                  |
                     |                                  |
     array of char*  |                                  |
       +--------+ <--+                                  |
0      | ...    |                                       |
       | ...    |                                       |
       | name   | --------------------------------------+
       | ...    |
       | ...    |
       | name   | ---> NULL (most entries are NULL, why?)
       |        |
2^16-1 | ...    |
       +--------+