pico_qt.h

Go to the documentation of this file.

 
#ifndef PICO_QT_H
#define PICO_QT_H
 
#include <stdbool.h>
#include <stdint.h>
 
#ifdef __cplusplus
extern "C" {
#endif
 
#ifdef PICO_QT_USE_DOUBLE
typedef double qt_float;
#else
typedef float  qt_float;
#endif
 
// Node value default type
#ifndef PICO_QT_VALUE_TYPE
#define PICO_QT_VALUE_TYPE uint32_t
#endif
 
typedef PICO_QT_VALUE_TYPE qt_value_t;
 
typedef struct qt_t qt_t;
 
typedef struct
{
    qt_float x, y, w, h;
} qt_rect_t;
 
qt_rect_t qt_make_rect(qt_float x, qt_float y, qt_float w, qt_float h);
 
qt_t* qt_create(qt_rect_t bounds, int max_depth, void* mem_ctx);
 
void qt_destroy(qt_t* qt);
 
void qt_reset(qt_t* qt);
 
void qt_insert(qt_t* qt, qt_rect_t bounds, qt_value_t value);
 
bool qt_remove(qt_t* qt, qt_value_t value);
 
qt_value_t* qt_query(const qt_t* qt, qt_rect_t area, int* size);
 
qt_rect_t* qt_grid_rects(const qt_t* qt, int* size);
 
void qt_free(qt_t* qt, void* array);
 
void qt_clear(qt_t* qt);
 
void qt_clean(qt_t* qt);
 
#ifdef __cplusplus
}
#endif
 
#endif // PICO_QT_H
 
#ifdef PICO_QT_IMPLEMENTATION
 
/*=============================================================================
 * Macros and constants
 *============================================================================*/
 
#ifdef NDEBUG
    #define PICO_QT_ASSERT(expr) ((void)0)
#else
    #ifndef PICO_QT_ASSERT
        #include <assert.h>
        #define PICO_QT_ASSERT(expr) (assert(expr))
    #endif
#endif
 
#if !defined(PICO_QT_MALLOC) || !defined(PICO_QT_REALLOC) || !defined(PICO_QT_FREE)
    #include <stdlib.h>
    #define PICO_QT_MALLOC(size, ctx)       (malloc(size))
    #define PICO_QT_REALLOC(ptr, size, ctx) (realloc(ptr, size))
    #define PICO_QT_FREE(ptr, ctx)          (free(ptr))
#endif
 
#ifndef PICO_QT_MEMCPY
    #include <string.h>
    #define PICO_QT_MEMCPY memcpy
#endif
 
#ifndef PICO_QT_MEMSET
    #include <string.h>
    #define PICO_QT_MEMSET memset
#endif
 
#ifndef PICO_QT_BLOCK_SIZE
    #define PICO_QT_BLOCK_SIZE 128
#endif
 
/*=============================================================================
 * Internal aliases
 *============================================================================*/
 
#define QT_ASSERT   PICO_QT_ASSERT
#define QT_MEMCPY   PICO_QT_MEMCPY
#define QT_MEMSET   PICO_QT_MEMSET
#define QT_MALLOC   PICO_QT_MALLOC
#define QT_REALLOC  PICO_QT_REALLOC
#define QT_FREE     PICO_QT_FREE
 
/*=============================================================================
 * Internal data structures
 *============================================================================*/
 
// An optional empty macro used to markup dynamic arrays. This is useful to help remind
// us that a particular pointer is a dynamic array, and not merely a pointer.
#define qt_array
 
typedef struct qt_node_t qt_node_t;
 
typedef struct qt_array_header_t
{
    int capacity;
    int size;
    char* data;
    uint32_t cookie;
} qt_array_header_t;
 
typedef struct
{
    qt_rect_t  bounds;
    qt_value_t value;
} qt_item_t;
 
struct qt_node_t
{
    int        depth;
    int        max_depth;
    qt_rect_t  bounds[4];
    qt_node_t* nodes[4];
    qt_array qt_item_t* items;
};
 
typedef union qt_unode_t
{
    qt_node_t node;
    union qt_unode_t* next;
} qt_unode_t;
 
