root/opal/class/opal_list.c

DEFINITIONS

1. opal_list_item_construct
2. opal_list_item_destruct
3. opal_list_construct
4. opal_list_destruct
5. opal_list_insert
6. opal_list_transfer
7. opal_list_join
8. opal_list_splice
9. opal_list_sort

   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 
  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  /* OPAL_ENABLE_DEBUG */
  72 }
  73 
  74 
  75 /*
  76  *
  77  *      opal_list_list_t interface
  78  *
  79  */
  80 
  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  */
 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  */
 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 insertted 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
 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
 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
 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 
 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 }