<commit_before>/*
 * Copyright (C) 2012 Mail.RU
 * Copyright (C) 2010 <NAME>
 *
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY AUTHOR 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 AUTHOR 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.
 */

#ifndef _SPTREE_H_
#define _SPTREE_H_

#include <sys/types.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */

#ifndef SPTREE_NODE_SELF
/*
 * user could suggest pointer's storage himself
 */
typedef    uint32_t spnode_t;
#define    SPNIL (0xffffffff)
#define SPTREE_MIN_SIZE 64

typedef struct sptree_node_pointers {
    uint32_t    left;   /* sizeof(spnode_t) >= sizeof(sptree_node_pointers.left) !!! */
    uint32_t    right;
} sptree_node_pointers;

#define GET_SPNODE_LEFT(snp)        ( (snp)->left )
#define SET_SPNODE_LEFT(snp, v)     (snp)->left = (v)
#define GET_SPNODE_RIGHT(snp)       ( (snp)->right )
#define SET_SPNODE_RIGHT(snp, v)    (snp)->right = (v)

#endif /* SPTREE_NODE_SELF */

#ifndef alpha
#define    alpha                       ((double)0.75)
#endif
#define    COUNTALPHA(size)            floor(log((double)(size))/log((double)1.0/alpha))

#define    _GET_SPNODE_LEFT(n)         GET_SPNODE_LEFT( t->lrpointers + (n) )
#define    _SET_SPNODE_LEFT(n, v)      SET_SPNODE_LEFT( t->lrpointers + (n), (v) )
#define    _GET_SPNODE_RIGHT(n)        GET_SPNODE_RIGHT( t->lrpointers + (n) )
#define    _SET_SPNODE_RIGHT(n, v)     SET_SPNODE_RIGHT( t->lrpointers + (n), (v) )

#define    ITHELEM(t, i)               ( (char *) (t)->members + (t)->elemsize * (i) )
#define    ELEMIDX(t, e)               ( ((e) - (t)->members) / (t)->elemsize )

/*
 * makes definition of tree with methods, name should
 * be unique across all definitions.
 *
 * Methods:
 *   void sptree_NAME_init(sptree_NAME *tree, size_t elemsize, void *array,
 *                         spnode_t array_len, spnode_t array_size,
 *                         int (*compare)(const void *key, const void *elem, void *arg),
 *                         int (*elemcompare)(const void *e1, const void *e2, void *arg),
 *                         void *arg)
 *
 *   void sptree_NAME_replace(sptree_NAME *tree, void *value, void **p_oldvalue)
 *   void sptree_NAME_delete(sptree_NAME *tree, void *value)
 *   void* sptree_NAME_find(sptree_NAME *tree, void *key)
 *
 *   spnode_t sptree_NAME_walk(sptree_NAME *t, void* array, spnode_t limit, spnode_t offset)
 *   void sptree_NAME_walk_cb(sptree_NAME *t, int (*cb)(void* cb_arg, void* elem), void *cb_arg)
 *
 *   sptree_NAME_iterator* sptree_NAME_iterator_init(sptree_NAME *t)
 *   void sptree_NAME_iterator_init_set(sptree_NAME *t, sptree_NAME_iterator **iterator, void *start)
 *   sptree_NAME_iterator* sptree_NAME_iterator_reverse_init(sptree_NAME *t)
 *   void sptree_NAME_iterator_reverse_init_set(sptree_NAME *t, sptree_NAME_iterator **iterator, void *start)
 *   void sptree_NAME_iterator_free(sptree_NAME_iterator *i)
 *
 *   void* sptree_NAME_iterator_next(sptree_NAME_iterator *i)
 *   void* sptree_NAME_iterator_reverse_next(sptree_NAME_iterator *i)
 */

