lib/llist.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2016, 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 https://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 "curl_setup.h"
  24
  25 #include <curl/curl.h>
  26
  27 #include "llist.h"
  28 #include "curl_memory.h"
  29
  30 /* this must be the last include file */
  31 #include "memdebug.h"
  32
  33 /*
  34  * @unittest: 1300
  35  */
  36 static void
  37 llist_init(struct curl_llist *l, curl_llist_dtor dtor)
  38 {
  39   l->size = 0;
  40   l->dtor = dtor;
  41   l->head = NULL;
  42   l->tail = NULL;
  43 }
  44
  45 struct curl_llist *
  46 Curl_llist_alloc(curl_llist_dtor dtor)
  47 {
  48   struct curl_llist *list;
  49
  50   list = malloc(sizeof(struct curl_llist));
  51   if(!list)
  52     return NULL;
  53
  54   llist_init(list, dtor);
  55
  56   return list;
  57 }
  58
  59 /*
  60  * Curl_llist_insert_next()
  61  *
  62  * Inserts a new list element after the given one 'e'. If the given existing
  63  * entry is NULL and the list already has elements, the new one will be
  64  * inserted first in the list.
  65  *
  66  * Returns: 1 on success and 0 on failure.
  67  *
  68  * @unittest: 1300
  69  */
  70 int
  71 Curl_llist_insert_next(struct curl_llist *list, struct curl_llist_element *e,
  72                        const void *p)
  73 {
  74   struct curl_llist_element *ne = malloc(sizeof(struct curl_llist_element));
  75   if(!ne)
  76     return 0;
  77
  78   ne->ptr = (void *) p;
  79   if(list->size == 0) {
  80     list->head = ne;
  81     list->head->prev = NULL;
  82     list->head->next = NULL;
  83     list->tail = ne;
  84   }
  85   else {
  86     /* if 'e' is NULL here, we insert the new element first in the list */
  87     ne->next = e?e->next:list->head;
  88     ne->prev = e;
  89     if(!e) {
  90       list->head->prev = ne;
  91       list->head = ne;
  92     }
  93     else if(e->next) {
  94       e->next->prev = ne;
  95     }
  96     else {
  97       list->tail = ne;
  98     }
  99     if(e)
 100       e->next = ne;
 101   }
 102
 103   ++list->size;
 104
 105   return 1;
 106 }
 107
 108 /*
 109  * @unittest: 1300
 110  */
 111 int
 112 Curl_llist_remove(struct curl_llist *list, struct curl_llist_element *e,
 113                   void *user)
 114 {
 115   if(e == NULL || list->size == 0)
 116     return 1;
 117
 118   if(e == list->head) {
 119     list->head = e->next;
 120
 121     if(list->head == NULL)
 122       list->tail = NULL;
 123     else
 124       e->next->prev = NULL;
 125   }
 126   else {
 127     e->prev->next = e->next;
 128     if(!e->next)
 129       list->tail = e->prev;
 130     else
 131       e->next->prev = e->prev;
 132   }
 133
 134   list->dtor(user, e->ptr);
 135
 136   e->ptr  = NULL;
 137   e->prev = NULL;
 138   e->next = NULL;
 139
 140   free(e);
 141   --list->size;
 142
 143   return 1;
 144 }
 145
 146 void
 147 Curl_llist_destroy(struct curl_llist *list, void *user)
 148 {
 149   if(list) {
 150     while(list->size > 0)
 151       Curl_llist_remove(list, list->tail, user);
 152
 153     free(list);
 154   }
 155 }
 156
 157 size_t
 158 Curl_llist_count(struct curl_llist *list)
 159 {
 160   return list->size;
 161 }
 162
 163 /*
 164  * @unittest: 1300
 165  */
 166 int Curl_llist_move(struct curl_llist *list, struct curl_llist_element *e,
 167                     struct curl_llist *to_list,
 168                     struct curl_llist_element *to_e)
 169 {
 170   /* Remove element from list */
 171   if(e == NULL || list->size == 0)
 172     return 0;
 173
 174   if(e == list->head) {
 175     list->head = e->next;
 176
 177     if(list->head == NULL)
 178       list->tail = NULL;
 179     else
 180       e->next->prev = NULL;
 181   }
 182   else {
 183     e->prev->next = e->next;
 184     if(!e->next)
 185       list->tail = e->prev;
 186     else
 187       e->next->prev = e->prev;
 188   }
 189
 190   --list->size;
 191
 192   /* Add element to to_list after to_e */
 193   if(to_list->size == 0) {
 194     to_list->head = e;
 195     to_list->head->prev = NULL;
 196     to_list->head->next = NULL;
 197     to_list->tail = e;
 198   }
 199   else {
 200     e->next = to_e->next;
 201     e->prev = to_e;
 202     if(to_e->next) {
 203       to_e->next->prev = e;
 204     }
 205     else {
 206       to_list->tail = e;
 207     }
 208     to_e->next = e;
 209   }
 210
 211   ++to_list->size;
 212
 213   return 1;
 214 }