BGI/SOAPdenovo2/standardPregraph/stack.c

   1 /*
   2  * stack.c
   3  *
   4  * Copyright (c) 2008-2012 BGI-Shenzhen <soap at genomics dot org dot cn>.
   5  *
   6  * This file is part of SOAPdenovo.
   7  *
   8  * SOAPdenovo is free software: you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation, either version 3 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * SOAPdenovo is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with SOAPdenovo.  If not, see <http://www.gnu.org/licenses/>.
  20  *
  21  */
  22
  23 #include "stack.h"
  24
  25 STACK * createStack ( int num_items, size_t unit_size )
  26 {
  27         STACK * newStack = ( STACK * ) malloc ( 1 * sizeof ( STACK ) );
  28         newStack->block_list = NULL;
  29         newStack->items_per_block = num_items;
  30         newStack->item_size = unit_size;
  31         newStack->item_c = 0;
  32         return newStack;
  33 }
  34
  35 void emptyStack ( STACK * astack )
  36 {
  37         BLOCK_STARTER * block;
  38
  39         if ( !astack || !astack->block_list )
  40         {
  41                 return;
  42         }
  43
  44         block = astack->block_list;
  45
  46         if ( block->next )
  47         {
  48                 block = block->next;
  49         }
  50
  51         astack->block_list = block;
  52         astack->item_c = 0;
  53         astack->index_in_block = 0;
  54 }
  55
  56 void freeStack ( STACK * astack )
  57 {
  58         BLOCK_STARTER * ite_block, *temp_block;
  59
  60         if ( !astack )
  61         {
  62                 return;
  63         }
  64
  65         ite_block = astack->block_list;
  66
  67         if ( ite_block )
  68         {
  69                 while ( ite_block->next )
  70                 {
  71                         ite_block = ite_block->next;
  72                 }
  73         }
  74
  75         while ( ite_block )
  76         {
  77                 temp_block = ite_block;
  78                 ite_block = ite_block->prev;
  79                 free ( ( void * ) temp_block );
  80         }
  81
  82         free ( ( void * ) astack );
  83 }
  84
  85 void stackBackup ( STACK * astack )
  86 {
  87         astack->block_backup = astack->block_list;
  88         astack->index_backup = astack->index_in_block;
  89         astack->item_c_backup = astack->item_c;
  90 }
  91
  92 void stackRecover ( STACK * astack )
  93 {
  94         astack->block_list = astack->block_backup;
  95         astack->index_in_block = astack->index_backup;
  96         astack->item_c = astack->item_c_backup;
  97 }
  98
  99 void * stackPop ( STACK * astack )
 100 {
 101         BLOCK_STARTER * block;
 102
 103         if ( !astack || !astack->block_list || !astack->item_c )
 104         {
 105                 return NULL;
 106         }
 107
 108         astack->item_c--;
 109         block = astack->block_list;
 110
 111         if ( astack->index_in_block == 1 )
 112         {
 113                 if ( block->next )
 114                 {
 115                         astack->block_list = block->next;
 116                         astack->index_in_block = astack->items_per_block;
 117                 }
 118                 else
 119                 {
 120                         astack->index_in_block = 0;
 121                         astack->item_c = 0;
 122                 }
 123
 124                 return ( void * ) ( ( void * ) block + sizeof ( BLOCK_STARTER ) );
 125         }
 126
 127         return ( void * ) ( ( void * ) block + sizeof ( BLOCK_STARTER ) + astack->item_size * ( --astack->index_in_block ) );
 128 }
 129
 130 void * stackPush ( STACK * astack )
 131 {
 132         BLOCK_STARTER * block;
 133
 134         if ( !astack )
 135         {
 136                 return NULL;
 137         }
 138
 139         astack->item_c++;
 140
 141         if ( !astack->block_list || ( astack->index_in_block == astack->items_per_block && !astack->block_list->prev ) )
 142         {
 143                 block = malloc ( sizeof ( BLOCK_STARTER ) + astack->items_per_block * astack->item_size );
 144                 block->prev = NULL;
 145
 146                 if ( astack->block_list )
 147                 {
 148                         astack->block_list->prev = block;
 149                 }
 150
 151                 block->next = astack->block_list;
 152                 astack->block_list = block;
 153                 astack->index_in_block = 1;
 154                 return ( void * ) ( ( void * ) block + sizeof ( BLOCK_STARTER ) );
 155         }
 156         else if ( astack->index_in_block == astack->items_per_block && astack->block_list->prev )
 157         {
 158                 astack->block_list = astack->block_list->prev;
 159                 astack->index_in_block = 1;
 160                 return ( void * ) ( ( void * ) astack->block_list + sizeof ( BLOCK_STARTER ) );
 161         }
 162
 163         block = astack->block_list;
 164         return ( void * ) ( ( void * ) block + sizeof ( BLOCK_STARTER ) + astack->item_size * astack->index_in_block++ );
 165 }