typedef struct qt_node_allocator_t
{
    qt_unode_t* free_list;
    qt_array qt_unode_t** blocks;
} qt_node_allocator_t;
 
struct qt_t
{
    qt_rect_t  bounds;
    qt_node_t* root;
    void*      mem_ctx;
 
    // A custom allocator is used here to allocate individual nodes.
    // This attempts to pack all the nodes together in memory to try and
    // keep them in similar cache lines. This is slightly superior to calling
    // `QT_MALLOC` once per node, where traversing the tree (if cold and not
    // currently in the CPU cache) would incur a cache miss for every single
    // node no matter what.
    qt_node_allocator_t allocator;
};
 
/*=============================================================================
 * Internal macros
 *============================================================================*/
 
// Fetches the header `qt_array_header_t` of a dynamic array.
#define qt_hdr(a) ((qt_array_header_t*)a - 1)
 
// Helper to assert this pointer is indeed a dynamic array.
// Like a "canary in the coal mine".
#ifdef NDEBUG
    #define QT_ARRAY_CANARY(a) ((void)0)
#else
    #define QT_ARRAY_CANARY(a) ((a) ? QT_ASSERT(qt_hdr(a)->cookie == QT_ARRAY_COOKIE) : (void)0)
#endif
 
// A magic number for `QT_ARRAY_CANARY`.
#define QT_ARRAY_COOKIE 0xE6F7E359
 
// Returns the number of elements in the array.
// This is a proper l-value, so you can do e.g. qt_array_size(a)--
#define qt_array_len(a) (qt_hdr(a)->size)
 
// Returns the number of elements in the array.
// Passing in NULL will return 0.
#define qt_array_size(a) (QT_ARRAY_CANARY(a), a ? qt_hdr(a)->size : 0)
 
// Returns the capacity of the array.
#define qt_array_capacity(a) (QT_ARRAY_CANARY(a), (a) ? qt_hdr(a)->capacity : 0)
 
// Makes sure the capacity of the array can fit `n` elements.
#define qt_array_fit(ctx, a, n) ((n) <= qt_array_capacity(a) ? 0 : (*(void**)&(a) = qt_array_fit_impl((a), (n), sizeof(*a), (ctx))))
 
// Pushes an element onto the array. Will resize itself as necessary.
#define qt_array_push(ctx, a , ...) (QT_ARRAY_CANARY(a), qt_array_fit((ctx), (a), 1 + ((a) ? qt_array_size(a) : 0)), (a)[qt_array_len(a)++] = (__VA_ARGS__))
 
// Clears the array.
#define qt_array_clear(a) (QT_ARRAY_CANARY(a), a ? (void)(qt_array_len(a) = 0) : (void)0)
 
// Free's up a dynamic array.
#define qt_array_destroy(ctx, a) (QT_ARRAY_CANARY(a), a ? QT_FREE(qt_hdr(a), (ctx)) : (void)0, a = NULL)
 
// Overwrites the item at the index with the item at the end of the array.
// This is fast, but it changes the order of the array Fortunately, order
// doesn't matter in this case.
#define qt_array_remove(a, i) (QT_ARRAY_CANARY(a), a[i] = a[--qt_array_len(a)])
 
/*=============================================================================
 * Internal function declarations
 *============================================================================*/
 
static bool qt_rect_contains(const qt_rect_t* r1, const qt_rect_t* r2);
static bool qt_rect_overlaps(const qt_rect_t* r1, const qt_rect_t* r2);
 
static void* qt_array_fit_impl(const void* array, int new_size, size_t element_size, void* mem_ctx);
 
static qt_node_t* qt_node_alloc(qt_t* qt);
static void qt_node_free(qt_t* qt, qt_node_t* node);
 
static qt_node_t* qt_node_create(qt_t* qt, qt_rect_t bounds, int depth, int max_depth);
static void qt_node_destroy(qt_t* qt, qt_node_t* node);
static void qt_node_insert(qt_t* qt, qt_node_t* node, const qt_rect_t* bounds, qt_value_t value);
static bool qt_node_remove(qt_node_t* node, qt_value_t value);
 
