<commit_before>/******************************************************************************/
/*          pfixtools: a collection of postfix related tools                  */
/*          ~~~~~~~~~                                                         */
/*  ________________________________________________________________________  */
/*                                                                            */
/*  Redistribution and use in source and binary forms, with or without        */
/*  modification, are permitted provided that the following conditions        */
/*  are met:                                                                  */
/*                                                                            */
/*  1. Redistributions of source code must retain the above copyright         */
/*     notice, this list of conditions and the following disclaimer.          */
/*  2. Redistributions in binary form must reproduce the above copyright      */
/*     notice, this list of conditions and the following disclaimer in the    */
/*     documentation and/or other materials provided with the distribution.   */
/*  3. The names of its contributors may not be used to endorse or promote    */
/*     products derived from this software without specific prior written     */
/*     permission.                                                            */
/*                                                                            */
/*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
/*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
/*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
/*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
/*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
/*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
/*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
/*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
/*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
/*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
/*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
/******************************************************************************/

/*
 * Copyright © 2008 <NAME>
 */

#include "array.h"
#include "str.h"
#include "trie.h"

typedef struct trie_entry_t trie_entry_t;

struct trie_entry_t {
    int32_t  c_offset;
    int32_t  c_len;

    int32_t children_offset;
    int32_t children_len;
};
#define TRIE_ENTRY_INIT { 0, 0, 0, 0 }
ARRAY(trie_entry_t)

struct trie_t {
    A(trie_entry_t) entries;
    A(char)         c;
    A(char)         keys;
    A(int)          keys_offset;

    bool locked;
};

trie_t *trie_new(void)
{
    return p_new(trie_t, 1);
}

static inline void trie_cleanup_build_data(trie_t *trie)
{
    array_wipe(trie->keys);
    array_wipe(trie->keys_offset);
}

void trie_delete(trie_t **trie)
{
    if (*trie) {
        trie_cleanup_build_data(*trie);
        trie_unlock(*trie);
        array_wipe((*trie)->entries);
        array_wipe((*trie)->c);
        p_delete(trie);
    }
}

/** Check that the given entry is a prefix for the given key.
 */
static inline bool trie_entry_c_match(const trie_t *trie,
                                      const trie_entry_t *entry,
                                      const char *key, int *pos)
{
    const char *c = array_ptr(trie->c, entry->c_offset);
    int i = 0;
    for (i = 0 ; i < entry->c_len ; ++i) {
        if (key[i] != c[i]) {
            if (pos) {
                *pos = i;
            }
            return false;
        }
    }
    if (pos) {
        *pos = i;
    }
    return true;
}

static inline bool trie_entry_match(const trie_t *trie,
                                    const trie_entry_t *entry, const char *key)
{
    return !!(strcmp(array_ptr(trie->c, entry->c_offset), key) == 0);
}

static inline bool trie_entry_is_leaf(const trie_entry_t *entry)
{
    return entry->children_len == 0;
}

/** Lookup for a child of entry matching the given entry at the given pos.
 * Only the first character of the children is taken into account in the
 * lookup. The current entry is assumed to match the key.
 */
static inline trie_entry_t* trie_entry_child(const trie_t *trie,
                                             const trie_entry_t* entry,
                                             const char *key)
{
    int start = entry->children_offset;
    int end   = start + entry->children_len;
    const char c = *key;

    while (start < end) {
        int mid = (start + end) / 2;
        trie_entry_t* child = array_ptr(trie->entries, mid);
        const char c2 = array_elt(trie->c, child->c_offset);

        if (child->c_len) {
            if (c2 == c) {
                return child;
            }
            if (c < c2) {
                end = mid;
            } else {
                start = mid + 1;
            }
        } else {
            abort();
        }
    }
    return NULL;
}

static inline int trie_entry_new(trie_t *trie)
{
    const trie_entry_t e = TRIE_ENTRY_INIT;
    array_add(trie->entries, e);
    return trie->entries.len;
}