#define SPTREE_DEF(name, realloc, qsort_arg)                                                         \
typedef int (*sptree_##name##_compare)(const void *, const void *, void *);               \
                                                                                          \
typedef struct sptree_##name {                                                            \
    void                    *members;                                                     \
    sptree_node_pointers    *lrpointers;                                                  \
                                                                                          \
    spnode_t                nmember;                                                      \
    spnode_t                ntotal;                                                       \
                                                                                          \<commit_msg>minor fixes<commit_after>/*
 * Copyright (C) 2012 Mail.RU
 * Copyright (C) 2010 <NAME>
 *
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY AUTHOR 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 AUTHOR 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.
 */

#ifndef _SPTREE_H_
#define _SPTREE_H_

#include <sys/types.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */

#ifndef SPTREE_NODE_SELF
/*
 * user could suggest pointer's storage himself
 */
typedef    uint32_t spnode_t;
#define    SPNIL (0xffffffff)
#define SPTREE_MIN_SIZE 64

typedef struct sptree_node_pointers {
    uint32_t    left;   /* sizeof(spnode_t) >= sizeof(sptree_node_pointers.left) !!! */
    uint32_t    right;
} sptree_node_pointers;

#define GET_SPNODE_LEFT(snp)        ( (snp)->left )
#define SET_SPNODE_LEFT(snp, v)     (snp)->left = (v)
#define GET_SPNODE_RIGHT(snp)       ( (snp)->right )
#define SET_SPNODE_RIGHT(snp, v)    (snp)->right = (v)

#endif /* SPTREE_NODE_SELF */

#ifndef alpha
#define    alpha                       ((double)0.75)
#endif
#define    COUNTALPHA(size)            floor(log((double)(size))/log((double)1.0/alpha))

#define    _GET_SPNODE_LEFT(n)         GET_SPNODE_LEFT( t->lrpointers + (n) )
#define    _SET_SPNODE_LEFT(n, v)      SET_SPNODE_LEFT( t->lrpointers + (n), (v) )
#define    _GET_SPNODE_RIGHT(n)        GET_SPNODE_RIGHT( t->lrpointers + (n) )
#define    _SET_SPNODE_RIGHT(n, v)     SET_SPNODE_RIGHT( t->lrpointers + (n), (v) )

#define    ITHELEM(t, i)               ( (char *) (t)->members + (t)->elemsize * (i) )
#define    ELEMIDX(t, e)               ( ((e) - (t)->members) / (t)->elemsize )

/*
 * makes definition of tree with methods, name should
 * be unique across all definitions.
 *
 * Methods:
 *   void sptree_NAME_init(sptree_NAME *tree, size_t elemsize, void *array,
 *                         spnode_t array_len, spnode_t array_size,
 *                         int (*compare)(const void *key, const void *elem, void *arg),
 *                         int (*elemcompare)(const void *e1, const void *e2, void *arg),
 *                         void *arg)
 *
 *   void sptree_NAME_replace(sptree_NAME *tree, void *value, void **p_oldvalue)
 *   void sptree_NAME_delete(sptree_NAME *tree, void *value)
 *   void* sptree_NAME_find(sptree_NAME *tree, void *key)
 *
 *   spnode_t sptree_NAME_walk(sptree_NAME *t, void* array, spnode_t limit, spnode_t offset)
 *   void sptree_NAME_walk_cb(sptree_NAME *t, int (*cb)(void* cb_arg, void* elem), void *cb_arg)
 *
 *   sptree_NAME_iterator* sptree_NAME_iterator_init(sptree_NAME *t)
 *   void sptree_NAME_iterator_init_set(sptree_NAME *t, sptree_NAME_iterator **iterator, void *start)
 *   sptree_NAME_iterator* sptree_NAME_iterator_reverse_init(sptree_NAME *t)
 *   void sptree_NAME_iterator_reverse_init_set(sptree_NAME *t, sptree_NAME_iterator **iterator, void *start)
 *   void sptree_NAME_iterator_free(sptree_NAME_iterator *i)
 *
 *   void* sptree_NAME_iterator_next(sptree_NAME_iterator *i)
 *   void* sptree_NAME_iterator_reverse_next(sptree_NAME_iterator *i)
 */

#define SPTREE_DEF(name, realloc, qsort_arg)                                              \
typedef int (*sptree_##name##_compare)(const void *, const void *, void *);               \
                                                                                          \
typedef struct sptree_##name {                                                            \
    void                    *members;                                                     \
    sptree_node_pointers    *lrpointers;                                                  \
                                                                                          \
    spnode_t                nmember;                                                      \
    spnode_t                ntotal;                                                       \
                                                                                          \
{'fraction_non_alphanumeric': 0.09216768322199632, 'fraction_numerical': 0.0050343692516216475, 'mean_word_length': 2.219071361794952, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, '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': '6774674', 'n_tokens_mistral': 3194, 'n_tokens_neox': 3010, 'n_words': 863}