path: root/epan/wmem/wmem_interval_tree.c

/* wmem_interval_tree.c
 * Implements an augmented interval tree
 * Based on the red-black tree implementation in epan/wmem.*
 * Copyright 2015, Matthieu coudron <matthieu.coudron@lip6.fr>
 *
 * Wireshark - Network traffic analyzer
 * By Gerald Combs <gerald@wireshark.org>
 * Copyright 1998 Gerald Combs
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include "config.h"

#include <string.h>
#include <stdio.h>
#include <glib.h>

#include "wmem_core.h"
#include "wmem_tree-int.h"
#include "wmem_strutl.h"
#include "wmem_interval_tree.h"
#include "wmem_user_cb.h"
#include <wsutil/ws_printf.h> /* ws_debug_printf */


static void
print_range(const void *value)
{
    wmem_range_t *range = (wmem_range_t *)value;
    if(!value) {
        return;
    }
    ws_debug_printf("Range: low=%" G_GUINT64_FORMAT " high=%" G_GUINT64_FORMAT " max_edge=%" G_GUINT64_FORMAT "\n", range->low, range->high, range->max_edge);
}

/**
 * In an augmented interval tree, each node saves the maximum edge of its child subtrees
 * This function compares the children max_edge with the current max_edge
 * and propagates any change to the parent nodes.
 */
static void
update_max_edge(wmem_tree_node_t *node)
{
    wmem_range_t *range;
    wmem_range_t *range_l;
    wmem_range_t *range_r;
    guint64 maxEdge  = 0;

    if(!node) {
        return ;
    }

    range = (wmem_range_t *)node->key;

    range_l = (node->left) ? (wmem_range_t *) (node->left->key) : NULL;
    range_r = (node->right) ? (wmem_range_t *) (node->right->key) : NULL;

    maxEdge = range->max_edge;

    if(range_r) {
        maxEdge = MAX(maxEdge, range_r->max_edge) ;
    }
    if(range_l) {
        maxEdge = MAX(maxEdge, range_l->max_edge) ;
    }

    /* a change was made, update the parent nodes */
    if(range->max_edge != maxEdge) {
        range->max_edge = maxEdge;
        update_max_edge(node->parent);
    }
}

gboolean
wmem_itree_range_overlap(const wmem_range_t *r1, const wmem_range_t *r2)
{
    return (r1->low <= r2->high && r2->low <= r1->high);
}

wmem_itree_t *
wmem_itree_new(wmem_allocator_t *allocator)
{
    wmem_itree_t *tree      = wmem_tree_new(allocator);
    tree->post_rotation_cb  = &update_max_edge;
    return tree;
}

gboolean
wmem_itree_is_empty(wmem_itree_t *tree)
{
    return wmem_tree_is_empty(tree);
}

static int
wmem_tree_compare_ranges(const wmem_range_t *ra, const wmem_range_t *rb)
{
    if( ra->low == rb->low) {
        return 0;
    }
    else if(ra->low < rb->low) {
        return -1;
    }
    else {
        return 1;
    }
}


void
wmem_itree_insert(wmem_itree_t *tree, const guint64 low, const guint64 high, void *data)
{
    wmem_tree_node_t *node;
    wmem_range_t *range = (wmem_range_t *)wmem_new(tree->allocator, wmem_range_t);

    g_assert(low <= high);
    range->low = low;
    range->high = high;
    range->max_edge = high;

    node = wmem_tree_insert(tree, range, data, (compare_func)wmem_tree_compare_ranges);

    /* Even If no rotations, still a need to update max_edge */
    update_max_edge(node);
}

struct point_search_result {
    wmem_tree_node_t *left;
    wmem_tree_node_t *middle;
    wmem_tree_node_t *right;
};

static void
wmem_itree_find_points_in_subtree(wmem_tree_node_t *node, guint64 low, guint64 pos, guint64 high, struct point_search_result *result)
{
    const wmem_range_t *current;

    if (!node) {
        return;
    }
    current = (wmem_range_t *)node->key;

    /* there is no child that can possibly match */
    if (low > current->max_edge) {
        return;
    }

    /* TODO implement a wmem_tree_remove method such that this check can be
     * removed. */
    if (!node->is_removed) {
        if (current->low <= pos && pos <= current->high) {
            /* overlap: point x overlaps the current interval. */
            result->middle = node;
        } else {
            if (low != pos && current->high == low) {
                /* current node is an interval at x-1 */
                result->left = node;
            }
            if (high != pos && current->low == high) {
                /* current node is an interval at x+1 */
                result->right = node;
            }
        }
    }

    wmem_itree_find_points_in_subtree(node->left, low, pos, high, result);
    wmem_itree_find_points_in_subtree(node->right, low, pos, high, result);
}


