cgit.sxemacs.org Git - sxemacs/blob - src/dllist.h

   1 /*
   2   dllist.c -- Doubly Linked Lists
   3   Copyright (C) 2005, 2006 Sebastian Freundt
   4
   5   Author:  Sebastian Freundt <hroptatyr@sxemacs.org>
   6
   7 This file is part of SXEmacs
   8
   9 SXEmacs is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 SXEmacs is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  21
  22
  23 /* Synched up with: Not in FSF. */
  24
  25 #ifndef INCLUDED_dllist_h_
  26 #define INCLUDED_dllist_h_
  27
  28 #if defined(HAVE_THREADS)
  29 #include "semaphore.h"
  30 #endif
  31
  32 extern void dllist_reinit(void);
  33
  34 typedef struct dllist_item_s *dllist_item_t;
  35 typedef struct dllist_s *dllist_t;
  36
  37 \f
  38 struct dllist_item_s {
  39         void *item;
  40         dllist_item_t next;
  41         dllist_item_t prev;
  42 };
  43
  44 struct dllist_s {
  45         struct lcrecord_header lheader;
  46
  47         /* the sequence category */
  48         void *si;
  49
  50         dllist_item_t first;    /* pointer to first item */
  51         dllist_item_t last;     /* pointer to last item */
  52         size_t size;            /* number of elements */
  53
  54         Lisp_Object plist;      /* property list */
  55         void *noseeum_data;     /* data for noseeum dllists */
  56
  57 #if !defined(EF_USE_POM) && defined(HAVE_THREADS)
  58         /* we want thread-safe dllists anyway, do we? */
  59         sxe_mutex_t mtx;
  60 #endif
  61 };
  62
  63 extern Lisp_Object Qdllistp;
  64 extern Lisp_Object Qdllist;
  65
  66 DECLARE_LRECORD(dllist, struct dllist_s);
  67 #define XDLLIST(x) XRECORD(x, dllist, struct dllist_s)
  68 #define XSETDLLIST(x, p) XSETRECORD(x, p, dllist)
  69 #define wrap_dllist(p) wrap_object(p)
  70 #define DLLISTP(x) RECORDP(x, dllist)
  71 #define CHECK_DLLIST(x) CHECK_RECORD(x, dllist)
  72 #define CONCHECK_DLLIST(x) CONCHECK_RECORD(x, dllist)
  73
  74 #define dllist_first(ms) (ms)->first
  75 #define dllist_last(ms) (ms)->last
  76 #define dllist_size(ms) (ms)->size
  77 #define dllist_plist(ms) (ms)->plist
  78 #define XDLLIST_FIRST(x) dllist_first(XDLLIST(x))
  79 #define XDLLIST_LAST(x) dllist_last(XDLLIST(x))
  80 #define XDLLIST_SIZE(x) dllist_size(XDLLIST(x))
  81 #define XDLLIST_PLIST(x) dllist_plist(XDLLIST(x))
  82
  83 #if defined(EF_USE_POM)
  84 #define dllist_mtx(dllist)              XRECORD_MTX(dllist)
  85 #define DLL_MUTEX_INIT(dllist)          SXE_MUTEX_INIT(&dllist_mtx(dllist));
  86 #define DLL_MUTEX_FINI(dllist)          SXE_MUTEX_FINI(&dllist_mtx(dllist));
  87 #define DLL_LOCK(dllist)                SXE_MUTEX_LOCK(&dllist_mtx(dllist))
  88 #define DLL_UNLOCK(dllist)              SXE_MUTEX_UNLOCK(&dllist_mtx(dllist))
  89 #elif defined(HAVE_THREADS)
  90 #define dllist_mtx(dllist)              ((dllist)->mtx)
  91 #define DLL_MUTEX_INIT(dllist)          SXE_MUTEX_INIT(&dllist_mtx(dllist));
  92 #define DLL_MUTEX_FINI(dllist)          SXE_MUTEX_FINI(&dllist_mtx(dllist));
  93 #define DLL_LOCK(dllist)                SXE_MUTEX_LOCK(&dllist_mtx(dllist))
  94 #define DLL_UNLOCK(dllist)              SXE_MUTEX_UNLOCK(&dllist_mtx(dllist))
  95 #else  /* !EF_USE_POM && !HAVE_THREADS */
  96 #define dllist_mtx(dllist)
  97 #define DLL_MUTEX_INIT(dllist)
  98 #define DLL_MUTEX_FINI(dllist)
  99 #define DLL_LOCK(dllist)
 100 #define DLL_UNLOCK(dllist)
 101 #endif
 102
 103 #define dllist_item     _el->item
 104 #define RETURN_FROM_DLLIST_TRAVERSE(_dl, _retval)       \
 105         {                                               \
 106                 DLL_UNLOCK(_dl);                        \
 107                 return _retval;                         \
 108         }
 109 #define WITH_DLLIST_TRAVERSE(_dl, args...)                      \
 110         do {                                                    \
 111                 dllist_item_t _el = NULL;                       \
 112                 DLL_LOCK(_dl);                                  \
 113                 _el = dllist_first(_dl);                        \
 114                 while (_el) {                                   \
 115                         dllist_item_t _eln = _el->next;         \
 116                         args;                                   \
 117                         /* if the idiots nuked all my elems */  \
 118                         if (dllist_size(_dl) == 0)              \
 119                                 break;                          \
 120                         _el = _eln;                             \
 121                 }                                               \
 122                 DLL_UNLOCK(_dl);                                \
 123         } while (0)
 124
 125 #define new_dllist_item()       xnew_and_zero(struct dllist_item_s)
 126 #define free_dllist_item(di)    xfree(di)
 127
 128 #define WITH_DLL_LOCK(dllist, args...)          \
 129         do {                                    \
 130                 DLL_LOCK(dllist);               \
 131                 args;                           \
 132                 DLL_UNLOCK(dllist);             \
 133         } while (0)
 134
 135 \f
 136 extern dllist_t make_dllist(void);
 137 extern dllist_t make_noseeum_dllist(void);
 138 extern void free_noseeum_dllist(dllist_t);
 139 extern void dllist_prepend(dllist_t, void*);
 140 extern void dllist_append(dllist_t, void*);
 141 extern void *dllist_pop_car(dllist_t);
 142 extern void *dllist_pop_rac(dllist_t);
 143 extern dllist_t copy_dllist(dllist_t);
 144 extern void dllist_map_inplace(Lisp_Object, Lisp_Object);
 145 extern void dllist_map_inplace_C(void*(*)(void*), dllist_t);
 146 extern void dllist_map_C(void(*)(void*), dllist_t);
 147 extern void *dllist_rrotate(dllist_t);
 148 extern void *dllist_lrotate(dllist_t);
 149
 150 /* for special purposes */
 151 extern_inline void dllist_pop_and_pro_car(Lisp_Object*, dllist_t);
 152 extern_inline void dllist_pop_and_pro_rac(Lisp_Object*, dllist_t);
 153
 154 EXFUN(Fdllist, MANY);
 155 EXFUN(Fdllist_to_list, 1);
 156 EXFUN(Fdllist_to_list_reversed, 1);
 157 EXFUN(Fcopy_dllist, 1);
 158 EXFUN(Fdllist_car, 1);
 159 EXFUN(Fdllist_rac, 1);
 160 EXFUN(Fdllist_prepend, 2);
 161 EXFUN(Fdllist_append, 2);
 162 EXFUN(Fdllist_pop_car, 1);
 163 EXFUN(Fdllist_pop_rac, 1);
 164
 165 /* inlines */
 166 extern_inline void *dllist_car(dllist_t);
 167 extern_inline void *dllist_rac(dllist_t);
 168 extern_inline size_t dllist_get_size(dllist_t);
 169 extern_inline void dllist_prepend_item(dllist_t, dllist_item_t);
 170 extern_inline void dllist_append_item(dllist_t, dllist_item_t);
 171 extern_inline dllist_item_t dllist_transfer_car(dllist_t);
 172 extern_inline dllist_item_t dllist_transfer_rac(dllist_t);
 173 extern_inline dllist_item_t dllist_transfer_inner(dllist_t, dllist_item_t);
 174 extern_inline void *dllist_pop_inner(dllist_t, dllist_item_t);
 175
 176 \f
 177 extern_inline void *
 178 dllist_car(dllist_t dllist)
 179 {
 180         void *result = NULL;
 181
 182         WITH_DLL_LOCK(
 183                 dllist,
 184                 if (dllist_first(dllist))
 185                         result = dllist_first(dllist)->item);
 186
 187         return result;
 188 }
 189
 190 extern_inline void *
 191 dllist_rac(dllist_t dllist)
 192 {
 193         void *result = NULL;
 194
 195         WITH_DLL_LOCK(
 196                 dllist,
 197                 if (dllist_last(dllist))
 198                         result = dllist_last(dllist)->item);
 199
 200         return result;
 201 }
 202
 203 extern_inline size_t
 204 dllist_get_size(dllist_t dllist)
 205 {
 206         size_t result = 0;
 207
 208         WITH_DLL_LOCK(dllist, result = dllist_size(dllist));
 209         return result;
 210 }
 211
 212 extern_inline void
 213 dllist_prepend_item(dllist_t dllist, dllist_item_t item)
 214 {
 215         dllist_item_t old;
 216
 217         if (item == NULL)
 218                 return;
 219
 220         WITH_DLL_LOCK(
 221                 dllist,
 222                 old = dllist_first(dllist);
 223                 item->prev = NULL;
 224                 item->next = old;
 225
 226                 if (old) {
 227                         old->prev = item;
 228                 } else {
 229                         /* fiddle with the tail as we are the only element */
 230                         dllist_last(dllist) = item;
 231                 }
 232
 233                 dllist_first(dllist) = item;
 234                 dllist_size(dllist)++);
 235         return;
 236 }
 237
 238 extern_inline void
 239 dllist_append_item(dllist_t dllist, dllist_item_t item)
 240 {
 241         dllist_item_t old;
 242
 243         if (item == NULL)
 244                 return;
 245
 246         WITH_DLL_LOCK(
 247                 dllist,
 248                 old = dllist_last(dllist);
 249                 item->prev = old;
 250                 item->next = NULL;
 251
 252                 if (old) {
 253                         old->next = item;
 254                 } else {
 255                         /* fiddle with the head as we are the only element */
 256                         dllist_first(dllist) = item;
 257                 }
 258
 259                 dllist_last(dllist) = item;
 260                 dllist_size(dllist)++);
 261         return;
 262 }
 263
 264 extern_inline dllist_item_t
 265 dllist_transfer_car(dllist_t dllist)
 266 {
 267         dllist_item_t new;
 268         dllist_item_t old;
 269
 270         WITH_DLL_LOCK(
 271                 dllist,
 272                 old = dllist_first(dllist);
 273
 274                 if (old == NULL) {
 275                         /* unlock the mutex due to non-local exit */
 276                         DLL_UNLOCK(dllist);
 277                         return NULL;
 278                 }
 279
 280                 new = old->next;
 281                 dllist_first(dllist) = new;
 282                 dllist_size(dllist)--;
 283
 284                 if (new == NULL) {
 285                         dllist_last(dllist) = new;
 286                 } else
 287                         new->prev = NULL;
 288                 );
 289
 290         /* wipe out navigation information */
 291         old->next = old->prev = NULL;
 292         return old;
 293 }
 294
 295 extern_inline void
 296 dllist_pop_and_pro_car(Lisp_Object *result, dllist_t dllist)
 297 {
 298         dllist_item_t new;
 299         dllist_item_t old;
 300
 301         WITH_DLL_LOCK(
 302                 dllist,
 303                 old = dllist_first(dllist);
 304
 305                 if (old == NULL) {
 306                         /* unlock the mutex due to non-local exit */
 307                         DLL_UNLOCK(dllist);
 308                         return;
 309                 }
 310
 311                 *result = (Lisp_Object)old->item;
 312                 new = old->next;
 313                 dllist_first(dllist) = new;
 314                 dllist_size(dllist)--;
 315
 316                 if (new == NULL) {
 317                         dllist_last(dllist) = new;
 318                 } else
 319                         new->prev = NULL;
 320                 );
 321
 322         /* wipe out navigation information */
 323         old->next = old->prev = NULL;
 324         return;
 325 }
 326
 327 extern_inline dllist_item_t
 328 dllist_transfer_rac(dllist_t dllist)
 329 {
 330         dllist_item_t new;
 331         dllist_item_t old;
 332
 333         WITH_DLL_LOCK(
 334                 dllist,
 335                 old = dllist_last(dllist);
 336
 337                 if (old == NULL) {
 338                         /* unlock the mutex due to non-local exit */
 339                         DLL_UNLOCK(dllist);
 340                         return NULL;
 341                 }
 342
 343                 new = old->prev;
 344                 dllist_last(dllist) = new;
 345                 dllist_size(dllist)--;
 346
 347                 if (new == NULL) {
 348                         dllist_first(dllist) = new;
 349                 } else
 350                         new->next = NULL;
 351                 );
 352
 353         /* wipe out navigation information */
 354         old->next = old->prev = NULL;
 355         return old;
 356 }
 357
 358 extern_inline void
 359 dllist_pop_and_pro_rac(Lisp_Object *result, dllist_t dllist)
 360 {
 361         dllist_item_t new;
 362         dllist_item_t old;
 363
 364         WITH_DLL_LOCK(
 365                 dllist,
 366                 old = dllist_last(dllist);
 367
 368                 if (old == NULL) {
 369                         /* unlock the mutex due to non-local exit */
 370                         DLL_UNLOCK(dllist);
 371                         return;
 372                 }
 373
 374                 *result = (Lisp_Object)old->item;
 375                 new = old->prev;
 376                 dllist_last(dllist) = new;
 377                 dllist_size(dllist)--;
 378
 379                 if (new == NULL) {
 380                         dllist_first(dllist) = new;
 381                 } else
 382                         new->next = NULL;
 383                 );
 384
 385         /* wipe out navigation information */
 386         old->next = old->prev = NULL;
 387         return;
 388 }
 389
 390 extern_inline dllist_item_t
 391 dllist_transfer_inner(dllist_t dll, dllist_item_t dlli)
 392 {
 393         /* assumes lock has been set already,
 394          * also see dllist_transfer_inner_with_lock */
 395         if (dlli == NULL || dll == NULL)
 396                 return NULL;
 397
 398         if (dlli->prev != NULL && dlli->next != NULL) {
 399                 /* we're truly an inner node */
 400                 dllist_size(dll)--;
 401                 dlli->prev->next = dlli->next;
 402                 dlli->next->prev = dlli->prev;
 403         } else if (dlli->prev == NULL && dlli->next == NULL) {
 404                 /* we're the only node */
 405                 dllist_size(dll) = 0;
 406                 dllist_first(dll) = dllist_last(dll) = NULL;
 407         } else if (dlli->prev == NULL) {
 408                 /* we're the head-node */
 409                 dllist_size(dll)--;
 410                 dlli->next->prev = NULL;
 411                 dllist_first(dll) = dlli->next;
 412         } else if (dlli->next == NULL) {
 413                 /* we're the tail-node */
 414                 dllist_size(dll)--;
 415                 dlli->prev->next = NULL;
 416                 dllist_last(dll) = dlli->prev;
 417         }
 418
 419         /* wipe out navigation info */
 420         dlli->next = dlli->prev = NULL;
 421         return dlli;
 422 }
 423
 424 extern_inline void*
 425 dllist_pop_inner(dllist_t dll, dllist_item_t dlli)
 426 {
 427         /* transfers an inner item and frees it afterwards */
 428         void *result = dllist_transfer_inner(dll, dlli)->item;
 429         free_dllist_item(dlli);
 430         return result;
 431 }
 432
 433 #endif  /* INCLUDED_dllist_h_ */