/* O. Baudon, project Inca, December 18, 1998 Copyright (c) 1993-1998 Olivier Baudon - LaBRI, Universite Bordeaux 1. All rights reserved. See the file "license.terms" for information on usage and redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES. */ #include #include #include "list.h" struct s_atom { list_position prev; void * object; list_position next; }; struct s_list { int size; list_position cursor; list_position first, last; list_malloc_type malloc; list_free_type free; list_deallocate_type deallocate; }; /* Used to transform a list to an array. */ static int s_insert_to_array(void * element, void ** data); list list_create(list_malloc_type malloc, list_free_type free, list_deallocate_type deallocate) { list temp; temp = (list)malloc(sizeof(struct s_list)); temp->size = 0; temp->cursor = BEGINNING; temp->first = temp->last = NULL; temp->malloc = malloc; temp->free = free; temp->deallocate = deallocate; return temp; } void list_destroy(list list) { list_position cursor = list->first; while (cursor) { list_position next = cursor->next; if (list->deallocate) list->deallocate(cursor->object); list->free(cursor); cursor = next; } list->free(list); } int list_size(list list) { return list->size; } int list_empty(list list) { return (list->size == 0); } list_position list_insert(list list, void * object) { list_position old_cursor = list->cursor; list_position new_cursor = (list_position)list->malloc(sizeof(struct s_atom)); if (old_cursor == BEGINNING) /* object will be the first element.*/ { new_cursor->prev = NULL; new_cursor->next = list->first; list->first = new_cursor; if (list->last == NULL) /* list was empty */ list->last = new_cursor; } else { new_cursor->prev = old_cursor; new_cursor->next = old_cursor->next; if (new_cursor->next) /* test if not last position */ new_cursor->next->prev = new_cursor; else list->last = new_cursor; old_cursor->next = new_cursor; } new_cursor->object = object; list->cursor = new_cursor; list->size++; return (list_position)new_cursor; } list_position list_insert_after(list list, list_position pos, void * object) { list_position old_position = list->cursor; list_position insert_position = NULL; list_modify_position(list, pos); insert_position = list_insert(list, object); list_modify_position(list, old_position); return insert_position; } void list_replace(list list, void * object) { assert(list->cursor != BEGINNING); if (list->deallocate) list->deallocate(list->cursor->object); list->cursor->object = object; } void list_remove(list list) { list_position old_cursor = list->cursor; assert(old_cursor != BEGINNING); if (list->deallocate) list->deallocate(old_cursor->object); if (old_cursor->prev) old_cursor->prev->next = old_cursor->next; else list->first = old_cursor->next; if (old_cursor->next) { list->cursor = old_cursor->next; old_cursor->next->prev = old_cursor->prev; } else list->cursor = list->last = old_cursor->prev; list->free(old_cursor); --list->size; } void list_remove_from_position(list list, list_position pos) { list_position old_position = list->cursor; list_modify_position(list, pos); list_remove(list); if (old_position != pos) list_modify_position(list, old_position); } void * list_get_current(list list) { assert(list->cursor != BEGINNING); return list->cursor->object; } void * list_get_object(list list, list_position pos) { assert(pos); return pos->object; } void * list_get_first(list list) { assert(list->first); return list->first->object; } void * list_get_last(list list) { assert(list->first); return list->last->object; } list_position list_get_position(list list) { return (list_position)list->cursor; } int list_at_first(list list) { return list->cursor == list->first; } int list_at_last(list list) { return list->cursor == list->last; } int list_at_beginning(list list) { return list->cursor == BEGINNING; } void list_modify_position(list list, list_position new_pos) { list->cursor = new_pos; } void list_go_previous(list list) { assert (!list_at_beginning(list)); list->cursor = list->cursor->prev; } void list_go_next(list list) { assert (!list_at_last(list)); if (list->cursor == BEGINNING) list->cursor = list->first; else list->cursor = list->cursor->next; } void list_go_first(list list) { list->cursor = list->first; } void list_go_last(list list) { list->cursor = list->last; } void list_go_beginning(list list) { list->cursor = BEGINNING; } void list_map(list list, list_map_type fun, void *call_data) { list_position cursor = list->first; for (; cursor; cursor = cursor->next) if (! fun(cursor->object, call_data)) break; } list list_append(list l1, list l2) { assert(l1->malloc == l2->malloc && l1->free == l2->free && l1->deallocate == l2->deallocate); if (l1->size) l1->last->next = l2->first; else l1->first = l2->first; if (l2->size) { l2->first->prev = l1->last; l1->last = l2->last; } l1->size += l2->size; return l1; } void list_to_array(list l, void *** arrayPtr) { int size = list_size(l); void ** array = (void **)l->malloc(sizeof(void *) * size); int index = 0; void * data[2]; *arrayPtr = array; data[0] = &index; data[1] = array; list_map(l, (list_map_type)s_insert_to_array, data); } static int s_insert_to_array(void * element, void ** data) { int *indexPtr = (int*)data[0]; void ** array = data[1]; array[*indexPtr++] = element; return 1; } static void s_print_list(list l) { int i; list_position pos = l->first; printf("list %0x size %0d first %0x last %0x current %0x\n", (unsigned int)l, l->size, (unsigned int)l->first, (unsigned int)l->last, (unsigned int)l->cursor); for (i = 0; i < l->size; ++i, pos = pos->next) printf("%d: prev %0x obj %0x next %0x\n", i, (unsigned int)pos->prev, (unsigned int)pos->object, (unsigned int)pos->next); }