2 Copyright (c) 2013-2014 Genome Research Ltd.
3 Author: James Bonfield <jkb@sanger.ac.uk>
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
8 1. Redistributions of source code must retain the above copyright notice,
9 this list of conditions and the following disclaimer.
11 2. Redistributions in binary form must reproduce the above copyright notice,
12 this list of conditions and the following disclaimer in the documentation
13 and/or other materials provided with the distribution.
15 3. Neither the names Genome Research Ltd and Wellcome Trust Sanger
16 Institute nor the names of its contributors may be used to endorse or promote
17 products derived from this software without specific prior written permission.
19 THIS SOFTWARE IS PROVIDED BY GENOME RESEARCH LTD AND CONTRIBUTORS "AS IS" AND
20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL GENOME RESEARCH LTD OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 * These functions can be shared between SAM, BAM and CRAM file
35 * formats as all three internally use the same string encoding for
42 * - Sort order (parse to struct, enum type, updating funcs)
52 #include "cram/string_alloc.h"
53 #include "cram/pooled_alloc.h"
55 #include "htslib/khash.h"
56 #include "htslib/kstring.h"
62 // For structure assignment. Eg kstring_t s = KS_INITIALIZER;
63 #define KS_INITIALIZER {0,0,0}
65 // For initialisation elsewhere. Eg KS_INIT(x->str);
66 #define KS_INIT(ks) ((ks)->l = 0, (ks)->m = 0, (ks)->s = NULL)
68 // Frees the string subfield only. Assumes 's' itself is static.
69 #define KS_FREE(ks) do { if ((ks)->s) free((ks)->s); } while(0)
72 * Proposed new SAM header parsing
76 3 @SQ ID:ram LN:300 UR:xyz
80 Hash table for 2-char @keys without dup entries.
81 If dup lines, we form a circular linked list. Ie hash keys = {RG, SQ}.
85 (3) <-> 1 <-> 2 <-> 3 <-> (1)
89 (5) <-> 4 <-> 5 <-> (4)
91 Items stored in the hash values also form their own linked lists:
92 Ie SQ->ID(foo)->LN(100)
94 SQ->ID(ram)->LN(300)->UR(xyz)
98 /*! A single key:value pair on a header line
100 * These form a linked list and hold strings. The strings are
101 * allocated from a string_alloc_t pool referenced in the master
102 * SAM_hdr structure. Do not attempt to free, malloc or manipulate
103 * these strings directly.
105 typedef struct SAM_hdr_tag_s
{
106 struct SAM_hdr_tag_s
*next
;
111 /*! The parsed version of the SAM header string.
113 * Each header type (SQ, RG, HD, etc) points to its own SAM_hdr_type
114 * struct via the main hash table h in the SAM_hdr struct.
116 * These in turn consist of circular bi-directional linked lists (ie
117 * rings) to hold the multiple instances of the same header type
118 * code. For example if we have 5 \@SQ lines the primary hash table
119 * will key on \@SQ pointing to the first SAM_hdr_type and that in turn
120 * will be part of a ring of 5 elements.
122 * For each SAM_hdr_type structure we also point to a SAM_hdr_tag
123 * structure which holds the tokenised attributes; the tab separated
124 * key:value pairs per line.
126 typedef struct SAM_hdr_item_s
{
127 struct SAM_hdr_item_s
*next
; // cirular
128 struct SAM_hdr_item_s
*prev
;
129 SAM_hdr_tag
*tag
; // first tag
130 int order
; // 0 upwards
133 /*! Parsed \@SQ lines */
141 /*! Parsed \@RG lines */
147 int id
; // numerical ID
150 /*! Parsed \@PG lines */
156 int id
; // numerical ID
157 int prev_id
; // -1 if none
160 /*! Sort order parsed from @HD line */
161 enum sam_sort_order
{
166 //ORDER_COLLATE = 3 // maybe one day!
169 KHASH_MAP_INIT_INT(sam_hdr
, SAM_hdr_type
*)
170 KHASH_MAP_INIT_STR(m_s2i
, int)
172 /*! Primary structure for header manipulation
174 * The initial header text is held in the text kstring_t, but is also
175 * parsed out into SQ, RG and PG arrays. These have a hash table
176 * associated with each to allow lookup by ID or SN fields instead of
177 * their numeric array indices. Additionally PG has an array to hold
178 * the linked list start points (the last in a PP chain).
180 * Use the appropriate sam_hdr_* functions to edit the header, and
181 * call sam_hdr_rebuild() any time the textual form needs to be
185 kstring_t text
; //!< concatenated text, indexed by SAM_hdr_tag
187 string_alloc_t
*str_pool
; //!< Pool of SAM_hdr_tag->str strings
188 pool_alloc_t
*type_pool
;//!< Pool of SAM_hdr_type structs
189 pool_alloc_t
*tag_pool
; //!< Pool of SAM_hdr_tag structs
191 // @SQ lines / references
192 int nref
; //!< Number of \@SQ lines
193 SAM_SQ
*ref
; //!< Array of parsed \@SQ lines
194 khash_t(m_s2i
) *ref_hash
; //!< Maps SQ SN field to sq[] index
196 // @RG lines / read-groups
197 int nrg
; //!< Number of \@RG lines
198 SAM_RG
*rg
; //!< Array of parsed \@RG lines
199 khash_t(m_s2i
) *rg_hash
; //!< Maps RG ID field to rg[] index
201 // @PG lines / programs
202 int npg
; //!< Number of \@PG lines
203 int npg_end
; //!< Number of terminating \@PG lines
204 int npg_end_alloc
; //!< Size of pg_end field
205 SAM_PG
*pg
; //!< Array of parsed \@PG lines
206 khash_t(m_s2i
) *pg_hash
; //!< Maps PG ID field to pg[] index
207 int *pg_end
; //!< \@PG chain termination IDs
210 enum sam_sort_order sort_order
; //!< @HD SO: field
213 char ID_buf
[1024]; // temporary buffer
215 int ref_count
; // number of uses of this SAM_hdr
219 /*! Creates an empty SAM header, ready to be populated.
222 * Returns a SAM_hdr struct on success (free with sam_hdr_free())
225 SAM_hdr
*sam_hdr_new(void);
227 /*! Tokenises a SAM header into a hash table.
229 * Also extracts a few bits on specific data types, such as @RG lines.
232 * Returns a SAM_hdr struct on success (free with sam_hdr_free());
235 SAM_hdr
*sam_hdr_parse_(const char *hdr
, int len
);
238 /*! Produces a duplicate copy of hdr and returns it.
240 * Returns NULL on failure
242 SAM_hdr
*sam_hdr_dup(SAM_hdr
*hdr
);
245 /*! Increments a reference count on hdr.
247 * This permits multiple files to share the same header, all calling
248 * sam_hdr_free when done, without causing errors for other open files.
250 void sam_hdr_incr_ref(SAM_hdr
*hdr
);
253 /*! Increments a reference count on hdr.
255 * This permits multiple files to share the same header, all calling
256 * sam_hdr_free when done, without causing errors for other open files.
258 * If the reference count hits zero then the header is automatically
259 * freed. This makes it a synonym for sam_hdr_free().
261 void sam_hdr_decr_ref(SAM_hdr
*hdr
);
264 /*! Deallocates all storage used by a SAM_hdr struct.
266 * This also decrements the header reference count. If after decrementing
267 * it is still non-zero then the header is assumed to be in use by another
268 * caller and the free is not done.
270 * This is a synonym for sam_hdr_dec_ref().
272 void sam_hdr_free(SAM_hdr
*hdr
);
274 /*! Returns the current length of the SAM_hdr in text form.
276 * Call sam_hdr_rebuild() first if editing has taken place.
278 int sam_hdr_length(SAM_hdr
*hdr
);
280 /*! Returns the string form of the SAM_hdr.
282 * Call sam_hdr_rebuild() first if editing has taken place.
284 char *sam_hdr_str(SAM_hdr
*hdr
);
286 /*! Appends a formatted line to an existing SAM header.
288 * Line is a full SAM header record, eg "@SQ\tSN:foo\tLN:100", with
289 * optional new-line. If it contains more than 1 line then multiple lines
290 * will be added in order.
292 * Input text is of maximum length len or as terminated earlier by a NUL.
293 * Len may be 0 if unknown, in which case lines must be NUL-terminated.
296 * Returns 0 on success;
299 int sam_hdr_add_lines(SAM_hdr
*sh
, const char *lines
, int len
);
301 /*! Adds a single line to a SAM header.
303 * Specify type and one or more key,value pairs, ending with the NULL key.
304 * Eg. sam_hdr_add(h, "SQ", "ID", "foo", "LN", "100", NULL).
307 * Returns 0 on success;
310 int sam_hdr_add(SAM_hdr
*sh
, const char *type
, ...);
312 /*! Adds a single line to a SAM header.
314 * This is much like sam_hdr_add() but with the additional va_list
315 * argument. This is followed by specifying type and one or more
316 * key,value pairs, ending with the NULL key.
318 * Eg. sam_hdr_vadd(h, "SQ", args, "ID", "foo", "LN", "100", NULL).
320 * The purpose of the additional va_list parameter is to permit other
321 * varargs functions to call this while including their own additional
322 * parameters; an example is in sam_hdr_add_PG().
324 * Note: this function invokes va_arg at least once, making the value
325 * of ap indeterminate after the return. The caller should call
326 * va_start/va_end before/after calling this function or use va_copy.
329 * Returns 0 on success;
332 int sam_hdr_vadd(SAM_hdr
*sh
, const char *type
, va_list ap
, ...);
336 * Returns the first header item matching 'type'. If ID is non-NULL it checks
337 * for the tag ID: and compares against the specified ID.
339 * Returns NULL if no type/ID is found
341 SAM_hdr_type
*sam_hdr_find(SAM_hdr
*hdr
, char *type
,
342 char *ID_key
, char *ID_value
);
346 * As per SAM_hdr_type, but returns a complete line of formatted text
347 * for a specific head type/ID combination. If ID is NULL then it returns
348 * the first line of the specified type.
350 * The returned string is malloced and should be freed by the calling
351 * function with free().
354 * Returns NULL if no type/ID is found.
356 char *sam_hdr_find_line(SAM_hdr
*hdr
, char *type
,
357 char *ID_key
, char *ID_value
);
359 /*! Looks for a specific key in a single sam header line.
361 * If prev is non-NULL it also fills this out with the previous tag, to
362 * permit use in key removal. *prev is set to NULL when the tag is the first
363 * key in the list. When a tag isn't found, prev (if non NULL) will be the last
364 * tag in the existing list.
367 * Returns the tag pointer on success;
370 SAM_hdr_tag
*sam_hdr_find_key(SAM_hdr
*sh
,
375 /*! Adds or updates tag key,value pairs in a header line.
377 * Eg for adding M5 tags to @SQ lines or updating sort order for the
378 * @HD line (although use the sam_hdr_sort_order() function for
379 * HD manipulation, which is a wrapper around this funuction).
381 * Specify multiple key,value pairs ending in NULL.
384 * Returns 0 on success;
387 int sam_hdr_update(SAM_hdr
*hdr
, SAM_hdr_type
*type
, ...);
389 /*! Returns the sort order from the @HD SO: field */
390 enum sam_sort_order
sam_hdr_sort_order(SAM_hdr
*hdr
);
392 /*! Reconstructs the kstring from the header hash table.
394 * Returns 0 on success;
397 int sam_hdr_rebuild(SAM_hdr
*hdr
);
399 /*! Looks up a reference sequence by name and returns the numerical ID.
401 * Returns -1 if unknown reference.
403 int sam_hdr_name2ref(SAM_hdr
*hdr
, const char *ref
);
405 /*! Looks up a read-group by name and returns a pointer to the start of the
406 * associated tag list.
409 * Returns NULL on failure
411 SAM_RG
*sam_hdr_find_rg(SAM_hdr
*hdr
, const char *rg
);
413 /*! Fixes any PP links in @PG headers.
415 * If the entries are in order then this doesn't need doing, but incase
416 * our header is out of order this goes through the sh->pg[] array
417 * setting the prev_id field.
420 * Returns 0 on sucess;
421 * -1 on failure (indicating broken PG/PP records)
423 int sam_hdr_link_pg(SAM_hdr
*hdr
);
428 * If we wish complete control over this use sam_hdr_add() directly. This
429 * function uses that, but attempts to do a lot of tedious house work for
432 * - It will generate a suitable ID if the supplied one clashes.
433 * - It will generate multiple @PG records if we have multiple PG chains.
435 * Call it as per sam_hdr_add() with a series of key,value pairs ending
439 * Returns 0 on success;
442 int sam_hdr_add_PG(SAM_hdr
*sh
, const char *name
, ...);
445 * A function to help with construction of CL tags in @PG records.
446 * Takes an argc, argv pair and returns a single space-separated string.
447 * This string should be deallocated by the calling function.
450 * Returns malloced char * on success;
453 char *stringify_argv(int argc
, char *argv
[]);
459 #endif /* _SAM_HDR_H_ */