static qt_array qt_value_t* qt_node_query(const qt_t* qt, const qt_node_t* node, const qt_rect_t* area, qt_array qt_value_t* values);
static void qt_node_clear(qt_node_t* node);
 
static qt_array qt_item_t* qt_node_all_items(const qt_t* qt, const qt_node_t* node, qt_array qt_item_t* items);
static qt_array qt_value_t* qt_node_all_values(const qt_t* qt, const qt_node_t* node, qt_array qt_value_t* values);
static qt_array qt_rect_t* qt_node_all_grid_rects(const qt_t* qt, const qt_node_t* node, qt_array qt_rect_t* rects);
 
/*=============================================================================
 * Public API implementation
 *============================================================================*/
 
qt_t* qt_create(qt_rect_t bounds, int max_depth, void* mem_ctx)
{
    qt_t* qt = (qt_t*)QT_MALLOC(sizeof(qt_t), mem_ctx);
 
    QT_MEMSET(qt, 0, sizeof(*qt));
 
    if (!qt)
        return NULL;
 
    qt->bounds = bounds;
    qt->root = qt_node_create(qt, bounds, 0, max_depth);
 
    qt->mem_ctx = mem_ctx;
 
    return qt;
}
 
void qt_destroy(qt_t* qt)
{
    QT_ASSERT(qt);
 
    qt_node_destroy(qt, qt->root);
 
    for (int i = 0; i < qt_array_size(qt->allocator.blocks); i++)
    {
        QT_FREE(qt->allocator.blocks[i], qt->mem_ctx);
    }
 
    qt_array_destroy(qt->mem_ctx, qt->allocator.blocks);
    QT_FREE(qt, qt->mem_ctx);
}
 
void qt_reset(qt_t* qt)
{
    QT_ASSERT(qt);
 
    int max_depth = qt->root->max_depth;
 
    qt_node_destroy(qt, qt->root);
 
    qt->root = qt_node_create(qt, qt->bounds, 0, max_depth);
}
 
void qt_insert(qt_t* qt, qt_rect_t bounds, qt_value_t value)
{
    QT_ASSERT(qt);
    qt_node_insert(qt, qt->root, &bounds, value);
}
 
bool qt_remove(qt_t* qt, qt_value_t value)
{
    QT_ASSERT(qt);
    return qt_node_remove(qt->root, value);
}
 
qt_value_t* qt_query(const qt_t* qt, qt_rect_t area, int* size)
{
    QT_ASSERT(qt);
    QT_ASSERT(size);
 
    // Size must be valid
    if (!size)
        return NULL;
 
    // Start query the root node
    qt_array qt_value_t* values = qt_node_query(qt, qt->root, &area, NULL);
 
    // If no results then return NULL
    if (!values)
    {
        *size = 0;
        return NULL;
    }
 
    // Set size and return
    *size = qt_array_size(values);
 
    return values;
}
 
qt_rect_t* qt_grid_rects(const qt_t* qt, int* size)
{
    QT_ASSERT(qt);
    QT_ASSERT(size);
 
    // Size must be valid
    if (!size)
        return NULL;
 
    qt_array qt_rect_t* rects = qt_node_all_grid_rects(qt, qt->root, NULL);
 
    // If no results then return NULL
    if (!rects)
    {
        *size = 0;
        return NULL;
    }
 
    // Set size and return
    *size = qt_array_size(rects);
 
    return rects;
}
 
void qt_free(qt_t* qt, void* array)
{
    (void)qt;
 
    if (!array)
        return;
 
    qt_array_destroy(qt->mem_ctx, array);
}
 
void qt_clear(qt_t* qt)
{
    QT_ASSERT(qt);
    qt_node_clear(qt->root);
}
 
void qt_clean(qt_t* qt)
{
    QT_ASSERT(qt);
 
    qt_array qt_item_t* items = qt_node_all_items(qt, qt->root, NULL);
 
    qt_reset(qt);
 
    for (int i = 0; i < qt_array_size(items); i++)
    {
        qt_insert(qt, items[i].bounds, items[i].value);
    }
 
    qt_array_destroy(qt->mem_ctx, items);
}
 
