File: opal_list.c

package info (click to toggle)
openmpi 5.0.8-4
  • links: PTS, VCS
  • area: main
  • in suites: sid
  • size: 201,684 kB
  • sloc: ansic: 613,078; makefile: 42,353; sh: 11,194; javascript: 9,244; f90: 7,052; java: 6,404; perl: 5,179; python: 1,859; lex: 740; fortran: 61; cpp: 20; tcl: 12
file content (184 lines) | stat: -rw-r--r-- 5,449 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
/*
 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
 *                         University Research and Technology
 *                         Corporation.  All rights reserved.
 * Copyright (c) 2004-2014 The University of Tennessee and The University
 *                         of Tennessee Research Foundation.  All rights
 *                         reserved.
 * Copyright (c) 2004-2007 High Performance Computing Center Stuttgart,
 *                         University of Stuttgart.  All rights reserved.
 * Copyright (c) 2004-2005 The Regents of the University of California.
 *                         All rights reserved.
 * Copyright (c) 2007      Voltaire All rights reserved.
 * $COPYRIGHT$
 *
 * Additional copyrights may follow
 *
 * $HEADER$
 */

#include "opal_config.h"

#include "opal/class/opal_list.h"
#include "opal/constants.h"

/*
 *  List classes
 */

static void opal_list_item_construct(opal_list_item_t *);
static void opal_list_item_destruct(opal_list_item_t *);

OBJ_CLASS_INSTANCE(opal_list_item_t, opal_object_t, opal_list_item_construct,
                   opal_list_item_destruct);

static void opal_list_construct(opal_list_t *);
static void opal_list_destruct(opal_list_t *);

OBJ_CLASS_INSTANCE(opal_list_t, opal_object_t, opal_list_construct, opal_list_destruct);

/*
 *
 *      opal_list_link_item_t interface
 *
 */

static void opal_list_item_construct(opal_list_item_t *item)
{
    item->opal_list_next = item->opal_list_prev = NULL;
    item->item_free = 1;
#if OPAL_ENABLE_DEBUG
    item->opal_list_item_refcount = 0;
    item->opal_list_item_belong_to = NULL;
#endif
}

static void opal_list_item_destruct(opal_list_item_t *item)
{
#if OPAL_ENABLE_DEBUG
    assert(0 == item->opal_list_item_refcount);
    assert(NULL == item->opal_list_item_belong_to);
#endif /* OPAL_ENABLE_DEBUG */
}

/*
 *
 *      opal_list_list_t interface
 *
 */

static void opal_list_construct(opal_list_t *list)
{
#if OPAL_ENABLE_DEBUG
    /* These refcounts should never be used in assertions because they
       should never be removed from this list, added to another list,
       etc.  So set them to sentinel values. */

    OBJ_CONSTRUCT(&(list->opal_list_sentinel), opal_list_item_t);
    list->opal_list_sentinel.opal_list_item_refcount = 1;
    list->opal_list_sentinel.opal_list_item_belong_to = list;
#endif

    list->opal_list_sentinel.opal_list_next = &list->opal_list_sentinel;
    list->opal_list_sentinel.opal_list_prev = &list->opal_list_sentinel;
    list->opal_list_length = 0;
}

/*
 * Reset all the pointers to be NULL -- do not actually destroy
 * anything.
 */
static void opal_list_destruct(opal_list_t *list)
{
    opal_list_construct(list);
}

static void opal_list_transfer(opal_list_item_t *pos, opal_list_item_t *begin,
                               opal_list_item_t *end)
{
    volatile opal_list_item_t *tmp;

    if (pos != end) {
        /* remove [begin, end) */
        end->opal_list_prev->opal_list_next = pos;
        begin->opal_list_prev->opal_list_next = end;
        pos->opal_list_prev->opal_list_next = begin;

        /* splice into new position before pos */
        tmp = pos->opal_list_prev;
        pos->opal_list_prev = end->opal_list_prev;
        end->opal_list_prev = begin->opal_list_prev;
        begin->opal_list_prev = tmp;
#if OPAL_ENABLE_DEBUG
        {
            volatile opal_list_item_t *item = begin;
            while (pos != item) {
                item->opal_list_item_belong_to = pos->opal_list_item_belong_to;
                item = item->opal_list_next;
                assert(NULL != item);
            }
        }
#endif /* OPAL_ENABLE_DEBUG */
    }
}

void opal_list_join(opal_list_t *thislist, opal_list_item_t *pos, opal_list_t *xlist)
{
    if (0 != opal_list_get_size(xlist)) {
        opal_list_transfer(pos, opal_list_get_first(xlist), opal_list_get_end(xlist));

        /* fix the sizes */
        thislist->opal_list_length += xlist->opal_list_length;
        xlist->opal_list_length = 0;
    }
}

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)
{
    size_t change = 0;
    opal_list_item_t *tmp;

    if (first != last) {
        /* figure out how many things we are going to move (have to do
         * first, since last might be end and then we wouldn't be able
         * to run the loop)
         */
        for (tmp = first; tmp != last; tmp = opal_list_get_next(tmp)) {
            change++;
        }

        opal_list_transfer(pos, first, last);

        /* fix the sizes */
        thislist->opal_list_length += change;
        xlist->opal_list_length -= change;
    }
}

int opal_list_sort(opal_list_t *list, opal_list_item_compare_fn_t compare)
{
    opal_list_item_t *item;
    opal_list_item_t **items;
    size_t i, index = 0;

    if (0 == list->opal_list_length) {
        return OPAL_SUCCESS;
    }
    items = (opal_list_item_t **) malloc(sizeof(opal_list_item_t *) * list->opal_list_length);

    if (NULL == items) {
        return OPAL_ERR_OUT_OF_RESOURCE;
    }

    while (NULL != (item = opal_list_remove_first(list))) {
        items[index++] = item;
    }

    qsort(items, index, sizeof(opal_list_item_t *), (int (*)(const void *, const void *)) compare);
    for (i = 0; i < index; i++) {
        opal_list_append(list, items[i]);
    }
    free(items);
    return OPAL_SUCCESS;
}