root/ompi/class/ompi_seq_tracker.c

DEFINITIONS

1. ompi_seq_tracker_construct
2. ompi_seq_tracker_destruct
3. ompi_seq_tracker_check_duplicate
4. ompi_seq_tracker_insert
5. ompi_seq_tracker_copy

   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-2006 The University of Tennessee and The University
   6  *                         of Tennessee Research Foundation.  All rights
   7  *                         reserved.
   8  * Copyright (c) 2004-2005 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) 2010      Cisco Systems, Inc.  All rights reserved.
  13  * $COPYRIGHT$
  14  *
  15  * Additional copyrights may follow
  16  *
  17  * $HEADER$
  18  */
  19 
  20 #include "ompi_config.h"
  21 
  22 #include "ompi/class/ompi_seq_tracker.h"
  23 
  24 
  25 
  26 OBJ_CLASS_INSTANCE(ompi_seq_tracker_range_t,
  27                    opal_list_item_t,
  28                    NULL,
  29                    NULL);
  30 
  31 
  32 static void ompi_seq_tracker_construct(ompi_seq_tracker_t* seq_tracker) {
  33     OBJ_CONSTRUCT(&seq_tracker->seq_ids, opal_list_t);
  34     seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*)opal_list_get_end(&seq_tracker->seq_ids);
  35 }
  36 
  37 
  38 static void ompi_seq_tracker_destruct(ompi_seq_tracker_t* seq_tracker)
  39 {
  40     opal_list_item_t* item;
  41     while(NULL != (item = opal_list_remove_first(&seq_tracker->seq_ids)))
  42         OBJ_RELEASE(item);
  43     OBJ_DESTRUCT(&seq_tracker->seq_ids);
  44 }
  45 
  46 OBJ_CLASS_INSTANCE(
  47                    ompi_seq_tracker_t,
  48                    opal_object_t,
  49                    ompi_seq_tracker_construct,
  50                    ompi_seq_tracker_destruct);
  51 
  52 
  53 /**
  54  *  Look for duplicate sequence number in current range.
  55  *  Must be called w/ matching lock held.
  56  */
  57 
  58 bool ompi_seq_tracker_check_duplicate(
  59     ompi_seq_tracker_t* seq_tracker,
  60     uint32_t seq_id)
  61 {
  62     ompi_seq_tracker_range_t* item;
  63     const ompi_seq_tracker_range_t* sentinel = (ompi_seq_tracker_range_t*)opal_list_get_end(&seq_tracker->seq_ids);
  64     int8_t direction = 0; /* 1 is next, -1 is previous */
  65 
  66     item = seq_tracker->seq_ids_current;
  67     while(true) {
  68         if(sentinel == item) {
  69             return false;
  70         } else if(item->seq_id_high >= seq_id && item->seq_id_low <= seq_id) {
  71             seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) item;
  72             return true;
  73         } else if(seq_id > item->seq_id_high && direction != -1) {
  74             direction = 1;
  75             item = (ompi_seq_tracker_range_t*) opal_list_get_next(item);
  76         } else if(seq_id < item->seq_id_low && direction != 1) {
  77             direction = -1;
  78             item = (ompi_seq_tracker_range_t*) opal_list_get_prev(item);
  79         } else {
  80             return false;
  81         }
  82     }
  83 }
  84 
  85 
  86 /*
  87  * insert item into sequence tracking list,
  88  *   compacts continuous regions into a single entry
  89  * GMS::: Use a free list for the items (don't do OBJ_NEW)!
  90  */
  91 void ompi_seq_tracker_insert(ompi_seq_tracker_t* seq_tracker,
  92                                                 uint32_t seq_id)
  93 {
  94     opal_list_t* seq_ids = &seq_tracker->seq_ids;
  95     ompi_seq_tracker_range_t* item = seq_tracker->seq_ids_current;
  96     int8_t direction = 0; /* 1 is next, -1 is previous */
  97     ompi_seq_tracker_range_t *new_item, *next_item, *prev_item;
  98     const ompi_seq_tracker_range_t* sentinel = (ompi_seq_tracker_range_t*)opal_list_get_end(seq_ids);
  99 
 100     while( true ) {
 101         if( item == sentinel )  {
 102             new_item = OBJ_NEW(ompi_seq_tracker_range_t);
 103             new_item->seq_id_low = new_item->seq_id_high = seq_id;
 104             if( -1 == direction ) {
 105                 opal_list_prepend(seq_ids, (opal_list_item_t*) new_item);
 106             } else {
 107                 opal_list_append(seq_ids, (opal_list_item_t*) new_item);
 108             }
 109             seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) new_item;
 110             return;
 111 
 112         } else if(item->seq_id_high >= seq_id && item->seq_id_low <= seq_id ) {
 113 
 114             seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) item;
 115             return;
 116 
 117         } else if((item->seq_id_high + 1) == seq_id) {
 118 
 119             next_item = (ompi_seq_tracker_range_t*) opal_list_get_next(item);
 120             /* try to consolidate */
 121             if( (sentinel != next_item) && next_item->seq_id_low == (seq_id+1)) {
 122                 item->seq_id_high = next_item->seq_id_high;
 123                 opal_list_remove_item(seq_ids, (opal_list_item_t*) next_item);
 124                 OBJ_RELEASE(next_item);
 125             } else {
 126                 item->seq_id_high = seq_id;
 127             }
 128             seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) item;
 129             return;
 130 
 131         } else if((item->seq_id_low - 1) == seq_id) {
 132 
 133             prev_item = (ompi_seq_tracker_range_t*) opal_list_get_prev(item);
 134             /* try to consolidate */
 135             if( (sentinel != prev_item) && prev_item->seq_id_high == (seq_id-1)) {
 136                 item->seq_id_low = prev_item->seq_id_low;
 137                 opal_list_remove_item(seq_ids, (opal_list_item_t*) prev_item);
 138                 OBJ_RELEASE(prev_item);
 139             } else {
 140                 item->seq_id_low = seq_id;
 141             }
 142             seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) item;
 143             return;
 144 
 145         } else if(seq_id > item->seq_id_high ) {
 146             if(direction == -1) {
 147                 /* we have gone back in the list, and we went one item too far */
 148                 new_item = OBJ_NEW(ompi_seq_tracker_range_t);
 149                 new_item->seq_id_low = new_item->seq_id_high = seq_id;
 150                 next_item = (ompi_seq_tracker_range_t*) opal_list_get_next(item);
 151                 /* insert new_item directly before item */
 152                 opal_list_insert_pos(seq_ids,
 153                                      (opal_list_item_t*) next_item,
 154                                      (opal_list_item_t*) new_item);
 155                 seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) new_item;
 156                 return;
 157             } else {
 158                 direction = 1;
 159                 item = (ompi_seq_tracker_range_t*) opal_list_get_next(item);
 160             }
 161         } else if(seq_id < item->seq_id_low) {
 162             if(direction == 1) {
 163                 /* we have gone forward in the list, and we went one item too far */
 164                 new_item = OBJ_NEW(ompi_seq_tracker_range_t);
 165                 new_item->seq_id_low = new_item->seq_id_high = seq_id;
 166                 opal_list_insert_pos(seq_ids,
 167                                      (opal_list_item_t*) item,
 168                                      (opal_list_item_t*) new_item);
 169 
 170                 seq_tracker->seq_ids_current = (ompi_seq_tracker_range_t*) new_item;
 171                 return;
 172             } else {
 173                 direction = -1;
 174                 item = (ompi_seq_tracker_range_t*) opal_list_get_prev(item);
 175             }
 176         } else {
 177             return;
 178         }
 179     }
 180 }
 181 
 182 
 183 void ompi_seq_tracker_copy(ompi_seq_tracker_t* dst, ompi_seq_tracker_t* src)
 184 {
 185     opal_list_item_t* item;
 186     for( item =  opal_list_get_first(&src->seq_ids);
 187          item != opal_list_get_end(&src->seq_ids);
 188          item =  opal_list_get_next(item)) {
 189         ompi_seq_tracker_range_t* src_item = (ompi_seq_tracker_range_t*)item;
 190         ompi_seq_tracker_range_t* dst_item = OBJ_NEW(ompi_seq_tracker_range_t);
 191         dst_item->seq_id_high = src_item->seq_id_high;
 192         dst_item->seq_id_low = src_item->seq_id_low;
 193         opal_list_append(&dst->seq_ids, &dst_item->super);
 194         if(src->seq_ids_current == src_item) {
 195            dst->seq_ids_current = dst_item;
 196         }
 197     }
 198 }