<commit_before>/*
 * The contents of this file are subject to the MonetDB Public License
 * Version 1.1 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.monetdb.org/Legal/MonetDBLicense
 *
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
 * License for the specific language governing rights and limitations
 * under the License.
 *
 * The Original Code is the MonetDB Database System.
 *
 * The Initial Developer of the Original Code is CWI.
 * Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
 * Copyright August 2008-2014 MonetDB B.V.
 * All Rights Reserved.
 */

/*
 * Implementation for the column imprints index.
 * See paper:
 * Column Imprints: A Secondary Index Structure,
 * L.Sidirourgos and M.Kersten.
 */

#include "monetdb_config.h"
#include "gdk.h"
#include "gdk_private.h"
#include "gdk_imprints.h"

#define BINSIZE(B, FUNC, T) do {		\
	switch (B) {				\
		case 8: FUNC(T,8); break;	\
		case 16: FUNC(T,16); break;	\
		case 32: FUNC(T,32); break;	\
		case 64: FUNC(T,64); break;	\
		default: assert(0); break;	\
	}					\
} while (0)

/* binary search */
#define check(Z,X,W) if ((X) >= bins[W] && (X) < bins[W+1]) (Z) = W;
#define left(Z,X,W)  if ((X) < bins[W+1])
#define right(Z,X,W) if ((X) >= bins[W])

#define GETBIN64(Z,X)						\
	right(Z,X,32) {						\
		right(Z,X,48) {					\
			right(Z,X,56) {				\
				right(Z,X,60){			\
					right(Z,X,62) {		\
						Z = 62;		\
						right(Z,X,63) {	\
							Z = 63;	\
						}		\
					}			\
					check(Z,X,61)		\
					left(Z,X,60) {		\
						Z = 60;		\
					}			\
				}				\
				check(Z,X,59)			\
				left(Z,X,58) {			\
					right(Z,X,58) {		\
						Z = 58;		\
					}			\
					check(Z,X,57)		\
					left(Z,X,56) {		\
						Z = 56;		\
					}			\
				}				\
			}					\
			check(Z,X,55)				\
			left(Z,X,54) {				\
				right(Z,X,52){			\
					right(Z,X,54) {		\
						Z = 54;		\
					}			\
					check(Z,X,53)		\
					left(Z,X,52) {		\
						Z = 52;		\
					}			\
				}				\
				check(Z,X,51)			\
				left(Z,X,50) {			\
					right(Z,X,50) {		\
						Z = 50;		\
					}			\
					check(Z,X,49)		\
					left(Z,X,48) {		\
						Z = 48;		\
					}			\
				}				\
			}					\
		}						\
		check(Z,X,47)					\
		left(Z,X,46) {					\
			right(Z,X,40) {				\
				right(Z,X,44){			\
					right(Z,X,46) {		\
						Z = 46;		\
					}			\
					check(Z,X,45)		\
					left(Z,X,44) {		\
						Z = 44;		\
					}			\
				}				\
				check(Z,X,43)			\
				left(Z,X,42) {			\
					right(Z,X,42) {		\
						Z = 42;		\
					}			\
					check(Z,X,41)		\
					left(Z,X,40) {		\
						Z = 40;		\
					}			\
				}				\
			}					\
			check(Z,X,39)				\
			left(Z,X,38) {				\
				right(Z,X,36){			\
					right(Z,X,38) {		\
						Z = 38;		\
					}			\
					check(Z,X,37)		\
					left(Z,X,36) {		\
						Z = 36;		\
					}			\
				}				\
				check(Z,X,35)			\
				left(Z,X,34) {			\
					right(Z,X,34) {		\
						Z = 34;		\
					}			\
					check(Z,X,33)		\
					left(Z,X,32) {		\
						Z = 32;		\
					}			\
				}				\
			}					\
		}						\
	}							\
	check(Z,X,31)						\
	left(Z,X,30) {						\
		right(Z,X,16) {					\
			right(Z,X,24) {				\
				right(Z,X,28){			\
					right(Z,X,30) {		\
						Z = 30;		\
					}			\
					check(Z,X,29)		\
					left(Z,X,28) {		\
						Z = 28;		\
					}			\
				}				\
				check(Z,X,27)			\
				left(Z,X,26) {			\
					right(Z,X,26) {		\
						Z = 26;		\
					}			\
					check(Z,X,25)		\
					left(Z,X,24) {		\
						Z = 24;		\
					}			\
				}				\
			}					\
			check(Z,X,23)				\
			left(Z,X,22) {				\
				right(Z,X,20){			\
					right(Z,X,22) {		\
						Z = 22;		\
					}			\
					check(Z,X,21)		\
					left(Z,X,20) {		\
						Z = 20;		\
					}			\
				}				\
				check(Z,X,19)			\
				left(Z,X,18) {			\
					right(Z,X,18) {		\
						Z = 18;		\
					}			\
					check(Z,X,17)		\
					left(Z,X,16) {		\
						Z = 16;		\
					}			\
				}				\
			}					\
		}						\
		check(Z,X,15)					\
		left(Z,X,14) {					\
			right(Z,X,8) {				\
				right(Z,X,12){			\
					right(Z,X,14) {		\
						Z = 14;		\
					}			\
					check(Z,X,13)		\
					left(Z,X,12) {		\
						Z = 12;		\
					}			\
				}				\
				check(Z,X,11)			\
				left(Z,X,10) {			\
					right(Z,X,10) {		\
						Z = 10;		\
					}			\
					check(Z,X,9)		\
					left(Z,X,8) {		\
						Z = 8;		\
					}			\
				}				\
			}					\
			check(Z,X,7)				\
			left(Z,X,6) {				\
				right(Z,X,4){			\
					right(Z,X,6) {		\
						Z = 6;		\
					}			\
					check(Z,X,5)		\
					left(Z,X,4) {		\
						Z = 4;		\
					}			\
				}				\
				check(Z,X,3)			\
				left(Z,X,2) {			\
					right(Z,X,2) {		\
						Z = 2;		\
					}			\
					check(Z,X,1)		\
					left(Z,X,0) {		\
						Z = 0;		\
					}			\
				}				\
			}					\
		}						\
	}

