List.c File Reference

#include "Config.h"
#include <assert.h>
#include <stdlib.h>
#include "List.h"

Go to the source code of this file.

Macros
#define	_Class   _List

Functions
Class *	_List (void)
static void	_remove (List *self, const ident element)
static void	_sort (List *self, Comparator comparator)
static void	append (List *self, const ident element)
static bool	contains (const List *self, const ident element)
static Object *	copy (const Object *self)
static void	dealloc (Object *self)
static void	enumerate (const List *self, ListEnumerator enumerator, ident element)
static void	filter (List *self, Predicate predicate, ident data)
static List *	filteredList (const List *self, Predicate predicate, ident data)
static ident	find (const List *self, Predicate predicate, ident data)
static List *	init (List *self)
static void	initialize (Class *clazz)
static void	insertAfter (List *self, ListNode *node, const ident element)
static void	map (List *self, Functor functor, ident data)
static List *	mappedList (const List *self, Functor functor, ident data)
static ListNode *	nodeForElement (const List *self, const ident element)
static void	prepend (List *self, const ident element)
static ident	reduce (const List *self, Reducer reducer, ident accumulator, ident data)
static void	removeAll (List *self)
static void	removeNode (List *self, ListNode *node)

Macro Definition Documentation

_Class

#define _Class   _List

Definition at line 31 of file List.c.

Function Documentation

_List()

Class * _List

(

void

)

Definition at line 406 of file List.c.

                   {
  static Class *clazz;
  static Once once;
 
  do_once(&once, {
    clazz = _initialize(&(const ClassDef) {
      .name = "List",
      .superclass = _Object(),
      .instanceSize = sizeof(List),
      .interfaceSize = sizeof(ListInterface),
      .initialize = initialize,
    });
  });
 
  return clazz;
}

_remove()

static void _remove ( List *  self, const ident  element  )

static

Definition at line 310 of file List.c.

                                                     {
 
  ListNode *node = $(self, nodeForElement, element);
  if (node) {
    $(self, removeNode, node);
  }
}

_sort()

static void _sort ( List *  self, Comparator  comparator  )

static

Definition at line 350 of file List.c.

                                                     {
 
  assert(comparator);
 
  if (self->count < 2) {
    return;
  }
 
  for (ListNode *node = self->head->next; node; ) {
    ListNode *next = node->next;
    ident key = node->element;
 
    ListNode *j = node->prev;
    while (j && comparator(j->element, key) > OrderSame) {
      j->next->element = j->element;
      j = j->prev;
    }
 
    (j ? j->next : self->head)->element = key;
    node = next;
  }
}

append()

static void append ( List *  self, const ident  element  )

static

Definition at line 72 of file List.c.

                                                    {
 
  ListNode *node = calloc(1, sizeof(ListNode));
  assert(node);
 
  node->element = element;
  node->prev = self->tail;
 
  if (self->tail) {
    self->tail->next = node;
  } else {
    self->head = node;
  }
 
  self->tail = node;
  self->count++;
}

contains()

static bool contains ( const List *  self, const ident  element  )

static

Definition at line 94 of file List.c.

                                                            {
  return $(self, nodeForElement, element) != NULL;
}

copy()

static Object * copy ( const Object *  self )

static

See also

Object::copy(const Object *)

Remarks

Elements are not retained, since List does not retain them on insertion either. The copy does not inherit destroy, and so borrows the elements rather than owning them, as filteredList and mappedList do.

Definition at line 41 of file List.c.

                                        {
 
  const List *this = (List *) self;
 
  List *copy = $(alloc(List), init);
  assert(copy);
 
  for (ListNode *node = this->head; node; node = node->next) {
    $(copy, append, node->element);
  }
 
  return (Object *) copy;
}

dealloc()

static void dealloc ( Object *  self )

static

See also

Object::dealloc(Object *)

Definition at line 58 of file List.c.

                                  {
 
  List *this = (List *) self;
  $(this, removeAll);
 
  super(Object, self, dealloc);
}

enumerate()

static void enumerate ( const List *  self, ListEnumerator  enumerator, ident  element  )

static

Definition at line 102 of file List.c.

                                                                                  {
 
  assert(enumerator);
 
  for (ListNode *node = self->head; node; ) {
    ListNode *next = node->next;
    if (enumerator(self, node, element)) {
      break;
    }
    node = next;
  }
}

filter()

static void filter ( List *  self, Predicate  predicate, ident  data  )

static

Definition at line 119 of file List.c.

                                                                {
 
  assert(predicate);
 
  for (ListNode *node = self->head; node; ) {
    ListNode *next = node->next;
    if (!predicate(node->element, data)) {
      $(self, removeNode, node);
    }
    node = next;
  }
}

filteredList()

static List * filteredList ( const List *  self, Predicate  predicate, ident  data  )

static

Definition at line 136 of file List.c.

                                                                             {
 
  assert(predicate);
 
  List *list = $(alloc(List), init);
  for (ListNode *node = self->head; node; node = node->next) {
    if (predicate(node->element, data)) {
      $(list, append, node->element);
    }
  }
 
  return list;
}

