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 | |
21 | NSYNC_CPP_START_ |
22 | |
23 | /* Initialize *e. */ |
24 | void 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. */ |
31 | int nsync_dll_is_empty_ (nsync_dll_list_ list) { |
32 | return (list == NULL); |
33 | } |
34 | |
35 | /* Remove *e from list, and returns the new list. */ |
36 | nsync_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. */ |
61 | void 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 | */ |
84 | nsync_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. */ |
100 | nsync_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. */ |
109 | nsync_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. */ |
118 | nsync_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. */ |
124 | nsync_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. */ |
134 | nsync_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 | |
142 | NSYNC_CPP_END_ |
143 | |