#define GETBIN32(Z,X)					\
	right(Z,X,16) {					\
		right(Z,X,24) {				\
			right(Z,X,28){			\
				right(Z,X,30) {		\
					Z = 30;		\
					right(Z,X,31) {	\
						Z = 31;	\
					}		\
				}			\
				check(Z,X,29)		\
				left(Z,X,28) {		\
					Z = 28;		\
				}			\
			}				\
			check(Z,X,27)			\
			left(Z,X,26) {			\
				right(Z,X,26) {		\
					Z = 26;		\
				}			\
				check(Z,X,25)		\
				left(Z,X,24) {		\
					Z = 24;		\
				}			\
			}				\
		}					\
		check(Z,X,23)				\
		left(Z,X,22) {				\
			right(Z,X,20){			\
				right(Z,X,22) {		\
					Z = 22;		\
				}			\
				check(Z,X,21)		\
				left(Z,X,20) {		\
					Z = 20;		\
				}			\
			}				\
			check(Z,X,19)			\
			left(Z,X,18) {			\
				right(Z,X,18) {		\
					Z = 18;		\
				}			\
				check(Z,X,17)		\
				left(Z,X,16) {		\
					Z = 16;		\
				}			\
			}				\
		}					\
	}						\
	check(Z,X,15)					\
	left(Z,X,14) {					\
		right(Z,X,8) {				\
			right(Z,X,12){			\
				right(Z,X,14) {		\
					Z = 14;		\
				}			\
				check(Z,X,13)		\
				left(Z,X,12) {		\
					Z = 12;		\
				}			\
			}				\
			check(Z,X,11)			\
			left(Z,X,10) {			\
				right(Z,X,10) {		\
					Z = 10;		\
				}			\
				check(Z,X,9)		\
				left(Z,X,8) {		\
					Z = 8;		\
				}			\
			}				\
		}					\
		check(Z,X,7)				\
		left(Z,X,6) {				\
			right(Z,X,4){			\
				right(Z,X,6) {		\
					Z = 6;		\
				}			\
				check(Z,X,5)		\
				left(Z,X,4) {		\
					Z = 4;		\
				}			\
			}				\
			check(Z,X,3)			\
			left(Z,X,2) {			\
				right(Z,X,2) {		\
					Z = 2;		\
				}			\
				check(Z,X,1)		\
				left(Z,X,0) {		\
					Z = 0;		\
				}			\
			}				\
		}					\
	}

