lib/libmeinos/llist.c

   1 /*
   2  * Copyright (c) 2007 The LOST Project. All rights reserved.
   3  *
   4  * This code is derived from software contributed to the LOST Project
   5  * by Kevin Wolf.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  18  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  23  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  24  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  25  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  26  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include <sys/types.h>
  30 #include <llist.h>
  31 #include <malloc.h>
  32
  33 /**
  34  * Creates a linked list
  35  *  @return linked list
  36  */
  37 llist_t llist_create() {
  38   llist_t list = malloc(sizeof(struct llist_S));
  39   list->anchor = NULL;
  40   list->size = 0;
  41   return list;
  42 }
  43
  44 /**
  45  * Destroys a linked list
  46  *  @param list linked list to destroy
  47  */
  48 void llist_destroy(llist_t list) {
  49   while (llist_pop(list)!=NULL);
  50   free(list);
  51 }
  52
  53 /**
  54  * Gets size of a linked list
  55  *  @param list linked list to get size of
  56  *  @return linked list
  57  */
  58 size_t llist_size(llist_t list) {
  59   if (!list || !list->anchor) return 0;
  60   else return list->size;
  61 }
  62
  63 /**
  64  * Push element to linked list
  65  *  @param list linked list to get size of
  66  *  @param value Value to add to list
  67  *  @return linked list
  68  */
  69 llist_t llist_push(llist_t list,void *value) {
  70   if (!list) return NULL;
  71   struct llist_node *node = malloc(sizeof(struct llist_node));
  72   node->value = value;
  73   node->next = list->anchor;
  74   list->anchor = node;
  75   list->size++;
  76   return list;
  77 }
  78
  79 /**
  80  * Pops element from linked list
  81  *  @param list linked list to pop from
  82  *  @return Value popped
  83  */
  84 void* llist_pop(llist_t list) {
  85   struct llist_node* old_anchor;
  86   void* value;
  87
  88   if (!list) return NULL;
  89
  90   if (list->anchor) {
  91     value = list->anchor->value;
  92     old_anchor = list->anchor;
  93     list->anchor = list->anchor->next;
  94     free(old_anchor);
  95     list->size--;
  96   }
  97   else value = NULL;
  98
  99   return value;
 100 }
 101
 102 /**
 103  * Gets element from a list
 104  *  @param list linked list to get element from
 105  *  @param index Index of element
 106  *  @return Element
 107  */
 108 struct llist_node *llist_get_node_at(llist_t list,size_t index) {
 109   if (!list || !list->anchor || index<0) return NULL;
 110   struct llist_node* current = list->anchor;
 111   int n = index;
 112   if (index>list->size-1) return NULL;
 113
 114   while (n--) {
 115     current = current->next;
 116     if (!current) return NULL;
 117   }
 118
 119   return current;
 120 }
 121
 122 /**
 123  * Gets value of a element in a list
 124  *  @param list linked list to get value from
 125  *  @param index Index of element to get value from
 126  *  @return Value
 127  */
 128 void *llist_get(llist_t list,size_t index) {
 129   struct llist_node *node = llist_get_node_at(list,index);
 130   if (node==NULL) return NULL;
 131   else return node->value;
 132 }
 133
 134 /**
 135  * Inserts an element in a list
 136  *  @param list linked list to insert in
 137  *  @param index Index of new element
 138  *  @param value Value of new element
 139  *  @return linked list
 140  */
 141 llist_t llist_insert(llist_t list,size_t index,void* value) {
 142   struct llist_node* new_node = malloc(sizeof(struct llist_node));
 143   new_node->value = value;
 144
 145   if (!list) return NULL;
 146
 147   if (index) {
 148     struct llist_node* prev_node = llist_get_node_at(list,index-1);
 149     if (!prev_node) return NULL;
 150     new_node->next = prev_node->next;
 151     prev_node->next = new_node;
 152   }
 153   else {
 154     new_node->next = list->anchor;
 155     list->anchor = new_node;
 156   }
 157
 158   list->size++;
 159
 160   return list;
 161 }
 162
 163 /**
 164  * Removes element from list
 165  *  @param list linked list to remove element from
 166  *  @param index Index of element to remove
 167  *  @return Value of removed element
 168  */
 169 void* llist_remove(llist_t list, size_t index) {
 170     void* value;
 171
 172     if (!list) return NULL;
 173
 174     struct llist_node* node;
 175     if (index) {
 176       struct llist_node* prev_node = llist_get_node_at(list,index-1);
 177
 178       if (!prev_node || !prev_node->next) return NULL;
 179
 180       node = prev_node->next;
 181       prev_node->next = node->next;
 182       value = node->value;
 183       free(node);
 184     }
 185     else {
 186       if (!list->anchor) return NULL;
 187
 188       node = list->anchor;
 189       list->anchor = node->next;;
 190       value = node->value;
 191       free(node);
 192     }
 193
 194     list->size--;
 195
 196     return value;
 197 }
 198
 199 /**
 200  * Finds element in list
 201  *  @param list Linked list to search in
 202  *  @param find Element to find
 203  *  @return Index of found Element
 204  */
 205 size_t llist_find(llist_t list,void *find) {
 206   void *element;
 207   size_t i;
 208
 209   for (i=0;(element = llist_get(list,i));i++) {
 210     if (element==find) return i;
 211   }
 212   return -1;
 213 }
 214
 215 /**
 216  * Copies list
 217  *  @param list Linked list to be copied
 218  *  @return New linked list
 219  */
 220 llist_t llist_copy(llist_t list) {
 221   size_t i;
 222   void *element;
 223   llist_t new = llist_create();
 224   for (i=0;(element = llist_get(list,i));i++) llist_push(new,element);
 225   return new;
 226 }