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

Go to the SVN repository for this file.

1 /* $Id: index_ungapped.c 84562 2018-11-19 15:12:17Z rackerst $
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: Aleksandr Morgulis
27  *
28  */
29 
30 /** @file index_ungapped.c
31  * Definitions of functions needed to implement diagonal hash to
32  * support ungapped extensions for indexed version of megablast.
33  */
34 
35 #include "index_ungapped.h"
36 
37 #define FP_ENTRY_SIZE (1024*1024)
38 
39 /** Free memory block destructor.
40 
41  @param e Pointer to the block being destroyed.
42 
43  @return NULL.
44  */
46 {
47  if( e != 0 ) {
48  free( e->entries );
49  free( e );
50  e = 0;
51  }
52 
53  return e;
54 }
55 
56 /** Free memory block constructor.
57 
58  @return Pointer to a newly allocated free memory block.
59 */
61 {
62  ir_fp_entry * result = (ir_fp_entry *) calloc(1, sizeof( ir_fp_entry ) );
63 
64  if( result != 0 ) {
66  FP_ENTRY_SIZE, sizeof( ir_hash_entry ) );
67  if( entries == 0 ) return ir_fp_entry_destroy( result );
68  result->next = 0;
69  result->entries = entries;
70 
71  {
72  size_t i = 0;
73  for( ; i < FP_ENTRY_SIZE - 1; ++i ) {
74  entries[i].next = entries + i + 1;
75  }
76  }
77  }
78 
79  return result;
80 }
81 
83 {
84  ir_diag_hash * result = 0;
85  result = (ir_diag_hash *) calloc(1, sizeof( ir_diag_hash ) );
86 
87  if( result != 0 ) {
89  IR_HASH_SIZE, sizeof( ir_hash_entry ) );
90  if( entries == 0 ) return ir_hash_destroy( result );
91  result->entries = entries;
92  result->free = 0;
93  result->free_pool = 0;
94  }
95 
96  return result;
97 }
98 
100 {
101  if( hash != 0 ) {
102  ir_fp_entry * fpe = hash->free_pool;
103  ir_fp_entry * fpn;
104 
105  while( fpe != 0 ) {
106  fpn = fpe->next;
107  fpe = ir_fp_entry_destroy( fpe );
108  fpe = fpn;
109  }
110 
111  free( hash->entries );
112  free( hash );
113  hash = 0;
114  }
115 
116  return hash;
117 }
118 
120  ir_diag_hash * hash, Uint4 diag, Uint4 key )
121 {
122  ir_hash_entry * e = hash->entries + key;
123  ir_hash_entry * ce = e->next;
124 
125  while( ce != 0 ) {
126  if( ce->diag_data.diag == diag ) {
127  ir_diag_data tmp = ce->diag_data;
128  ce->diag_data = e->diag_data;
129  e->diag_data = tmp;
130  return e;
131  }
132 
133  ce = ce->next;
134  }
135 
136  if( hash->free == 0 ) {
138  if (fp == 0) {
139  return (ir_hash_entry *) 0;
140  }
141  fp->next = hash->free_pool;
142  hash->free_pool = fp;
143  hash->free = fp->entries;
144  }
145 
146  ce = hash->free;
147  hash->free = ce->next;
148  ce->next = e->next;
149  e->next = ce;
150  ce->diag_data.diag = diag;
151  return ce;
152 }
153 
static const char fp[]
Definition: des.c:87
uint32_t Uint4
4-byte (32-bit) unsigned integer
Definition: ncbitype.h:103
ir_hash_entry * ir_locate(ir_diag_hash *hash, Uint4 diag, Uint4 key)
Find a hash table entry for the given diagonal.
ir_diag_hash * ir_hash_create(void)
Hash table constructor.
#define FP_ENTRY_SIZE
ir_diag_hash * ir_hash_destroy(ir_diag_hash *hash)
Hash table destructor.
static ir_fp_entry * ir_fp_entry_destroy(ir_fp_entry *e)
Free memory block destructor.
static ir_fp_entry * ir_fp_entry_create(void)
Free memory block constructor.
Declarations of structures needed to implement diagonal hash to support ungapped extensions for index...
#define IR_HASH_SIZE
How many keys are there in diagonal hash table.
int i
const struct ncbi::grid::netcache::search::fields::KEY key
static char tmp[2048]
Definition: utf8.c:42
Definition: _hash_fun.h:40
Part of the hash table entry describing the diagonal.
Uint4 diag
Diagonal identifier.
Hash table structure.
Free memory block structure.
ir_hash_entry * entries
struct ir_fp_entry_ * next
Storage for hash table entries.
Hash table entry.
ir_diag_data diag_data
struct ir_hash_entry_ * next
Diagonal information.
else result
Definition: token2.c:20
static wxAcceleratorEntry entries[3]
void free(voidpf ptr)
voidp calloc(uInt items, uInt size)
Modified on Sun Feb 25 03:08:29 2024 by modify_doxy.py rev. 669887