1 /*
2 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
3 * University Research and Technology
4 * Corporation. All rights reserved.
5 * Copyright (c) 2004-2014 The University of Tennessee and The University
6 * of Tennessee Research Foundation. All rights
7 * reserved.
8 * Copyright (c) 2004-2007 High Performance Computing Center Stuttgart,
9 * University of Stuttgart. All rights reserved.
10 * Copyright (c) 2004-2005 The Regents of the University of California.
11 * All rights reserved.
12 * Copyright (c) 2007 Voltaire All rights reserved.
13 * $COPYRIGHT$
14 *
15 * Additional copyrights may follow
16 *
17 * $HEADER$
18 */
19
20 #include "opal_config.h"
21
22 #include "opal/class/opal_list.h"
23 #include "opal/constants.h"
24
25 /*
26 * List classes
27 */
28
29 static void opal_list_item_construct(opal_list_item_t*);
30 static void opal_list_item_destruct(opal_list_item_t*);
31
32 OBJ_CLASS_INSTANCE(
33 opal_list_item_t,
34 opal_object_t,
35 opal_list_item_construct,
36 opal_list_item_destruct
37 );
38
39 static void opal_list_construct(opal_list_t*);
40 static void opal_list_destruct(opal_list_t*);
41
42 OBJ_CLASS_INSTANCE(
43 opal_list_t,
44 opal_object_t,
45 opal_list_construct,
46 opal_list_destruct
47 );
48
49
50 /*
51 *
52 * opal_list_link_item_t interface
53 *
54 */
55
opal_list_item_construct(opal_list_item_t * item)56 static void opal_list_item_construct(opal_list_item_t *item)
57 {
58 item->opal_list_next = item->opal_list_prev = NULL;
59 item->item_free = 1;
60 #if OPAL_ENABLE_DEBUG
61 item->opal_list_item_refcount = 0;
62 item->opal_list_item_belong_to = NULL;
63 #endif
64 }
65
opal_list_item_destruct(opal_list_item_t * item)66 static void opal_list_item_destruct(opal_list_item_t *item)
67 {
68 #if OPAL_ENABLE_DEBUG
69 assert( 0 == item->opal_list_item_refcount );
70 assert( NULL == item->opal_list_item_belong_to );
71 #endif /* OPAL_ENABLE_DEBUG */
72 }
73
74
75 /*
76 *
77 * opal_list_list_t interface
78 *
79 */
80
opal_list_construct(opal_list_t * list)81 static void opal_list_construct(opal_list_t *list)
82 {
83 #if OPAL_ENABLE_DEBUG
84 /* These refcounts should never be used in assertions because they
85 should never be removed from this list, added to another list,
86 etc. So set them to sentinel values. */
87
88 OBJ_CONSTRUCT( &(list->opal_list_sentinel), opal_list_item_t );
89 list->opal_list_sentinel.opal_list_item_refcount = 1;
90 list->opal_list_sentinel.opal_list_item_belong_to = list;
91 #endif
92
93 list->opal_list_sentinel.opal_list_next = &list->opal_list_sentinel;
94 list->opal_list_sentinel.opal_list_prev = &list->opal_list_sentinel;
95 list->opal_list_length = 0;
96 }
97
98
99 /*
100 * Reset all the pointers to be NULL -- do not actually destroy
101 * anything.
102 */
opal_list_destruct(opal_list_t * list)103 static void opal_list_destruct(opal_list_t *list)
104 {
105 opal_list_construct(list);
106 }
107
108
109 /*
110 * Insert an item at a specific place in a list
111 */
opal_list_insert(opal_list_t * list,opal_list_item_t * item,long long idx)112 bool opal_list_insert(opal_list_t *list, opal_list_item_t *item, long long idx)
113 {
114 /* Adds item to list at index and retains item. */
115 int i;
116 volatile opal_list_item_t *ptr, *next;
117
118 if ( idx >= (long long)list->opal_list_length ) {
119 return false;
120 }
121
122 if ( 0 == idx )
123 {
124 opal_list_prepend(list, item);
125 } else {
126 #if OPAL_ENABLE_DEBUG
127 /* Spot check: ensure that this item is previously on no
128 lists */
129
130 assert(0 == item->opal_list_item_refcount);
131 #endif
132 /* pointer to element 0 */
133 ptr = list->opal_list_sentinel.opal_list_next;
134 for ( i = 0; i < idx-1; i++ )
135 ptr = ptr->opal_list_next;
136
137 next = ptr->opal_list_next;
138 item->opal_list_next = next;
139 item->opal_list_prev = ptr;
140 next->opal_list_prev = item;
141 ptr->opal_list_next = item;
142
143 #if OPAL_ENABLE_DEBUG
144 /* Spot check: ensure this item is only on the list that we
145 just inserted it into */
146
147 opal_atomic_add ( &(item->opal_list_item_refcount), 1 );
148 assert(1 == item->opal_list_item_refcount);
149 item->opal_list_item_belong_to = list;
150 #endif
151 }
152
153 list->opal_list_length++;
154 return true;
155 }
156
157
158 static
159 void
opal_list_transfer(opal_list_item_t * pos,opal_list_item_t * begin,opal_list_item_t * end)160 opal_list_transfer(opal_list_item_t *pos, opal_list_item_t *begin,
161 opal_list_item_t *end)
162 {
163 volatile opal_list_item_t *tmp;
164
165 if (pos != end) {
166 /* remove [begin, end) */
167 end->opal_list_prev->opal_list_next = pos;
168 begin->opal_list_prev->opal_list_next = end;
169 pos->opal_list_prev->opal_list_next = begin;
170
171 /* splice into new position before pos */
172 tmp = pos->opal_list_prev;
173 pos->opal_list_prev = end->opal_list_prev;
174 end->opal_list_prev = begin->opal_list_prev;
175 begin->opal_list_prev = tmp;
176 #if OPAL_ENABLE_DEBUG
177 {
178 volatile opal_list_item_t* item = begin;
179 while( pos != item ) {
180 item->opal_list_item_belong_to = pos->opal_list_item_belong_to;
181 item = item->opal_list_next;
182 assert(NULL != item);
183 }
184 }
185 #endif /* OPAL_ENABLE_DEBUG */
186 }
187 }
188
189
190 void
opal_list_join(opal_list_t * thislist,opal_list_item_t * pos,opal_list_t * xlist)191 opal_list_join(opal_list_t *thislist, opal_list_item_t *pos,
192 opal_list_t *xlist)
193 {
194 if (0 != opal_list_get_size(xlist)) {
195 opal_list_transfer(pos, opal_list_get_first(xlist),
196 opal_list_get_end(xlist));
197
198 /* fix the sizes */
199 thislist->opal_list_length += xlist->opal_list_length;
200 xlist->opal_list_length = 0;
201 }
202 }
203
204
205 void
opal_list_splice(opal_list_t * thislist,opal_list_item_t * pos,opal_list_t * xlist,opal_list_item_t * first,opal_list_item_t * last)206 opal_list_splice(opal_list_t *thislist, opal_list_item_t *pos,
207 opal_list_t *xlist, opal_list_item_t *first,
208 opal_list_item_t *last)
209 {
210 size_t change = 0;
211 opal_list_item_t *tmp;
212
213 if (first != last) {
214 /* figure out how many things we are going to move (have to do
215 * first, since last might be end and then we wouldn't be able
216 * to run the loop)
217 */
218 for (tmp = first ; tmp != last ; tmp = opal_list_get_next(tmp)) {
219 change++;
220 }
221
222 opal_list_transfer(pos, first, last);
223
224 /* fix the sizes */
225 thislist->opal_list_length += change;
226 xlist->opal_list_length -= change;
227 }
228 }
229
230
opal_list_sort(opal_list_t * list,opal_list_item_compare_fn_t compare)231 int opal_list_sort(opal_list_t* list, opal_list_item_compare_fn_t compare)
232 {
233 opal_list_item_t* item;
234 opal_list_item_t** items;
235 size_t i, index=0;
236
237 if (0 == list->opal_list_length) {
238 return OPAL_SUCCESS;
239 }
240 items = (opal_list_item_t**)malloc(sizeof(opal_list_item_t*) *
241 list->opal_list_length);
242
243 if (NULL == items) {
244 return OPAL_ERR_OUT_OF_RESOURCE;
245 }
246
247 while(NULL != (item = opal_list_remove_first(list))) {
248 items[index++] = item;
249 }
250
251 qsort(items, index, sizeof(opal_list_item_t*),
252 (int(*)(const void*,const void*))compare);
253 for (i=0; i<index; i++) {
254 opal_list_append(list,items[i]);
255 }
256 free(items);
257 return OPAL_SUCCESS;
258 }
259