path: root/src-cslul/tree.c

/*

  tree.c -- AVL tree map for hashed items

  Copyright © 2021-2024 Samuel Lidén Borell <samuel@kodafritt.se>

  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 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.

*/

#include "internal.h"
#include <assert.h>
#include <string.h>
#define INTERR_TREE(errnum) MAKE_INTERR(errnum, INTERRBASE_TREE)

#define RDZERO  0
#define RDMINUS 1
#define RDPLUS  2

/** Simple locale-insensitive strcasecmp, for equal-length strings,
    that supports a-zA-Z0-9._/ */
int silly_casestrcmp(const char *a, const char *b, size_t len)
{
    while (len--) {
        char ca = *(a++) | 0x20;
        char cb = *(b++) | 0x20;
        if (ca == cb) continue;
        else if (ca < cb) return -1;
        else return 1;
    }
    return 0;
}

const char *node_nameptr(const struct TreeNode *n)
{
    return (n->length <= PTRSIZE ? n->name.copy : n->name.ptr);
}

int ident_equals(const struct TreeNode *n, const char *s, size_t len)
{
    if (n->length != len) return 0;
    return !memcmp(node_nameptr(n), s, len);
}

/**
 * Compares the node a with the sought value b
 * \return -1 if b is larger, 0 if equal, 1 if a is larger
 */
static int ncmp(const struct CSlul *ctx, const struct TreeNode *a,
                HashCode bhash, uint32 blen, const char *bname)
{
    uint32 alen;
    /* Sort by hash first */
    if (a->hashcode < bhash) return -1;
    if (a->hashcode > bhash) return 1;
    /* Sort by length second */
    alen = a->length;
    if (alen < blen) return -1;
    if (alen > blen) return 1;
    /* Sort by contents as a last resort */
    if (!ctx->case_insens) {
        return memcmp(node_nameptr(a), bname, alen);
    } else {
        return silly_casestrcmp(node_nameptr(a), bname, alen);
    }
}

/**
 * Looks up a node.
 *
 * \return A pointer the to node if it existed, or NULL if not found.
 */
struct TreeNode *tree_search(const struct CSlul *ctx,
                             const struct TreeNode *root,
                             HashCode h, uint32 len, const char *name)
{
    const struct TreeNode *n = root;
    while (n) {
        int cmp = ncmp(ctx, n, h, len, name);
        if (cmp == 0) return (struct TreeNode *)n;
        else if (cmp > 0) n = n->lower;
        else n = n->higher;
    }
    return NULL;
}

struct TreeNode *tree_search_node(const struct CSlul *ctx,
                                  const struct TreeNode *root,
                                  const struct TreeNode *n)
{
    return tree_search(ctx, root, n->hashcode, n->length, node_nameptr(n));
}

static struct TreeNode *rotate_left(struct TreeNode *n)
{
    struct TreeNode *higher = n->higher;
    n->higher = higher->lower;
    higher->lower = n;
    n->rankdelta = higher->rankdelta = RDZERO;
    return higher;
}

static struct TreeNode *rotate_right(struct TreeNode *n)
{
    struct TreeNode *lower = n->lower;
    n->lower = lower->higher;
    lower->higher = n;
    n->rankdelta = lower->rankdelta = RDZERO;
    return lower;
}

static struct TreeNode *rotate_leftright(struct TreeNode *base)
{
    struct TreeNode *l = base->lower;    /*       ___________b_   */
    struct TreeNode *lh = l->higher;     /*    __l____         h  */
    base->lower = lh->higher;            /*  ll       _lh_        */
    l->higher = lh->lower;               /*        lhl    lhh     */
    lh->higher = base;
    lh->lower = l;                       /*       becomes         */
    if (lh->rankdelta == RDMINUS) {
        base->rankdelta = RDPLUS;        /*       _____lh____     */
        l->rankdelta = RDZERO;           /*    __l__        _b_   */
    } else {                             /*  ll     lhl  lhh   h  */
        base->rankdelta = RDZERO;
        l->rankdelta = RDMINUS;
    }
    lh->rankdelta = RDZERO;
    return lh;
}