#define GETBIN16(Z,X)				\
	right(Z,X,8) {				\
		right(Z,X,12){			\
			right(Z,X,14) {		\
				Z = 14;		\
				right(Z,X,15) {	\
					Z = 15;	\
				}		\
			}			\
			check(Z,X,13)		\
			left(Z,X,12) {		\
				Z = 12;		\
			}			\
		}				\
		check(Z,X,11)			\
		left(Z,X,10) {			\
			right(Z,X,10) {		\
				Z = 10;		\
			}			\
			check(Z,X,9)		\
			left(Z,X,8) {		\
				Z = 8;		\
			}			\
		}				\
	}					\
	check(Z,X,7)				\
	left(Z,X,6) {				\
		right(Z,X,4){			\
			right(Z,X,6) {		\
				Z = 6;		\
			}			\
			check(Z,X,5)		\
			left(Z,X,4) {		\
				Z = 4;		\
			}			\
		}				\
		check(Z,X,3)			\
		left(Z,X,2) {			\
			right(Z,X,2) {		\
				Z = 2;		\
			}			\
			check(Z,X,1)		\
			left(Z,X,0) {		\
				Z = 0;		\
			}			\
		}				\
	}

#define GETBIN8(Z,X)				\
	right(Z,X,4){				\
		right(Z,X,6) {			\
			Z = 6;			\
			right(Z,X,7) {		\
				Z = 7;		\
			}			\
		}				\
		check(Z,X,5)			\
		left(Z,X,4) {			\
			Z = 4;			\
		}				\
	}					\
	check(Z,X,3)				\
	left(Z,X,2) {				\
		right(Z,X,2) {			\
			Z = 2;			\
		}				\
		check(Z,X,1)			\
		left(Z,X,0) {			\
			Z = 0;			\
		}				\
	}

/* end of binary search */

#define IMPS_CREATE(TYPE,B)						\
do {									\
	uint##B##_t mask, prvmask;					\
	uint##B##_t *im = (uint##B##_t *) imps;				\
	TYPE *col = (TYPE *) Tloc(b, b->batFirst);			\
	TYPE *bins = (TYPE *) inbins;					\
	prvmask = mask = 0;						\
	new = (IMPS_PAGE/sizeof(TYPE))-1;				\
	for (i = 0; i < b->batCount; i++) {				\
		if (!(i&new) && i>0) {					\
			/* same mask as previous and enough count to add */ \
			if ((prvmask == mask) &&			\
			    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) {	\
				/* not a repeat header */		\
				if (!dict[dcnt-1].repeat) {		\
					/* if compressed */		\
					if (dict[dcnt-1].cnt > 1) {	\
						/* uncompress last */	\
						dict[dcnt-1].cnt--;	\
						dcnt++; /* new header */ \
						dict[dcnt-1].cnt = 1;	\
					}				\
					/* set repeat */		\
					dict[dcnt-1].repeat = 1;	\
				}					\
				/* increase cnt */			\
				dict[dcnt-1].cnt++;			\
			} else { /* new mask (or run out of header count) */ \
				prvmask=mask;				\
				im[icnt] = mask;			\
				icnt++;					\
				if ((dcnt > 0) && !(dict[dcnt-1].repeat) && \
				    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) { \
					dict[dcnt-1].cnt++;		\
				} else {				\
					dict[dcnt].cnt = 1;		\
					dict[dcnt].repeat = 0;		\
					dict[dcnt].flags = 0;		\
					dcnt++;				\
				}					\
			}						\
			/* new mask */					\
			mask = 0;					\
		}							\
		GETBIN##B(bin,col[i]);					\
		mask = IMPSsetBit(B,mask,bin);				\
	}								\
	/* one last left */						\
	if (prvmask == mask && dcnt > 0 &&				\
	    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) {			\
		if (!dict[dcnt-1].repeat) {				\
			if (dict[dcnt-1].cnt > 1) {			\
				dict[dcnt-1].cnt--;			\
				dict[dcnt].cnt = 1;			\
				dict[dcnt].flags = 0;			\
				dcnt++;					\
			}						\
			dict[dcnt-1].repeat = 1;			\
		}							\
		dict[dcnt-1].cnt ++;					\
	} else {							\
		im[icnt] = mask;					\
		icnt++;							\
		if ((dcnt > 0) && !(dict[dcnt-1].repeat) &&		\
		    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) {		\
			dict[dcnt-1].cnt++;				\
		} else {						\
			dict[dcnt].cnt = 1;				\
			dict[dcnt].repeat = 0;				\
			dict[dcnt].flags = 0;				\
			dcnt++;						\
		}							\
	}								\
} while (0)

