NCBI C++ ToolKit
gapinfo.c
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: gapinfo.c 72378 2016-05-04 14:59:01Z camacho $
2  * ===========================================================================
3  *
4  * PUBLIC DOMAIN NOTICE
5  * National Center for Biotechnology Information
6  *
7  * This software/database is a "United States Government Work" under the
8  * terms of the United States Copyright Act. It was written as part of
9  * the author's official duties as a United States Government employee and
10  * thus cannot be copyrighted. This software/database is freely available
11  * to the public for use. The National Library of Medicine and the U.S.
12  * Government have not placed any restriction on its use or reproduction.
13  *
14  * Although all reasonable efforts have been taken to ensure the accuracy
15  * and reliability of the software and data, the NLM and the U.S.
16  * Government do not and cannot warrant the performance or results that
17  * may be obtained by using this software or data. The NLM and the U.S.
18  * Government disclaim all warranties, express or implied, including
19  * warranties of performance, merchantability or fitness for any particular
20  * purpose.
21  *
22  * Please cite the author in any work or product based on this material.
23  *
24  * ===========================================================================
25  *
26  * Author: Ilya Dondoshansky
27  *
28  */
29 
30 /** @file gapinfo.c
31  * Initialization and freeing of structures containing traceback information.
32  */
33 
34 
37 
40 
41 {
43 
44  while (state_struct) {
45  next = state_struct->next;
46  sfree(state_struct->state_array);
47  sfree(state_struct);
48  state_struct = next;
49  }
50 
51  return NULL;
52 }
53 
54 /* see gapinfo.h for description */
57 
58 {
59  GapEditScript* new;
60 
61  if (size <= 0)
62  return NULL;
63 
64  new = (GapEditScript*) calloc(1, sizeof(GapEditScript));
65  if (new)
66  {
67  new->size = size;
68  new->op_type = (EGapAlignOpType*) calloc(size, sizeof(EGapAlignOpType));
69  new->num = (Int4*) calloc(size, sizeof(Int4));
70  }
71  return new;
72 }
73 
76 {
77 
78  if (old)
79  {
80  sfree(old->op_type);
81  sfree(old->num);
82  sfree(old);
83  }
84  return old;
85 }
86 
87 /* see gapinfo.h for description */
90 {
91  GapEditScript* new = NULL;
92  if (old)
93  {
94  new = GapEditScriptNew(old->size);
95  if (new)
96  {
97  memcpy(new->op_type, old->op_type, (old->size)*sizeof(EGapAlignOpType));
98  memcpy(new->num, old->num, (old->size)*sizeof(Int4));
99  }
100  }
101  return new;
102 }
103 
104 Int2
105 GapEditScriptPartialCopy(GapEditScript* new, int offset, const GapEditScript* old, int start, int stop)
106 {
107  int size = 1+stop-start;
108  int new_index = 0;
109  int old_index = 0;
110 
111  if (old == NULL || new == NULL || stop-start+1 > new->size)
112  return -1;
113 
114  old_index = start;
115  for (new_index=offset; new_index<size+offset; new_index++)
116  {
117  new->num[new_index] = old->num[old_index];
118  new->op_type[new_index] = old->op_type[old_index];
119  old_index++;
120  }
121 
122  return 0;
123 }
124 
125 /** Ensures that a preliminary edit script has enough memory allocated
126  * to hold a given number of edit operations
127  *
128  * @param edit_block The script to examine [in/modified]
129  * @param total_ops Number of operations the script must support [in]
130  * @return 0 if successful, nonzero otherwise
131  */
132 static Int2
134 {
135  if (edit_block->num_ops_allocated <= total_ops) {
136  Int4 new_size = total_ops * 2;
137  GapPrelimEditScript *new_ops;
138 
139  new_ops = realloc(edit_block->edit_ops, new_size *
140  sizeof(GapPrelimEditScript));
141  if (new_ops == NULL)
142  return -1;
143 
144  edit_block->edit_ops = new_ops;
145  edit_block->num_ops_allocated = new_size;
146  }
147  return 0;
148 }
149 
150 /** Add an edit operation to an edit script
151 
152  @param edit_block The edit script to update [in/modified]
153  @param op_type The edit operation to add [in]
154  @param num_ops The number of operations of the specified type [in]
155  @return 0 on success, nonzero otherwise
156 */
157 static Int2
159  EGapAlignOpType op_type, Int4 num_ops)
160 {
161  if (s_GapPrelimEditBlockRealloc(edit_block, edit_block->num_ops + 2) != 0)
162  return -1;
163 
164  ASSERT(op_type != eGapAlignInvalid);
165 
166  edit_block->last_op = op_type;
167  edit_block->edit_ops[edit_block->num_ops].op_type = op_type;
168  edit_block->edit_ops[edit_block->num_ops].num = num_ops;
169  edit_block->num_ops++;
170 
171  return 0;
172 }
173 
174 void
176  EGapAlignOpType op_type, Int4 num_ops)
177 {
178  if (num_ops == 0)
179  return;
180 
181  if (edit_block->last_op == op_type)
182  edit_block->edit_ops[edit_block->num_ops-1].num += num_ops;
183  else
184  s_GapPrelimEditBlockAddNew(edit_block, op_type, num_ops);
185 }
186 
189 {
190  GapPrelimEditBlock *edit_block = malloc(sizeof(GapPrelimEditBlock));
191  if (edit_block != NULL) {
192  edit_block->edit_ops = NULL;
193  edit_block->num_ops_allocated = 0;
194  edit_block->num_ops = 0;
195  edit_block->last_op = eGapAlignInvalid;
196  s_GapPrelimEditBlockRealloc(edit_block, 100);
197  }
198  return edit_block;
199 }
200 
203 {
204  if (edit_block == NULL)
205  return NULL;
206 
207  sfree(edit_block->edit_ops);
208  sfree(edit_block);
209  return NULL;
210 }
211 
212 void
214 {
215  if (edit_block) {
216  edit_block->num_ops = 0;
217  edit_block->last_op = eGapAlignInvalid;
218  }
219 }
220 
221 void
223  GapPrelimEditBlock *edit_block2)
224 {
225  Int4 index;
227 
228  for (index = 0, op = edit_block2->edit_ops; index < edit_block2->num_ops;
229  ++index, ++op) {
230  GapPrelimEditBlockAdd(edit_block1, op->op_type, op->num);
231  }
232 }
Definitions used throughout BLAST.
#define sfree(x)
Safe free a pointer: belongs to a higher level header.
Definition: blast_def.h:112
static DLIST_TYPE *DLIST_NAME() next(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:56
int offset
Definition: replacements.h:160
void GapPrelimEditBlockAdd(GapPrelimEditBlock *edit_block, EGapAlignOpType op_type, Int4 num_ops)
Add a new operation to a preliminary edit block, possibly combining it with the last operation if the...
Definition: gapinfo.c:175
GapPrelimEditBlock * GapPrelimEditBlockFree(GapPrelimEditBlock *edit_block)
Frees a preliminary edit block structure.
Definition: gapinfo.c:202
static Int2 s_GapPrelimEditBlockRealloc(GapPrelimEditBlock *edit_block, Int4 total_ops)
Ensures that a preliminary edit script has enough memory allocated to hold a given number of edit ope...
Definition: gapinfo.c:133
GapEditScript * GapEditScriptDup(const GapEditScript *old)
Duplicates the edit script structure.
Definition: gapinfo.c:89
GapStateArrayStruct * GapStateFree(GapStateArrayStruct *state_struct)
Free the gap state structure.
Definition: gapinfo.c:39
GapEditScript * GapEditScriptNew(Int4 size)
Initialize the edit script structure.
Definition: gapinfo.c:56
void GapPrelimEditBlockAppend(GapPrelimEditBlock *edit_block1, GapPrelimEditBlock *edit_block2)
Append one GapPrelimEditBlock to the end of the other.
Definition: gapinfo.c:222
Int2 GapEditScriptPartialCopy(GapEditScript *new, int offset, const GapEditScript *old, int start, int stop)
Copies the portion of the GapEditScript specified by start and stop to a new one the new one should a...
Definition: gapinfo.c:105
GapEditScript * GapEditScriptDelete(GapEditScript *old)
Free edit script structure.
Definition: gapinfo.c:75
GapPrelimEditBlock * GapPrelimEditBlockNew(void)
Allocates a preliminary edit block structure.
Definition: gapinfo.c:188
void GapPrelimEditBlockReset(GapPrelimEditBlock *edit_block)
Reset a preliminary edit block without freeing it.
Definition: gapinfo.c:213
static Int2 s_GapPrelimEditBlockAddNew(GapPrelimEditBlock *edit_block, EGapAlignOpType op_type, Int4 num_ops)
Add an edit operation to an edit script.
Definition: gapinfo.c:158
Definitions of structures used for saving traceback information.
EGapAlignOpType
Operation types within the edit script.
Definition: gapinfo.h:44
@ eGapAlignInvalid
Invalid operation.
Definition: gapinfo.h:53
#define NULL
Definition: ncbistd.hpp:225
int16_t Int2
2-byte (16-bit) signed integer
Definition: ncbitype.h:100
int32_t Int4
4-byte (32-bit) signed integer
Definition: ncbitype.h:102
const struct ncbi::grid::netcache::search::fields::SIZE size
#define ASSERT
macro for assert.
Definition: ncbi_std.h:107
Edit script: linked list of correspondencies between two sequences.
Definition: gapinfo.h:57
Int4 * num
Array of number of operations.
Definition: gapinfo.h:59
Int4 size
Size of above arrays.
Definition: gapinfo.h:60
EGapAlignOpType * op_type
Array of type of operation.
Definition: gapinfo.h:58
Preliminary version of GapEditBlock, used directly by the low- level dynamic programming routines.
Definition: gapinfo.h:73
Int4 num_ops_allocated
size of allocated array
Definition: gapinfo.h:75
GapPrelimEditScript * edit_ops
array of edit operations
Definition: gapinfo.h:74
EGapAlignOpType last_op
most recent operation added
Definition: gapinfo.h:77
Int4 num_ops
number of edit ops presently in use
Definition: gapinfo.h:76
A version of GapEditScript used to store initial results from the gapped alignment routines.
Definition: gapinfo.h:65
Int4 num
Number of operations.
Definition: gapinfo.h:67
EGapAlignOpType op_type
Type of operation.
Definition: gapinfo.h:66
Structure to keep memory for state structure.
Definition: gapinfo.h:81
struct GapStateArrayStruct * next
Next link in the list.
Definition: gapinfo.h:85
Uint1 * state_array
array to be used.
Definition: gapinfo.h:84
voidp malloc(uInt size)
voidp calloc(uInt items, uInt size)
Modified on Fri Sep 20 14:57:13 2024 by modify_doxy.py rev. 669887