lib/core/lws_dll2.c

   1 /*
   2  * libwebsockets - small server side websockets and web server implementation
   3  *
   4  * Copyright (C) 2010-2019 Andy Green <andy@warmcat.com>
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation:
   9  *  version 2.1 of the License.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  19  *  MA  02110-1301  USA
  20  */
  21
  22 #include "private-lib-core.h"
  23
  24 #ifdef LWS_HAVE_SYS_TYPES_H
  25 #include <sys/types.h>
  26 #endif
  27
  28 int
  29 lws_dll2_foreach_safe(struct lws_dll2_owner *owner, void *user,
  30                       int (*cb)(struct lws_dll2 *d, void *user))
  31 {
  32         lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp, owner->head) {
  33                 if (cb(p, user))
  34                         return 1;
  35         } lws_end_foreach_dll_safe(p, tp);
  36
  37         return 0;
  38 }
  39
  40 void
  41 lws_dll2_add_head(struct lws_dll2 *d, struct lws_dll2_owner *owner)
  42 {
  43         if (!lws_dll2_is_detached(d)) {
  44                 assert(0); /* only wholly detached things can be added */
  45                 return;
  46         }
  47
  48         /* our next guy is current first guy, if any */
  49         if (owner->head != d)
  50                 d->next = owner->head;
  51
  52         /* if there is a next guy, set his prev ptr to our next ptr */
  53         if (d->next)
  54                 d->next->prev = d;
  55         /* there is nobody previous to us, we are the head */
  56         d->prev = NULL;
  57
  58         /* set the first guy to be us */
  59         owner->head = d;
  60
  61         if (!owner->tail)
  62                 owner->tail = d;
  63
  64         d->owner = owner;
  65         owner->count++;
  66 }
  67
  68 /*
  69  * add us to the list that 'after' is in, just before him
  70  */
  71
  72 void
  73 lws_dll2_add_before(struct lws_dll2 *d, struct lws_dll2 *after)
  74 {
  75         lws_dll2_owner_t *owner = after->owner;
  76
  77         if (!lws_dll2_is_detached(d)) {
  78                 assert(0); /* only wholly detached things can be added */
  79                 return;
  80         }
  81
  82         if (lws_dll2_is_detached(after)) {
  83                 assert(0); /* can't add after something detached */
  84                 return;
  85         }
  86
  87         d->owner = owner;
  88
  89         /* we need to point forward to after */
  90
  91         d->next = after;
  92
  93         /* we need to point back to after->prev */
  94
  95         d->prev = after->prev;
  96
  97         /* guy that used to point to after, needs to point to us */
  98
  99         if (after->prev)
 100                 after->prev->next = d;
 101         else
 102                 owner->head = d;
 103
 104         /* then after needs to point back to us */
 105
 106         after->prev = d;
 107
 108         owner->count++;
 109 }
 110
 111 void
 112 lws_dll2_add_tail(struct lws_dll2 *d, struct lws_dll2_owner *owner)
 113 {
 114         if (!lws_dll2_is_detached(d)) {
 115                 assert(0); /* only wholly detached things can be added */
 116                 return;
 117         }
 118
 119         /* our previous guy is current last guy */
 120         d->prev = owner->tail;
 121         /* if there is a prev guy, set his next ptr to our prev ptr */
 122         if (d->prev)
 123                 d->prev->next = d;
 124         /* our next ptr is NULL */
 125         d->next = NULL;
 126         /* set the last guy to be us */
 127         owner->tail = d;
 128
 129         /* list head is also us if we're the first */
 130         if (!owner->head)
 131                 owner->head = d;
 132
 133         d->owner = owner;
 134         owner->count++;
 135 }
 136
 137 void
 138 lws_dll2_remove(struct lws_dll2 *d)
 139 {
 140         if (lws_dll2_is_detached(d))
 141                 return;
 142
 143         /* if we have a next guy, set his prev to our prev */
 144         if (d->next)
 145                 d->next->prev = d->prev;
 146
 147         /* if we have a previous guy, set his next to our next */
 148         if (d->prev)
 149                 d->prev->next = d->next;
 150
 151         /* if we have phead, track the tail and head if it points to us... */
 152
 153         if (d->owner->tail == d)
 154                 d->owner->tail = d->prev;
 155
 156         if (d->owner->head == d)
 157                 d->owner->head = d->next;
 158
 159         d->owner->count--;
 160
 161         /* we're out of the list, we should not point anywhere any more */
 162         d->owner = NULL;
 163         d->prev = NULL;
 164         d->next = NULL;
 165 }
 166
 167 void
 168 lws_dll2_clear(struct lws_dll2 *d)
 169 {
 170         d->owner = NULL;
 171         d->prev = NULL;
 172         d->next = NULL;
 173 }
 174
 175 void
 176 lws_dll2_owner_clear(struct lws_dll2_owner *d)
 177 {
 178         d->head = NULL;
 179         d->tail = NULL;
 180         d->count = 0;
 181 }
 182
 183 void
 184 lws_dll2_add_sorted(lws_dll2_t *d, lws_dll2_owner_t *own,
 185                     int (*compare)(const lws_dll2_t *d, const lws_dll2_t *i))
 186 {
 187         lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp,
 188                                    lws_dll2_get_head(own)) {
 189                 assert(p != d);
 190
 191                 if (compare(p, d) >= 0) {
 192                         /* drop us in before this guy */
 193                         lws_dll2_add_before(d, p);
 194
 195                         // lws_dll2_describe(own, "post-insert");
 196
 197                         return;
 198                 }
 199         } lws_end_foreach_dll_safe(p, tp);
 200
 201         /*
 202          * Either nobody on the list yet to compare him to, or he's the
 203          * furthest away timeout... stick him at the tail end
 204          */
 205
 206         lws_dll2_add_tail(d, own);
 207 }
 208
 209 #if defined(_DEBUG)
 210
 211 void
 212 lws_dll2_describe(lws_dll2_owner_t *owner, const char *desc)
 213 {
 214         int n = 1;
 215
 216         lwsl_info("%s: %s: owner %p: count %d, head %p, tail %p\n",
 217                     __func__, desc, owner, owner->count, owner->head, owner->tail);
 218
 219         lws_start_foreach_dll_safe(struct lws_dll2 *, p, tp,
 220                                    lws_dll2_get_head(owner)) {
 221                 lwsl_info("%s:    %d: %p: owner %p, prev %p, next %p\n",
 222                             __func__, n++, p, p->owner, p->prev, p->next);
 223         } lws_end_foreach_dll_safe(p, tp);
 224 }
 225
 226 #endif