SIC架构汇编器哈希表打印方式及C语言实现咨询

核心问题解答 #

1. 是否记录哈希表插入顺序？
   • 取决于汇编器的需求：如果需要按符号在源程序中定义的顺序打印（方便对应源码排查问题），就必须记录插入顺序；若仅需按哈希桶顺序、符号字典序打印，则不需要。实际开发中，多数调试用的符号表会支持按插入顺序输出。
2. 是否仅通过中间文件打印？
   • 不是必须的。你可以选择直接在终端输出、写入中间文件，甚至同时支持两种方式——这完全由你的汇编器设计决定。中间文件更多是用于留存编译过程信息，而非唯一的打印途径。

C语言实现带插入顺序的哈希表 #

要实现能保留插入顺序的哈希表，通常采用哈希表+双向链表的组合结构：哈希表负责快速查找符号，双向链表负责按插入顺序存储节点，方便遍历打印。

结构体定义示例 #

// 符号表节点结构体
typedef struct SymbolNode {
    char* name;          // 符号名
    int address;         // 符号对应的内存地址
    struct SymbolNode* next_hash;  // 哈希桶内冲突链的下一个节点
    struct SymbolNode* next_list;  // 顺序链表的下一个节点
    struct SymbolNode* prev_list;  // 顺序链表的上一个节点
} SymbolNode;

// 哈希表与顺序链表的组合结构
typedef struct {
    SymbolNode** buckets;  // 哈希桶数组
    int bucket_count;      // 哈希桶的数量
    SymbolNode* list_head; // 顺序链表的头节点
    SymbolNode* list_tail; // 顺序链表的尾节点
} OrderedHashTable;

核心操作实现 #

1. 初始化哈希表

OrderedHashTable* create_ordered_hash_table(int bucket_count) {
    OrderedHashTable* table = malloc(sizeof(OrderedHashTable));
    table->buckets = calloc(bucket_count, sizeof(SymbolNode*));
    table->bucket_count = bucket_count;
    table->list_head = NULL;
    table->list_tail = NULL;
    return table;
}

2. 插入符号（同时维护哈希表和顺序链表）

// 自定义哈希函数示例：字符串ASCII值累加取模
unsigned int hash_function(const char* name, int bucket_count) {
    unsigned int hash = 0;
    while (*name != '\0') {
        hash = hash * 31 + *name++;
    }
    return hash % bucket_count;
}

void insert_symbol(OrderedHashTable* table, const char* name, int address) {
    // 1. 插入哈希桶，处理冲突
    unsigned int hash = hash_function(name, table->bucket_count);
    SymbolNode* new_node = malloc(sizeof(SymbolNode));
    new_node->name = strdup(name);
    new_node->address = address;
    new_node->next_hash = table->buckets[hash];
    table->buckets[hash] = new_node;

    // 2. 插入顺序链表尾部，维护顺序
    new_node->next_list = NULL;
    new_node->prev_list = table->list_tail;
    if (table->list_tail != NULL) {
        table->list_tail->next_list = new_node;
    } else {
        table->list_head = new_node; // 链表为空时，头节点指向新节点
    }
    table->list_tail = new_node;
}

3. 按插入顺序打印符号表

void print_symbol_table_in_order(OrderedHashTable* table) {
    printf("符号表（按插入顺序）:\n");
    printf("符号名\t内存地址\n");
    SymbolNode* current = table->list_head;
    while (current != NULL) {
        printf("%s\t0x%X\n", current->name, current->address);
        current = current->next_list;
    }
}

注意事项 #

• 记得在汇编器退出前释放所有节点和哈希表的内存，避免内存泄漏。
• 哈希函数可根据需求优化，比如采用djb2等更高效的实现，减少冲突概率。

内容的提问来源于stack exchange，提问作者Dalim Oh