lib/llist.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2010, Daniel Stenberg, <daniel@haxx.se>, et al.
   9  *
  10  * This software is licensed as described in the file COPYING, which
  11  * you should have received as part of this distribution. The terms
  12  * are also available at http://curl.haxx.se/docs/copyright.html.
  13  *
  14  * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  15  * copies of the Software, and permit persons to whom the Software is
  16  * furnished to do so, under the terms of the COPYING file.
  17  *
  18  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19  * KIND, either express or implied.
  20  *
  21  ***************************************************************************/
  22
  23 #include "setup.h"
  24
  25 #include <string.h>
  26 #include <stdlib.h>
  27
  28 #include "llist.h"
  29 #include "curl_memory.h"
  30
  31 /* this must be the last include file */
  32 #include "memdebug.h"
  33
  34 static void
  35 llist_init(struct curl_llist *l, curl_llist_dtor dtor)
  36 {
  37   l->size = 0;
  38   l->dtor = dtor;
  39   l->head = NULL;
  40   l->tail = NULL;
  41 }
  42
  43 struct curl_llist *
  44 Curl_llist_alloc(curl_llist_dtor dtor)
  45 {
  46   struct curl_llist *list;
  47
  48   list = malloc(sizeof(struct curl_llist));
  49   if(NULL == list)
  50     return NULL;
  51
  52   llist_init(list, dtor);
  53
  54   return list;
  55 }
  56
  57 /*
  58  * Curl_llist_insert_next()
  59  *
  60  * Inserts a new list element after the given one 'e'. If the given existing
  61  * entry is NULL and the list already has elements, the new one will be
  62  * inserted first in the list.
  63  *
  64  * Returns: 1 on success and 0 on failure.
  65  */
  66 int
  67 Curl_llist_insert_next(struct curl_llist *list, struct curl_llist_element *e,
  68                        const void *p)
  69 {
  70   struct curl_llist_element *ne = malloc(sizeof(struct curl_llist_element));
  71   if(!ne)
  72     return 0;
  73
  74   ne->ptr = (void *) p;
  75   if(list->size == 0) {
  76     list->head = ne;
  77     list->head->prev = NULL;
  78     list->head->next = NULL;
  79     list->tail = ne;
  80   }
  81   else {
  82     /* if 'e' is NULL here, we insert the new element first in the list */
  83     ne->next = e?e->next:list->head;
  84     ne->prev = e;
  85     if(!e) {
  86       list->head->prev = ne;
  87       list->head = ne;
  88     }
  89     else if(e->next) {
  90       e->next->prev = ne;
  91     }
  92     else {
  93       list->tail = ne;
  94     }
  95     if(e)
  96       e->next = ne;
  97   }
  98
  99   ++list->size;
 100
 101   return 1;
 102 }
 103
 104 int
 105 Curl_llist_remove(struct curl_llist *list, struct curl_llist_element *e,
 106                   void *user)
 107 {
 108   if(e == NULL || list->size == 0)
 109     return 1;
 110
 111   if(e == list->head) {
 112     list->head = e->next;
 113
 114     if(list->head == NULL)
 115       list->tail = NULL;
 116     else
 117       e->next->prev = NULL;
 118   } else {
 119     e->prev->next = e->next;
 120     if(!e->next)
 121       list->tail = e->prev;
 122     else
 123       e->next->prev = e->prev;
 124   }
 125
 126   list->dtor(user, e->ptr);
 127
 128   free(e);
 129   --list->size;
 130
 131   return 1;
 132 }
 133
 134 void
 135 Curl_llist_destroy(struct curl_llist *list, void *user)
 136 {
 137   if(list) {
 138     while(list->size > 0)
 139       Curl_llist_remove(list, list->tail, user);
 140
 141     free(list);
 142   }
 143 }
 144
 145 size_t
 146 Curl_llist_count(struct curl_llist *list)
 147 {
 148   return list->size;
 149 }
 150
 151 int Curl_llist_move(struct curl_llist *list, struct curl_llist_element *e,
 152                     struct curl_llist *to_list, struct curl_llist_element *to_e)
 153 {
 154   /* Remove element from list */
 155   if(e == NULL || list->size == 0)
 156     return 0;
 157
 158   if(e == list->head) {
 159     list->head = e->next;
 160
 161     if(list->head == NULL)
 162       list->tail = NULL;
 163     else
 164       e->next->prev = NULL;
 165   }
 166   else {
 167     e->prev->next = e->next;
 168     if(!e->next)
 169       list->tail = e->prev;
 170     else
 171       e->next->prev = e->prev;
 172   }
 173
 174   --list->size;
 175
 176   /* Add element to to_list after to_e */
 177   if(to_list->size == 0) {
 178     to_list->head = e;
 179     to_list->head->prev = NULL;
 180     to_list->head->next = NULL;
 181     to_list->tail = e;
 182   }
 183   else {
 184     e->next = to_e->next;
 185     e->prev = to_e;
 186     if(to_e->next) {
 187       to_e->next->prev = e;
 188     }
 189     else {
 190       to_list->tail = e;
 191     }
 192     to_e->next = e;
 193   }
 194
 195   ++to_list->size;
 196
 197   return 1;
 198 }