/** Performs a right-left rotation and returns the new subtree root */
static struct TreeNode *rotate_rightleft(struct TreeNode *base)
{
    struct TreeNode *h = base->higher;   /*   _b___________       */
    struct TreeNode *hl = h->lower;      /*  l         ____h__    */
    base->higher = hl->lower;            /*         _hl_      hh  */
    h->lower = hl->higher;               /*      hll    hlh       */
    hl->lower = base;
    hl->higher = h;                      /*       becomes         */
    if (hl->rankdelta == RDPLUS) {
        base->rankdelta = RDMINUS;       /*     ____hl_____       */
        h->rankdelta = RDZERO;           /*   _b_        __h__    */
    } else {                             /*  l   hll  hlh    hhh  */
        base->rankdelta = RDZERO;
        h->rankdelta = RDPLUS;
    }
    hl->rankdelta = RDZERO;
    return hl;
}

static struct TreeNode *create_node(struct CSlul *ctx,
                                    HashCode h, uint32 len, const char *name,
                                    struct TreeNode *newnode, size_t newsize)
{
    if (!newnode) {
        assert(len != USE_EXISTING);
        newnode = aallocp(ctx, newsize);
        if (!newnode) return NULL;
        if (newsize > sizeof(struct TreeNode)) {
            memset(newnode+1, 0, newsize - sizeof(struct TreeNode));
            #ifdef SLUL_DEBUG
            /* Fill the middle bytes (assuming 32 bit) to make sure we don't
               create a "valid", but not standards compliant, NULL pointer.
               (This works on 64 bit platforms too) */
            {
                char *p = (char*)&newnode[1];
                char *end = (char*)newnode +
                                (newsize - sizeof(struct TreeNode) + 1);
                for (; p < end; p++) {
                    uintptr modulo = (uintptr)p & 0x3;
                    if (modulo == 1 || modulo == 2) *p = 0x10;
                }
            }
            #endif
        }
    }
    newnode->lower = NULL;
    newnode->higher = NULL;
    if (len != USE_EXISTING) {
        assert(name != NULL);
        newnode->hashcode = h;
        newnode->rankdelta = RDZERO;
        newnode->state = TNS_INITIAL;
        newnode->length = len;
        newnode->line = ctx->tokline;
        newnode->column = ctx->tokcolumn;
        newnode->is_new = 1;
        newnode->filename = ctx->current_filename;
        if (len <= PTRSIZE) {
            memcpy(newnode->name.copy, name, len);
        } else {
            if (!(newnode->name.ptr = aalloc_memzdup(ctx, name, len)))
                return NULL;
        }
    } else {
        newnode->rankdelta = RDZERO;
        newnode->is_new = 1;
    }
    PROTECT_STRUCT(*newnode);
    return newnode;
}

/**
 * Looks up or inserts a node. If newnode is NULL, the node is allocated
 * if it does not exist.
 *
 * If len is set to USE_EXISTING, then the name, length and hashcode are
 * taken from newnode (which must be non-NULL)
 *
 * The is_new field is set to 0 if the node already existed, or
 * 1 if it was just inserted.
 *
 * \return A pointer the to node, or NULL is returned on memory
 *         allocation failure.
 */
struct TreeNode *tree_insert(struct CSlul *ctx, struct TreeNode **root,
                             HashCode h, uint32 len, const char *name,
                             struct TreeNode *newnode, size_t newsize)
{
    struct TreeNode *path[MAXDEPTH];
    struct TreeNode **lastp;
    struct TreeNode *n, *rotroot;
    struct TreeNode **inspoint;
    uint32 length;
    short depth;

