 +/*  bam_sam2bam.c -- format converter framework
 +
 +    Author: Takeshi Ogasawara <takeshi@jp.ibm.com>
-+	$Rev: 79 $
-+	$Date: 2016-10-18 17:33:05 +0900 (Tue, 18 Oct 2016) $
++	$Rev: 80 $
++	$Date: 2016-10-21 18:24:49 +0900 (Fri, 21 Oct 2016) $
 +
 +	*/
 +

+      bamptr_array_t * const fma = container_of(top, bamptr_array_t, bp[0]);
+
+      if (top){
+      /* sort by bamid since reads were not enqueued to bu[j] as they appear in the file when there are multiple parsers  */
+      if (fma->size >= 2) {
+	qsort(get_bamptr_at(fma, 0, 1/*unclip*/), fma->size, sizeof_bamptr(1), bamid_cmpfuncU);
+        //if (is_unclipped) {
+	//  qsort(get_bamptr_at(fma, 0, is_unclipped), fma->size, sizeof_bamptr(is_unclipped), bamid_cmpfuncC);
+	//} else {
+	//  qsort(get_bamptr_at(fma, 0, is_unclipped), fma->size, sizeof_bamptr(is_unclipped), bamid_cmpfuncU);
+	//}
+      }
+
+      for(fmx=0,bamp=top; fmx<fma->size; fmx++, bamp=get_bamptr_at(fma, fmx, 1/*unclipped*/))
+#else
+      for(bamp=top; bamp; bamp=(is_unclipped ? bamp->unclipped_next : bamp->clipped_next))
+#endif
+      {
+#if 0 // DEBUG
+{
+	        char str[256];
+	        long len;
+	        get_qname(bamptr_get_qnameid(bamp), str, sizeof(str), &len);
+	        fprintf(stderr, "(I) %.*s mate %p has_mate %d\n", (int)len, str, bamptr_get_mate(bamp), has_mate(bamptr_get_flag(bamp,0)));
+}
+#endif
+if(NULL == bamptr_get_mate(bamp)){
+  short const flag = bamptr_get_flag(bamp);
+  if(has_mate(flag)
+    && (0 == (flag & BAM_FSECONDARY)) // skip not-primary alignments (e.g., if there are pri1, pri2, and sec1 alignments, either pri1-pri2 or sec1-pri2 are paired, but sec1-pri2 is ignored) 
+    ){
+	uint64_t const qnameid = bamptr_get_qnameid(bamp);
+	uint32_t const idx0 = qnameid % hash_size;
+/*
+        TODO:
+          Cache collisions rarely happen with our test cases if hash table slots are cleared when mates are found on the slots.
+          However, hash functions should be modified if mate finding is slow because of hash collisions.
+	// uint32_t const idx2 = 7 - (qnameid % 7);	// second hash func
+*/
+	uint32_t const idx2 = 1;			// second hash func
+	uint32_t idx = idx0;
+        long cmpxchg = 0;
+//#define PROF_COLLISION
+#if defined(PROF_COLLISION)
+{{{
+long n_collision = 0;
+}}}
+#endif
+	do {
+	  bamptr_t * hash_ent = ma[idx];
+	  if (NULL == hash_ent) {
+	    // no bamptr with the same qnameid found until an empty slot is reached
+            if (__sync_bool_compare_and_swap(&ma[idx],NULL,bamp)) {
+              cmpxchg = 1;
+	      break;
+            }
+	    // cmpxchg failed -> the slot was updated by other thread 
+	    hash_ent = ma[idx];
+          }
+	  if (qnameid == bamptr_get_qnameid(hash_ent)) {
+            // check if one points to the other
+	    if(bamptr_get_tid(hash_ent,1) == bamptr_get_tid(bamp,0) && bamptr_get_pos(hash_ent,1) == bamptr_get_pos(bamp,0) &&
+              bamptr_get_tid(bamp,1) == bamptr_get_tid(hash_ent,0) && bamptr_get_pos(bamp,1) == bamptr_get_pos(hash_ent,0)) { 
+              ma[idx] = 0; // clear the slot to reduce collision frequency
+	      bamptr_set_mate(hash_ent, bamp);
+	      bamptr_set_mate(bamp, hash_ent);
+	    } else {
+	      char str[256];
+	      long len;
+	      get_qname(qnameid, str, sizeof(str), &len);
+	      fprintf(stderr, "(W) two alignments (with paried flag) have the same qnameid but do not point to each other: %.*s tid1 %d pos1 %d mtid1 %d mpos1 %d *** tid2 %d pos2 %d mtid2 %d mpos2 %d\n", (int)len, str,
+			bamptr_get_tid(hash_ent,0), bamptr_get_pos(hash_ent,0), bamptr_get_tid(hash_ent,1), bamptr_get_pos(hash_ent,1),
+			bamptr_get_tid(bamp,0), bamptr_get_pos(bamp,0), bamptr_get_tid(bamp,1), bamptr_get_pos(bamp,1));
+	    }
+	    break;
+	  }
+	  // collision
+#if defined(PROF_COLLISION)
+{{{
+//char qname[128], qname2[128];
+//bamptr_get_qname(hash_ent, qname, sizeof(qname));
+//bamptr_get_qname(bamp, qname2, sizeof(qname2));
+//fprintf(stderr, "collision %s %s hash_size 0x%x idx0 0x%x idx 0x%x\n", qname, qname2, hash_size, idx0, idx);
+n_collision ++;
+}}}
+#endif
+	  idx = (idx + idx2) % hash_size;
+	} while (idx != idx0);
+#if defined(PROF_COLLISION)
+{{{
+static uint64_t g_n_collision = 0;
+static uint64_t g_n_hashing = 0;
+__atomic_fetch_add(&g_n_collision, n_collision, __ATOMIC_RELAXED);
+__atomic_fetch_add(&g_n_hashing, 1, __ATOMIC_RELAXED);
+if (0 == (g_n_hashing & 0xffff)) {
+fprintf(stderr, "hashing %ld collision rate %f\n", g_n_hashing, g_n_collision*1.0/g_n_hashing);
+}
+}}}
+#endif
+
+if (NULL == bamptr_get_mate(bamp) && 0 == cmpxchg) {
+int i;
+int found = -1;
+for(i=0; i<hash_size; i++) {
+if (ma[i] && qnameid == bamptr_get_qnameid(ma[i])) {
+  found = i;
+  break;
+}
+}
+char qname[128];
+bamptr_get_qname(bamp, qname, sizeof(qname));
+if (-1 == found) {
+fprintf(stderr, "(W) mate not found %s flag %d tid %d pos %d\n", qname, bamptr_get_flag(bamp), bamptr_get_tid(bamp,0), bamptr_get_pos(bamp,0));
+} else {
+fprintf(stderr, "(W) mate@%d missed (orig %d) %s flag %d tid %d pos %d\n", found, idx0, qname, bamptr_get_flag(bamp), bamptr_get_tid(bamp,0), bamptr_get_pos(bamp,0));
+}
+}
+#if 0
+/*
+if(0==memcmp("20GAVAAXX100126:4:48:6445:78655",dump_bamptr_get_qname(bamp,0),strlen("20GAVAAXX100126:4:48:6445:78655")) ||
+   0==memcmp("20FUKAAXX100202:2:3:20926:186385",dump_bamptr_get_qname(bamp,0),strlen("20FUKAAXX100202:2:3:20926:186385"))){
+fprintf(stderr, "(**) %s qnameid %d \n", dump_bamptr_get_qname(bamp,0), idx);
+} */
+        
+        if (__sync_bool_compare_and_swap(&ma[idx],NULL,bamp)) {
+	  // no other thread has written bamp to ma[idx]
+//if(bamptr_get_pos(bamp, 0)+1 == debug_pos){
+//fprintf(stderr, "mate_finder[%d] (%d,%d) [1st] qnameid %d bamp %p %s flag %d pos %d\n", tidx, i, j, idx, bamp, dump_bamptr_get_qname(bamp,0), bamptr_get_flag(bamp, 0), bamptr_get_pos(bamp, 0));
+//}
+	} else {
+	  // this/another thread has written bamp to ma[idx] <== mate
+	  bamptr_t * const mate = ma[idx]; 
+//if(bamptr_get_pos(bamp, 0)+1 == debug_pos || bamptr_get_pos(mate, 0)+1 == debug_pos){
+//fprintf(stderr, "mate_finder[%d] (%d,%d) [2nd] qnameid %d bamp %p %s flag %d pos %d\n", tidx, i, j, idx, bamp, dump_bamptr_get_qname(bamp,0), bamptr_get_flag(bamp, 0), bamptr_get_pos(bamp, 0));
+//}
+/*
+if(0==memcmp("20GAVAAXX100126:4:48:6445:78655",dump_bamptr_get_qname(bamp,0),strlen("20GAVAAXX100126:4:48:6445:78655")) ||
+   0==memcmp("20FUKAAXX100202:2:3:20926:186385",dump_bamptr_get_qname(bamp,0),strlen("20FUKAAXX100202:2:3:20926:186385"))){
+fprintf(stderr, "(**) mate %s qnameid %d \n", dump_bamptr_get_qname(mate,0), idx);
+} */
+	  bamptr_set_mate(mate, bamp);
+	  bamptr_set_mate(bamp, mate);
+	}
+#endif
+  }
+}
+      }
+#if defined(BAMP_ARRAY)
+      }
+#endif
+    }
+    }
+  }
+}
+
+static void *mt_mate_finder(void *data) {

# DEALINGS IN THE SOFTWARE.
diff -uprN -x '*_Jul11' -x 'ibm_*' -x 'Numer*' -x a.out -x '#*#' -x version.h -x q -x '*~' -x '*.c.*' -x '*.a' -x .git -x .svn -x '*.MIT' 00_svn_r2/samtools-2015-08-19/samtools/bam_sam2bam.c ../files/samtools/bam_sam2bam.c
--- 00_svn_r2/samtools-2015-08-19/samtools/bam_sam2bam.c	1970-01-01 09:00:00.000000000 +0900
+++ ../files/samtools/bam_sam2bam.c	2016-10-21 18:24:50.175316172 +0900
@@ -0,0 +1,7763 @@
+#define _BAM_SAM2BAM_C
+/*  bam_sam2bam.c
+
