root/opal/mca/pmix/pmix4x/pmix/src/class/pmix_list.c

DEFINITIONS

1. pmix_list_item_construct
2. pmix_list_item_destruct
3. pmix_list_construct
4. pmix_list_destruct
5. pmix_list_insert
6. pmix_list_transfer
7. pmix_list_join
8. pmix_list_splice
9. pmix_list_sort

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