    if (!*root) {
        n = create_node(ctx, h, len, name, newnode, newsize);
        if (!n) return NULL;
        *root = n;
        return n;
    }
    length = len;
    if (len == USE_EXISTING) {
        h = newnode->hashcode;
        length = newnode->length;
        name = node_nameptr(newnode);
    }
    lastp = &path[0];
    depth = 0;
    n = *root;
    /* Insert */
    for (;;) {
        int cmp;
        if (++depth >= MAXDEPTH) goto too_deep;
        *lastp = n;
        cmp = ncmp(ctx, n, h, length, name);
        if (cmp == 0) {
            n->is_new = 0;
            return n;
        } else if (cmp > 0) {
            inspoint = &n->lower;
            n = n->lower;
        } else {
            inspoint = &n->higher;
            n = n->higher;
        }
        if (!n) break;
        lastp++;
    }
    n = create_node(ctx, h, len, name, newnode, newsize);
    if (!n) return NULL; /* out of memory */
    *inspoint = n;
    newnode = n;
    /* Rebalance if necessary.
       This is done by backtracking through the path. */
    for (;;) { /* while depth > 0 */
        struct TreeNode *p = *lastp;
        assert(n->lower  || n->rankdelta != RDMINUS);
        assert(n->higher || n->rankdelta != RDPLUS);
        if (p->lower == n) { /* new node is in left/lower subtree */
            if (p->rankdelta == RDMINUS) {
                if (n->rankdelta == RDPLUS) {
                    rotroot = rotate_leftright(p);
                } else {
                    rotroot = rotate_right(p);
                }
            } else if (p->rankdelta == RDPLUS) {
                p->rankdelta = RDZERO;
                break;
            } else {
                p->rankdelta = RDMINUS;
                goto continue_up;
            }
        } else { /* new node is in right/higher subtree */
            assert(p->higher == n);
            if (p->rankdelta == RDPLUS) {
                if (n->rankdelta == RDMINUS) {
                    rotroot = rotate_rightleft(p);
                } else {
                    rotroot = rotate_left(p);
                }
            } else if (p->rankdelta == RDMINUS) {
                p->rankdelta = RDZERO;
                break;
            } else {
                p->rankdelta = RDPLUS;
                goto continue_up;
            }
        }
        if (depth <= 1) *root = rotroot;
        else if (lastp[-1]->lower == p) {
            lastp[-1]->lower = rotroot;
        } else {
            assert(lastp[-1]->higher == p);
            lastp[-1]->higher = rotroot;
        }
        break;
      continue_up:
        if (!--depth) break;
        lastp--;
        n = p;
    }
    return newnode;
  too_deep:
    error_linecol(ctx, CSLUL_E_TREETOODEEP, 0, 0);
    return NULL;
}

/**
 * Initializes an iterator and points it to the lowest/first node in the tree.
 */
void tree_iter_init(struct TreeIter *iter, struct TreeNode *root)
{
    struct TreeNode **stack = &iter->stack[0];
    struct TreeNode *n = root;
    short depth = -1;
    for (;;) {
        *stack = n;
        if (!n) break;
        depth++;
        n = n->lower;
        if (!n) break;
        stack++;
        assert(depth < MAXDEPTH);
    }
    iter->depth = depth;

}

/**
 * Iterates through the nodes in a tree. Each call returns the next node.
 *
 * \param iter Iterator
 * \param nodeptr This pointer is updated to point to the next node
 * \return 1 if a node was returned
 */
int tree_iter_next(struct TreeIter *iter, struct TreeNode **nodeptr)
{
    struct TreeNode **stack;
    struct TreeNode *n;
    short depth = iter->depth;
    if (depth < 0) return 0;
    stack = &iter->stack[depth];
    n = *stack;
    *nodeptr = n;
    /* Determine next node */
    if (n->higher) {
        n = n->higher;
        /* Go to the lowest node in the subtree */
        for (;;) {
            *stack = n;
            n = n->lower;
            if (!n) break;
            stack++;
            depth++;
            assert(depth < MAXDEPTH);
        }
    } else {
        /* Go one level up */
        depth--;
    }
    iter->depth = depth;
    return 1;
}