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#include "nsync_cpp.h"
16#include "platform.h"
17#include "compiler.h"
18#include "cputype.h"
19#include "dll.h"
20
21NSYNC_CPP_START_
22
23/* Initialize *e. */
24void nsync_dll_init_ (nsync_dll_element_ *e, void *container) {
25 e->next = e;
26 e->prev = e;
27 e->container = container;
28}
29
30/* Return whether list is empty. */
31int nsync_dll_is_empty_ (nsync_dll_list_ list) {
32 return (list == NULL);
33}
34
35/* Remove *e from list, and returns the new list. */
36nsync_dll_list_ nsync_dll_remove_ (nsync_dll_list_ list, nsync_dll_element_ *e) {
37 if (list == e) { /* removing tail of list */
38 if (list->prev == list) {
39 list = NULL; /* removing only element of list */
40 } else {
41 list = list->prev;
42 }
43 }
44 e->next->prev = e->prev;
45 e->prev->next = e->next;
46 e->next = e;
47 e->prev = e;
48 return (list);
49}
50
51/* Cause element *n and its successors to come after element *p.
52 Requires n and p are non-NULL and do not point at elements of the same list.
53
54 Unlike the other operations in this API, this operation acts on
55 two circular lists of elements, rather than on a "head" location that points
56 to such a circular list.
57
58 If the two lists are p->p_2nd->p_mid->p_last->p and n->n_2nd->n_mid->n_last->n,
59 then after nsync_dll_splice_after_ (p, n), the p list would be:
60 p->n->n_2nd->n_mid->n_last->p_2nd->p_mid->p_last->p. */
61void nsync_dll_splice_after_ (nsync_dll_element_ *p, nsync_dll_element_ *n) {
62 nsync_dll_element_ *p_2nd = p->next;
63 nsync_dll_element_ *n_last = n->prev;
64 p->next = n; /* n follows p */
65 n->prev = p;
66 n_last->next = p_2nd; /* remainder of p-list follows last of n-list */
67 p_2nd->prev = n_last;
68}
69
70/* Make element *e the first element of list, and return
71 the list. The resulting list will have *e as its first element, followed by
72 any elements in the same list as *e, followed by the elements that were
73 previously in list. Requires that *e not be in list. If e==NULL, list is
74 returned unchanged.
75
76 Suppose the e list is e->e_2nd->e_mid->e_last->e.
77 Recall that a head "list" points to the last element of its list.
78 If list is initially null, then the outcome is:
79 result = e_last->e->e_2nd->e_mid->e_last
80 If list is initially list->list_last->list_1st->list_mid->list_last,
81 then the outcome is:
82 result = list_last->e->e_2nd->e_mid->e_last->list_1st->list_mid->list_last
83 */
84nsync_dll_list_ nsync_dll_make_first_in_list_ (nsync_dll_list_ list, nsync_dll_element_ *e) {
85 if (e != NULL) {
86 if (list == NULL) {
87 list = e->prev; /*e->prev is e_last*/
88 } else {
89 nsync_dll_splice_after_ (list, e);
90 }
91 }
92 return (list);
93}
94
95/* Make element *e the last element of list, and return
96 the list. The resulting list will have *e as its last element, preceded by
97 any elements in the same list as *e, preceded by the elements that were
98 previously in list. Requires that *e not be in list. If e==NULL, list is
99 returned unchanged. */
100nsync_dll_list_ nsync_dll_make_last_in_list_ (nsync_dll_list_ list, nsync_dll_element_ *e) {
101 if (e != NULL) {
102 nsync_dll_make_first_in_list_ (list, e->next);
103 list = e;
104 }
105 return (list);
106}
107
108/* Return a pointer to the first element of list, or NULL if list is empty. */
109nsync_dll_element_ *nsync_dll_first_ (nsync_dll_list_ list) {
110 nsync_dll_element_ *first = NULL;
111 if (list != NULL) {
112 first = list->next;
113 }
114 return (first);
115}
116
117/* Return a pointer to the last element of list, or NULL if list is empty. */
118nsync_dll_element_ *nsync_dll_last_ (nsync_dll_list_ list) {
119 return (list);
120}
121
122/* Return a pointer to the next element of list following *e,
123 or NULL if there is no such element. */
124nsync_dll_element_ *nsync_dll_next_ (nsync_dll_list_ list, nsync_dll_element_ *e) {
125 nsync_dll_element_ *next = NULL;
126 if (e != list) {
127 next = e->next;
128 }
129 return (next);
130}
131
132/* Return a pointer to the previous element of list following *e,
133 or NULL if there is no such element. */
134nsync_dll_element_ *nsync_dll_prev_ (nsync_dll_list_ list, nsync_dll_element_ *e) {
135 nsync_dll_element_ *prev = NULL;
136 if (e != list->next) {
137 prev = e->prev;
138 }
139 return (prev);
140}
141
142NSYNC_CPP_END_
143