bloodhound.h

Go to the documentation of this file.

/*  MIT License
 *
 *  Copyright (c) 2019 Gregory Meyer
 *
 *  Permission is hereby granted, free of charge, to any person
 *  obtaining a copy of this software and associated documentation
 *  files (the "Software"), to deal in the Software without
 *  restriction, including without limitation the rights to use, copy,
 *  modify, merge, publish, distribute, sublicense, and/or sell copies
 *  of the Software, and to permit persons to whom the Software is
 *  furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice (including
 *  the next paragraph) shall be included in all copies or substantial
 *  portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 *  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 *  ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 *  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 *  IN THE SOFTWARE.
 */

#ifndef BLOODHOUND_H
#define BLOODHOUND_H

#include <stddef.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct AvlTree AvlTree;

typedef struct AvlNode AvlNode;

/* int compare(const AvlNode *lhs, const AvlNode *rhs, void *arg); */
typedef int (*AvlComparator)(const AvlNode*, const AvlNode*, void*);

/* int compare(const void *lhs, const AvlNode *rhs, void *arg); */
typedef int (*AvlHetComparator)(const void*, const AvlNode*, void*);

/* void traverse(void *context, const AvlNode *node); */
typedef void (*AvlTraverseCb)(void*, const AvlNode*);

/* void traverse_mut(void *context, AvlNode *node); */
typedef void (*AvlTraverseMutCb)(void*, AvlNode*);

/* void delete(AvlNode *node, void *arg); */
typedef void (*AvlDeleter)(AvlNode*, void*);

void AvlTree_new(AvlTree *self, AvlComparator compare, void *compare_arg,
                 AvlDeleter deleter, void *deleter_arg);

void AvlTree_drop(AvlTree *self);

const AvlNode* AvlTree_get(const AvlTree *self, const void *key,
                           AvlHetComparator compare, void *arg);

AvlNode* AvlTree_get_mut(AvlTree *self, const void *key, AvlHetComparator compare, void *arg);

AvlNode* AvlTree_insert(AvlTree *self, AvlNode *node);

AvlNode* AvlTree_get_or_insert(AvlTree *self, const void *key, AvlHetComparator compare,
                               void *compare_arg, AvlNode* (*insert)(const void*, void*),
                               void *insert_arg, int *inserted);

AvlNode* AvlTree_remove(AvlTree *self, const void *key, AvlHetComparator compare, void *arg);

void AvlTree_clear(AvlTree *self);

struct AvlTree {
    AvlNode *root;
    size_t len;
    AvlComparator compare;
    void *compare_arg;
    AvlDeleter deleter;
    void *deleter_arg;
};

struct AvlNode {
    AvlNode *left;
    AvlNode *right;
    signed char balance_factor; /* one of {-2, -1, 0, 1, -2} */
};

#ifdef __cplusplus
} // extern "C"
#endif

#endif