/*=============================================================================
 * Internal function definitions
 *============================================================================*/
 
static int qt_max(int a, int b)
{
    return a > b ? a : b;
}
 
// Don't call this directly -- use `qt_array_fit` instead.
static void* qt_array_fit_impl(const void* array, int new_size, size_t element_size, void* mem_ctx)
{
    (void)mem_ctx;
 
    QT_ARRAY_CANARY(array);
 
    // Double the old capacity, or pick at least 16 for the starting size.
    // This helps unnecessarily numerous realloc's for low capacities when starting out.
    int new_capacity = qt_max(2 * qt_array_capacity(array), qt_max(new_size, 16));
 
    QT_ASSERT(new_size <= new_capacity);
 
    // Total size of the header struct `qt_array_header_t` along with the size of all
    // elements packed together in a single allocation.
    size_t total_size = sizeof(qt_array_header_t) + new_capacity * element_size;
 
    qt_array_header_t* hdr;
 
    if (array)
    {
        // Realloc of the header isn't new.
        // This expands the capacity.
        hdr = (qt_array_header_t*)QT_REALLOC(qt_hdr(array), total_size, mem_ctx);
    }
 
    else
    {
        // Create a new array if the pointer passed in was NULL, as NULL means an empty array.
        hdr = (qt_array_header_t*)QT_MALLOC(total_size, mem_ctx);
        hdr->size = 0;
    }
 
    hdr->cookie = QT_ARRAY_COOKIE; // For sanity checks with `QT_ARRAY_CANARY`.
    hdr->capacity = new_capacity;
    hdr->data = (char*)(hdr + 1); // For debugging convenience.
 
    return (void*)(hdr + 1);
}
 
qt_rect_t qt_make_rect(qt_float x, qt_float y, qt_float w, qt_float h)
{
    qt_rect_t r = { x, y, w, h }; return r;
}
 
static bool qt_rect_contains(const qt_rect_t* r1, const qt_rect_t* r2)
{
    QT_ASSERT(r1);
    QT_ASSERT(r2);
 
    return r1->x <= r2->x &&
           r1->y <= r2->y &&
           r1->x + r1->w >= r2->x + r2->w &&
           r1->y + r1->h >= r2->y + r2->h;
}
 
static bool qt_rect_overlaps(const qt_rect_t* r1, const qt_rect_t* r2)
{
    QT_ASSERT(r1);
    QT_ASSERT(r2);
 
    return r1->x + r1->w >= r2->x &&
           r1->y + r1->h >= r2->y &&
           r2->x + r2->w >= r1->x &&
           r2->y + r2->h >= r1->y;
}
 
static qt_node_t* qt_node_create(qt_t* qt, qt_rect_t bounds, int depth, int max_depth)
{
    qt_node_t* node = qt_node_alloc(qt);
 
    node->depth = depth;
    node->max_depth = max_depth;
 
    // Calculate subdivided bounds
    bounds.w /= 2.0f;
    bounds.h /= 2.0f;
 
    // Calculates bounds of subtrees
    node->bounds[0] = qt_make_rect(bounds.x,
                                   bounds.y,
                                   bounds.w,
                                   bounds.h);
 
    node->bounds[1] = qt_make_rect(bounds.x + bounds.w,
                                   bounds.y,
                                   bounds.w,
                                   bounds.h);
 
    node->bounds[2] = qt_make_rect(bounds.x,
                                   bounds.y + bounds.h,
                                   bounds.w,
                                   bounds.h);
 
    node->bounds[3] = qt_make_rect(bounds.x + bounds.w,
                                   bounds.y + bounds.h,
                                   bounds.w,
                                   bounds.h);
 
    return node;
}
 
static void qt_node_destroy(qt_t* qt, qt_node_t* node)
{
    QT_ASSERT(node);
 
    qt_array_destroy(qt->mem_ctx, node->items);
 
    // Recursively destroy nodes
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
            qt_node_destroy(qt, node->nodes[i]);
    }
 
    // Free current node by pushing it onto the free list
    qt_node_free(qt, node);
}
 
