apue（第三版）11章多线程互斥量链表的例子搞晕了

keenboa

书上的代码：
#include <stdlib.h>
#include <pthread.h>
#define NHASH 29
#define HASH(id) (((unsigned long)id)%NHASH)
struct foo *fh[NHASH];
pthread_mutex_t hashlock = PTHREAD_MUTEX_INITIALIZER;
struct foo {
        int f_count;
        pthread_mutex_t f_lock;
        int f_id;
        struct foo *f_next; /* protected by hashlock */
/* ... more stuff here ... */
};
struct foo *
foo_alloc(int id) /* allocate the object */
{
        struct foo *fp;
        int idx;
        if ((fp = malloc(sizeof(struct foo))) != NULL) {
                fp->f_count = 1;
                fp->f_id = id;
                if (pthread_mutex_init(&fp->f_lock, NULL) != 0) {
                        free(fp);
                        return (NULL);
                }
                idx = HASH(id);  /*这里id只要是小于29，那结果idx=id吧？*/
                pthread_mutex_lock(&hashlock);
                fp->f_next = fh[idx]; /*fh只是在前面声明了一下，fh[idx]应该是NULL吧？。*/
                fh[idx] = fp; /*fh[idx]->f_next就也应该是空吧？网上说是把新项插入头节点，但fh[idx]->f_next都是空的呀，没链起来呀。*/   
                pthread_mutex_lock(&fp->f_lock);
                pthread_mutex_unlock(&hashlock);
                /* ... continue initialization ... */
                pthread_mutex_unlock(&fp->f_lock);
        }
        return (fp);
}
void foo_hold(struct foo *fp) /* add a reference to the object */
{
        pthread_mutex_lock(&fp->f_lock);
        fp->f_count++;
        pthread_mutex_unlock(&fp->f_lock);
}
struct foo *
foo_find(int id) /* find an existing object */
{
        struct foo *fp;
        pthread_mutex_lock(&hashlock);
        for (fp = fh[HASH(id)]; fp != NULL; fp = fp->f_next) {
                if (fp->f_id == id) {
                        foo_hold(fp);
                        break;
                }
        }
        pthread_mutex_unlock(&hashlock);
        return (fp);
}
void foo_rele(struct foo *fp) /* release a reference to the object */
{
        struct foo *tfp;
        int idx;
        pthread_mutex_lock(&fp->f_lock);
        if (fp->f_count == 1) { /* last reference */
                pthread_mutex_unlock(&fp->f_lock);
                pthread_mutex_lock(&hashlock);
                pthread_mutex_lock(&fp->f_lock);
                /* need to recheck the condition */
                if (fp->f_count != 1) {
                        fp->f_count--;
                        pthread_mutex_unlock(&fp->f_lock);
                        pthread_mutex_unlock(&hashlock);
                        return;
                }
                /* remove from list */
                idx = HASH(fp->f_id);
                tfp = fh[idx];
                if (tfp == fp) {
                        fh[idx] = fp->f_next;
                } else {
                        while (tfp->f_next != fp)
                                tfp = tfp->f_next;
                        tfp->f_next = fp->f_next;
                }
                pthread_mutex_unlock(&hashlock);
                pthread_mutex_unlock(&fp->f_lock);
                pthread_mutex_destroy(&fp->f_lock);
                free(fp);
        } else {
                fp->f_count--;
                pthread_mutex_unlock(&fp->f_lock);
        }
}

疑问如上面程序中的注释，我做了一个循环：

int main(void) {
        int t = 0;
        while (t < NHASH) {
                 foo_alloc(t);
                printf("%d:%d:%d\n", t, fh[t]->f_next, fh[t] ) ;
                t++;
        }
   return 0;

}

结果是fh数组里面的所有成员的fp->f_next都是NULL，这链表也没有链起来啊？

fp->f_next = fh[idx];
fh[idx] = fp; 网上说是把新项插入头节点，但fh[idx]->f_next都是空的呀，没链起来呀。

还是我理解错了，foo_alloc不是这样用的吗？

qshllxfx

fh[idx]就是头结点

keenboa

回复 2# qshllxfx
您是说它这个例子没错吗？是我理解错了？能详细一点解答一下我的疑问吗？谢谢！

   

qshllxfx

初始
    fh[idx](0)
增加一个节点fp1
    fh[idx](fp1) -->  fp1->f_next(0)
增加第二个相同hash id的节点fp2
    fh[idx](fp2)  -->  fp2->f_next(fp1) --> fp1->f_next(0)

括号里的是指针的值

keenboa

回复 4# qshllxfx
明白了，主要是对散列的概念没理解对，谢谢。