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 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 385 of file List.c.

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

_remove()

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

static

Definition at line 290 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 330 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 52 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 74 of file List.c.

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

dealloc()

static void dealloc ( Object *  self )

static

See also

Object::dealloc(Object *)

Definition at line 38 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 82 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 99 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 116 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 134 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 153 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 358 of file List.c.

                                     {
 
  ((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 163 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 189 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 202 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 218 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 233 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 255 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 270 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 302 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--;
}