List Interface

List and iterator interface.

This header contains the declarations for the list interface and the iterator interface. Both of these structs allow code to use linked lists or array lists without consideration for which list implementation they’re using. The iterator is also the only way to efficiently iterate through the linked list.

Author
Stephen Brennan
Date
Created Sunday, 3 August 2014

Copyright
Copyright (c) 2013-2016, Stephen Brennan. Released under the Revised BSD License. See the LICENSE.txt file for details.

Typedefs

typedef smb_list

A generic list data structure.

Can represent an array list or a linked list. Uses function pointers to hide the implementation. Has heavyweight memory requirements (many pointers). Function calls must be made like this:

list->functionName(list, <params...>)

typedef smb_iter

A generic iterator type.

This is a generic iterator type. It should be implemented for any data structure that has some semblance of sequential access. It can also be used to implement a (lazy) generator. It only provides one directional, read-only access, which makes it apply to a more general set of data structures and generators.

The semantics of the iterator are as follows: An iterator points *between* any two elements in the sequential list. Its current index is the index of the element it will return next.

Functions

void iter_print(smb_iter it, FILE * f, DATA_PRINTER printer)

Prints anything with an iterator.

Parameters
  • it: The iterator. Will be invalidated after this use.
  • f: The file to print to.
  • printer: The printer for handling DATA objects.

struct smb_list
#include <list.h>

A generic list data structure.

Can represent an array list or a linked list. Uses function pointers to hide the implementation. Has heavyweight memory requirements (many pointers). Function calls must be made like this:

list->functionName(list, <params...>)

Public Members

void* data

A pointer to implementation-specific data.

This data is used by the rest of the functions in the struct to perform all required actions.

void(* append)(struct smb_list *l, DATA newData)

See

ll_append

al_append

void(* prepend)(struct smb_list *l, DATA newData)

See

ll_prepend

al_prepend

DATA(* get)(const struct smb_list *l, int index, smb_status *status)

See

ll_get

al_get

void(* set)(struct smb_list *l, int index, DATA newData, smb_status *status)

See

ll_set

al_set

void(* remove)(struct smb_list *l, int index, smb_status *status)

See

ll_remove

al_remove

void(* insert)(struct smb_list *l, int index, DATA newData)

See

ll_insert

al_insert

void(* delete)(struct smb_list *l)

See

ll_delete

al_delete

int(* length)(const struct smb_list *l)

See

ll_length

al_length

void(* push_back)(struct smb_list *l, DATA newData)

See

ll_push_back

al_push_back

DATA(* pop_back)(struct smb_list *l, smb_status *status)

See

ll_pop_back

al_pop_back

DATA(* peek_back)(struct smb_list *l, smb_status *status)

See

ll_peek_back

al_peek_back

void(* push_front)(struct smb_list *l, DATA newData)

See

ll_push_front

al_push_front

DATA(* pop_front)(struct smb_list *l, smb_status *status)

See

ll_pop_front

al_pop_front

DATA(* peek_front)(struct smb_list *l, smb_status *status)

See

ll_pop_front

al_pop_front

int(* index_of)(const struct smb_list *l, DATA d, DATA_COMPARE comp)

Return the index of an item, or -1 if the list doesn’t contain it.

Performs a linear search, O(n) in the number of elements of the list.

Return
The index of the first occurrence of d, else -1.
Parameters
  • l: A pointer to the list.
  • d: The data to search for.
  • comp: The comparator to use. If NULL, compares the bits of d.
Exceptions
  • None.:

struct smb_iter
#include <list.h>

A generic iterator type.

This is a generic iterator type. It should be implemented for any data structure that has some semblance of sequential access. It can also be used to implement a (lazy) generator. It only provides one directional, read-only access, which makes it apply to a more general set of data structures and generators.

The semantics of the iterator are as follows: An iterator points *between* any two elements in the sequential list. Its current index is the index of the element it will return next.

Public Members

const void* ds

The data structure this iterator refers to.

This field is implementation-specific to any iterator. Behavior is undefined when it is modified. It is intended (but not required) to be used by the iterator to store a reference to the data structure.

DATA state

The state of the iterator.

This field is implementation-specific to any iterator. Behavior is undefined when it is modified. It is intended (but not required) to store a state variable of the iterator.

int index

The zero-based index of the iterator.

This field should be automatically updated by the iterator implementation as it operates, requiring no programmer intervention. It should not be modified, but may be accessed. It stores the index of the element that will be returned next.

DATA(* next)(struct smb_iter *iter, smb_status *status)

Returns the next element of the iteration.

Return
The next element of the iteration.
Parameters
  • iter: The iterator being used.

bool(* has_next)(struct smb_iter *iter)

Returns whether the iteration has a next element.

Return
Whether the iteration has a next element.
Parameters
  • iter: The iterator being used.

void(* destroy)(struct smb_iter *iter)

Frees any resources held by the iterator (but not the iterator).

Parameters
  • iter: The iterator being used.
  • free_src: Whether to free the data structure used as the source.

void(* delete)(struct smb_iter *iter)

Frees any resources held by the iterator, and the iterator.

Parameters
  • iter: The iterator being used.
  • free_src: Whether to free the data structure used as the source.