/* Copyright 2013-14. Los Alamos National Security, LLC. This material was produced
* under U.S. Government contract DE-AC52-06NA25396 for Los Alamos National
* Laboratory (LANL), which is operated by Los Alamos National Security, LLC
* for the U.S. Department of Energy. The U.S. Government has rights to use,
* reproduce, and distribute this software. NEITHER THE GOVERNMENT NOR LOS
* ALAMOS NATIONAL SECURITY, LLC MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR
* ASSUMES ANY LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified
* to produce derivative works, such modified software should be clearly marked,
* so as not to confuse it with the version available from LANL.
*
* Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software distributed
* under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
* CONDITIONS OF ANY KIND, either express or implied. See the License for the
* specific language governing permissions and limitations under the License.
*
* Under this license, it is required to include a reference to this work. We
* request that each derivative work contain a reference to LANL Copyright
* Disclosure C14043/LA-CC-14-003 so that this work's impact can be roughly
* measured. In addition, it is requested that a modifier is included as in
* the following example:
*
* //<Uses | improves on | modified from> LANL Copyright Disclosure C14043/LA-CC-14-003
*
* This is LANL Copyright Disclosure C14043/LA-CC-14-003
*/
#undef UNDEFINED
#ifdef UNDEFINED
/**
* @file compactHash.cm
* @author Peter Ahrens
* @date Thu Jun 6 2013
*/
#endif
#include "baseHash.cm"
#define COMPACT_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, SEARCH_EXP, ...)\
\
BASE_HASH_DEFINE(NAME, MODIFIER##Compact, HASH_ID, KEY_TYPE, VALUE_TYPE, KEY_VALUE_BASE_HASH_TYPES_DEFINE, COMPRESS_FUNC, COMPRESS_FUNC_DATA,,, INIT_EXP, SEARCH_EXP, KEY_VALUE_HASH_INNER_EMPTY_EXP, ##__VA_ARGS__)\
\
#define COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, SEARCH_EXP, ...)\
\
CL_HASH_KERN_DEFINE(NAME, MODIFIER##Compact, KEY_TYPE, VALUE_TYPE, KEY_VALUE_BASE_HASH_TYPES_DEFINE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, ATOMIC_CMPXCHG_HASH_READ_KEY_EXP, SEARCH_EXP, ##__VA_ARGS__)\
\
#define COMPACT_CL_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP)\
\
CL_BASE_HASH_DEFINE(NAME, MODIFIER##Compact, HASH_ID, KEY_TYPE, VALUE_TYPE, KEY_VALUE_BASE_HASH_TYPES_DEFINE, COMPRESS_FUNC, COMPRESS_FUNC_DATA,,, INIT_EXP, KEY_VALUE_CL_HASH_INNER_EMPTY_EXP)\
\
#define COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, SEARCH_EXP, ...)\
\
OPENMP_BASE_HASH_DEFINE(NAME, MODIFIER##CompactOpenMP, HASH_ID, KEY_TYPE, VALUE_TYPE, KEY_VALUE_BASE_HASH_TYPES_DEFINE, COMPRESS_FUNC, COMPRESS_FUNC_DATA,,, INIT_EXP, SEARCH_EXP, KEY_VALUE_HASH_INNER_EMPTY_EXP, ##__VA_ARGS__)\
\
#define OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER, INIT_EXP) \
((NAME##MODIFIER##Hash_TableData*)table->tableData)->numBuckets = (unsigned int)((double)numEntries / loadFactor);\
INIT_EXP\
\
#ifdef XXX
unsigned int c = COMPRESS_FUNC(((CL_GLOBAL NAME##MODIFIER##Hash_TableData*)tableData)->compressFuncData, key);\
#endif
#define OPEN_COMPACT_HASH_SEARCH_EXP(NAME, MODIFIER, COMPRESS_FUNC, COMPRESS_FUNC_DATA, READ_KEY_EXP, CL_GLOBAL, JUMP_EXP, CYCLE_EXP) \
GLOBAL NAME##MODIFIER##Hash_TableData* mytableData = (GLOBAL NAME##MODIFIER##Hash_TableData*)tableData;\
NAME##Hash_CompressLCGData compressFuncData = mytableData->compressFuncData;\
unsigned int c = COMPRESS_FUNC(compressFuncData, key);\
unsigned long int iteration = 0;\
for(;;){\
index = JUMP_EXP;\
if(READ_KEY_EXP == HASH_BUCKET_STATUS_EMPTY){\
exitCode = HASH_SEARCH_CODE_EMPTY;\
break;\
}else if(key == buckets[index].key){\
exitCode = HASH_SEARCH_CODE_MATCH;\
break;\
}else if(CYCLE_EXP){\
exitCode = HASH_EXIT_CODE_CYCLE;\
break;\
}\
iteration++;\
}\
\
#define OPEN_COMPACT_OPENMP_HASH_SEARCH_EXP(NAME, MODIFIER, COMPRESS_FUNC, COMPRESS_FUNC_DATA, READ_KEY_EXP, CL_GLOBAL, JUMP_EXP, CYCLE_EXP) \
GLOBAL NAME##MODIFIER##Hash_TableData* mytableData = (GLOBAL NAME##MODIFIER##Hash_TableData*)tableData;\
NAME##Hash_CompressLCGData compressFuncData = mytableData->compressFuncData;\
unsigned int c = COMPRESS_FUNC(compressFuncData, key);\
unsigned long int iteration = 0;\
for(;;){\
index = JUMP_EXP;\
int old_key = __sync_val_compare_and_swap(&buckets[index].key, -1, key);\
if(old_key == HASH_BUCKET_STATUS_EMPTY){\
exitCode = HASH_SEARCH_CODE_EMPTY;\
break;\
}else if(old_key == key){\
exitCode = HASH_SEARCH_CODE_MATCH;\
break;\
}else if(CYCLE_EXP){\
exitCode = HASH_EXIT_CODE_CYCLE;\
break;\
}\
iteration++;\
}\
\
#define OPEN_COMPACT_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, ...)\
\
COMPACT_HASH_DEFINE(NAME, MODIFIER##Open, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##OpenCompact, INIT_EXP), OPEN_COMPACT_HASH_SEARCH_EXP, ##__VA_ARGS__)\
#define OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, ...)\
\
COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER##Open, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, OPEN_COMPACT_HASH_SEARCH_EXP, ##__VA_ARGS__)\
\
#define OPEN_COMPACT_CL_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP)\
\
COMPACT_CL_HASH_DEFINE(NAME, MODIFIER##Open, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##OpenCompactCL, INIT_EXP))\
\
#define OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, ...)\
\
COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER##Open, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##OpenCompactOpenMP, INIT_EXP), OPEN_COMPACT_OPENMP_HASH_SEARCH_EXP, ##__VA_ARGS__)\
#define LINEAR_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER, B, CL_GLOBAL) ((B * iteration + c) % ((CL_GLOBAL NAME##MODIFIER##Hash_TableData*)tableData)->numBuckets)
#define LINEAR_OPEN_COMPACT_HASH_CYCLE_EXP (index == c && iteration > 0)
#define LINEAR_OPEN_COMPACT_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, B)\
\
OPEN_COMPACT_HASH_DEFINE(NAME, MODIFIER##Linear, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, LINEAR_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER##LinearOpenCompact, B,), LINEAR_OPEN_COMPACT_HASH_CYCLE_EXP)\
#define LINEAR_OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, B)\
\
OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER##Linear, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, LINEAR_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER##LinearOpenCompactCL, B, __global), LINEAR_OPEN_COMPACT_HASH_CYCLE_EXP)\
\
#define LINEAR_OPEN_COMPACT_CL_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP)\
\
OPEN_COMPACT_CL_HASH_DEFINE(NAME, MODIFIER##Linear, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP)\
\
#define LINEAR_OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, B)\
\
OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER##Linear, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, LINEAR_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER##LinearOpenCompactOpenMP, B,), LINEAR_OPEN_COMPACT_HASH_CYCLE_EXP)\
#define QUADRATIC_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER, A, B, CL_GLOBAL) ((A * iteration * iteration + B * iteration + c) % ((CL_GLOBAL NAME##MODIFIER##Hash_TableData*)tableData)->numBuckets)
#define QUADRATIC_OPEN_COMPACT_HASH_CYCLE_EXP(NAME, MODIFIER, CL_GLOBAL) (iteration > ((CL_GLOBAL NAME##MODIFIER##Hash_TableData*)tableData)->numBuckets)
#define QUADRATIC_OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER, INIT_EXP)\
INIT_EXP\
((NAME##MODIFIER##Hash_TableData*)table->tableData)->numBuckets = largestProthPrimeUnder(((NAME##MODIFIER##Hash_TableData*)table->tableData)->numBuckets);\
\
#define QUADRATIC_OPEN_COMPACT_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, A, B)\
\
OPEN_COMPACT_HASH_DEFINE(NAME, MODIFIER##Quadratic, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, QUADRATIC_OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##QuadraticOpenCompact, INIT_EXP), QUADRATIC_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER##QuadraticOpenCompact, A, B,), QUADRATIC_OPEN_COMPACT_HASH_CYCLE_EXP(NAME, MODIFIER##QuadraticOpenCompact,))\
\
#define QUADRATIC_OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, A, B)\
\
OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, MODIFIER##Quadratic, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, QUADRATIC_OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##QuadraticOpenCompactCL, INIT_EXP), QUADRATIC_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER##QuadraticOpenCompactCL, A, B, __global), QUADRATIC_OPEN_COMPACT_HASH_CYCLE_EXP(NAME, MODIFIER##QuadraticOpenCompactCL, __global))\
\
#define QUADRATIC_OPEN_COMPACT_CL_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP)\
\
OPEN_COMPACT_CL_HASH_DEFINE(NAME, MODIFIER##Quadratic, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, QUADRATIC_OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##QuadraticOpenCompactCL, INIT_EXP))
\
#define QUADRATIC_OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, INIT_EXP, A, B)\
\
OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, MODIFIER##Quadratic, HASH_ID, KEY_TYPE, VALUE_TYPE, COMPRESS_FUNC, COMPRESS_FUNC_DATA, QUADRATIC_OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER##QuadraticOpenCompactOpenMP, INIT_EXP), QUADRATIC_OPEN_COMPACT_HASH_JUMP_EXP(NAME, MODIFIER##QuadraticOpenCompactOpenMP, A, B,), QUADRATIC_OPEN_COMPACT_HASH_CYCLE_EXP(NAME, MODIFIER##QuadraticOpenCompactOpenMP,))\
\
#define LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, MODIFIER)\
((NAME##MODIFIER##Hash_TableData*)table->tableData)->compressFuncData.a = HASH_LCG_A;\
((NAME##MODIFIER##Hash_TableData*)table->tableData)->compressFuncData.c = HASH_LCG_C;\
((NAME##MODIFIER##Hash_TableData*)table->tableData)->compressFuncData.m = HASH_LCG_M;\
((NAME##MODIFIER##Hash_TableData*)table->tableData)->compressFuncData.n = ((NAME##MODIFIER##Hash_TableData*)table->tableData)->numBuckets;\
\
#define LCG_LINEAR_OPEN_COMPACT_HASH_DEFINE(NAME, KEY_TYPE, VALUE_TYPE, B)\
\
LINEAR_OPEN_COMPACT_HASH_DEFINE(NAME, LCG, LCG_LINEAR_OPEN_COMPACT_HASH_ID, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGLinearOpenCompact), B)\
\
#define LCG_LINEAR_OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, KEY_TYPE, VALUE_TYPE, B)\
\
LINEAR_OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, LCG, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGLinearOpenCompactCL), B)\
\
#define LCG_LINEAR_OPEN_COMPACT_CL_HASH_DEFINE(NAME, KEY_TYPE, VALUE_TYPE)\
\
LINEAR_OPEN_COMPACT_CL_HASH_DEFINE(NAME, LCG, LCG_LINEAR_OPEN_COMPACT_CL_HASH_ID, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGLinearOpenCompactCL))\
\
#define LCG_LINEAR_OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, KEY_TYPE, VALUE_TYPE, B)\
\
LINEAR_OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, LCG, LCG_LINEAR_OPEN_COMPACT_OPENMP_HASH_ID, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGLinearOpenCompactOpenMP), B)\
\
#define LCG_QUADRATIC_OPEN_COMPACT_HASH_DEFINE(NAME, KEY_TYPE, VALUE_TYPE, A, B)\
\
QUADRATIC_OPEN_COMPACT_HASH_DEFINE(NAME, LCG, LCG_QUADRATIC_OPEN_COMPACT_HASH_ID, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGQuadraticOpenCompact), A, B)\
\
#define LCG_QUADRATIC_OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, KEY_TYPE, VALUE_TYPE, A, B)\
\
QUADRATIC_OPEN_COMPACT_CL_HASH_KERN_DEFINE(NAME, LCG, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGQuadraticOpenCompactCL), A, B)\
\
#define LCG_QUADRATIC_OPEN_COMPACT_CL_HASH_DEFINE(NAME, KEY_TYPE, VALUE_TYPE)\
\
QUADRATIC_OPEN_COMPACT_CL_HASH_DEFINE(NAME, LCG, LCG_QUADRATIC_OPEN_COMPACT_CL_HASH_ID, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGQuadraticOpenCompactCL))\
\
#define LCG_QUADRATIC_OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, KEY_TYPE, VALUE_TYPE, A, B)\
\
QUADRATIC_OPEN_COMPACT_OPENMP_HASH_DEFINE(NAME, LCG, LCG_QUADRATIC_OPEN_COMPACT_OPENMP_HASH_ID, KEY_TYPE, VALUE_TYPE, NAME##Hash_CompressLCG, NAME##Hash_CompressLCGData, LCG_OPEN_COMPACT_HASH_INIT_EXP(NAME, LCGQuadraticOpenCompactOpenMP), A, B)\
\