static inline int trie_add_leaf(trie_t *trie, const char *key)
{
    trie_entry_t *entry;<commit_msg>Fix off-by-one.<commit_after>/******************************************************************************/
/*          pfixtools: a collection of postfix related tools                  */
/*          ~~~~~~~~~                                                         */
/*  ________________________________________________________________________  */
/*                                                                            */
/*  Redistribution and use in source and binary forms, with or without        */
/*  modification, are permitted provided that the following conditions        */
/*  are met:                                                                  */
/*                                                                            */
/*  1. Redistributions of source code must retain the above copyright         */
/*     notice, this list of conditions and the following disclaimer.          */
/*  2. Redistributions in binary form must reproduce the above copyright      */
/*     notice, this list of conditions and the following disclaimer in the    */
/*     documentation and/or other materials provided with the distribution.   */
/*  3. The names of its contributors may not be used to endorse or promote    */
/*     products derived from this software without specific prior written     */
/*     permission.                                                            */
/*                                                                            */
/*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
/*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
/*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
/*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
/*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
/*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
/*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
/*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
/*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
/*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
/*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
/******************************************************************************/

/*
 * Copyright © 2008 <NAME>
 */

#include "array.h"
#include "str.h"
#include "trie.h"

typedef struct trie_entry_t trie_entry_t;

struct trie_entry_t {
    int32_t  c_offset;
    int32_t  c_len;

    int32_t children_offset;
    int32_t children_len;
};
#define TRIE_ENTRY_INIT { 0, 0, 0, 0 }
ARRAY(trie_entry_t)

struct trie_t {
    A(trie_entry_t) entries;
    A(char)         c;
    A(char)         keys;
    A(int)          keys_offset;

    bool locked;
};

trie_t *trie_new(void)
{
    return p_new(trie_t, 1);
}

static inline void trie_cleanup_build_data(trie_t *trie)
{
    array_wipe(trie->keys);
    array_wipe(trie->keys_offset);
}

void trie_delete(trie_t **trie)
{
    if (*trie) {
        trie_cleanup_build_data(*trie);
        trie_unlock(*trie);
        array_wipe((*trie)->entries);
        array_wipe((*trie)->c);
        p_delete(trie);
    }
}

/** Check that the given entry is a prefix for the given key.
 */
static inline bool trie_entry_c_match(const trie_t *trie,
                                      const trie_entry_t *entry,
                                      const char *key, int *pos)
{
    const char *c = array_ptr(trie->c, entry->c_offset);
    int i = 0;
    for (i = 0 ; i < entry->c_len ; ++i) {
        if (key[i] != c[i]) {
            if (pos) {
                *pos = i;
            }
            return false;
        }
    }
    if (pos) {
        *pos = i;
    }
    return true;
}

static inline bool trie_entry_match(const trie_t *trie,
                                    const trie_entry_t *entry, const char *key)
{
    return !!(strcmp(array_ptr(trie->c, entry->c_offset), key) == 0);
}

static inline bool trie_entry_is_leaf(const trie_entry_t *entry)
{
    return entry->children_len == 0;
}

/** Lookup for a child of entry matching the given entry at the given pos.
 * Only the first character of the children is taken into account in the
 * lookup. The current entry is assumed to match the key.
 */
static inline trie_entry_t* trie_entry_child(const trie_t *trie,
                                             const trie_entry_t* entry,
                                             const char *key)
{
    int start = entry->children_offset;
    int end   = start + entry->children_len;
    const char c = *key;

    while (start < end) {
        int mid = (start + end) / 2;
        trie_entry_t* child = array_ptr(trie->entries, mid);
        const char c2 = array_elt(trie->c, child->c_offset);

        if (child->c_len) {
            if (c2 == c) {
                return child;
            }
            if (c < c2) {
                end = mid;
            } else {
                start = mid + 1;
            }
        } else {
            abort();
        }
    }
    return NULL;
}

static inline int trie_entry_new(trie_t *trie)
{
    const trie_entry_t e = TRIE_ENTRY_INIT;
    array_add(trie->entries, e);
    return trie->entries.len - 1;
}

static inline int trie_add_leaf(trie_t *trie, const char *key)
{
    trie_entry_t *entry;
{'fraction_non_alphanumeric': 0.12079062957540264, 'fraction_numerical': 0.005398975109809663, 'mean_word_length': 1.733616808404202, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 48, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3117093', 'n_tokens_mistral': 3111, 'n_tokens_neox': 2956, 'n_words': 963}