X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fbasics.h;fp=libcds%2Fsrc%2Fbasics.h;h=0000000000000000000000000000000000000000;hb=58aa6c1117e13edd366329cdcac4ba7388faed95;hp=85bfe22e6f3b0702bcd4fc170004b0a0b79322cc;hpb=a75155efc2ed07c1907ef017360bd719a47f9c06;p=SXSI%2FXMLTree.git diff --git a/libcds/src/basics.h b/libcds/src/basics.h deleted file mode 100644 index 85bfe22..0000000 --- a/libcds/src/basics.h +++ /dev/null @@ -1,262 +0,0 @@ -/* basics.h - * Copyright (C) 2005, Rodrigo Gonzalez, all rights reserved. - * - * Some preliminary stuff - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - */ - - -#ifndef _BASICS_H -#define _BASICS_H - -#include -#include -#include -#include -#include -#include -#include -#include -#include -////using namespace std; -#include -#include - - -/** mask for obtaining the first 5 bits */ -#define mask31 0x0000001F - -/** max function */ -//#define max(x,y) ((x)>(y)?(x):(y)) -/** min function */ -//#define min(x,y) ((x)<(y)?(x):(y)) - - -/** number of bits in a uint */ -#undef W -#define W 32 - -/** W-1 */ -#undef Wminusone -#define Wminusone 31 - -/** 2W*/ -#undef WW -#define WW 64 - -/** number of bits per uchar */ -#define bitsM 8 - -/** number of bytes per uint */ -#define BW 4 - -/** uchar = unsigned char */ -#ifndef uchar -#define uchar unsigned char -#endif - -/** ushort = unsigned short */ -#ifndef ushort -#define ushort unsigned short -#endif - -/** ulong = unsigned long */ -#ifndef ulong -#define ulong unsigned long -#endif - -/** uint = unsigned int */ -#ifndef uint -#define uint unsigned int -#endif - -/** number of different uchar values 0..255 */ -#define size_uchar 256 - -/** popcount array for uchars */ -const unsigned char __popcount_tab[] = { - 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, - 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, -}; - -/** select array for uchars */ -const unsigned char select_tab[] = { - 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, - 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, -}; - -/** prev array for uchars */ -const unsigned char prev_tab[] = { - 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, -}; - - - -/** bits needed to represent a number between 0 and n */ -inline uint bits(uint n){ - uint b = 0; - while (n) { b++; n >>= 1; } - return b; -} - -/** reads bit p from e */ -#define bitget(e,p) ((((e)[(p)/W] >> ((p)%W))) & 1) - -/** sets bit p in e */ -#define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W))) - -/** cleans bit p in e */ -#define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W))) - -/** uints required to represent e integers of n bits each */ -//#define uint_len(e,n) (((e)*(n))/W+(((e)*(n))%W > 0)) -inline uint uint_len(uint e, uint n) { - return ((unsigned long long)e*n/W+((unsigned long long)e*n%W>0)); -} - -/** Retrieve a given index from array A where every value uses len bits - * @param A Array - * @param len Length in bits of each field - * @param index Position to be retrieved - */ -inline uint get_field(uint *A, uint len, uint index) { - if(len==0) return 0; - register uint i=index*len/W, j=index*len-W*i, result; - if (j+len <= W) - result = (A[i] << (W-j-len)) >> (W-len); - else { - result = A[i] >> j; - result = result | (A[i+1] << (WW-j-len)) >> (W-len); - } - return result; -} - -/** Store a given value in index into array A where every value uses len bits - * @param A Array - * @param len Length in bits of each field - * @param index Position to store in - * @param x Value to be stored - */ -inline void set_field(uint *A, uint len, uint index, uint x) { - if(len==0) return; - uint i=index*len/W, j=index*len-i*W; - uint mask = ((j+len) < W ? ~0u << (j+len) : 0) - | ((W-j) < W ? ~0u >> (W-j) : 0); - A[i] = (A[i] & mask) | x << j; - if (j+len>W) { - mask = ((~0u) << (len+j-W)); - A[i+1] = (A[i+1] & mask)| x >> (W-j); - } -} - -/** Retrieve a given bitsequence from array A - * @param A Array - * @param ini Starting position - * @param fin Retrieve until end-1 - */ -inline uint get_var_field(uint *A, uint ini, uint fin) { - if(ini==fin+1) return 0; - uint i=ini/W, j=ini-W*i, result; - uint len = (fin-ini+1); - if (j+len <= W) - result = (A[i] << (W-j-len)) >> (W-len); - else { - result = A[i] >> j; - result = result | (A[i+1] << (WW-j-len)) >> (W-len); - } - return result; -} - -/** Stores a given bitsequence into array A - * @param A Array - * @param ini Starting position - * @param fin Store until end-1 - * @param x Value to be stored - */ -inline void set_var_field(uint *A, uint ini, uint fin, uint x) { - if(ini==fin+1) return; - uint i=ini/W, j=ini-i*W; - uint len = (fin-ini+1); - uint mask = ((j+len) < W ? ~0u << (j+len) : 0) - | ((W-j) < W ? ~0u >> (W-j) : 0); - A[i] = (A[i] & mask) | x << j; - if (j+len>W) { - mask = ((~0u) << (len+j-W)); - A[i+1] = (A[i+1] & mask)| x >> (W-j); - } -} - -/** Retrieve a given index from array A where every value uses 4 bits - * @param A Array - * @param index Position to be retrieved - */ -inline uint get_field4(uint *A, uint index) { - unsigned i=index/8, j=(index&0x7)<<2; - return (A[i] << (28-j)) >> (28); -} - -/** Counts the number of 1s in x */ -inline uint popcount(int x){ - return __popcount_tab[(x >> 0) & 0xff] + __popcount_tab[(x >> 8) & 0xff] - + __popcount_tab[(x >> 16) & 0xff] + __popcount_tab[(x >> 24) & 0xff]; -} -inline unsigned int -fast_popcount(int x) -{ - uint m1 = 0x55555555; - uint m2 = 0x33333333; - uint m4 = 0x0f0f0f0f; - x -= (x >> 1) & m1; - x = (x & m2) + ((x >> 2) & m2); - x = (x + (x >> 4)) & m4; - x += x >> 8; - return (x + (x >> 16)) & 0x3f; -} - - - -/** Counts the number of 1s in the first 16 bits of x */ -inline uint popcount16(int x){ - return __popcount_tab[x & 0xff] + __popcount_tab[(x >> 8) & 0xff]; -} - -/** Counts the number of 1s in the first 8 bits of x */ -inline uint popcount8(int x){ - return __popcount_tab[x & 0xff]; -} - -#endif /* _BASICS_H */ -