CP-Homework4

:material-circle-edit-outline: 约 361 个字 :fontawesome-solid-code: 197 行代码 :material-clock-time-two-outline: 预计阅读时间 4 分钟

[!ABSTRACT] Modern Compiler Implementation in C.pdf P123
3220104929 250331

5.1

PROGRAM 5.2

struct bucket { 
    string key; 
    void *binding; 
    struct bucket *next; 
};

#define SIZE 109
struct bucket *table[SIZE];

unsigned int hash(char *s0){ 
    unsigned int h=0; char *s;
    for(s=s0; *s; s++) h=h*65599 + *s; 
    return h; 
}

struct bucket *Bucket (string key, void *binding, struct bucket *next) {
    struct bucket *b=checked_malloc(sizeof(*b));
    b->key = key; 
    b->binding = binding; 
    b->next = next;
    return b; 
}

void insert(string key, void *binding) {
    int index=hash(key)%SIZE;
    table[index]=Bucket(key, binding, table[index]); 
}

void *lookup(string key) {
    int index=hash(key)%SIZE;
    struct bucket *b;

    for (b = table[index]; b; b=b>next) 
        if (0==strcmp(b->key,key)) 
            return b->binding; 

    return NULL; 
}

void pop(string key) { 
    int index=hash(key)%SIZE;
    table[index]=table[index]->next; 
}

a

题目要求当满足特定条件后，将数组大小翻倍

主要修改：

通过 entry_count 记录当前有多少项，table_size 记录当前数组的大小
在 insert 时检查加入新项后是否达到临界条件，达到后则调用 double_rehash 完成数组的翻倍操作

struct bucket {
    string key; 
    void *binding;
    struct bucket *next;
};

#define SIZE 109
int table_size = SIZE;
int entry_count = 0;
struct bucket **table;

unsigned int hash(char *s0){ 
    unsigned int h=0; char *s;
    for(s=s0; *s; s++) h=h*65599 + *s; 
    return h; 
}

struct bucket *Bucket(char *key, void *binding, struct bucket *next) {
    struct bucket *b = malloc(sizeof(*b));
    b->key = key; 
    b->binding = binding; 
    b->next = next;
    return b; 
}

void double_rehash() {
    int new_size = table_size * 2;
    struct bucket **new_table = calloc(new_size, sizeof(struct bucket *));

    for (int i = 0; i < table_size; i++) {
        struct bucket *b = table[i];
        while (b) {
            struct bucket *next = b->next;
            int new_index = hash(b->key) % new_size;
            b->next = new_table[new_index];
            new_table[new_index] = b;
            b = next;
        }
    }

    free(table);
    table = new_table;
    table_size = new_size;
}

void insert(char *key, void *binding) {
    if ((entry_count / table_size) >= 2) {
        double_rehash();
    }
    int index = hash(key) % table_size;
    table[index] = Bucket(key, binding, table[index]);
    entry_count++;
}

void *lookup(char *key) {
    int index = hash(key) % table_size;
    struct bucket *b;

    for (b = table[index]; b; b = b->next) 
        if (0==strcmp(b->key,key)) 
            return b->binding; 

    return NULL; 
}

void pop(char *key) { 
    int index = hash(key) % table_size;
    table[index] = table[index]->next;
    entry_count--;
}

b

题目要求当前的各个函数能支持选择不同的 table 进行操作

主要修改：

增加 hash_table 结构用于存储 table
修改部分函数以支持对选择的 table 进行操作

struct bucket {
    char *key;
    void *binding;
    struct bucket *next;
};

#define SIZE 109

struct hash_table {
    int table_size;
    int entry_count;
    struct bucket **table;
};

unsigned int hash(char *s0) {
    unsigned int h = 0;
    char *s;
    for (s = s0; *s; s++) h = h * 65599 + *s;
    return h;
}

struct bucket *Bucket(char *key, void *binding, struct bucket *next) {
    struct bucket *b = malloc(sizeof(*b));
    b->key = key;
    b->binding = binding;
    b->next = next;
    return b;
}

void double_rehash(struct hash_table *ht) {
    int new_size = ht->table_size * 2;
    struct bucket **new_table = calloc(new_size, sizeof(struct bucket *));

    for (int i = 0; i < ht->table_size; i++) {
        struct bucket *b = ht->table[i];
        while (b) {
            struct bucket *next = b->next;
            int new_index = hash(b->key) % new_size;
            b->next = new_table[new_index];
            new_table[new_index] = b;
            b = next;
        }
    }

    free(ht->table);
    ht->table = new_table;
    ht->table_size = new_size;
}

void insert(struct hash_table *ht, char *key, void *binding) {
    if ((ht->entry_count / ht->table_size) >= 2) {
        double_rehash(ht);
    }
    int index = hash(key) % ht->table_size;
    ht->table[index] = Bucket(key, binding, ht->table[index]);
    ht->entry_count++;
}

void *lookup(struct hash_table *ht, char *key) {
    int index = hash(key) % ht->table_size;
    struct bucket *b;

    for (b = ht->table[index]; b; b = b->next)
        if (strcmp(b->key, key) == 0)
            return b->binding;

    return NULL;
}

void pop(struct hash_table *ht, char *key) {
    int index = hash(key) % ht->table_size;
    struct bucket **b = &ht->table[index];

    while (*b) {
        if (strcmp((*b)->key, key) == 0) {
            struct bucket *temp = *b;
            *b = (*b)->next;
            free(temp);
            ht->entry_count--;
            return;
        }
        b = &(*b)->next;
    }
}

6.3

a - register：不是引用/指针传参，不是数组，没有被内部的过程访问
b - memory：被以引用形式传参，且传递给了嵌套函数
c - memory：是数组，且传递给了嵌套函数
d - register：不是引用/指针传参，不是数组，没有被内部的过程访问
e - register：不是引用/指针传参，不是数组，没有被内部的过程访问

6.7

a

获取 show 函数的 fp 值
搜索对应的栈帧发现没有本地变量 output
获取 show 函数的 static link 值
搜索对应的栈帧得到本地变量 output 的值

b

确认 indent 的深度为 3
获取 D2 的值
搜索对应的栈帧发现没有本地变量 output
获取 D1 的值
搜索对应的栈帧得到本地变量 output 的值