static int
imprints_create(BAT *b, void *inbins, bte bits,
		void *imps, BUN *impcnt, cchdc_t *dict, BUN *dictcnt)
{
	BUN i;
	BUN dcnt, icnt, new;
	bte bin = 0;
	dcnt = icnt = 0;

	switch (ATOMstorage(b->T->type)) {
	case TYPE_bte:
		BINSIZE(bits, IMPS_CREATE, bte);
		break;
	case TYPE_sht:
		BINSIZE(bits, IMPS_CREATE, sht);
		break;
	case TYPE_int:
		BINSIZE(bits, IMPS_CREATE, int);
		break;
	case TYPE_lng:
		BINSIZE(bits, IMPS_CREATE, lng);
		break;
	case TYPE_flt:
		BINSIZE(bits, IMPS_CREATE, flt);
		break;
	case TYPE_dbl:
		BINSIZE(bits, IMPS_CREATE, dbl);
		break;
	default:
		/* should never reach here */
		assert(0);
	}

	*dictcnt = dcnt;
	*impcnt = icnt;

	return 1;
}

#define FILL_HISTOGRAM(TYPE)						\
do {									\
	BUN k;								\
	TYPE *s = (TYPE *) Tloc(smp, smp->batFirst);			\
	TYPE *h = imprints->bins;					\
	if (cnt < 64-1) {						\
		TYPE max = GDK_##TYPE##_max;				\
		for (k = 0; k < cnt; k++)				\
			h[k] = s[k];					\
		while (k < (BUN) imprints->bits)			\
			h[k++] = max;					\
	} else {							\
		double y, ystep = (double) cnt / (64 - 1);		\
		for (k = 0, y = 0; (BUN) y < cnt; y += ystep, k++)	\
			h[k] = s[(BUN) y];				\
		if (k == 64 - 1) /* there is one left */		\
			h[k] = s[cnt - 1];				\
	}								\
} while (0)

