KAT_INT8, // order matters as ranges of size are used in selection
KAT_INT16,
KAT_INT32,
KAT_INT64,
KAT_UINT8,
KAT_UINT16,
KAT_UINT32,
KAT_UINT64,
KAT_FLOAT16,
KAT_FLOAT32,
KAT_FLOAT64,
KAT_UNICODE,
KAT_STRING,
KAT_DTY,
KAT_DTM,
KAT_DTW,
KAT_DTD,
KAT_DTh,
KAT_DTm,
KAT_DTs,
KAT_DTms,
KAT_DTus,
KAT_DTns,
KAT_DTps,
KAT_DTfs,
KAT_DTas,
} KeysArrayType;
NPY_DATETIMEUNIT
dt_unit_from_array(PyArrayObject*a) {
// This is based on get_datetime_metadata_from_dtype in the NumPy source, but that function is private. This does not check that the dytpe is of the appropriate type.
// Based on convert_pyobject_to_datetime and related usage in datetime.c
PyArray_DatetimeMetaData*dma=&(dts->obmeta);
returndma->base;
}
KeysArrayType
at_to_kat(intarray_t, PyArrayObject*a) {
switch (array_t) {
caseNPY_INT64:
returnKAT_INT64;
caseNPY_INT32:
returnKAT_INT32;
caseNPY_INT16:
returnKAT_INT16;
caseNPY_INT8:
returnKAT_INT8;
caseNPY_UINT64:
returnKAT_UINT64;
caseNPY_UINT32:
returnKAT_UINT32;
caseNPY_UINT16:
returnKAT_UINT16;
caseNPY_UINT8:
returnKAT_UINT8;
caseNPY_FLOAT64:
returnKAT_FLOAT64;
caseNPY_FLOAT32:
returnKAT_FLOAT32;
caseNPY_FLOAT16:
returnKAT_FLOAT16;
caseNPY_UNICODE:
returnKAT_UNICODE;
caseNPY_STRING:
returnKAT_STRING;
caseNPY_DATETIME: {
NPY_DATETIMEUNITdtu=dt_unit_from_array(a);
switch (dtu) {
caseNPY_FR_Y:
returnKAT_DTY;
caseNPY_FR_M:
returnKAT_DTM;
caseNPY_FR_W:
returnKAT_DTW;
caseNPY_FR_D:
returnKAT_DTD;
caseNPY_FR_h:
returnKAT_DTh;
caseNPY_FR_m:
returnKAT_DTm;
caseNPY_FR_s:
returnKAT_DTs;
caseNPY_FR_ms:
returnKAT_DTms;
caseNPY_FR_us:
returnKAT_DTus;
caseNPY_FR_ns:
returnKAT_DTns;
caseNPY_FR_ps:
returnKAT_DTps;
caseNPY_FR_fs:
returnKAT_DTfs;
caseNPY_FR_as:
returnKAT_DTas;
caseNPY_FR_ERROR:
caseNPY_FR_GENERIC:
returnKAT_LIST; // fall back to list
}
}
default:
returnKAT_LIST;
}
}
// To determine when we can use direct array lookups, this function return 1 if we match, 0 if we do not match. Given a keys array type and the kind of lookup key, return true only for the largest KAT types.
int
kat_is_kind(KeysArrayTypekat, charkind) {
switch (kat) {
caseKAT_INT64:
// case KAT_INT32:
// case KAT_INT16:
// case KAT_INT8:
returnkind=='i';
caseKAT_UINT64:
// case KAT_UINT32:
// case KAT_UINT16:
// case KAT_UINT8:
returnkind=='u';
caseKAT_FLOAT64:
// case KAT_FLOAT32:
// case KAT_FLOAT16:
returnkind=='f';
caseKAT_UNICODE:
returnkind=='U';
caseKAT_STRING:
returnkind=='S';
caseKAT_DTY:
caseKAT_DTM:
caseKAT_DTW:
caseKAT_DTD:
caseKAT_DTh:
caseKAT_DTm:
caseKAT_DTs:
caseKAT_DTms:
caseKAT_DTus:
caseKAT_DTns:
caseKAT_DTps:
caseKAT_DTfs:
caseKAT_DTas:
returnkind=='M';
default:
return0;
}
}
// Given a KAT, determine if it matches a NumPy dt64 unit.
TableElement*table; // an array of TableElement structs
PyObject*keys;
KeysArrayTypekeys_array_type;
Py_ssize_tkeys_size;
Py_UCS4*key_buffer;
} FAMObject;
typedefenumViewKind{
ITEMS,
KEYS,
VALUES,
} ViewKind;
// Return the end pointer, or the pointer to the location after the last valid character. The end pointer minus the start pointer is the number of characters. For an empty string, all characters are NULL, and the start pointer and end pointer should be equal. NOTE: would like to use strchr(str, '\0') instead of this routine, but some buffers might not have a null terminator and stread by full to the the dt_size.
for (Py_UCS4*p=p_start+dt_size-1; p >= p_start; p--) {
if (*p!='\0') {
returnp+1; // 1 after first non-null
}
}
returnp_start;
}
staticinlinechar*
char_get_end_p(char*p_start, Py_ssize_tdt_size) {
for (char*p=p_start+dt_size-1; p >= p_start; p--) {
if (*p!='\0') {
returnp+1; // 1 after first non-null
}
}
returnp_start;
}
// This masks the input with INT64_MAX, which removes the MSB; we then cast to an int64; the range is now between 0 and INT64_MAX. We then use the MSB of the original value; if set, we negate the number, producing negative values for the upper half of the uint64 range. Note that we only need to check for hash -1 in this branch.
staticinlinePy_hash_t
uint_to_hash(npy_uint64v) {
Py_hash_thash= (Py_hash_t)(v&INT64_MAX);
if (v >> 63) {
hash=-hash;
}
if (hash==-1) { // might happen due to overflow on 32 bit systems
return-2;
}
returnhash;
}
staticinlinePy_hash_t
int_to_hash(npy_int64v) {
Py_hash_thash= (Py_hash_t)v;
if (hash==-1) {
return-2;
}
returnhash;
}
// This is a adapted from https://github.com/python/cpython/blob/ba65a065cf07a7a9f53be61057a090f7311a5ad7/Python/pyhash.c#L92
#defineHASH_MODULUS (((size_t)1 << 61) - 1)
#defineHASH_BITS 61
staticinlinePy_hash_t
double_to_hash(doublev)
{
inte, sign;
doublem;
Py_uhash_tx, y;
if (isinf(v)) {
returnv>0 ? 314159 : -314159;
}
if (isnan(v)) {
return0;
}
m=frexp(v, &e);
sign=1;
if (m<0) {
sign=-1;
m=-m;
}
x=0;
while (m) {
x= ((x << 28) &HASH_MODULUS) | x >> (HASH_BITS-28);
// the global int_cache is shared among all instances
staticPyObject*int_cache=NULL;
// NOTE: this used to be a Py_ssize_t, which can be 32 bits on some machines and might easily overflow with a few very large indices. Using an explicit 64-bit int seems safer
staticnpy_int64key_count_global=0;
// Fill the int_cache up to size_needed with PyObject ints; `size` is not the key_count_global.
staticint
int_cache_fill(Py_ssize_tsize_needed)
{
PyObject*item;
if (!int_cache) {
int_cache=PyList_New(0);
if (!int_cache) {
return-1;
}
}
for (Py_ssize_ti=PyList_GET_SIZE(int_cache); i<size_needed; i++) {
item=PyLong_FromSsize_t(i);
if (!item) {
return-1;
}
if (PyList_Append(int_cache, item)) {
Py_DECREF(item);
return-1;
}
Py_DECREF(item);
}
return0;
}
// Given the current key_count_global, remove cache elements only if the key_count is less than the the current size of the int_cache.
Py_ssize_tindex; // current index state, mutated in-place
} FAMIObject;
staticvoid
fami_dealloc(FAMIObject*self)
{
Py_DECREF(self->fam);
PyObject_Del((PyObject*)self);
}
staticFAMIObject*
fami_iter(FAMIObject*self)
{
Py_INCREF(self);
returnself;
}
// For a FAMI, Return appropriate PyObject for items, keys, and values. When values are needed they are retrieved from the int_cache. For consistency with NumPy array iteration, arrays use PyArray_ToScalar instead of PyArray_GETITEM.
// Given a key and a computed hash, return the table_pos if that hash and key are found, or if not, the first table position that has not been assigned. Return -1 on error.