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"
21NSYNC_CPP_START_
22
23/* A nsync_dll_element_ represents an element of a doubly-linked list of waiters. */
24typedef 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_. */
31typedef nsync_dll_element_ *nsync_dll_list_; /* last elem of circular list; nil => empty; first is x.next. */
32
33
34/* Initialize *e. */
35void nsync_dll_init_ (nsync_dll_element_ *e, void *container);
36
37/* Return whether list is empty. */
38int nsync_dll_is_empty_ (nsync_dll_list_ list);
39
40/* Remove *e from list, and returns the new list. */
41nsync_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. */
45void 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. */
52nsync_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. */
59nsync_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. */
62nsync_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. */
65nsync_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. */
69nsync_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. */
73nsync_dll_element_ *nsync_dll_prev_ (nsync_dll_list_ list, nsync_dll_element_ *e);
74
75NSYNC_CPP_END_
76
77#endif /*NSYNC_INTERNAL_DLL_H_*/
78