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