2 dllist.c -- Doubly Linked Lists
3 Copyright (C) 2005, 2006 Sebastian Freundt
5 Author: Sebastian Freundt <hroptatyr@sxemacs.org>
7 This file is part of SXEmacs
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.
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.
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/>. */
23 /* Synched up with: Not in FSF. */
25 #ifndef INCLUDED_dllist_h_
26 #define INCLUDED_dllist_h_
28 #if defined(HAVE_THREADS)
29 #include "semaphore.h"
32 extern void dllist_reinit(void);
34 typedef struct dllist_item_s *dllist_item_t;
35 typedef struct dllist_s *dllist_t;
38 struct dllist_item_s {
45 struct lcrecord_header lheader;
47 /* the sequence category */
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 */
54 Lisp_Object plist; /* property list */
55 void *noseeum_data; /* data for noseeum dllists */
57 #if !defined(EF_USE_POM) && defined(HAVE_THREADS)
58 /* we want thread-safe dllists anyway, do we? */
63 extern Lisp_Object Qdllistp;
64 extern Lisp_Object Qdllist;
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)
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))
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)
103 #define dllist_item _el->item
104 #define RETURN_FROM_DLLIST_TRAVERSE(_dl, _retval) \
109 #define WITH_DLLIST_TRAVERSE(_dl, args...) \
111 dllist_item_t _el = NULL; \
113 _el = dllist_first(_dl); \
115 dllist_item_t _eln = _el->next; \
117 /* if the idiots nuked all my elems */ \
118 if (dllist_size(_dl) == 0) \
125 #define new_dllist_item() xnew_and_zero(struct dllist_item_s)
126 #define free_dllist_item(di) xfree(di)
128 #define WITH_DLL_LOCK(dllist, args...) \
132 DLL_UNLOCK(dllist); \
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);
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);
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);
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);
178 dllist_car(dllist_t dllist)
184 if (dllist_first(dllist))
185 result = dllist_first(dllist)->item);
191 dllist_rac(dllist_t dllist)
197 if (dllist_last(dllist))
198 result = dllist_last(dllist)->item);
204 dllist_get_size(dllist_t dllist)
208 WITH_DLL_LOCK(dllist, result = dllist_size(dllist));
213 dllist_prepend_item(dllist_t dllist, dllist_item_t item)
222 old = dllist_first(dllist);
229 /* fiddle with the tail as we are the only element */
230 dllist_last(dllist) = item;
233 dllist_first(dllist) = item;
234 dllist_size(dllist)++);
239 dllist_append_item(dllist_t dllist, dllist_item_t item)
248 old = dllist_last(dllist);
255 /* fiddle with the head as we are the only element */
256 dllist_first(dllist) = item;
259 dllist_last(dllist) = item;
260 dllist_size(dllist)++);
264 extern_inline dllist_item_t
265 dllist_transfer_car(dllist_t dllist)
272 old = dllist_first(dllist);
275 /* unlock the mutex due to non-local exit */
281 dllist_first(dllist) = new;
282 dllist_size(dllist)--;
285 dllist_last(dllist) = new;
290 /* wipe out navigation information */
291 old->next = old->prev = NULL;
296 dllist_pop_and_pro_car(Lisp_Object *result, dllist_t dllist)
303 old = dllist_first(dllist);
306 /* unlock the mutex due to non-local exit */
311 *result = (Lisp_Object)old->item;
313 dllist_first(dllist) = new;
314 dllist_size(dllist)--;
317 dllist_last(dllist) = new;
322 /* wipe out navigation information */
323 old->next = old->prev = NULL;
327 extern_inline dllist_item_t
328 dllist_transfer_rac(dllist_t dllist)
335 old = dllist_last(dllist);
338 /* unlock the mutex due to non-local exit */
344 dllist_last(dllist) = new;
345 dllist_size(dllist)--;
348 dllist_first(dllist) = new;
353 /* wipe out navigation information */
354 old->next = old->prev = NULL;
359 dllist_pop_and_pro_rac(Lisp_Object *result, dllist_t dllist)
366 old = dllist_last(dllist);
369 /* unlock the mutex due to non-local exit */
374 *result = (Lisp_Object)old->item;
376 dllist_last(dllist) = new;
377 dllist_size(dllist)--;
380 dllist_first(dllist) = new;
385 /* wipe out navigation information */
386 old->next = old->prev = NULL;
390 extern_inline dllist_item_t
391 dllist_transfer_inner(dllist_t dll, dllist_item_t dlli)
393 /* assumes lock has been set already,
394 * also see dllist_transfer_inner_with_lock */
395 if (dlli == NULL || dll == NULL)
398 if (dlli->prev != NULL && dlli->next != NULL) {
399 /* we're truly an inner node */
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 */
410 dlli->next->prev = NULL;
411 dllist_first(dll) = dlli->next;
412 } else if (dlli->next == NULL) {
413 /* we're the tail-node */
415 dlli->prev->next = NULL;
416 dllist_last(dll) = dlli->prev;
419 /* wipe out navigation info */
420 dlli->next = dlli->prev = NULL;
425 dllist_pop_inner(dllist_t dll, dllist_item_t dlli)
427 /* transfers an inner item and frees it afterwards */
428 void *result = dllist_transfer_inner(dll, dlli)->item;
429 free_dllist_item(dlli);
433 #endif /* INCLUDED_dllist_h_ */