<commit_before>from libc cimport stdlib
cimport numpy as cnp
import numpy as np

from extensibletype cimport *
from . import extensibletype

import intern

def roundup(x):
    "Round up to a power of two"
    x -= 1
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    x += 1
    return x

cdef PyCustomSlots_Table *allocate_hash_table(uint16_t size) except NULL:
    cdef PyCustomSlots_Table *table

    size = roundup(size)

    table = <PyCustomSlots_Table *> stdlib.calloc(
        1, sizeof(PyCustomSlots_Table) + sizeof(uint16_t) * size +
           sizeof(PyCustomSlots_Entry) * size)

    if table == NULL:
        raise MemoryError

    table.n = size
    table.b = size
    table.flags = 0

    table.entries = <PyCustomSlots_Entry *> ((<char *> &table[1]) +
                                             size * sizeof(uint16_t))

    return table


cdef class Hasher(object):
    """
    Generate a globally unique hashes for signature strings.
    """

    def hash_signature(self, signature):
        cdef uint64_t hashvalue
        # cdef bytes md5 = hashlib.md5(signature).digest()
        # (&hashvalue)[0] = (<uint64_t *> <char *> md5)[0]
        hashvalue = intern.global_intern(signature)

        return hashvalue


cdef class PerfectHashMethodTable(object):
    """
    Simple wrapper for hash-based virtual method tables.
    """

    cdef PyCustomSlots_Table *table
    cdef uint16_t *displacements
    cdef Hasher hasher

    def __init__(self, hasher):
        self.hasher = hasher

    def generate_table(self, n, ids, flags, funcs):
        cdef Py_ssize_t i
        cdef cnp.ndarray[uint64_t] hashes

        self.table = allocate_hash_table(n)
        self.displacements = <uint16_t *> (<char *> self.table +
                                               sizeof(PyCustomSlots_Table))

        hashes = np.empty(self.table.n, dtype=np.uint64)

        intern.global_intern_initialize()

        # Initialize hash table entries, build hash ids
        for i, (signature, flag, func) in enumerate(zip(ids, flags, funcs)):
            self.table.entries[i].id = self.hasher.hash_signature(signature)
            self.table.entries[i].ptr = <void *> <uintptr_t> func

            hashes[i] = self.hasher.hash_signature(signature)

        hashes[n:self.table.n] = extensibletype.draw_hashes(np.random,
                                                            self.table.n - n)

        # Perfect hash our table
        PyCustomSlots_PerfectHash(self.table, &hashes[0])

        for signature in ids:
            assert self.find_method(signature)

    def find_method(self, signature):
        """
        Find method of the given signature. Use from non-performance
        critical code.
        """
        cdef uint64_t prehash = intern.global_intern(signature)

        cdef int idx = (((prehash >> self.table.r) & self.table.m_f) ^
                        self.displacements[prehash & self.table.m_g])

        assert 0 <= idx < self.size

        if <uintptr_t> self.table.entries[idx].id != prehash:
            return None

        return (<uintptr_t> self.table.entries[idx].ptr,
                self.table.entries[idx].id & 0xFF)

    def __dealloc__(self):
        # stdlib.free(self.table)
        # self.table = NULL
        pass

    property table_ptr:
        def __get__(self):
            return <uintptr_t> self.table

    property size:
        def __get__(self):
            return self.table.n
<commit_msg>Add string method to perfect hashing vtable<commit_after>from libc cimport stdlib
cimport numpy as cnp
import numpy as np

from extensibletype cimport *
from . import extensibletype

import intern

def roundup(x):
    "Round up to a power of two"
    x -= 1
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    x += 1
    return x

cdef PyCustomSlots_Table *allocate_hash_table(uint16_t size) except NULL:
    cdef PyCustomSlots_Table *table

    size = roundup(size)

    table = <PyCustomSlots_Table *> stdlib.calloc(
        1, sizeof(PyCustomSlots_Table) + sizeof(uint16_t) * size +
           sizeof(PyCustomSlots_Entry) * size)

    if table == NULL:
        raise MemoryError

    table.n = size
    table.b = size
    table.flags = 0

    table.entries = <PyCustomSlots_Entry *> ((<char *> &table[1]) +
                                             size * sizeof(uint16_t))

    return table


cdef class Hasher(object):
    """
    Generate a globally unique hashes for signature strings.
    """

    def hash_signature(self, signature):
        cdef uint64_t hashvalue
        # cdef bytes md5 = hashlib.md5(signature).digest()
        # (&hashvalue)[0] = (<uint64_t *> <char *> md5)[0]
        hashvalue = intern.global_intern(signature)

        return hashvalue


cdef class PerfectHashMethodTable(object):
    """
    Simple wrapper for hash-based virtual method tables.
    """

    cdef PyCustomSlots_Table *table
    cdef uint16_t *displacements
    cdef Hasher hasher

    cdef object id_to_signature, signatures

    def __init__(self, hasher):
        self.hasher = hasher
        # For debugging
        self.id_to_signature = {}

    def generate_table(self, n, ids, flags, funcs, method_names=None):
        cdef Py_ssize_t i
        cdef cnp.ndarray[uint64_t] hashes

        self.table = allocate_hash_table(n)
        self.displacements = <uint16_t *> (<char *> self.table +
                                               sizeof(PyCustomSlots_Table))

        hashes = np.empty(self.table.n, dtype=np.uint64)

        intern.global_intern_initialize()

        # Initialize hash table entries, build hash ids
        for i, (signature, flag, func) in enumerate(zip(ids, flags, funcs)):
            id = self.hasher.hash_signature(signature)

            self.table.entries[i].id = id
            self.table.entries[i].ptr = <void *> <uintptr_t> func

            hashes[i] = id
            self.id_to_signature[id] = signature

        hashes[n:self.table.n] = extensibletype.draw_hashes(np.random,
                                                            self.table.n - n)

        # Perfect hash our table
        PyCustomSlots_PerfectHash(self.table, &hashes[0])

        for signature in ids:
            assert self.find_method(signature)

        # For debugging
        self.signatures = ids

    def find_method(self, signature):
        """
        Find method of the given signature. Use from non-performance
        critical code.
        """
        cdef uint64_t prehash = intern.global_intern(signature)

        cdef int idx = (((prehash >> self.table.r) & self.table.m_f) ^
                        self.displacements[prehash & self.table.m_g])

        assert 0 <= idx < self.size

        if <uintptr_t> self.table.entries[idx].id != prehash:
            return None

        return (<uintptr_t> self.table.entries[idx].ptr,
                self.table.entries[idx].id & 0xFF)

    def __str__(self):
        buf = ["PerfectHashMethodTable("]
        for i in range(self.table.n):
            id = self.table.entries[i].id
            ptr = <uintptr_t> self.table.entries[i].ptr
            sig = self.id_to_signature.get(id, "<empty>")
            s = "    id: %20d  funcptr: %20d  signature: %s" % (id, ptr, sig)
            buf.append(s)

        buf.append(")")

        return "\n".join(buf)

    def __dealloc__(self):
        # stdlib.free(self.table)
        # self.table = NULL
        pass

    property table_ptr:
        def __get__(self):
            return <uintptr_t> self.table

    property size:
        def __get__(self):
            return self.table.n

{'fraction_non_alphanumeric': 0.1025808133472367, 'fraction_numerical': 0.011209593326381648, 'mean_word_length': 2.0244383129680723, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 57, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2363391', 'n_tokens_mistral': 2452, 'n_tokens_neox': 2306, 'n_words': 588}