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      capacity;    /**< length of hast_table array                  */
  int      size;        /**< number of symbols (may exceed capacity)     */
  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
+------------+       
| capacity   |
| size       |
| hash_table | -------------> +---------+
| addr_table | --+          0 | node_t* |
+------------+   |            | node_t* |        node_t
                 |            | node_t* | ---> +--------+        node_t
                 |            | ...     |      | next   | ---> +--------+
                 | capacity-1 |         |      | hash   |      | next   | --> NULL
                 |            +---------+      +--------+      | hash   |
                 |                             | symbol |      +--------+
                 |          "someLabel\0" <--- |   name |      | symbol |
                 |                             |   addr |  +-->|   name |
                 |                             +--------+  |   |   addr |
                 |                             +--------+  |   +--------+
                 |                                         |   +--------+
                 |                                         |
                 |                                         |
                 |                                         |
                 |                                         |
                 |                                         |
  array of char* |                                         |
    +--------+ <-+                                         |
0   |        |                                             |
    |        |                                             |
    | char*  | --------------------------------------------+
    |        |
    |        |
    |        |
    |        |
    |        | 2^16-1
    +--------+