9. Linkedlist

The linkedlist functions manipulate a sigularly linked list of data pointers.

Example 4. Inserting and Enumerating Elements in a List
The following example illustrates how to insert and iterate over elements in a linkedlist(3m): 


  #include <stdlib.h>
  #include <stdio.h>
  #include <mba/linkedlist.h>
  
  int
  main(int argc, char *argv[])
  {
      struct linkedlist list;
      int i;
      iter_t iter;
      const char *elem;
  
      linkedlist_init(&list,
                    0,                               /* no size limit */
                    NULL); /* use standard library allocator (malloc) */
  
      for (i = 1; i < argc; i++) {
          linkedlist_insert_sorted(&list,
                    cmp_text,               /* simple text comparison */
                    NULL,   /* cmp_text does not use a context object */
                    NULL,            /* do not replace equal elements */
                    argv[i]);
      }
  
      linkedlist_iterate(&list, &iter);
      while ((elem = linkedlist_next(&list, &iter))) {
          printf("%s\n", elem);
      }
  
      linkedlist_deinit(&list, NULL, NULL);
  
      return EXIT_SUCCESS;
  }
  
  $ ./t carbon silicon germanium carbon
  carbon
  carbon
  germanium
  silicon

9.1. Memory management functions

These functions should be used to manage linkedlist objects.

The linkedlist_init function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_init(struct linkedlist *l, unsigned int max_size, struct allocator *al);
Description
The linkedlist_init function initializes a linkedlist object. The linkedlist will accepts no more than max_size items. If max_size is zero the list will accept no more than MAX_INT items. Memory for list elements will be allocated from the allocator al. It may be necessary to call linkedlist_deinit to release memory from the allocator al.
Returns
The linkedlist_init function returns -1 if sets errno to an appropriate value if the operation failed or 0 if the list was successfully initialized.

The linkedlist_deinit function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_deinit(struct linkedlist *l, del_fn data_del, void *context);
Description
The linkedlist_deinit function calls the data_del function if it is not NULL with each data pointer in the list and the context parameter context and then releases memory allocated for list elements.
Returns
The linkedlist_deinit function returns -1 and sets errno to an appropriate value if the operation failed or 0 if the list was successfully deinitialized.

The linkedlist_new function
Synopsis 

  #include <mba/linkedlist.h>
  struct linkedlist *linkedlist_new(unsigned int max_size, struct allocator *al);
Description

Returns
The linkedlist_new function allocates memory from the allocator al, initializes it with the linkedlist_init function and returns a pointer to the a new linkedlist object. If memory for the linkedlist cannot be allocated a null pointer is returned and errno is set appropriately.

The linkedlist_del function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_del(struct linkedlist *l, del_fn data_del, void *context);
Description
The linkedlist_del function deinitializes the list l with the linkedlist_deinit function before freeing l itself.

The linkedlist_clear function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_clear(struct linkedlist *l, del_fn data_del, void *context);
Description
The linkedlist_clear function clears the list of all elements. If the data_del function is not NULL it will be called with the context argument and each data pointer in the list before releasing memory for list elements.

9.2. List functions

The linkedlist_add function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_add(struct linkedlist *l, void *data);
Description
The linkedlist_add function appends a data pointer to the end of the list. If the list has max_size elements, -1 is returned and errno is set to ERANGE.
Returns
The linkedlist_insert function returns 0 if the operation was successful and -1 if an error occurred in which case errno will be set appropriately.

The linkedlist_insert function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_insert(struct linkedlist *l, unsigned int idx, void *data);
Description
inserts a data pointer before the item at idx. If idx equals the size of the list, the data pointer will be appended to the list.
Returns
The linkedlist_insert function returns 0 if the operation was successful and -1 if an error occurred in which case errno will be set appropriately.

The linkedlist_insert_sorted function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_insert_sorted(struct linkedlist *l,
           cmp_fn cmp,
           void *context,
           void **replaced,
           const void *data);