BAT *
BATimprints(BAT *b)
{
	BAT *o = NULL;
	Imprints *imprints;

	assert(BAThdense(b));	/* assert void head */

	switch (ATOMstorage(b->T->type)) {
	case TYPE_bte:
	case TYPE_sht:
	case TYPE_int:
	case TYPE_lng:
	case TYPE_flt:
	case TYPE_dbl:
		break;
	default:		/* type not supported */
		GDKerror("#BATimprints: col type not "
			 "suitable for imprints index.\n");
		return NULL;	/* do nothing */
	}

	BATcheck(b, "BATimprints");

	if (VIEWtparent(b)) {
		bat p = VIEWtparent(b);
		o = b;
		b = BATmirror(BATdescriptor(p));
	}
	if (b->batFirst > 0) {
		/* no imprints if batFirst is not 0
		 * this shouldn't really happen */
		if (o)
			BBPunfix(b->batCacheid);
		return NULL;
	}

	MT_lock_set(&GDKimprintsLock(abs(b->batCacheid)), "BATimprints");
	if (b->T->imprints == NULL) {
		BAT *smp, *s;
		BUN cnt;
		str nme = BBP_physical(b->batCacheid);
		size_t pages;

		ALGODEBUG fprintf(stderr, "#BATimprints(b=%s#" BUNFMT ") %s: "<commit_msg>Better check whether imprints can be created. And it's not an error if they can't.<commit_after>/*
 * The contents of this file are subject to the MonetDB Public License
 * Version 1.1 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.monetdb.org/Legal/MonetDBLicense
 *
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
 * License for the specific language governing rights and limitations
 * under the License.
 *
 * The Original Code is the MonetDB Database System.
 *
 * The Initial Developer of the Original Code is CWI.
 * Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
 * Copyright August 2008-2014 MonetDB B.V.
 * All Rights Reserved.
 */

/*
 * Implementation for the column imprints index.
 * See paper:
 * Column Imprints: A Secondary Index Structure,
 * L.Sidirourgos and M.Kersten.
 */

#include "monetdb_config.h"
#include "gdk.h"
#include "gdk_private.h"
#include "gdk_imprints.h"

#define BINSIZE(B, FUNC, T) do {		\
	switch (B) {				\
		case 8: FUNC(T,8); break;	\
		case 16: FUNC(T,16); break;	\
		case 32: FUNC(T,32); break;	\
		case 64: FUNC(T,64); break;	\
		default: assert(0); break;	\
	}					\
} while (0)

/* binary search */
#define check(Z,X,W) if ((X) >= bins[W] && (X) < bins[W+1]) (Z) = W;
#define left(Z,X,W)  if ((X) < bins[W+1])
#define right(Z,X,W) if ((X) >= bins[W])

#define GETBIN64(Z,X)						\
	right(Z,X,32) {						\
		right(Z,X,48) {					\
			right(Z,X,56) {				\
				right(Z,X,60){			\
					right(Z,X,62) {		\
						Z = 62;		\
						right(Z,X,63) {	\
							Z = 63;	\
						}		\
					}			\
					check(Z,X,61)		\
					left(Z,X,60) {		\
						Z = 60;		\
					}			\
				}				\
				check(Z,X,59)			\
				left(Z,X,58) {			\
					right(Z,X,58) {		\
						Z = 58;		\
					}			\
					check(Z,X,57)		\
					left(Z,X,56) {		\
						Z = 56;		\
					}			\
				}				\
			}					\
			check(Z,X,55)				\
			left(Z,X,54) {				\
				right(Z,X,52){			\
					right(Z,X,54) {		\
						Z = 54;		\
					}			\
					check(Z,X,53)		\
					left(Z,X,52) {		\
						Z = 52;		\
					}			\
				}				\
				check(Z,X,51)			\
				left(Z,X,50) {			\
					right(Z,X,50) {		\
						Z = 50;		\
					}			\
					check(Z,X,49)		\
					left(Z,X,48) {		\
						Z = 48;		\
					}			\
				}				\
			}					\
		}						\
		check(Z,X,47)					\
		left(Z,X,46) {					\
			right(Z,X,40) {				\
				right(Z,X,44){			\
					right(Z,X,46) {		\
						Z = 46;		\
					}			\
					check(Z,X,45)		\
					left(Z,X,44) {		\
						Z = 44;		\
					}			\
				}				\
				check(Z,X,43)			\
				left(Z,X,42) {			\
					right(Z,X,42) {		\
						Z = 42;		\
					}			\
					check(Z,X,41)		\
					left(Z,X,40) {		\
						Z = 40;		\
					}			\
				}				\
			}					\
			check(Z,X,39)				\
			left(Z,X,38) {				\
				right(Z,X,36){			\
					right(Z,X,38) {		\
						Z = 38;		\
					}			\
					check(Z,X,37)		\
					left(Z,X,36) {		\
						Z = 36;		\
					}			\
				}				\
				check(Z,X,35)			\
				left(Z,X,34) {			\
					right(Z,X,34) {		\
						Z = 34;		\
					}			\
					check(Z,X,33)		\
					left(Z,X,32) {		\
						Z = 32;		\
					}			\
				}				\
			}					\
		}						\
	}							\
	check(Z,X,31)						\
	left(Z,X,30) {						\
		right(Z,X,16) {					\
			right(Z,X,24) {				\
				right(Z,X,28){			\
					right(Z,X,30) {		\
						Z = 30;		\
					}			\
					check(Z,X,29)		\
					left(Z,X,28) {		\
						Z = 28;		\
					}			\
				}				\
				check(Z,X,27)			\
				left(Z,X,26) {			\
					right(Z,X,26) {		\
						Z = 26;		\
					}			\
					check(Z,X,25)		\
					left(Z,X,24) {		\
						Z = 24;		\
					}			\
				}				\
			}					\
			check(Z,X,23)				\
			left(Z,X,22) {				\
				right(Z,X,20){			\
					right(Z,X,22) {		\
						Z = 22;		\
					}			\
					check(Z,X,21)		\
					left(Z,X,20) {		\
						Z = 20;		\
					}			\
				}				\
				check(Z,X,19)			\
				left(Z,X,18) {			\
					right(Z,X,18) {		\
						Z = 18;		\
					}			\
					check(Z,X,17)		\
					left(Z,X,16) {		\
						Z = 16;		\
					}			\
				}				\
			}					\
		}						\
		check(Z,X,15)					\
		left(Z,X,14) {					\
			right(Z,X,8) {				\
				right(Z,X,12){			\
					right(Z,X,14) {		\
						Z = 14;		\
					}			\
					check(Z,X,13)		\
					left(Z,X,12) {		\
						Z = 12;		\
					}			\
				}				\
				check(Z,X,11)			\
				left(Z,X,10) {			\
					right(Z,X,10) {		\
						Z = 10;		\
					}			\
					check(Z,X,9)		\
					left(Z,X,8) {		\
						Z = 8;		\
					}			\
				}				\
			}					\
			check(Z,X,7)				\
			left(Z,X,6) {				\
				right(Z,X,4){			\
					right(Z,X,6) {		\
						Z = 6;		\
					}			\
					check(Z,X,5)		\
					left(Z,X,4) {		\
						Z = 4;		\
					}			\
				}				\
				check(Z,X,3)			\
				left(Z,X,2) {			\
					right(Z,X,2) {		\
						Z = 2;		\
					}			\
					check(Z,X,1)		\
					left(Z,X,0) {		\
						Z = 0;		\
					}			\
				}				\
			}					\
		}						\
	}

#define GETBIN32(Z,X)					\
	right(Z,X,16) {					\
		right(Z,X,24) {				\
			right(Z,X,28){			\
				right(Z,X,30) {		\
					Z = 30;		\
					right(Z,X,31) {	\
						Z = 31;	\
					}		\
				}			\
				check(Z,X,29)		\
				left(Z,X,28) {		\
					Z = 28;		\
				}			\
			}				\
			check(Z,X,27)			\
			left(Z,X,26) {			\
				right(Z,X,26) {		\
					Z = 26;		\
				}			\
				check(Z,X,25)		\
				left(Z,X,24) {		\
					Z = 24;		\
				}			\
			}				\
		}					\
		check(Z,X,23)				\
		left(Z,X,22) {				\
			right(Z,X,20){			\
				right(Z,X,22) {		\
					Z = 22;		\
				}			\
				check(Z,X,21)		\
				left(Z,X,20) {		\
					Z = 20;		\
				}			\
			}				\
			check(Z,X,19)			\
			left(Z,X,18) {			\
				right(Z,X,18) {		\
					Z = 18;		\
				}			\
				check(Z,X,17)		\
				left(Z,X,16) {		\
					Z = 16;		\
				}			\
			}				\
		}					\
	}						\
	check(Z,X,15)					\
	left(Z,X,14) {					\
		right(Z,X,8) {				\
			right(Z,X,12){			\
				right(Z,X,14) {		\
					Z = 14;		\
				}			\
				check(Z,X,13)		\
				left(Z,X,12) {		\
					Z = 12;		\
				}			\
			}				\
			check(Z,X,11)			\
			left(Z,X,10) {			\
				right(Z,X,10) {		\
					Z = 10;		\
				}			\
				check(Z,X,9)		\
				left(Z,X,8) {		\
					Z = 8;		\
				}			\
			}				\
		}					\
		check(Z,X,7)				\
		left(Z,X,6) {				\
			right(Z,X,4){			\
				right(Z,X,6) {		\
					Z = 6;		\
				}			\
				check(Z,X,5)		\
				left(Z,X,4) {		\
					Z = 4;		\
				}			\
			}				\
			check(Z,X,3)			\
			left(Z,X,2) {			\
				right(Z,X,2) {		\
					Z = 2;		\
				}			\
				check(Z,X,1)		\
				left(Z,X,0) {		\
					Z = 0;		\
				}			\
			}				\
		}					\
	}

#define GETBIN16(Z,X)				\
	right(Z,X,8) {				\
		right(Z,X,12){			\
			right(Z,X,14) {		\
				Z = 14;		\
				right(Z,X,15) {	\
					Z = 15;	\
				}		\
			}			\
			check(Z,X,13)		\
			left(Z,X,12) {		\
				Z = 12;		\
			}			\
		}				\
		check(Z,X,11)			\
		left(Z,X,10) {			\
			right(Z,X,10) {		\
				Z = 10;		\
			}			\
			check(Z,X,9)		\
			left(Z,X,8) {		\
				Z = 8;		\
			}			\
		}				\
	}					\
	check(Z,X,7)				\
	left(Z,X,6) {				\
		right(Z,X,4){			\
			right(Z,X,6) {		\
				Z = 6;		\
			}			\
			check(Z,X,5)		\
			left(Z,X,4) {		\
				Z = 4;		\
			}			\
		}				\
		check(Z,X,3)			\
		left(Z,X,2) {			\
			right(Z,X,2) {		\
				Z = 2;		\
			}			\
			check(Z,X,1)		\
			left(Z,X,0) {		\
				Z = 0;		\
			}			\
		}				\
	}

#define GETBIN8(Z,X)				\
	right(Z,X,4){				\
		right(Z,X,6) {			\
			Z = 6;			\
			right(Z,X,7) {		\
				Z = 7;		\
			}			\
		}				\
		check(Z,X,5)			\
		left(Z,X,4) {			\
			Z = 4;			\
		}				\
	}					\
	check(Z,X,3)				\
	left(Z,X,2) {				\
		right(Z,X,2) {			\
			Z = 2;			\
		}				\
		check(Z,X,1)			\
		left(Z,X,0) {			\
			Z = 0;			\
		}				\
	}

/* end of binary search */

#define IMPS_CREATE(TYPE,B)						\
do {									\
	uint##B##_t mask, prvmask;					\
	uint##B##_t *im = (uint##B##_t *) imps;				\
	TYPE *col = (TYPE *) Tloc(b, b->batFirst);			\
	TYPE *bins = (TYPE *) inbins;					\
	prvmask = mask = 0;						\
	new = (IMPS_PAGE/sizeof(TYPE))-1;				\
	for (i = 0; i < b->batCount; i++) {				\
		if (!(i&new) && i>0) {					\
			/* same mask as previous and enough count to add */ \
			if ((prvmask == mask) &&			\
			    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) {	\
				/* not a repeat header */		\
				if (!dict[dcnt-1].repeat) {		\
					/* if compressed */		\
					if (dict[dcnt-1].cnt > 1) {	\
						/* uncompress last */	\
						dict[dcnt-1].cnt--;	\
						dcnt++; /* new header */ \
						dict[dcnt-1].cnt = 1;	\
					}				\
					/* set repeat */		\
					dict[dcnt-1].repeat = 1;	\
				}					\
				/* increase cnt */			\
				dict[dcnt-1].cnt++;			\
			} else { /* new mask (or run out of header count) */ \
				prvmask=mask;				\
				im[icnt] = mask;			\
				icnt++;					\
				if ((dcnt > 0) && !(dict[dcnt-1].repeat) && \
				    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) { \
					dict[dcnt-1].cnt++;		\
				} else {				\
					dict[dcnt].cnt = 1;		\
					dict[dcnt].repeat = 0;		\
					dict[dcnt].flags = 0;		\
					dcnt++;				\
				}					\
			}						\
			/* new mask */					\
			mask = 0;					\
		}							\
		GETBIN##B(bin,col[i]);					\
		mask = IMPSsetBit(B,mask,bin);				\
	}								\
	/* one last left */						\
	if (prvmask == mask && dcnt > 0 &&				\
	    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) {			\
		if (!dict[dcnt-1].repeat) {				\
			if (dict[dcnt-1].cnt > 1) {			\
				dict[dcnt-1].cnt--;			\
				dict[dcnt].cnt = 1;			\
				dict[dcnt].flags = 0;			\
				dcnt++;					\
			}						\
			dict[dcnt-1].repeat = 1;			\
		}							\
		dict[dcnt-1].cnt ++;					\
	} else {							\
		im[icnt] = mask;					\
		icnt++;							\
		if ((dcnt > 0) && !(dict[dcnt-1].repeat) &&		\
		    (dict[dcnt-1].cnt < (IMPS_MAX_CNT-1))) {		\
			dict[dcnt-1].cnt++;				\
		} else {						\
			dict[dcnt].cnt = 1;				\
			dict[dcnt].repeat = 0;				\
			dict[dcnt].flags = 0;				\
			dcnt++;						\
		}							\
	}								\
} while (0)

static int
imprints_create(BAT *b, void *inbins, bte bits,
		void *imps, BUN *impcnt, cchdc_t *dict, BUN *dictcnt)
{
	BUN i;
	BUN dcnt, icnt, new;
	bte bin = 0;
	dcnt = icnt = 0;

	switch (ATOMstorage(b->T->type)) {
	case TYPE_bte:
		BINSIZE(bits, IMPS_CREATE, bte);
		break;
	case TYPE_sht:
		BINSIZE(bits, IMPS_CREATE, sht);
		break;
	case TYPE_int:
		BINSIZE(bits, IMPS_CREATE, int);
		break;
	case TYPE_lng:
		BINSIZE(bits, IMPS_CREATE, lng);
		break;
	case TYPE_flt:
		BINSIZE(bits, IMPS_CREATE, flt);
		break;
	case TYPE_dbl:
		BINSIZE(bits, IMPS_CREATE, dbl);
		break;
	default:
		/* should never reach here */
		assert(0);
	}

	*dictcnt = dcnt;
	*impcnt = icnt;

	return 1;
}

#define FILL_HISTOGRAM(TYPE)						\
do {									\
	BUN k;								\
	TYPE *s = (TYPE *) Tloc(smp, smp->batFirst);			\
	TYPE *h = imprints->bins;					\
	if (cnt < 64-1) {						\
		TYPE max = GDK_##TYPE##_max;				\
		for (k = 0; k < cnt; k++)				\
			h[k] = s[k];					\
		while (k < (BUN) imprints->bits)			\
			h[k++] = max;					\
	} else {							\
		double y, ystep = (double) cnt / (64 - 1);		\
		for (k = 0, y = 0; (BUN) y < cnt; y += ystep, k++)	\
			h[k] = s[(BUN) y];				\
		if (k == 64 - 1) /* there is one left */		\
			h[k] = s[cnt - 1];				\
	}								\
} while (0)

BAT *
BATimprints(BAT *b)
{
	BAT *o = NULL;
	Imprints *imprints;

	assert(BAThdense(b));	/* assert void head */

	/* we only create imprints for types that look like types we know */
	if (b->ttype != ATOMstorage(b->ttype) &&
	    (ATOMnilptr(b->ttype) != ATOMnilptr(ATOMstorage(b->ttype)) ||
	     BATatoms[b->ttype].atomCmp != BATatoms[ATOMstorage(b->ttype)].atomCmp))
		return NULL;	/* doesn't look enough like base type */

	switch (ATOMstorage(b->T->type)) {
	case TYPE_bte:
	case TYPE_sht:
	case TYPE_int:
	case TYPE_lng:
	case TYPE_flt:
	case TYPE_dbl:
		break;
	default:		/* type not supported */
		return NULL;	/* do nothing */
	}

	BATcheck(b, "BATimprints");

	if (VIEWtparent(b)) {
		bat p = VIEWtparent(b);
		o = b;
		b = BATmirror(BATdescriptor(p));
	}
	if (b->batFirst > 0) {
		/* no imprints if batFirst is not 0
		 * this shouldn't really happen */
		if (o)
			BBPunfix(b->batCacheid);
		return NULL;
	}

	MT_lock_set(&GDKimprintsLock(abs(b->batCacheid)), "BATimprints");
	if (b->T->imprints == NULL) {
		BAT *smp, *s;
		BUN cnt;
		str nme = BBP_physical(b->batCacheid);
		size_t pages;

		ALGODEBUG fprintf(stderr, "#BATimprints(b=%s#" BUNFMT ") %s: "
{'fraction_non_alphanumeric': 0.20605683468160133, 'fraction_numerical': 0.04214893175689691, 'mean_word_length': 1.3094462540716612, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 57, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5271897', 'n_tokens_mistral': 16569, 'n_tokens_neox': 12386, 'n_words': 1807}