static void qt_node_insert(qt_t* qt, qt_node_t* node, const qt_rect_t* bounds, qt_value_t value)
{
    QT_ASSERT(node);
    QT_ASSERT(bounds);
 
    // The purpose of this function is to optimally fit the item into a subtree.
    // This occurs when the item is no longer fully contained within a subtree,
    // or the depth limit has been reached.
 
    // Checks to see if the depth limit has been reached. If it hasn't, try to
    // fit the item into a subtree
    if (node->depth + 1 < node->max_depth)
    {
        // Loop over child nodes
        for (int i = 0; i < 4; i++)
        {
            // Check if subtree contains the bounds
            if (qt_rect_contains(&node->bounds[i], bounds))
            {
                // If child node does not exist, then create it
                if (!node->nodes[i])
                {
                    node->nodes[i] = qt_node_create(qt,
                                                    node->bounds[i],
                                                    node->depth + 1,
                                                    node->max_depth);
                }
 
                // Recursively try to insert the item into the subtree
                qt_node_insert(qt, node->nodes[i], bounds, value);
                return;
            }
        }
    }
 
    // If none of the children fully contain the bounds, or the maximum depth
    // has been reached, then the item belongs to this node
    qt_array_push(qt->mem_ctx, node->items, (qt_item_t){ *bounds, value });
}
 
static bool qt_node_remove(qt_node_t* node, qt_value_t value)
{
    QT_ASSERT(node);
 
    // Searches the items in this node and, if found, removes the item with the
    // specified value
    for (int i = 0; i < qt_array_size(node->items); i++)
    {
        // If value is found, then remove it and it's bounds from the node
        if (node->items[i].value == value)
        {
            qt_array_remove(node->items, i);
            return true;
        }
    }
 
    // If the item wasn't found, recursively search the subtrees of this node
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
        {
            if (qt_node_remove(node->nodes[i], value))
                return true;
        }
    }
 
    // Value wasn't found
    return false;
}
 
static qt_array qt_item_t* qt_node_all_items(const qt_t* qt, const qt_node_t* node, qt_array qt_item_t* items)
{
    QT_ASSERT(node);
 
    // Add all values in this node into the array
    for (int i = 0; i < qt_array_size(node->items); i++)
    {
        qt_array_push(qt->mem_ctx, items, node->items[i]);
    }
 
    // Recursively add all values found in the subtrees
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
            items = qt_node_all_items(qt, node->nodes[i], items);
    }
 
    return items;
}
 
static qt_array qt_value_t* qt_node_all_values(const qt_t* qt, const qt_node_t* node, qt_array qt_value_t* values)
{
    QT_ASSERT(node);
 
    // Add all values in this node into the array
    for (int i = 0; i < qt_array_size(node->items); i++)
    {
        qt_array_push(qt->mem_ctx, values, node->items[i].value);
    }
 
    // Recursively add all values found in the subtrees
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
            values = qt_node_all_values(qt, node->nodes[i], values);
    }
 
    return values;
}
 
static qt_array qt_rect_t* qt_node_all_grid_rects(const qt_t* qt, const qt_node_t* node, qt_array qt_rect_t* rects)
{
    QT_ASSERT(node);
 
    // Add all grid bounds in this node into the array
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
            qt_array_push(qt->mem_ctx, rects, node->bounds[i]);
    }
 
    // Recursively add all grid bounds found in the subtrees
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
            rects = qt_node_all_grid_rects(qt, node->nodes[i], rects);
    }
 
    return rects;
}
 
static qt_array qt_value_t* qt_node_query(const qt_t* qt, const qt_node_t* node, const qt_rect_t* area, qt_array qt_value_t* values)
{
    QT_ASSERT(node);
    QT_ASSERT(area);
 
    // Searches for items in this node that intersect the area and adds them to
    // the array
    for (int i = 0; i < qt_array_size(node->items); i++)
    {
        const qt_item_t* item = &node->items[i];
 
        if (qt_rect_overlaps(area, &item->bounds))
            qt_array_push(qt->mem_ctx, values, node->items[i].value);
    }
 
    // Loop over subtrees
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
        {
            // If the area contains the the entire subtree, all items in the
            // subtree match and are recursively added to the array
            if (qt_rect_contains(area, &node->bounds[i]))
            {
                values = qt_node_all_values(qt, node->nodes[i], values);
            }
            else
            {
                // Otherwise, if the area intersects the bounds of the subtree,
                // the subtree is recursively searched for items intersecting
                // or contained within the area
                if (qt_rect_overlaps(area, &node->bounds[i]))
                {
                    values = qt_node_query(qt, node->nodes[i], area, values);
                }
            }
        }
    }
 
    return values;
}
 