Description
The linkedlist_insert_sorted function inserts the data pointer data into the linked list l in a position determined by the comparison function cmp which is defined as follows: 

  typedef int (*cmp_fn)(const void *object1, const void *object2, void *context);
This function will be called repeatedly with the new data pointer and each data pointer in the list until the insertion is complete or an error occurs. The context parameter is passed as-is. The following describes the outcome of the insertion based on the return value of the cmp_fn:
Returns
The linkedlist_insert_sorted function returns 0 if the operation was successful and -1 if an error occurred in which case errno will be set appropriately.

The linkedlist_is_empty function
Synopsis 

  #include <mba/linkedlist.h>
  int linkedlist_is_empty(const struct linkedlist *l);
Description
The linkedlist_is_empty function returns non-zero if the list is empty and zero if it is not empty.

The linkedlist_size function
Synopsis 

  #include <mba/linkedlist.h>
  unsigned int linkedlist_size(const struct linkedlist *l);
Description
The linkedlist_size function returns the number of items in the list.

The linkedlist_get function
Synopsis 

  #include <mba/linkedlist.h>
  void *linkedlist_get(const struct linkedlist *l, unsigned int idx);
Description
The linkedlist_get function retrieves an item from the list by index. If elements are accessed forward-sequentially each call is an O(1) operation.
Returns
The linkedlist_get function returns the data pointer being retrieved. If the specified idx was out of range, a null pointer is returned and errno is set to ERANGE.

The linkedlist_get_last function
Synopsis 

  #include <mba/linkedlist.h>
  void *linkedlist_get_last(const struct linkedlist *l);
Description
The linkedlist_get_last function returns the last data pointer int the list or a null pointer if the list is empty.

The linkedlist_iterate function
Synopsis 

  #include <mba/linkedlist.h>
  void linkedlist_iterate(void *l, iter_t *iter);
Description
Enumerate each element in the list. The linkedlist_iterate function initializes the iter object to point to the first item in the list. Each subsequent call to linkedlist_next returns the next element in the list or NULL if all elements have been enumerated. The elements are returned in order.

Because linkedlist uses an element index for the state of an interator, after a data object returned by linkedlist_next is removed a subsequent call to linkedlist_next will skip an element. Therefore, to remove elements during iteration, linkedlist_get should be used instead. This will have no performance impact as sequential access is O(1) optimized.

To enumerate each element in a list the following code might be used: 

  iter_t iter;
  linkedlist_iterate(lst, &iter);
  while ((el = linkedlist_next(lst, &iter))) {
      /* use el */
  }

The linkedlist_next function
Synopsis 

  #include <mba/linkedlist.h>
  void *linkedlist_next(void *l, iter_t *iter);
Returns
The linkedlist_next function returns the next data pointer in the list or NULL if all elements have been enumerated.

The linkedlist_remove function
Synopsis 

  #include <mba/linkedlist.h>
  void *linkedlist_remove(struct linkedlist *l, unsigned int idx);
Description
The linkedlist_remove function removes the data pointer at idx from the list. Please refer to the description of linkedlist_iterate for important information regarding the removal of elements during an iteration.
Returns
The linkedlist_remove function returns the data pointer removed from the list.

The linkedlist_remove_data function
Synopsis 

  #include <mba/linkedlist.h>
  void *linkedlist_remove_data(struct linkedlist *l, const void *data);
Description
The linkedlist_remove_data function removes the data pointer data from the list l. Note that if the key is not returned or freed -- that operation must be performed independantly if necessary. Also, please refer to the description of linkedlist_iterate for important information regarding the removal of elements during an iteration.
Returns
The linkedlist_remove_data function returns the data pointer removed from the list.

The linkedlist_remove_last function
Synopsis 

  #include <mba/linkedlist.h>
  void *linkedlist_remove_last(struct linkedlist *l);
Description
The linkedlist_remove_last function removes the last data pointer in the list.
Returns
The linkedlist_remove_last function returns the data pointer removed from the list.

Copyright 2002 Michael B. Allen <mba2000 ioplex.com>