1 /*************************************************************** 2 3 The Subread software package is free software package: 4 you can redistribute it and/or modify it under the terms 5 of the GNU General Public License as published by the 6 Free Software Foundation, either version 3 of the License, 7 or (at your option) any later version. 8 9 Subread is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty 11 of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 13 See the GNU General Public License for more details. 14 15 Authors: Drs Yang Liao and Wei Shi 16 17 ***************************************************************/ 18 19 20 #ifndef _LONG_HASHTABLE_H_ 21 #define _LONG_HASHTABLE_H_ 22 #include <stdlib.h> 23 #include <stdio.h> 24 #include "subread.h" 25 26 #define LNHASH_BUCKET_SIZE_INCREMENT 1.4 27 #define LNHASH_INIT_BUCKET_SIZE 300 28 29 typedef unsigned long long lnhash_data_t; 30 31 typedef struct { 32 unsigned int num_elements; 33 unsigned int space_elements; 34 35 gehash_key_t * key_array; 36 lnhash_data_t * value_array; 37 } lnhash_buckct_t; 38 39 40 41 typedef struct { 42 int is_sorted; 43 unsigned long long int num_elements; 44 unsigned int num_buckets; 45 unsigned short * key_repeated_numbers; 46 unsigned short subread_repeat_max; 47 48 lnhash_buckct_t * buckets; 49 } lnhash_t; 50 51 #define LNHASH_VOTE_ARRAY_WIDTH 240 52 #define LNHASH_VOTE_ARRAY_HEIGHT 233 53 //#define LNHASH_VOTE_ARRAY_WIDTH 48 54 //#define LNHASH_VOTE_ARRAY_HEIGHT 31 55 56 typedef struct{ 57 lnhash_data_t head_position; 58 short coverage_start; 59 short coverage_end; 60 short num_votes; 61 } lnhash_vote_record_t; 62 63 typedef struct{ 64 int max_votes; 65 int vote_record_items [LNHASH_VOTE_ARRAY_HEIGHT]; 66 lnhash_vote_record_t vote_records [LNHASH_VOTE_ARRAY_HEIGHT][LNHASH_VOTE_ARRAY_WIDTH]; 67 } lnhash_vote_t; 68 69 #define lnhash_init_votes(v) memset(v->vote_record_items, 0, sizeof(int) * LNHASH_VOTE_ARRAY_HEIGHT) 70 71 // The EX version creates a hashtable with the given version number 72 int lnhash_create(lnhash_t * the_table, unsigned int num_buckets); 73 74 // This function puts a data item into the table. If there is duplication, it insert another copy into the table but do not overlap on the old one. 75 int lnhash_insert(lnhash_t * the_table, gehash_key_t key, lnhash_data_t data); 76 77 // this function must be called before querying or dumpping. 78 void lnhash_resort(lnhash_t * the_table); 79 80 // this function returns the number of items being hit 81 int lnhash_query(lnhash_t * the_table, lnhash_vote_t * vote, gehash_key_t queried_key, short dist_to_head); 82 83 // Free all memory that is allocated for the table. Only the table structure itself is not freed. 84 void lnhash_destroy(lnhash_t * the_table); 85 86 // This function returns the number of votes that has at least "minimum_votes" votes; the vote records are sorted by their head_position. 87 int sorted_voting_table(lnhash_vote_t * vote, lnhash_vote_record_t ** result_buffer, int minimum_votes); 88 89 // This function adds rec -> coverage_start to rec -> head_position. 90 int sorted_voting_table_offset(lnhash_vote_t * vote, lnhash_vote_record_t ** result_buffer, int minimum_votes); 91 92 #endif 93