c - 迭代 "opaque"抽象数据类型的最佳方式

Question

我正在编写一个哈希表，并且我正在使用一个不透明的指针来管理这个 ADT。这是我的代码的样子:

哈希表.h

typedef struct hash_table *Hash_table;

Hash_table hash_table_init(int size, int(*compare)(void *key_a, void *key_b), int(*hash)(void *key, int size));
void       hash_table_insert(Hash_table ht, void *item);
void*      hash_table_search(Hash_table ht, void *key);
void       hash_table_start_iteration(Hash_table ht);
void*      hash_table_get_next_item(Hash_table ht);
void       hash_table_destroy(Hash_table ht);

哈希表.c

#include <stdlib.h>
#include "hash_table.h"

struct hash_table{
  void *v;                      //array of items (created with a malloc)
  int n;                        //array size
  int iterator;                 //iterator to retrive all the items
  int (*compare)(void*, void*); //compare function
  int (*hash)(void*, int);      //hash function
};

Hash_table hash_table_init(int size, int(*compare)(void *key_a, void *key_b), int(*hash)(void *key, int size))
{...}

void hash_table_insert(Hash_table ht, void *item)
{...}

void* hash_table_search(Hash_table ht, void *key)
{...}

void hash_table_start_iteration(Hash_table ht)
{
  ht->iterator = 0;
}

void* hash_table_get_next_item(Hash_table ht)
{
  if(ht->iterator >= ht->n) return NULL;
  return v[ht->iterator++];
}

void hash_table_destroy(Hash_table ht)
{...}

这是我编写的“for each”函数的代码。它工作得很好，但我真的不喜欢它，我认为这不是一个优雅的代码。

我怎样才能更好地执行此操作？提前致谢

Answer 1

有多种方法支持抽象数据类型的迭代。这取决于您想要抽象多少以及您希望用户拥有多少控制权。

随机访问

如果您的数据类型支持随机访问，您可以让用户负责迭代(如数组):

/* size of hash table */
unsigned hash_table_item_count(Hash_table ht) { return ht->n }

/* random access */
void * hash_table_item_at(Hash_table ht, unsigned n) { /* returns nth item */ }

然后你像这样使用它:

int main() {
  Hash_table table;
  for (unsigned index = 0; index < hash_table_item_count(table); index++) {
    printf("%p\n", hash_table_item_at(table, it));
  }
  return 0;
}

您的数据类型的用户可以控制迭代的方式和时间。这非常易于使用和理解，并且不会占用您更多的内存。

这种方法的一个变体是返回一个指向项目数组的 const 指针，而不是让它们通过一个函数来访问它。

迭代器结构

您可以提供一个知道如何遍历哈希表的迭代器数据类型。这是 C++ 最常用的方法。我倾向于喜欢它，因为您可以在其中抽象出任何类型的迭代逻辑(即，仅对填充的桶进行迭代)并且具有明确的责任分离:

/* the hash table iterator control structure */
struct ht_iterator {
  Hash_table table;
  unsigned index;
};

typedef struct ht_iterator * Ht_iterator;

/* returns a iterator pointing to the first item */
Ht_iterator hash_table_begin(Hash_table ht) {
  Ht_iterator it = malloc(sizeof(*it));
  it->table = ht;
  it->index = 0;
  return it;
}

/* increments the iterator */
void ht_iterator_next(Ht_iterator it) {
  it->index++;
}

/* checks if iterator is at end */
unsigned char ht_iterator_at_end(Ht_iterator it) {
  return !(it->index < it->table->n);
}

/* returns the data this iterator is pointing at */
void * ht_iterator_data(Ht_iterator it) {
  return ht_iterator_at_end(it) ? NULL : it->table->v[it->index];
}

/* frees iterator memory */
void ht_iterator_release(Ht_iterator it) { free(it); }

然后你像这样使用它:

int main() {
  Hash_table t;
  for (Ht_iterator it = hash_table_begin(t); !ht_iterator_at_end(it); ht_iterator_next(it)) {
    printf("%p\n", ht_iterator_data(it));
  }
  ht_iterator_release(it);
  return 0;

它更冗长，但正如我所说，您获得了完全抽象迭代的能力，并且仍然支持控制迭代发生的时间。不过，您不再具有随机访问权限。

遍历回调

第三种方法是自己迭代项目并为每个项目执行用户回调:

/* typedef the process function */
typedef void (*ht_item_processor)(Hash_table t, unsigned i, void * item, void * priv);

/* iterates over all items, calling process() for each one of them */
void hash_table_traversal(Hash_table table, ht_item_processor process, void * priv) {
  for (unsigned i = 0; i < table->n; i++) {
    process(table, i, table->v[i], priv);
  }
}

然后你像这样使用它:

typedef struct {
  /* holds any private state for you */
} my_state;

/* callback to process each item */
void my_process(Hash_table table, unsigned index, void * item, my_state * priv) {
    printf("at %d: %p\n", index, item);
}

int main() {
  Hash_table table;
  my_state state;
  table_traversal(table, my_process, &state);
  return 0;
}

这种方式不那么冗长，仍然抽象迭代逻辑，但用户不再控制迭代。您可以使 hash_table_traversal 对 process() 返回值敏感。如果它为零，它将停止迭代，给用户一些控制权。

priv 指针让用户在每个 process 调用之间存储状态，使他们能够将此代码与 C++ 一起使用(例如，priv 会指向一个类实例)(但如果您使用的是 C++，我会使用 lambda)。

您这样做的方式不仅混合了数据类型的责任，而且还失去了多线程迭代。

当您可以轻松创建一个对您和使用您的代码的任何人都清楚的解决方案时，我并不是很喜欢宏，但是无论如何，here是指向 SO 问题的链接，它似乎提供了您想要的宏。