Source/charon/linked_list.c

   1 /**
   2  * @file linked_list.c
   3  *
   4  * @brief Generic Double Linked List
   5  *
   6  */
   7
   8 /*
   9  * Copyright (C) 2005 Jan Hutter, Martin Willi
  10  * Hochschule fuer Technik Rapperswil
  11  *
  12  * This program is free software; you can redistribute it and/or modify it
  13  * under the terms of the GNU General Public License as published by the
  14  * Free Software Foundation; either version 2 of the License, or (at your
  15  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
  16  *
  17  * This program is distributed in the hope that it will be useful, but
  18  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  19  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  20  * for more details.
  21  */
  22
  23 #include <stdlib.h>
  24 #include <freeswan.h>
  25 #include <pluto/constants.h>
  26 #include <pluto/defs.h>
  27
  28 #include "linked_list.h"
  29
  30
  31 /**
  32  * @brief implements function destroy of linked_list_item_t
  33  */
  34 static status_t destroy_linked_list_element(linked_list_element_t *linked_list_element)
  35 {
  36         linked_list_element_t * this =  linked_list_element;
  37         pfree(this);
  38         return SUCCESS;
  39 }
  40
  41 linked_list_element_t *linked_list_element_create(void *value)
  42 {
  43         linked_list_element_t *this = alloc_thing(linked_list_element_t, "linked_list_element_t");
  44
  45         this->destroy = destroy_linked_list_element;
  46
  47         this->previous=NULL;
  48         this->next=NULL;
  49         this->value = value;
  50
  51         return this;
  52 }
  53
  54 /**
  55  * @brief implements function insert_first of linked_list_t
  56  */
  57 static status_t insert_first(linked_list_t *linked_list, void *item)
  58 {
  59         linked_list_t *this = linked_list;
  60
  61         linked_list_element_t *element = linked_list_element_create(item);
  62
  63         if (this->count == 0)
  64         {
  65                 /* first entry in list */
  66                 this->first = element;
  67                 this->last = element;
  68                 element->previous = NULL;
  69                 element->next = NULL;
  70         }else
  71         {
  72                 if ((this->first == NULL) || (this->last == NULL))
  73                 {
  74                         /* should never happen */
  75                         element->destroy(element);
  76                         return FAILED;
  77                 }
  78                 linked_list_element_t *old_first_element = this->first;
  79                 element->next = old_first_element;
  80                 old_first_element->previous = element;
  81                 this->first = element;
  82         }
  83
  84         this->count++;
  85
  86         return SUCCESS;
  87 }
  88
  89 /**
  90  * @brief implements function remove_first of linked_list_t
  91  */
  92 static status_t remove_first(linked_list_t *linked_list, void **item)
  93 {
  94         linked_list_t *this = linked_list;
  95
  96         if (this->count == 0)
  97         {
  98                 return FAILED;
  99         }
 100
 101         if (this->first == NULL)
 102         {
 103                 return FAILED;
 104         }
 105
 106         linked_list_element_t *element = this->first;
 107
 108         if (element->next != NULL)
 109         {
 110                 element->next->previous = NULL;
 111         }
 112         this->first = element->next;
 113
 114         *item = element->value;
 115
 116         this->count--;
 117
 118         return  element->destroy(element);
 119 }
 120
 121 /**
 122  * @brief implements function get_first of linked_list_t
 123  */
 124 static status_t get_first(linked_list_t *linked_list, void **item)
 125 {
 126         linked_list_t *this = linked_list;
 127
 128         if (this->count == 0)
 129         {
 130                 return FAILED;
 131         }
 132
 133         if (this->first == NULL)
 134         {
 135                 return FAILED;
 136         }
 137
 138         *item = this->first->value;
 139
 140         return SUCCESS;
 141 }
 142
 143 /**
 144  * @brief implements function insert_last of linked_list_t
 145  */
 146 static status_t insert_last(linked_list_t *linked_list, void *item)
 147 {
 148         linked_list_t *this = linked_list;
 149
 150         linked_list_element_t *element = linked_list_element_create(item);
 151
 152         if (this->count == 0)
 153         {
 154                 /* first entry in list */
 155                 this->first = element;
 156                 this->last = element;
 157                 element->previous = NULL;
 158                 element->next = NULL;
 159         }else
 160         {
 161                 if ((this->first == NULL) || (this->last == NULL))
 162                 {
 163                         /* should never happen */
 164                         element->destroy(element);
 165                         return FAILED;
 166                 }
 167                 linked_list_element_t *old_last_element = this->last;
 168                 element->previous = old_last_element;
 169                 old_last_element->next = element;
 170                 this->last = element;
 171         }
 172
 173         this->count++;
 174
 175         return SUCCESS;
 176 }
 177
 178 /**
 179  * @brief implements function remove_last of linked_list_t
 180  */
 181 static status_t remove_last(linked_list_t *linked_list, void **item)
 182 {
 183         linked_list_t *this = linked_list;
 184
 185         if (this->count == 0)
 186         {
 187                 return FAILED;
 188         }
 189
 190         if (this->last == NULL)
 191         {
 192                 return FAILED;
 193         }
 194
 195         linked_list_element_t *element = this->last;
 196
 197         if (element->previous != NULL)
 198         {
 199                 element->previous->next = NULL;
 200         }
 201         this->last = element->previous;
 202
 203         *item = element->value;
 204
 205         this->count--;
 206
 207         return  element->destroy(element);
 208 }
 209
 210 /**
 211  * @brief implements function get_last of linked_list_t
 212  */
 213 static status_t get_last(linked_list_t *linked_list, void **item)
 214 {
 215         linked_list_t *this = linked_list;
 216
 217         if (this->count == 0)
 218         {
 219                 return FAILED;
 220         }
 221
 222         if (this->last == NULL)
 223         {
 224                 return FAILED;
 225         }
 226
 227         *item = this->last->value;
 228
 229         return SUCCESS;
 230 }
 231
 232 /**
 233  * @brief implements function destroy of linked_list_t
 234  */
 235 static status_t destroy_linked_list(linked_list_t *linked_list)
 236 {
 237         linked_list_t *this = linked_list;
 238
 239         /* Delete all list items before deleting list */
 240         while (this->count > 0)
 241         {
 242                 void * value;
 243                 if (this->remove_first(this,&value) != SUCCESS)
 244                 {
 245                         pfree(this);
 246                         return FAILED;
 247                 }
 248         }
 249         pfree(this);
 250         return SUCCESS;
 251 }
 252
 253
 254 linked_list_t *linked_list_create()
 255 {
 256         linked_list_t *this = alloc_thing(linked_list_t, "linked_list_t");
 257
 258         this->get_first = get_first;
 259         this->get_last = get_last;
 260         this->insert_first = insert_first;
 261         this->insert_last = insert_last;
 262         this->remove_first = remove_first;
 263         this->remove_last = remove_last;
 264         this->destroy = destroy_linked_list;
 265
 266         this->count = 0;
 267         this->first = NULL;
 268         this->last = NULL;
 269
 270         return this;
 271 }