void
wmem_itree_insert_point(wmem_itree_t *tree, const guint64 pos, wmem_itree_data_callback callback)
{
    const guint64 low = pos > 0 ? pos - 1 : pos;
    const guint64 high = pos < G_MAXUINT64 ? pos + 1 : pos;
    struct point_search_result result = { NULL, NULL, NULL };
    wmem_range_t *leftKey, *rightKey;
    void *leftData = NULL, *rightData = NULL;

    /*
     * Look for intervals overlapping at x-1, x or x+1.
     * If an interval matches "x", then the interval range remains unmodified.
     * Else if it is adjacent to both x-1 or x+1, merge those intervals.
     * Else if it is adjacent to either x-1 or x+1, extend interval.
     * Otherwise add a new interval.
     */
    wmem_itree_find_points_in_subtree(tree->root, low, pos, high, &result);
    if (result.middle) {
        /* interval exists, do not replace data. */
        /* TODO maybe allow existing data to be replaced? Something like:
         * result.middle->data = callback(result.middle->data, result.middle->data) */
    } else if (result.left && result.right) {
        /* need to merge the intervals. */
        leftData = result.left->data;
        rightData = result.right->data;

        /* remove (insert NULL for) right key, it will be merged into left node. */
        leftKey = (wmem_range_t *)result.left->key;
        rightKey = (wmem_range_t *)result.right->key;
        g_assert(leftKey->high + 1 == pos);
        g_assert(rightKey->low - 1 == pos);
        const wmem_range_t oldRightRange = *rightKey;
        /* TODO use wmem_tree_remove when available. */
        wmem_tree_insert(tree, rightKey, NULL, (compare_func)wmem_tree_compare_ranges);
        leftKey->high = oldRightRange.high;
        leftKey->max_edge = oldRightRange.max_edge;
        update_max_edge(result.left);

        result.left->data = callback(leftData, rightData);
    } else if (result.left) {
        /* Interval at x-1, simply extend left node. */
        leftData = result.left->data;

        leftKey = (wmem_range_t *)result.left->key;
        g_assert(leftKey->high + 1 == pos);
        leftKey->high = pos;
        leftKey->max_edge = MAX(leftKey->max_edge, pos);
        update_max_edge(result.left);

        result.left->data = callback(leftData, NULL);
    } else if (result.right) {
        /* Interval at x+1. As tree is keyed by low, need to remove+insert. */
        rightData = result.right->data;

        rightKey = (wmem_range_t *)result.right->key;
        g_assert(rightKey->low - 1 == pos);
        const guint64 rightHigh = rightKey->high;
        /* TODO use wmem_tree_remove when available. */
        wmem_tree_insert(tree, rightKey, NULL, (compare_func)wmem_tree_compare_ranges);

        rightData = callback(NULL, rightData);
        wmem_itree_insert(tree, pos, rightHigh, rightData);
    } else {
        /* This is a new interval. */
        leftData = callback(NULL, NULL);
        wmem_itree_insert(tree, pos, pos, leftData);
    }
}


static void
wmem_itree_find_intervals_in_subtree(wmem_tree_node_t *node, wmem_range_t requested, wmem_list_t *results)
{
    const wmem_range_t* current;

    if(!node) {
        return;
    }
    current = (wmem_range_t*)node->key;

    /* there is no child that can possibly match */
    if(requested.low > current->max_edge) {
        return;
    }

    if(wmem_itree_range_overlap(current, &requested)) {
        wmem_list_prepend(results, node->data);
    }

    wmem_itree_find_intervals_in_subtree(node->left, requested, results);
    wmem_itree_find_intervals_in_subtree(node->right, requested, results);
}

wmem_list_t *
wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, guint64 low, guint64 high)
{
    wmem_list_t *results = NULL;
    wmem_range_t requested = { low, high, 0 };
    results = wmem_list_new(allocator);

    wmem_itree_find_intervals_in_subtree(tree->root, requested, results);
    return results;
}


void
wmem_print_itree(wmem_tree_t *tree)
{
    wmem_print_tree(tree, &print_range, NULL);
}

/*
 * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 *
 * Local variables:
 * c-basic-offset: 4
 * tab-width: 8
 * indent-tabs-mode: nil
 * End:
 *
 * vi: set shiftwidth=4 tabstop=8 expandtab:
 * :indentSize=4:tabSize=8:noTabs=true:
 */