This source file includes following definitions.
- opal_list_item_construct
- opal_list_item_destruct
- opal_list_construct
- opal_list_destruct
- opal_list_insert
- opal_list_transfer
- opal_list_join
- opal_list_splice
- opal_list_sort
   1 
   2 
   3 
   4 
   5 
   6 
   7 
   8 
   9 
  10 
  11 
  12 
  13 
  14 
  15 
  16 
  17 
  18 
  19 
  20 #include "opal_config.h"
  21 
  22 #include "opal/class/opal_list.h"
  23 #include "opal/constants.h"
  24 
  25 
  26 
  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 
  53 
  54 
  55 
  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 
  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  
  72 }
  73 
  74 
  75 
  76 
  77 
  78 
  79 
  80 
  81 static void opal_list_construct(opal_list_t *list)
  82 {
  83 #if OPAL_ENABLE_DEBUG
  84     
  85 
  86 
  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 
 101 
 102 
 103 static void opal_list_destruct(opal_list_t *list)
 104 {
 105     opal_list_construct(list);
 106 }
 107 
 108 
 109 
 110 
 111 
 112 bool opal_list_insert(opal_list_t *list, opal_list_item_t *item, long long idx)
 113 {
 114     
 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         
 128 
 129 
 130         assert(0 == item->opal_list_item_refcount);
 131 #endif
 132         
 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         
 145 
 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
 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         
 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         
 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  
 186     }
 187 }
 188 
 189 
 190 void
 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         
 199         thislist->opal_list_length += xlist->opal_list_length;
 200         xlist->opal_list_length = 0;
 201     }
 202 }
 203 
 204 
 205 void
 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         
 215 
 216 
 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         
 225         thislist->opal_list_length += change;
 226         xlist->opal_list_length -= change;
 227     }
 228 }
 229 
 230 
 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 }