1 | /* Copyright 2016 Google Inc. |
2 | |
3 | Licensed under the Apache License, Version 2.0 (the "License"); |
4 | you may not use this file except in compliance with the License. |
5 | You may obtain a copy of the License at |
6 | |
7 | http://www.apache.org/licenses/LICENSE-2.0 |
8 | |
9 | Unless required by applicable law or agreed to in writing, software |
10 | distributed under the License is distributed on an "AS IS" BASIS, |
11 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | See the License for the specific language governing permissions and |
13 | limitations under the License. */ |
14 | |
15 | #ifndef NSYNC_INTERNAL_DLL_H_ |
16 | #define NSYNC_INTERNAL_DLL_H_ |
17 | |
18 | /* Doubly linked lists. */ |
19 | |
20 | #include "nsync_cpp.h" |
21 | NSYNC_CPP_START_ |
22 | |
23 | /* A nsync_dll_element_ represents an element of a doubly-linked list of waiters. */ |
24 | typedef struct nsync_dll_element_s_ { |
25 | struct nsync_dll_element_s_ *next; |
26 | struct nsync_dll_element_s_ *prev; |
27 | void *container; /* points to the struct this nsync_dll struct is embedded in. */ |
28 | } nsync_dll_element_; |
29 | |
30 | /* A nsync_dll_list_ represents a list of nsync_dll_elements_. */ |
31 | typedef nsync_dll_element_ *nsync_dll_list_; /* last elem of circular list; nil => empty; first is x.next. */ |
32 | |
33 | |
34 | /* Initialize *e. */ |
35 | void nsync_dll_init_ (nsync_dll_element_ *e, void *container); |
36 | |
37 | /* Return whether list is empty. */ |
38 | int nsync_dll_is_empty_ (nsync_dll_list_ list); |
39 | |
40 | /* Remove *e from list, and returns the new list. */ |
41 | nsync_dll_list_ nsync_dll_remove_ (nsync_dll_list_ list, nsync_dll_element_ *e); |
42 | |
43 | /* Cause element *n and its successors to come after element *p. |
44 | Requires n and p are non-NULL and do not point at elements of the same list. */ |
45 | void nsync_dll_splice_after_ (nsync_dll_element_ *p, nsync_dll_element_ *n); |
46 | |
47 | /* Make element *e the first element of list, and return |
48 | the list. The resulting list will have *e as its first element, followed by |
49 | any elements in the same list as *e, followed by the elements that were |
50 | previously in list. Requires that *e not be in list. If e==NULL, list is |
51 | returned unchanged. */ |
52 | nsync_dll_list_ nsync_dll_make_first_in_list_ (nsync_dll_list_ list, nsync_dll_element_ *e); |
53 | |
54 | /* Make element *e the last element of list, and return |
55 | the list. The resulting list will have *e as its last element, preceded by |
56 | any elements in the same list as *e, preceded by the elements that were |
57 | previously in list. Requires that *e not be in list. If e==NULL, list is |
58 | returned unchanged. */ |
59 | nsync_dll_list_ nsync_dll_make_last_in_list_ (nsync_dll_list_ list, nsync_dll_element_ *e); |
60 | |
61 | /* Return a pointer to the first element of list, or NULL if list is empty. */ |
62 | nsync_dll_element_ *nsync_dll_first_ (nsync_dll_list_ list); |
63 | |
64 | /* Return a pointer to the last element of list, or NULL if list is empty. */ |
65 | nsync_dll_element_ *nsync_dll_last_ (nsync_dll_list_ list); |
66 | |
67 | /* Return a pointer to the next element of list following *e, |
68 | or NULL if there is no such element. */ |
69 | nsync_dll_element_ *nsync_dll_next_ (nsync_dll_list_ list, nsync_dll_element_ *e); |
70 | |
71 | /* Return a pointer to the previous element of list following *e, |
72 | or NULL if there is no such element. */ |
73 | nsync_dll_element_ *nsync_dll_prev_ (nsync_dll_list_ list, nsync_dll_element_ *e); |
74 | |
75 | NSYNC_CPP_END_ |
76 | |
77 | #endif /*NSYNC_INTERNAL_DLL_H_*/ |
78 | |