C - How to iterate through an ADT struct?

Question

I am making a set ADT for a school assignment, and I'm pretty close to completion. However I am having some difficulties as to how I should iterate over the various items in a struct: It is essential that the "element" member of the set structure is a void pointer, if it was of the type int, I could set->element[i]. Any suggestions to alternatives?

struct set
{
    void *element;
    int size;
    cmpfunc_t cmpfunc;
    set_t *start;
    set_t *next;
};

int set_contains(set_t *set, void *elem)
{
    for(int i = 0;i<set->size;++i)
      if(set->element[i] == elem)
        return 1;

    return 0;
}

Answer 1

Your ADT structure doesn't really make a lot of sense; it looks like you've tried to cross-breed different design patterns, those being the use of an array to hold the set elements, and the use of a linked-list to hold the set.

I'll take the liberty of modifying the structure so that it is a little more in line with either pattern. First of all, typedef's hide information -> avoid them whenever possible.

First pattern: Use an array of elements

struct set {
  void **elements;              /* array of elements    */
  int nElem;                    /* array count          */
  size_t elemSize;              /* size of element type */
  int(*cmpFunc)(void*, void*);  /* equality comparison  */
};

The elemSize field is used to allocate and copy new elements without knowing their datatype. This is common to both patterns, and to generic ADT's in general. To iterate over this set, use:

int set_contains(struct set *pSet, void *elem) {
  for (int i = 0; i < pSet->nElem; ++i) {
    if (pSet->cmpFunc(pSet->elements[i], elem))
      return 1;
  }
  return 0;
}

Second pattern: Use a linked-list to represent the set

struct node {
  void *data;         /* element data      */
  struct node *next;  /* next node in list */
};

struct set{
  struct node *head;            /* first element       */
  size_t elemSize;              /* size of data type   */
  int(*cmpFunc)(void*, void*);  /* equality comparison */
};

The element size and comparison function are attributes of a given set, not the data that is contained in that set, so they are defined on the set structure, not the node structure, which only defines the data and the associated link. To iterate over this set, use:

int set_contains(struct set *pSet, void *elem) {
  struct node *head = pSet->head;
  while(head) {
    if (pSet->cmpFunc(head->data, elem))
      return 1;
    head = head->next;
  }
  return 0;
}