1

我正在阅读 Richard Stevens 在 unix 环境中的高级编程。
线程同步类中有一段代码（第 11 章）。这是显示如何避免许多相同类型的共享结构的竞争条件的代码。
这段代码显示了两个用于同步的互斥锁。一个用于列表fh（一个跟踪所有 foo 结构的列表）和f_next字段，另一个用于结构foo
代码是： 

#include <stdlib.h>
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

#define NHASH 29
#define HASH(fp) (((unsigned long)fp)%NHASH)

struct foo *fh[NHASH];

pthread_mutex_t hashlock = PTHREAD_MUTEX_INITIALIZER;

struct foo {
  int             f_count;
  pthread_mutex_t f_lock;
  struct foo     *f_next; /* protected by hashlock */
  int             f_id;
  /* ... more stuff here ... */
};

struct foo * foo_alloc(void) /* allocate the object */
{
  struct foo  *fp;
  int         idx;

  if ((fp = malloc(sizeof(struct foo))) != NULL) {
      fp->f_count = 1;
      if (pthread_mutex_init(&fp->f_lock, NULL) != 0) {
          free(fp);
          return(NULL);
      }
      idx = HASH(fp);
      pthread_mutex_lock(&hashlock);
      ///////////////////// HERE -----------------
      fp->f_next = fh[idx];
      fh[idx] = fp->f_next;
      //////////////////// UPTO HERE -------------
      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 */
.......

疑问是
1)HASH(fp)预处理器在做什么？
我知道它正在对fp存储的内容进行类型转换，然后对其取模。但是，在函数中，foo_alloc我们只是传递了新分配的 foo 结构的地址。
我们为什么要这样做 我知道这会给我一个 0 到 28 之间的整数 - 存储在数组中fh。但是为什么我们要对地址取模。为什么会有这么多随机化？

2）假设我接受，现在这两行在做什么（也在代码中突出显示）： 

fp->f_next = fh[idx];
fh[idx] = fp->f_next;

我希望最初fh[idx]有我分配给f_nextfoo 字段的任何垃圾值，并且在下一行发生了什么，再次进行相同的分配，但顺序相反。

4

1 回答 1

0

struct foo *fh[NHASH]是一个哈希表，并使用HASH宏作为哈希函数。

1)HASH(fp)计算索引来决定fh存储在哪里fp，fp并使用地址作为关键字来计算索引。我们可以轻松地将地址类型转换为长类型。

2）使用链表来避免散列冲突称为分离链，我认为下面的代码是对的，你可以在书中查看：

fp->f_next = fh[idx];
fh[idx] = fp;

将fp元素插入到链表的头部，fh[idx]初始值为fh[idx]null。

于 2012-04-08T14:45:26.087 回答