find()

static ident find ( const List *  self, Predicate  predicate, ident  data  )

static

Definition at line 154 of file List.c.

                                                                     {
 
  assert(predicate);
 
  for (ListNode *node = self->head; node; node = node->next) {
    if (predicate(node->element, data)) {
      return node->element;
    }
  }
 
  return NULL;
}

init()

static List * init ( List *  self )

static

Definition at line 173 of file List.c.

                              {
 
  self = (List *) super(Object, self, init);
  return self;
}

initialize()

static void initialize ( Class *  clazz )

static

See also

Class::initialize(Class *)

Definition at line 378 of file List.c.

                                     {
 
  ((ObjectInterface *) clazz->interface)->copy = copy;
  ((ObjectInterface *) clazz->interface)->dealloc = dealloc;
 
  ((ListInterface *) clazz->interface)->append = append;
  ((ListInterface *) clazz->interface)->contains = contains;
  ((ListInterface *) clazz->interface)->enumerate = enumerate;
  ((ListInterface *) clazz->interface)->filter = filter;
  ((ListInterface *) clazz->interface)->filteredList = filteredList;
  ((ListInterface *) clazz->interface)->find = find;
  ((ListInterface *) clazz->interface)->init = init;
  ((ListInterface *) clazz->interface)->insertAfter = insertAfter;
  ((ListInterface *) clazz->interface)->map = map;
  ((ListInterface *) clazz->interface)->mappedList = mappedList;
  ((ListInterface *) clazz->interface)->nodeForElement = nodeForElement;
  ((ListInterface *) clazz->interface)->prepend = prepend;
  ((ListInterface *) clazz->interface)->reduce = reduce;
  ((ListInterface *) clazz->interface)->removeAll = removeAll;
  ((ListInterface *) clazz->interface)->remove = _remove;
  ((ListInterface *) clazz->interface)->removeNode = removeNode;
  ((ListInterface *) clazz->interface)->sort = _sort;
}

insertAfter()

static void insertAfter ( List *  self, ListNode *  node, const ident  element  )

static

Definition at line 183 of file List.c.

                                                                         {
 
  if (node == NULL || node == self->tail) {
    $(self, append, element);
    return;
  }
 
  ListNode *newNode = calloc(1, sizeof(ListNode));
  assert(newNode);
 
  newNode->element = element;
  newNode->prev = node;
  newNode->next = node->next;
 
  if (node->next) {
    node->next->prev = newNode;
  }
  node->next = newNode;
 
  self->count++;
}

map()

static void map ( List *  self, Functor  functor, ident  data  )

static

Definition at line 209 of file List.c.

                                                         {
 
  assert(functor);
 
  for (ListNode *node = self->head; node; node = node->next) {
    node->element = functor(node->element, data);
  }
}

mappedList()

static List * mappedList ( const List *  self, Functor  functor, ident  data  )

static

Definition at line 222 of file List.c.

                                                                       {
 
  assert(functor);
 
  List *list = $(alloc(List), init);
  for (ListNode *node = self->head; node; node = node->next) {
    $(list, append, functor(node->element, data));
  }
 
  return list;
}

nodeForElement()

static ListNode * nodeForElement ( const List *  self, const ident  element  )

static

Definition at line 238 of file List.c.

                                                                       {
 
  for (ListNode *node = self->head; node; node = node->next) {
    if (node->element == element) {
      return node;
    }
  }
 
  return NULL;
}

prepend()

static void prepend ( List *  self, const ident  element  )

static

Definition at line 253 of file List.c.

                                                     {
 
  ListNode *node = calloc(1, sizeof(ListNode));
  assert(node);
 
  node->element = element;
  node->next = self->head;
 
  if (self->head) {
    self->head->prev = node;
  } else {
    self->tail = node;
  }
 
  self->head = node;
  self->count++;
}

reduce()

static ident reduce ( const List *  self, Reducer  reducer, ident  accumulator, ident  data  )

static

Definition at line 275 of file List.c.

                                                                                      {
 
  assert(reducer);
 
  for (ListNode *node = self->head; node; node = node->next) {
    accumulator = reducer(node->element, accumulator, data);
  }
 
  return accumulator;
}

removeAll()

static void removeAll ( List *  self )

static

Definition at line 290 of file List.c.

                                  {
 
  ListNode *node = self->head;
  while (node) {
    ListNode *next = node->next;
    if (self->destroy) {
      self->destroy(node->element);
    }
    free(node);
    node = next;
  }
 
  self->head = self->tail = NULL;
  self->count = 0;
}

removeNode()

static void removeNode ( List *  self, ListNode *  node  )

static

Definition at line 322 of file List.c.

                                                   {
 
  assert(node);
 
  if (node->prev) {
    node->prev->next = node->next;
  } else {
    self->head = node->next;
  }
 
  if (node->next) {
    node->next->prev = node->prev;
  } else {
    self->tail = node->prev;
  }
 
  if (self->destroy) {
    self->destroy(node->element);
  }
 
  free(node);
  self->count--;
}