1 /* $Id: index_ungapped.h 103491 2007-05-04 17:18:18Z kazimird $
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.h
31  * Declarations of structures needed to implement diagonal hash to
32  * support ungapped extensions for indexed version of megablast.
33  */
34 
35 #ifndef ALGO_BLAST_CORE__INDEX_UNGAPPED__H
36 #define ALGO_BLAST_CORE__INDEX_UNGAPPED__H
37 
38 #include <algo/blast/core/ncbi_std.h>
39 
40 /** How many keys are there in diagonal hash table. */
41 #define IR_HASH_SIZE (4*1024)
42 
43 /** Compute diagonal identifier from subject and query offsets.
44 
45     @param qoff Query offset.
46     @param soff Subject offset.
47 
48     @return Integer diagonal identifier.
49   */
50 #define IR_DIAG(qoff,soff) (0x10000000 + (soff) - (qoff))
51 
52 /** Compute the hash key from a diagonal identifier.
53 
54     @param diag Diagonal identifier.
55 
56     @return Hash key corresponding to the diagonal.
57   */
58 #define IR_KEY(diag)       ((diag)%IR_HASH_SIZE)
59 
60 /** Find a hash table entry for the given diagonal.
61 
62     @param hash Pointer to hash table instance.
63     @param diag Diagonal identifier.
64     @param key  Hash table key corresponding to the diagonal.
65 
66     @return Pointer to ir_hash_entry representing the diagonal.
67   */
68 #define IR_LOCATE(hash,diag,key) (                                      \
69         ((hash)->entries[(key)].diag_data.qend == 0 ||                  \
70          (diag)==(hash)->entries[(key)].diag_data.diag) ?               \
71                 ((hash)->entries + (key))      :                        \
72                 (ir_locate(hash,diag,key)) )
73 
74 /** Part of the hash table entry describing the diagonal. */
75 typedef struct ir_diag_data_
76 {
77     Uint4 diag;         /**< Diagonal identifier. */
78     Uint4 qend;         /**< Right end (in the query) of
79                              the last seen seed on the diagonal. */
80 } ir_diag_data;
81 
82 /** Hash table entry. */
83 typedef struct ir_hash_entry_
84 {
85     ir_diag_data diag_data;             /** Diagonal information. */
86     struct ir_hash_entry_ * next;       /** Next entry for the same hash key. */
87 } ir_hash_entry;
88 
89 /** Free memory block structure. */
90 typedef struct ir_fp_entry_
91 {
92     ir_hash_entry * entries;            /** Storage for hash table entries. */
93     struct ir_fp_entry_ * next;         /** Next free memory block. */
94 } ir_fp_entry;
95 
96 /** Hash table structure. */
97 typedef struct ir_diag_hash_
98 {
99     ir_hash_entry * entries;            /**< Array of hash table entries
100                                              (one per hash table key). */
101     ir_fp_entry * free_pool;            /**< Pointer to the first free memory block. */
102     ir_hash_entry * free;               /**< Start of the free list of hash table entries. */
103 } ir_diag_hash;
104 
105 /** Hash table constructor.
106 
107     @return A pointer to a fresh copy of a diagonal hash table, or NULL.
108   */
109 extern ir_diag_hash * ir_hash_create( void );
110 
111 /** Hash table destructor.
112 
113     @param hash Pointer to the hash table instance to destroy.
114 
115     @return NULL.
116 */
117 extern ir_diag_hash * ir_hash_destroy( ir_diag_hash * hash );
118 
119 /** Find a hash table entry for the given diagonal.
120 
121     @param hash Pointer to hash table instance.
122     @param diag Diagonal identifier.
123     @param key  Hash table key corresponding to the diagonal.
124 
125     @return Pointer to ir_hash_entry representing the diagonal.
126   */
127 extern ir_hash_entry * ir_locate(
128         ir_diag_hash * hash, Uint4 diag, Uint4 key );
129 
130 #endif
131