Лучший способ итерации непрозрачного абстрактного типа данных

Существует несколько способов поддержки итераций в абстрактных типах данных. Это зависит от того, насколько вы хотите абстрагироваться и какой контроль вы хотите, чтобы ваши пользователи имели.

Произвольный доступ

Если ваш тип данных поддерживает произвольный доступ, вы можете позволить пользователю отвечать за итерацию (например, массивы):

/* 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++, я бы выбрал лямбда-выражения).

То, как вы это делаете, не только смешивает обязанности для ваших типов данных, но вы также теряете многопоточную итерацию.

Я не очень люблю макросы, когда можно легко создать решение, понятное и вам, и тому, кто использует ваш код, но, в любом случае, здесь ссылка на вопрос SO, который, кажется, дает то, что вы хотели, с помощью макросов.