static void qt_node_clear(qt_node_t* node)
{
    qt_array_clear(node->items);
 
    for (int i = 0; i < 4; i++)
    {
        if (node->nodes[i])
            qt_node_clear(node->nodes[i]);
    }
}
 
static void qt_freelist_push(qt_t* qt, qt_unode_t *unode)
{
    qt_node_allocator_t* allocator = &qt->allocator;
    unode->next = allocator->free_list;
    allocator->free_list = unode;
}
 
static qt_unode_t* qt_freelist_pop(qt_t* qt)
{
    qt_node_allocator_t* allocator = &qt->allocator;
    qt_unode_t* unode = allocator->free_list;
    allocator->free_list = allocator->free_list->next;
    return unode;
}
 
static void qt_block_alloc(qt_t* qt)
{
    // Allocate space for more nodes and add them to the free list.
 
    qt_node_allocator_t* allocator = &qt->allocator;
 
    const int block_count = PICO_QT_BLOCK_SIZE;
 
    qt_unode_t* nodes = (qt_unode_t*)QT_MALLOC(sizeof(qt_unode_t) * block_count, qt->mem_ctx);
 
    for (int i = 0; i < block_count; i++)
    {
        qt_freelist_push(qt, &nodes[i]);
    }
 
    qt_array_push(qt->mem_ctx, allocator->blocks, nodes);
}
 
static qt_node_t* qt_node_alloc(qt_t* qt)
{
    qt_node_allocator_t* allocator = &qt->allocator;
 
    if (!allocator->free_list)
    {
        qt_block_alloc(qt);
    }
 
    // Pop a node off of the free list.
    qt_unode_t* unode = qt_freelist_pop(qt);
    QT_MEMSET(unode, 0, sizeof(qt_unode_t));
 
    qt_node_t* result = &unode->node;
 
    return result;
}
 
static void qt_node_free(qt_t* qt, qt_node_t* node)
{
    qt_freelist_push(qt, (qt_unode_t*)node);
}
 
#endif // PICO_QT_IMPLEMENTATION
 
/*
    ----------------------------------------------------------------------------
    This software is available under two licenses (A) or (B). You may choose
    either one as you wish:
    ----------------------------------------------------------------------------
 
    (A) The zlib License
 
    Copyright (c) 2022 James McLean
 
    This software is provided 'as-is', without any express or implied warranty.
    In no event will the authors be held liable for any damages arising from the
    use of this software.
 
    Permission is granted to anyone to use this software for any purpose,
    including commercial applications, and to alter it and redistribute it
    freely, subject to the following restrictions:
 
    1. The origin of this software must not be misrepresented; you must not
    claim that you wrote the original software. If you use this software in a
    product, an acknowledgment in the product documentation would be appreciated
    but is not required.
 
    2. Altered source versions must be plainly marked as such, and must not be
    misrepresented as being the original software.
 
    3. This notice may not be removed or altered from any source distribution.
 
    ----------------------------------------------------------------------------
 
    (B) Public Domain (www.unlicense.org)
 
    This is free and unencumbered software released into the public domain.
 
    Anyone is free to copy, modify, publish, use, compile, sell, or distribute
    this software, either in source code form or as a compiled binary, for any
    purpose, commercial or non-commercial, and by any means.
 
    In jurisdictions that recognize copyright laws, the author or authors of
    this software dedicate any and all copyright interest in the software to the
    public domain. We make this dedication for the benefit of the public at
    large and to the detriment of our heirs and successors. We intend this
    dedication to be an overt act of relinquishment in perpetuity of all present
    and future rights to this software under copyright law.
 
    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 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.
*/