CII读书笔记(1)：一种不同的内存分配方法

Table.h中的片断：
#define T Table_T
typedef struct T *T;
struct T {
    int size;
    int (*cmp)(const void *x, const void *y);
    unsigned (*hash)(const void *key);
    int length;
    unsigned timestamp;
    struct binding {
        struct binding *link;
        const void *key;
        void *value;
    } **buckets;
};
#undef T

Table.c中有如下片断：
#include "table.h"
T Table_new(int hint,
    int cmp(const void *x, const void *y),
    unsigned hash(const void *key)) {
    T table;
    int i;
    static int primes[] = { 509, 509, 1021, 2053, 4093,
        8191, 16381, 32771, 65521, INT_MAX };
    for (i = 1; primes[i] < hint; i++)
        ;
    table = ALLOC(sizeof (*table) +
        primes[i-1]*sizeof (table->buckets[0]));
    table->size = primes[i-1];
    /* some irrelevent code omitted */
    table->buckets = (struct binding **)(table + 1);
    /* some irrelevent code omitted */
    return table;
}
/* 上面的程序中，首先分配了
sizeof (*table) + primes[i-1]*sizeof (table->buckets[0])
个字节，并且让table指针指向这块内存。其中前sizeof(*table)个字节就是一个struct Table_T类型需要的内存，后面primes[i-1]*sizeof (table->buckets[0])个字节，实际上是分配给table的buckets成员的。其后的
table->buckets = (struct binding **)(table + 1);
所做的工作就是让table->buckets指向ALLOC分配的内存块中的后primes[i-1]*sizeof (table->buckets[0])个字节。

程序片断
    table = ALLOC(sizeof (*table) +
        primes[i-1]*sizeof (table->buckets[0]));
    table->buckets = (struct binding **)(table + 1);
效果上可以等价为：
    table = ALLOC(sizeof(*table);
    table->buckets = ALLOC(primes[i-1]*sizeof (table->buckets[0]));
但有两点区别：
第一，效率不同。用方法1的话，分配和释放内存都只需要一次函数调用。
第二，具体内存区域分布可能不同。方法1保证*table的最后一个字节和table->buckets的第一个字节逻辑地址上是连续的，但是法2对此没有保证。

理解table->buckets = (struct binding **)(table + 1);时注意，table的类型是struct Table_T *, table + 1的地址是(long)table + sizeof(*table)。这一点比较难想，可以通过类比帮助理解。比如定义int a[10], *pa，pa + 1应该是a[1]的地址。这个地址的值，就是(long)pa + sizeof(int)，即(long)a + sizeof(*a)。指针运算的结果可以一般化地表示为：
p + n = (long)p + n * sizeof(*p)
知道了这一点，即可以知道table + 1指向的内存地址是：从table的地址算起，跳过一个struct Table_T类型占用的内存之后的地址。以上的分析可以通过运行下面的程序验证：
*/

#include

#define T Table_T
typedef struct T *T;
struct T {
    int size;
    int (*cmp)(const void *x, const void *y);
    unsigned (*hash)(const void *key);
    int length;
    unsigned timestamp;
    struct binding {
        struct binding *link;
        const void *key;
        void *value;
    } **buckets;
};

#define addrof(x) printf("Address of "#x" is %x\n", (x));
int
main(void) {
    T table;
    addrof(table);
    addrof(table + 1);
    printf("Value of <(long)table + sizeof(*table)> is %x\n",
            ((long)table + sizeof(*table)));
    addrof(&(table->buckets));
    return 0;
}

/cygdrive/e/wrk/cpp/c/cii_lea $ ./a.exe
Address of table is 610e21a0
Address of table + 1 is 610e21b8
Value of <(long)table + sizeof(*table)> is 610e21b8
Address of &(table->buckets) is 610e21b4
/cygdrive/e/wrk/cpp/c/cii_lea $