Line data Source code
1 : /* cairo - a vector graphics library with display and print output
2 : *
3 : * Copyright © 2009 Chris Wilson
4 : *
5 : * This library is free software; you can redistribute it and/or
6 : * modify it either under the terms of the GNU Lesser General Public
7 : * License version 2.1 as published by the Free Software Foundation
8 : * (the "LGPL") or, at your option, under the terms of the Mozilla
9 : * Public License Version 1.1 (the "MPL"). If you do not alter this
10 : * notice, a recipient may use your version of this file under either
11 : * the MPL or the LGPL.
12 : *
13 : * You should have received a copy of the LGPL along with this library
14 : * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15 : * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16 : * You should have received a copy of the MPL along with this library
17 : * in the file COPYING-MPL-1.1
18 : *
19 : * The contents of this file are subject to the Mozilla Public License
20 : * Version 1.1 (the "License"); you may not use this file except in
21 : * compliance with the License. You may obtain a copy of the License at
22 : * http://www.mozilla.org/MPL/
23 : *
24 : * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25 : * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26 : * the specific language governing rights and limitations.
27 : *
28 : * The Original Code is the cairo graphics library.
29 : *
30 : * The Initial Developer of the Original Code is Chris Wilson.
31 : *
32 : * Contributor(s):
33 : * Chris Wilson <chris@chris-wilson.co.uk>
34 : *
35 : */
36 :
37 : #ifndef CAIRO_LIST_PRIVATE_H
38 : #define CAIRO_LIST_PRIVATE_H
39 :
40 : #include "cairo-compiler-private.h"
41 :
42 : /* Basic circular, doubly linked list implementation */
43 :
44 : typedef struct _cairo_list {
45 : struct _cairo_list *next, *prev;
46 : } cairo_list_t;
47 :
48 : #define cairo_list_entry(ptr, type, member) \
49 : cairo_container_of(ptr, type, member)
50 :
51 : #define cairo_list_first_entry(ptr, type, member) \
52 : cairo_list_entry((ptr)->next, type, member)
53 :
54 : #define cairo_list_last_entry(ptr, type, member) \
55 : cairo_list_entry((ptr)->prev, type, member)
56 :
57 : #define cairo_list_foreach(pos, head) \
58 : for (pos = (head)->next; pos != (head); pos = pos->next)
59 :
60 : #define cairo_list_foreach_entry(pos, type, head, member) \
61 : for (pos = cairo_list_entry((head)->next, type, member);\
62 : &pos->member != (head); \
63 : pos = cairo_list_entry(pos->member.next, type, member))
64 :
65 : #define cairo_list_foreach_entry_safe(pos, n, type, head, member) \
66 : for (pos = cairo_list_entry ((head)->next, type, member),\
67 : n = cairo_list_entry (pos->member.next, type, member);\
68 : &pos->member != (head); \
69 : pos = n, n = cairo_list_entry (n->member.next, type, member))
70 :
71 : #define cairo_list_foreach_entry_reverse(pos, type, head, member) \
72 : for (pos = cairo_list_entry((head)->prev, type, member);\
73 : &pos->member != (head); \
74 : pos = cairo_list_entry(pos->member.prev, type, member))
75 :
76 : #define cairo_list_foreach_entry_reverse_safe(pos, n, type, head, member) \
77 : for (pos = cairo_list_entry((head)->prev, type, member),\
78 : n = cairo_list_entry (pos->member.prev, type, member);\
79 : &pos->member != (head); \
80 : pos = n, n = cairo_list_entry (n->member.prev, type, member))
81 :
82 : #ifdef CAIRO_LIST_DEBUG
83 : static inline void
84 : _cairo_list_validate (const cairo_list_t *link)
85 : {
86 : assert (link->next->prev == link);
87 : assert (link->prev->next == link);
88 : }
89 : static inline void
90 : cairo_list_validate (const cairo_list_t *head)
91 : {
92 : cairo_list_t *link;
93 :
94 : cairo_list_foreach (link, head)
95 : _cairo_list_validate (link);
96 : }
97 : static inline cairo_bool_t
98 : cairo_list_is_empty (const cairo_list_t *head);
99 : static inline void
100 : cairo_list_validate_is_empty (const cairo_list_t *head)
101 : {
102 : assert (head->next == NULL || (cairo_list_is_empty (head) && head->next == head->prev));
103 : }
104 : #else
105 : #define _cairo_list_validate(link)
106 : #define cairo_list_validate(head)
107 : #define cairo_list_validate_is_empty(head)
108 : #endif
109 :
110 : static inline void
111 30 : cairo_list_init (cairo_list_t *entry)
112 : {
113 30 : entry->next = entry;
114 30 : entry->prev = entry;
115 30 : }
116 :
117 : static inline void
118 9 : __cairo_list_add (cairo_list_t *entry,
119 : cairo_list_t *prev,
120 : cairo_list_t *next)
121 : {
122 9 : next->prev = entry;
123 9 : entry->next = next;
124 9 : entry->prev = prev;
125 9 : prev->next = entry;
126 9 : }
127 :
128 : static inline void
129 2 : cairo_list_add (cairo_list_t *entry, cairo_list_t *head)
130 : {
131 : cairo_list_validate (head);
132 : cairo_list_validate_is_empty (entry);
133 2 : __cairo_list_add (entry, head, head->next);
134 : cairo_list_validate (head);
135 2 : }
136 :
137 : static inline void
138 7 : cairo_list_add_tail (cairo_list_t *entry, cairo_list_t *head)
139 : {
140 : cairo_list_validate (head);
141 : cairo_list_validate_is_empty (entry);
142 7 : __cairo_list_add (entry, head->prev, head);
143 : cairo_list_validate (head);
144 7 : }
145 :
146 : static inline void
147 0 : __cairo_list_del (cairo_list_t *prev, cairo_list_t *next)
148 : {
149 0 : next->prev = prev;
150 0 : prev->next = next;
151 0 : }
152 :
153 : static inline void
154 0 : cairo_list_del (cairo_list_t *entry)
155 : {
156 0 : __cairo_list_del (entry->prev, entry->next);
157 0 : cairo_list_init (entry);
158 0 : }
159 :
160 : static inline void
161 0 : cairo_list_move (cairo_list_t *entry, cairo_list_t *head)
162 : {
163 : cairo_list_validate (head);
164 0 : __cairo_list_del (entry->prev, entry->next);
165 0 : __cairo_list_add (entry, head, head->next);
166 : cairo_list_validate (head);
167 0 : }
168 :
169 : static inline void
170 : cairo_list_move_tail (cairo_list_t *entry, cairo_list_t *head)
171 : {
172 : cairo_list_validate (head);
173 : __cairo_list_del (entry->prev, entry->next);
174 : __cairo_list_add (entry, head->prev, head);
175 : cairo_list_validate (head);
176 : }
177 :
178 : static inline void
179 : cairo_list_swap (cairo_list_t *entry, cairo_list_t *other)
180 : {
181 : __cairo_list_add (entry, other->prev, other->next);
182 : cairo_list_init (other);
183 : }
184 :
185 : static inline cairo_bool_t
186 : cairo_list_is_first (const cairo_list_t *entry,
187 : const cairo_list_t *head)
188 : {
189 : cairo_list_validate (head);
190 : return entry->prev == head;
191 : }
192 :
193 : static inline cairo_bool_t
194 : cairo_list_is_last (const cairo_list_t *entry,
195 : const cairo_list_t *head)
196 : {
197 : cairo_list_validate (head);
198 : return entry->next == head;
199 : }
200 :
201 : static inline cairo_bool_t
202 132 : cairo_list_is_empty (const cairo_list_t *head)
203 : {
204 : cairo_list_validate (head);
205 132 : return head->next == head;
206 : }
207 :
208 : static inline cairo_bool_t
209 : cairo_list_is_singular (const cairo_list_t *head)
210 : {
211 : cairo_list_validate (head);
212 : return head->next == head || head->next == head->prev;
213 : }
214 :
215 : #endif /* CAIRO_LIST_PRIVATE_H */
|