lib/llist.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2017, 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 void
  37 Curl_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 /*
  46  * Curl_llist_insert_next()
  47  *
  48  * Inserts a new list element after the given one 'e'. If the given existing
  49  * entry is NULL and the list already has elements, the new one will be
  50  * inserted first in the list.
  51  *
  52  * The 'ne' argument should be a pointer into the object to store.
  53  *
  54  * @unittest: 1300
  55  */
  56 void
  57 Curl_llist_insert_next(struct curl_llist *list, struct curl_llist_element *e,
  58                        const void *p,
  59                        struct curl_llist_element *ne)
  60 {
  61   ne->ptr = (void *) p;
  62   if(list->size == 0) {
  63     list->head = ne;
  64     list->head->prev = NULL;
  65     list->head->next = NULL;
  66     list->tail = ne;
  67   }
  68   else {
  69     /* if 'e' is NULL here, we insert the new element first in the list */
  70     ne->next = e?e->next:list->head;
  71     ne->prev = e;
  72     if(!e) {
  73       list->head->prev = ne;
  74       list->head = ne;
  75     }
  76     else if(e->next) {
  77       e->next->prev = ne;
  78     }
  79     else {
  80       list->tail = ne;
  81     }
  82     if(e)
  83       e->next = ne;
  84   }
  85
  86   ++list->size;
  87 }
  88
  89 /*
  90  * @unittest: 1300
  91  */
  92 void
  93 Curl_llist_remove(struct curl_llist *list, struct curl_llist_element *e,
  94                   void *user)
  95 {
  96   void *ptr;
  97   if(e == NULL || list->size == 0)
  98     return;
  99
 100   if(e == list->head) {
 101     list->head = e->next;
 102
 103     if(list->head == NULL)
 104       list->tail = NULL;
 105     else
 106       e->next->prev = NULL;
 107   }
 108   else {
 109     if(!e->prev)
 110       list->head = e->next;
 111     else
 112       e->prev->next = e->next;
 113
 114     if(!e->next)
 115       list->tail = e->prev;
 116     else
 117       e->next->prev = e->prev;
 118   }
 119
 120   ptr = e->ptr;
 121
 122   e->ptr  = NULL;
 123   e->prev = NULL;
 124   e->next = NULL;
 125
 126   --list->size;
 127
 128   /* call the dtor() last for when it actually frees the 'e' memory itself */
 129   if(list->dtor)
 130     list->dtor(user, ptr);
 131 }
 132
 133 void
 134 Curl_llist_destroy(struct curl_llist *list, void *user)
 135 {
 136   if(list) {
 137     while(list->size > 0)
 138       Curl_llist_remove(list, list->tail, user);
 139   }
 140 }
 141
 142 size_t
 143 Curl_llist_count(struct curl_llist *list)
 144 {
 145   return list->size;
 146 }
 147
 148 /*
 149  * @unittest: 1300
 150  */
 151 void Curl_llist_move(struct curl_llist *list, struct curl_llist_element *e,
 152                      struct curl_llist *to_list,
 153                      struct curl_llist_element *to_e)
 154 {
 155   /* Remove element from list */
 156   if(e == NULL || list->size == 0)
 157     return;
 158
 159   if(e == list->head) {
 160     list->head = e->next;
 161
 162     if(list->head == NULL)
 163       list->tail = NULL;
 164     else
 165       e->next->prev = NULL;
 166   }
 167   else {
 168     e->prev->next = e->next;
 169     if(!e->next)
 170       list->tail = e->prev;
 171     else
 172       e->next->prev = e->prev;
 173   }
 174
 175   --list->size;
 176
 177   /* Add element to to_list after to_e */
 178   if(to_list->size == 0) {
 179     to_list->head = e;
 180     to_list->head->prev = NULL;
 181     to_list->head->next = NULL;
 182     to_list->tail = e;
 183   }
 184   else {
 185     e->next = to_e->next;
 186     e->prev = to_e;
 187     if(to_e->next) {
 188       to_e->next->prev = e;
 189     }
 190     else {
 191       to_list->tail = e;
 192     }
 193     to_e->next = e;
 194   }
 195
 196   ++to_list->size;
 197 }