#include "stdio.h"
#include "plugin.h"
#include <string.h>

static int stllimit = 0;
static int stlsizeof = 0;
static int stlprintcompatible = 1;

#define TREE_PARENT(A) ((CORE_ADDR)read_memory_integer ((A) + 1 * ptr_size, ptr_size))
#define TREE_LEFT(A)   ((CORE_ADDR)read_memory_integer ((A) + 2 * ptr_size, ptr_size))
#define TREE_RIGHT(A)  ((CORE_ADDR)read_memory_integer ((A) + 3 * ptr_size, ptr_size))

static struct plugin_functions ext_fcts;

void handle_stllimit(char * args, int from_tty)
{
    if (args && strlen(args))
    {
        stllimit = atoi(args);
    }

    if (stllimit == 0)
    {
        ext_fcts.printf_unfiltered("STL limit set to UNLIMITED\n");
    }
    else
    {
        ext_fcts.printf_unfiltered("STL limit set to %d\n", stllimit);
    }
}

void handle_stlstyle(char * args, int from_tty)
{
    if (args && strlen(args))
    {
        stlprintcompatible = atoi(args);
    }

    ext_fcts.printf_unfiltered("STL container style %d\n", stlprintcompatible);
}

void handle_stlsizeof(char *args, int from_tty)
{
    if (args && strlen(args))
    {
        stlsizeof = atoi(args);
    }

    if (stlsizeof)
    {
        ext_fcts.printf_unfiltered("sizeof operator on STL containers will print the number of elements.\n");
    }
    else
    {
        ext_fcts.printf_unfiltered("sizeof operator on STL containers will print the total size in bytes.\n");
    }
}

int init_plugin(struct plugin_functions fcts)
{
    ext_fcts = fcts;
    ext_fcts.add_cli_command("stllimit", "Set the maximum number of element display for STL containers", handle_stllimit, COMPLETE_NONE);
    ext_fcts.add_cli_command("stlstyle", "Set the display style of STL containers", handle_stlstyle, COMPLETE_NONE);
    ext_fcts.add_cli_command("stlsizeof", "Set if sizeof(X) on an STL container should return the number of elements (argument != 0) or the total number of bytes (argument = 0).\n", handle_stlsizeof, COMPLETE_NONE);
    ext_fcts.printf_unfiltered("GDB STL plugin loaded\n");
    return 1;
}

void uninit_plugin()
{
}

/*
 * helpers
 */

int get_stl_inner_type(const char * type_name, char *inner_type_name)
{
    int level = 1;
    char *pname = (char *)type_name;

    while (*pname && *pname != '<') pname++;
    if (*pname == 0)
    {
        // This is not a template !
        *inner_type_name = 0;
        return 0;
    }

    pname++;

    while (!(level == 1 && *pname == ','))
    {
        if (*pname == '<') level++;
        else if (*pname == '>') level--;
        if (!(level == 1 && *pname == ',')) *inner_type_name++ = *pname++;
    }
    *inner_type_name = 0;

    return 1;
}

int get_stl_inner_type_pair(const char * type_name, char *inner_type_key, char *inner_type_value, char *pair_name)
{
    int level = 1;
    char *pname = (char *)type_name;

    while (*pname && *pname != '<') pname++;
    if (*pname == 0)
    {
        // This is not a template !
        *inner_type_key   = 0;
        *inner_type_value = 0;
        return 0;
    }

    pname++;

    while (!(level == 1 && *pname == ','))
    {
        if (*pname == '<') level++;
        else if (*pname == '>') level--;
        if (!(level == 1 && *pname == ',')) *inner_type_key++ = *pname++;
    }
    *inner_type_key = 0;

    if (*pname == ',')
    {
        pname++;
        while (!(level == 1 && *pname == ','))
        {
            if (*pname == '<') level++;
            else if (*pname == '>') level--;
            if (!(level == 1 && *pname == ',')) *inner_type_value++ = *pname++;
        }
        *inner_type_value = 0;
    }

    if (pair_name == NULL) return 1;

    level = 0;
    pname++;
    while (!(level == 0 && *pname == ','))
    {
        if (*pname == '<') level++;
        else if (*pname == '>') level--;
        pname++;
    }
    pname++;

    if (strncmp(pname, "std::allocator<std::pair<", 25))
    {
        puts(pname);
        return 0;
    }
    pname += 15;
    level = 0;
    while (!(level == 0 && *pname == '>'))
    {
        if (*pname == '<') level++;
        else if (*pname == '>') level--;
        *pair_name++ = *pname++;
    }
    *pair_name++ = 0;

    return 1;
}

struct type * get_stl_container_inner_type(struct varobj * var)
{
    char * inner_name;
    struct type * type = ext_fcts.get_varobj_type(var);
    struct type * inner;
    struct block * block = ext_fcts.get_varobj_block(var);
    const char * type_name = ext_fcts.get_type_name(type);
    inner_name = (char *)malloc(strlen(type_name) + 1);
    if (!get_stl_inner_type(type_name, inner_name))
        return NULL;
    inner = ext_fcts.get_type(inner_name, block);
    free(inner_name);
    return inner;
}

/*
 * printers
 */

void print_stl_vector(const char * type_name, int type_name_len,
        CORE_ADDR address,
        struct ui_file *stream, int format, int recurse,
        enum val_prettyprint pretty)
{
    char                *inner_name;
    struct type         *void_type;
    struct type         *inner_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    CORE_ADDR           begin;
    CORE_ADDR           end;

    inner_name = (char *)malloc(type_name_len + 1);

    if (get_stl_inner_type (type_name, inner_name))
    {
        if (!stlprintcompatible) ext_fcts.fprintf_filtered (stream, "vector<%s>", inner_name);
        ext_fcts.fprintf_filtered (stream, "{");
        if (pretty) ext_fcts.fprintf_filtered (stream, "\n");
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            if (pretty) print_spaces_filtered (2 + 2 * recurse, stream);
            ext_fcts.fprintf_filtered (stream, "  // no information for type %s\n", inner_name);
        }
        else
        {
            idx   = 0;
            begin = (CORE_ADDR)ext_fcts.read_memory_integer(address,            ptr_size);
            end   = (CORE_ADDR)ext_fcts.read_memory_integer(address + ptr_size, ptr_size);
            while (begin != end)
            {
                if (stllimit && idx >= stllimit)
                {
                    fprintf_filtered (stream, "...");
                    break;
                }
                if (pretty) ext_fcts.print_spaces_filtered(2 + 2 * recurse, stream);
                if (!stlprintcompatible) ext_fcts.fprintf_filtered(stream, "[%d] = ", idx);
                idx++;
                ext_fcts.print(inner_type, begin, stream, format, recurse + 1, pretty);
                begin += ext_fcts.get_type_length(inner_type);
                if (begin != end) ext_fcts.fprintf_filtered(stream, ", ");
                if (pretty)
                {
                    ext_fcts.fprintf_filtered(stream, "\n");
                }
            }
        }
        if (pretty) ext_fcts.print_spaces_filtered (2 * recurse, stream);
        ext_fcts.fprintf_filtered (stream, "}");
        if (recurse == 0) ext_fcts.fprintf_filtered (stream, "\n");
    }

    free(inner_name);
}

void print_stl_list(const char * type_name, int type_name_len,
        CORE_ADDR address,
        struct ui_file *stream, int format, int recurse,
        enum val_prettyprint pretty)
{
    char                *inner_name;
    CORE_ADDR           node;
    CORE_ADDR           data_ptr;
    struct type         *inner_type;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        if (!stlprintcompatible) ext_fcts.fprintf_filtered (stream, "list<%s>", inner_name);
        ext_fcts.fprintf_filtered (stream, "{");
        if (pretty) ext_fcts.fprintf_filtered (stream, "\n");
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            if (pretty) ext_fcts.print_spaces_filtered(2 + 2 * recurse, stream);
            ext_fcts.fprintf_filtered(stream, "  // no information for type %s\n", inner_name);
        }
        else
        {
            idx  = 0;
            node = (CORE_ADDR)read_memory_integer (address, ptr_size);
            while (node != address)
            {
                if (stllimit && idx >= stllimit)
                {
                    ext_fcts.fprintf_filtered (stream, "...");
                    break;
                }
                data_ptr = (CORE_ADDR)(node + ptr_size * 2);
                if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
                if (!stlprintcompatible) ext_fcts.fprintf_filtered(stream, "[%d] = ", idx);
                idx++;
                ext_fcts.print(inner_type, data_ptr, stream, format, recurse + 1, pretty);
                node = (CORE_ADDR)ext_fcts.read_memory_integer (node, ptr_size);
                if (node != address) ext_fcts.fprintf_filtered(stream, ", ");
                if (pretty)
                {
                    ext_fcts.fprintf_filtered(stream, "\n");
                }
            }
        }
        if (pretty) ext_fcts.print_spaces_filtered (2 * recurse, stream);
        ext_fcts.fprintf_filtered (stream, "}");
        if (recurse == 0) ext_fcts.fprintf_filtered (stream, "\n");
    }

    free(inner_name);
}

void print_stl_set(const char * type_name, int type_name_len,
        CORE_ADDR address,
        struct ui_file *stream, int format, int recurse,
        enum val_prettyprint pretty)
{
    char                *inner_name;
    CORE_ADDR           node;
    CORE_ADDR           left;
    CORE_ADDR           tmp_node;
    CORE_ADDR           data_ptr;
    struct type         *inner_type;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    int                 count;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        if (!stlprintcompatible) ext_fcts.fprintf_filtered (stream, "set<%s>", inner_name);
        ext_fcts.fprintf_filtered (stream, "{");
        if (pretty) ext_fcts.fprintf_filtered (stream, "\n");
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
            ext_fcts.fprintf_filtered (stream, "  // no information for type %s\n", inner_name);
        }
        else
        {
            node  = (CORE_ADDR)read_memory_integer (address + 3 * ptr_size, ptr_size);
            count = (int)read_memory_integer(address + 5 * ptr_size, ptr_size);
            for (idx=0; idx<count; idx++)
            {
                if (stllimit && idx >= stllimit)
                {
                    ext_fcts.fprintf_filtered (stream, "...");
                    break;
                }
                data_ptr = (CORE_ADDR)(node + ptr_size * 4);
                if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
                if (!stlprintcompatible) ext_fcts.fprintf_filtered(stream, "[%d] = ", idx);
                ext_fcts.print(inner_type, data_ptr, stream, format, recurse + 1, pretty);

                if (TREE_RIGHT(node) != 0)
                {
                    node = TREE_RIGHT(node);
                    while ((left = TREE_LEFT(node)))
                    {
                        node = left;
                    }
                }
                else
                {
                    tmp_node = TREE_PARENT(node);
                    while (node == TREE_RIGHT(node))
                    {
                        node     = tmp_node;
                        tmp_node = TREE_PARENT(node);
                    }
                    if (TREE_RIGHT(node) != tmp_node)
                    {
                        node = tmp_node;
                    }
                }

                if (idx != count - 1) ext_fcts.fprintf_filtered(stream, ", ");
                if (pretty)
                {
                    ext_fcts.fprintf_filtered(stream, "\n");
                }
            }
        }
        if (pretty) ext_fcts.print_spaces_filtered (2 * recurse, stream);
        ext_fcts.fprintf_filtered (stream, "}");
        if (recurse == 0) ext_fcts.fprintf_filtered (stream, "\n");
    }

    free(inner_name);
}

void print_stl_map(const char * type_name, int type_name_len,
        CORE_ADDR address,
        struct ui_file *stream, int format, int recurse,
        enum val_prettyprint pretty)
{
    char                *inner_key;
    char                *inner_value;
    CORE_ADDR           node;
    CORE_ADDR           left;
    CORE_ADDR           tmp_node;
    CORE_ADDR           data_ptr;
    struct type         *inner_type_key;
    struct type         *inner_type_value;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    int                 count;

    inner_key   = (char *)malloc(strlen(type_name) + 1);
    inner_value = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type_pair(type_name, inner_key, inner_value, NULL))
    {
        if (!stlprintcompatible) ext_fcts.fprintf_filtered (stream, "map<%s, %s>", inner_key, inner_value);
        ext_fcts.fprintf_filtered (stream, "{");
        if (pretty) ext_fcts.fprintf_filtered (stream, "\n");
        block            = ext_fcts.get_current_block();
        inner_type_key   = ext_fcts.get_type(inner_key,   block);
        inner_type_value = ext_fcts.get_type(inner_value, block);
        void_type        = ext_fcts.get_type("void *", block);
        ptr_size         = ext_fcts.get_type_length(void_type);

        if (inner_type_key == NULL || inner_type_value == NULL)
        {
            if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
            ext_fcts.fprintf_filtered (stream, "  // no information for type std::pair<%s, %s>\n", inner_key, inner_value);
        }
        else
        {
            node    = (CORE_ADDR)read_memory_integer (address + 3 * ptr_size, ptr_size);
            count   = (int)read_memory_integer(address + 5 * ptr_size, ptr_size);
            for (idx=0; idx<count; idx++)
            {
                if (stllimit && idx >= stllimit)
                {
                    ext_fcts.fprintf_filtered (stream, "...");
                    break;
                }
                data_ptr = (CORE_ADDR)(node + ptr_size * 4);

                if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
                if (!stlprintcompatible) ext_fcts.fprintf_filtered(stream, "[%d] = ", idx);
                ext_fcts.fprintf_filtered (stream, "{");
                if (pretty) ext_fcts.fprintf_filtered(stream, "\n");

                if (pretty) ext_fcts.print_spaces_filtered (4 + 2 * recurse, stream);
                if (!stlprintcompatible)
                {
                    ext_fcts.fprintf_filtered(stream, "key ");
                    if (pretty) ext_fcts.fprintf_filtered(stream, "  ");
                    ext_fcts.fprintf_filtered(stream, "= ");
                }
                ext_fcts.print(inner_type_key, data_ptr, stream, format, recurse + 3, pretty);
                if (pretty) ext_fcts.fprintf_filtered(stream, ",\n"); else ext_fcts.fprintf_filtered(stream, ", ");
                if (pretty) ext_fcts.print_spaces_filtered (4 + 2 * recurse, stream);
                if (!stlprintcompatible)
                {
                    ext_fcts.fprintf_filtered(stream, "value = ");
                }
                ext_fcts.print(inner_type_value, data_ptr + ptr_size, stream, format, recurse + 3, pretty);
                if (pretty) ext_fcts.fprintf_filtered(stream, "\n");

                if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
                ext_fcts.fprintf_filtered(stream, "}");

                if (TREE_RIGHT(node) != 0)
                {
                    node = TREE_RIGHT(node);
                    while ((left = TREE_LEFT(node)))
                    {
                        node = left;
                    }
                }
                else
                {
                    tmp_node = TREE_PARENT(node);
                    while (node == TREE_RIGHT(node))
                    {
                        node     = tmp_node;
                        tmp_node = TREE_PARENT(node);
                    }
                    if (TREE_RIGHT(node) != tmp_node)
                    {
                        node = tmp_node;
                    }
                }

                if (idx != count - 1) ext_fcts.fprintf_filtered(stream, ", ");
                if (pretty)
                {
                    ext_fcts.fprintf_filtered(stream, "\n");
                }
            }
        }
        if (pretty) ext_fcts.print_spaces_filtered (2 * recurse, stream);
        ext_fcts.fprintf_filtered (stream, "}");
        if (recurse == 0) ext_fcts.fprintf_filtered (stream, "\n");
    }

    free(inner_key);
    free(inner_value);
}

void print_stl_deque(const char * type_name, int type_name_len,
        CORE_ADDR address,
        struct ui_file *stream, int format, int recurse,
        enum val_prettyprint pretty)
{
    char                *inner_name;
    CORE_ADDR           node;
    CORE_ADDR           data_ptr;
    CORE_ADDR           map;
    CORE_ADDR           cur_node;
    int                 iter_beg_cur;
    int                 iter_beg_first;
    int                 iter_beg_last;
    int                 iter_beg_node;
    int                 iter_end_cur;
    int                 iter_end_first;
    int                 iter_end_last;
    int                 iter_end_node;
    int                 elems_per_nodes;
    int                 size;
    struct type         *inner_type;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    int                 nodes_rem;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        if (!stlprintcompatible) ext_fcts.fprintf_filtered (stream, "deque<%s>", inner_name);
        ext_fcts.fprintf_filtered (stream, "{");
        if (pretty) ext_fcts.fprintf_filtered (stream, "\n");
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
            ext_fcts.fprintf_filtered (stream, "  // no information for type %s\n", inner_name);
        }
        else
        {
            map             = read_memory_integer (address, ptr_size);
            iter_beg_cur    = read_memory_integer (address + ptr_size * 2, ptr_size);
            iter_beg_first  = read_memory_integer (address + ptr_size * 3, ptr_size);
            iter_beg_last   = read_memory_integer (address + ptr_size * 4, ptr_size);
            iter_beg_node   = read_memory_integer (address + ptr_size * 5, ptr_size);
            iter_end_cur    = read_memory_integer (address + ptr_size * 6, ptr_size);
            iter_end_first  = read_memory_integer (address + ptr_size * 7, ptr_size);
            iter_end_last   = read_memory_integer (address + ptr_size * 8, ptr_size);
            iter_end_node   = read_memory_integer (address + ptr_size * 9, ptr_size);
            elems_per_nodes = TYPE_LENGTH(inner_type) < 512 ? 512 / TYPE_LENGTH(inner_type) : 1;
            size            = ( elems_per_nodes * (iter_end_node - iter_beg_node - ptr_size) + (iter_end_cur - iter_end_first) + (iter_beg_last - iter_beg_cur) ) / ptr_size;
            idx             = 0;
            nodes_rem       = elems_per_nodes;
            data_ptr        = iter_beg_cur;
            cur_node        = iter_beg_node;
            while (idx < size)
            {
                if (stllimit && idx >= stllimit)
                {
                    ext_fcts.fprintf_filtered (stream, "...");
                    break;
                }
                if (nodes_rem)
                {
                    if (pretty) ext_fcts.print_spaces_filtered (2 + 2 * recurse, stream);
                    if (!stlprintcompatible) ext_fcts.fprintf_filtered(stream, "[%d] = ", idx);
                    ext_fcts.print(inner_type, data_ptr, stream, format, recurse + 1, pretty);
                    if (idx != size - 1) ext_fcts.fprintf_filtered(stream, ", ");
                    if (pretty) ext_fcts.fprintf_filtered(stream, "\n");
                    data_ptr += TYPE_LENGTH(inner_type);
                    nodes_rem--;
                    idx++;
                }
                else
                {
                    nodes_rem = elems_per_nodes;
                    cur_node += ptr_size;
                    data_ptr  = read_memory_integer (cur_node, ptr_size);
                }
            }
            if (pretty) ext_fcts.print_spaces_filtered (2 * recurse, stream);
            ext_fcts.fprintf_filtered (stream, "}");
            if (recurse == 0) ext_fcts.fprintf_filtered (stream, "\n");
        }
    }

    free(inner_name);
}

void print_stl_string(const char * type_name, int type_name_len,
        CORE_ADDR address,
        struct ui_file *stream, int format, int recurse,
        enum val_prettyprint pretty)
{
    struct type         *char_type;
    struct block        *block;
    int                 ptr_size;
    CORE_ADDR           string_ptr;

    block            = ext_fcts.get_current_block();
    char_type        = ext_fcts.get_type("char *", block);
    ptr_size         = ext_fcts.get_type_length(char_type);

    string_ptr = ext_fcts.read_memory_integer(address, ptr_size);
    val_print_string(string_ptr, -1, 1, stream);
}

/*
 * getters
 */

struct value * get_stl_list_item_at(const char * type_name, int type_name_len, CORE_ADDR address, int index)
{
    char                *inner_name;
    CORE_ADDR           node;
    CORE_ADDR           data_ptr;
    struct type         *inner_type;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;

    if (index < 0) return NULL;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            free(inner_name);
            return NULL;
        }
        else
        {
            idx  = 0;
            node = (CORE_ADDR)ext_fcts.read_memory_integer(address, ptr_size);
            while (node != address && idx <= index)
            {
                if (idx == index)
                {
                    free(inner_name);
                    return ext_fcts.value_at(inner_type, (CORE_ADDR)(node + ptr_size * 2));
                }
                node = (CORE_ADDR)ext_fcts.read_memory_integer (node, ptr_size);
                idx++;
            }
        }
    }

    free(inner_name);
    return NULL;
}

struct value * get_stl_vector_item_at(const char * type_name, int type_name_len, CORE_ADDR address, int index)
{
    char                *inner_name;
    struct type         *void_type;
    struct type         *inner_type;
    struct block        *block;
    int                 ptr_size;
    CORE_ADDR           begin;
    CORE_ADDR           end;

    if (index < 0) return NULL;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            free(inner_name);
            return NULL;
        }
        else
        {
            begin  = (CORE_ADDR)read_memory_integer (address,            ptr_size);
            end    = (CORE_ADDR)read_memory_integer (address + ptr_size, ptr_size);
            begin += index * TYPE_LENGTH (inner_type);
            if (begin >= end)
            {
                free(inner_name);
                return NULL;
            }
            return ext_fcts.value_at(inner_type, begin);
        }
    }

    free(inner_name);
    return NULL;
}

struct value * get_stl_set_item_at(const char * type_name, int type_name_len, CORE_ADDR address, int index)
{
    char                *inner_name;
    CORE_ADDR           node;
    CORE_ADDR           left;
    CORE_ADDR           tmp_node;
    CORE_ADDR           data_ptr;
    struct type         *inner_type;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    int                 count;

    if (index < 0) return NULL;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            free(inner_name);
            return NULL;
        }
        else
        {
            node  = (CORE_ADDR)read_memory_integer (address + 3 * ptr_size, ptr_size);
            count = (int)read_memory_integer(address + 5 * ptr_size, ptr_size);
            if (index >= count)
            {
                free(inner_name);
                return NULL;
            }
            for (idx=0; idx<index; idx++)
            {
                if (TREE_RIGHT(node) != 0)
                {
                    node = TREE_RIGHT(node);
                    while ((left = TREE_LEFT(node)))
                    {
                        node = left;
                    }
                }
                else
                {
                    tmp_node = TREE_PARENT(node);
                    while (node == TREE_RIGHT(node))
                    {
                        node     = tmp_node;
                        tmp_node = TREE_PARENT(node);
                    }
                    if (TREE_RIGHT(node) != tmp_node)
                    {
                        node = tmp_node;
                    }
                }
            }
            free(inner_name);
            return ext_fcts.value_at(inner_type, (CORE_ADDR)(node + ptr_size * 4));
        }
    }

    free(inner_name);
    return NULL;
}

struct value * get_stl_map_pair_at(const char * type_name, int type_name_len, CORE_ADDR address, int index)
{
    char                *inner_key;
    char                *inner_value;
    char                *pair_name;
    CORE_ADDR           node;
    CORE_ADDR           left;
    CORE_ADDR           tmp_node;
    CORE_ADDR           data_ptr;
    struct type         *void_type;
    struct type         *pair_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    int                 count;

    if (index < 0) return NULL;

    inner_key   = (char *)malloc(strlen(type_name) + 1);
    inner_value = (char *)malloc(strlen(type_name) + 1);
    pair_name   = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type_pair(type_name, inner_key, inner_value, pair_name))
    {
        block         = ext_fcts.get_current_block();
        pair_type     = ext_fcts.get_type(pair_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (pair_type == NULL)
        {
            free (inner_key);
            free (inner_value);
            free (pair_name);
            return NULL;
        }
        else
        {
            node    = (CORE_ADDR)read_memory_integer (address + 3 * ptr_size, ptr_size);
            count   = (int)read_memory_integer(address + 5 * ptr_size, ptr_size);
            if (index >= count)
            {
                free (inner_key);
                free (inner_value);
                free (pair_name);
                return NULL;
            }
            for (idx=0; idx<index; idx++)
            {
                if (TREE_RIGHT(node) != 0)
                {
                    node = TREE_RIGHT(node);
                    while ((left = TREE_LEFT(node)))
                    {
                        node = left;
                    }
                }
                else
                {
                    tmp_node = TREE_PARENT(node);
                    while (node == TREE_RIGHT(node))
                    {
                        node     = tmp_node;
                        tmp_node = TREE_PARENT(node);
                    }
                    if (TREE_RIGHT(node) != tmp_node)
                    {
                        node = tmp_node;
                    }
                }
            }

            free (inner_key);
            free (inner_value);
            free (pair_name);
            return ext_fcts.value_at(pair_type, (CORE_ADDR)(node + ptr_size * 4));
        }
    }

    free(inner_key);
    free(inner_value);
    free (pair_name);
    return NULL;
}

struct value * get_stl_deque_item_at(const char * type_name, int type_name_len, CORE_ADDR address, int index)
{
    char                *inner_name;
    CORE_ADDR           node;
    CORE_ADDR           data_ptr;
    CORE_ADDR           map;
    CORE_ADDR           cur_node;
    int                 iter_beg_cur;
    int                 iter_beg_first;
    int                 iter_beg_last;
    int                 iter_beg_node;
    int                 iter_end_cur;
    int                 iter_end_first;
    int                 iter_end_last;
    int                 iter_end_node;
    int                 elems_per_nodes;
    int                 size;
    struct type         *inner_type;
    struct type         *void_type;
    struct block        *block;
    int                 ptr_size;
    unsigned int        idx;
    int                 nodes_rem;

    if (index < 0) return NULL;

    inner_name = (char *)malloc(strlen(type_name) + 1);

    if (get_stl_inner_type(type_name, inner_name))
    {
        block         = ext_fcts.get_current_block();
        inner_type    = ext_fcts.get_type(inner_name, block);
        void_type     = ext_fcts.get_type("void *", block);
        ptr_size      = ext_fcts.get_type_length(void_type);

        if (inner_type == NULL)
        {
            free(inner_name);
            return NULL;
        }
        else
        {
            map             = read_memory_integer (address, ptr_size);
            iter_beg_cur    = read_memory_integer (address + ptr_size * 2, ptr_size);
            iter_beg_first  = read_memory_integer (address + ptr_size * 3, ptr_size);
            iter_beg_last   = read_memory_integer (address + ptr_size * 4, ptr_size);
            iter_beg_node   = read_memory_integer (address + ptr_size * 5, ptr_size);
            iter_end_cur    = read_memory_integer (address + ptr_size * 6, ptr_size);
            iter_end_first  = read_memory_integer (address + ptr_size * 7, ptr_size);
            iter_end_last   = read_memory_integer (address + ptr_size * 8, ptr_size);
            iter_end_node   = read_memory_integer (address + ptr_size * 9, ptr_size);
            elems_per_nodes = TYPE_LENGTH(inner_type) < 512 ? 512 / TYPE_LENGTH(inner_type) : 1;
            size            = ( elems_per_nodes * (iter_end_node - iter_beg_node - ptr_size) + (iter_end_cur - iter_end_first) + (iter_beg_last - iter_beg_cur) ) / ptr_size;
            idx             = 0;
            nodes_rem       = elems_per_nodes;
            data_ptr        = iter_beg_cur;
            cur_node        = iter_beg_node;
            if (index >= size)
            {
                free(inner_name);
                return NULL;
            }
            while (idx < size)
            {
                if (index == idx)
                {
                    free(inner_name);
                    return ext_fcts.value_at(inner_type, data_ptr);
                }
                if (nodes_rem)
                {
                    nodes_rem--;
                    data_ptr += TYPE_LENGTH(inner_type);
                    idx++;
                }
                else
                {
                    nodes_rem = elems_per_nodes;
                    cur_node += ptr_size;
                    data_ptr  = read_memory_integer (cur_node, ptr_size);
                }
            }
        }
    }

    free(inner_name);
    return NULL;
}


int get_stl_list_size(const char * type_name, struct block * block, CORE_ADDR varadr)
{
    int children = 0;
    char * inner_name = (char *)malloc(strlen(type_name) + 1);
    if (get_stl_inner_type(type_name, inner_name))
    {
        struct type *       void_type     = ext_fcts.get_type("void *", block);
        struct type *       inner_type    = ext_fcts.get_type(inner_name, block);
        int                 ptr_size      = ext_fcts.get_type_length(void_type);
        CORE_ADDR           node          = (CORE_ADDR)read_memory_integer (varadr, ptr_size);
        while (node != varadr)
        {
            node = (CORE_ADDR)ext_fcts.read_memory_integer (node, ptr_size);
            children++;
        }
    }
    free (inner_name);
    return children;
}

int get_stl_list_size_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (!type) return 0;
    return get_stl_list_size(ext_fcts.get_type_name(type), ext_fcts.get_varobj_block(var), ext_fcts.get_value_address(ext_fcts.get_varobj_value(var)));
}

int get_stl_vector_size(const char * type_name, struct block * block, CORE_ADDR varadr)
{
    int children = 0;
    char * inner_name = (char *)malloc(strlen(type_name) + 1);
    if (get_stl_inner_type(type_name, inner_name))
    {
        struct type *       void_type     = ext_fcts.get_type("void *", block);
        struct type *       inner_type    = ext_fcts.get_type(inner_name, block);
        int                 ptr_size      = ext_fcts.get_type_length(void_type);
        CORE_ADDR           begin         = (CORE_ADDR)read_memory_integer (varadr,            ptr_size);
        CORE_ADDR           end           = (CORE_ADDR)read_memory_integer (varadr + ptr_size, ptr_size);
        children = (end - begin) / TYPE_LENGTH (inner_type);
    }
    free (inner_name);
    return children;
}

int get_stl_vector_size_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (!type) return 0;
    return get_stl_vector_size(ext_fcts.get_type_name(type), ext_fcts.get_varobj_block(var), ext_fcts.get_value_address(ext_fcts.get_varobj_value(var)));
}

int get_stl_set_or_multiset_size(const char * type_name, struct block * block, CORE_ADDR varadr)
{
    struct type *       void_type     = ext_fcts.get_type("void *", block);
    int                 ptr_size      = ext_fcts.get_type_length(void_type);
    return (int)read_memory_integer(varadr + 5 * ptr_size, ptr_size);
}

int get_stl_set_or_multiset_size_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (!type) return 0;
    return get_stl_set_or_multiset_size(ext_fcts.get_type_name(type), ext_fcts.get_varobj_block(var), ext_fcts.get_value_address(ext_fcts.get_varobj_value(var)));
}

int get_stl_map_or_multimap_size(const char * type_name, struct block * block, CORE_ADDR varadr)
{
    struct type *       void_type     = ext_fcts.get_type("void *", block);
    int                 ptr_size      = ext_fcts.get_type_length(void_type);
    return (int)read_memory_integer(varadr + 5 * ptr_size, ptr_size);
}

int get_stl_map_or_multimap_size_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (!type) return 0;
    return get_stl_map_or_multimap_size(ext_fcts.get_type_name(type), ext_fcts.get_varobj_block(var), ext_fcts.get_value_address(ext_fcts.get_varobj_value(var)));
}

int get_stl_deque_size(const char * type_name, struct block * block, CORE_ADDR varadr)
{
    char * inner_name    = (char *)malloc(strlen(type_name) + 1);

    struct type *       void_type     = ext_fcts.get_type("void *", block);
    int                 ptr_size      = ext_fcts.get_type_length(void_type);
    if (get_stl_inner_type(type_name, inner_name))
    {
        struct type *       inner_type    = ext_fcts.get_type(inner_name, block);
        int iter_beg_cur    = read_memory_integer (varadr + ptr_size * 2, ptr_size);
        int iter_beg_first  = read_memory_integer (varadr + ptr_size * 3, ptr_size);
        int iter_beg_last   = read_memory_integer (varadr + ptr_size * 4, ptr_size);
        int iter_beg_node   = read_memory_integer (varadr + ptr_size * 5, ptr_size);
        int iter_end_cur    = read_memory_integer (varadr + ptr_size * 6, ptr_size);
        int iter_end_first  = read_memory_integer (varadr + ptr_size * 7, ptr_size);
        int iter_end_last   = read_memory_integer (varadr + ptr_size * 8, ptr_size);
        int iter_end_node   = read_memory_integer (varadr + ptr_size * 9, ptr_size);
        int elems_per_nodes = ext_fcts.get_type_length(inner_type) < 512 ? 512 / ext_fcts.get_type_length(inner_type) : 1;
        return ( elems_per_nodes * (iter_end_node - iter_beg_node - ptr_size) + (iter_end_cur - iter_end_first) + (iter_beg_last - iter_beg_cur) ) / ptr_size;
    }
    return 0;
}

int get_stl_deque_size_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (!type) return 0;
    return get_stl_deque_size(ext_fcts.get_type_name(type), ext_fcts.get_varobj_block(var), ext_fcts.get_value_address(ext_fcts.get_varobj_value(var)));
}

/*
 * predicates
 */

int is_stl_vector_from_name(const char * name, int len)
{
    if (len > 2 && name[len - 1] == '>')
    {
        if (!strncmp(name, "std::vector<", 12))
            return 1;
        if (!strncmp(name, "std::_Vector_base<", 18))
            return 1;
    }
    return 0;
}

int is_stl_list_from_name(const char * name, int len)
{
    if (len > 2 && name[len - 1] == '>')
    {
        if (!strncmp(name, "std::list<", 10))
            return 1;
        if (!strncmp(name, "std::_List_base<", 16))
            return 1;
    }
    return 0;
}

int is_stl_set_or_multiset_from_name(const char * name, int len)
{
    if (len > 2 && name[len - 1] == '>')
    {
        if (!strncmp(name, "std::set<", 9))
            return 1;
        if (!strncmp(name, "std::multiset<", 14))
            return 1;
        if (!strncmp(name, "std::_Rb_tree<", 14))
            return 1;
    }
    return 0;
}

int is_stl_map_or_multimap_from_name(const char * name, int len)
{
    if (len > 2 && name[len - 1] == '>')
    {
        if (!strncmp(name, "std::map<", 9))
            return 1;
        if (!strncmp(name, "std::multimap<", 14))
            return 1;
    }
    return 0;
}

int is_stl_deque_from_name(const char * name, int len)
{
    if (len > 2 && name[len - 1] == '>')
    {
        if (!strncmp(name, "std::deque<", 11))
            return 1;
        if (!strncmp(name, "std::_Deque_base<", 17))
            return 1;
    }
    return 0;
}

int is_stl_string_from_name(const char * name, int len)
{
    len = strlen (name);
    if (len > 2 && name[len - 1] == '>' && !strncmp(name, "std::basic_string<char,", 23))
        return 1;
    return 0;
}

int is_stl_vector_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (type)
    {
        const char * type_name = ext_fcts.get_type_name(type);
        int len = strlen(type_name);
        return is_stl_vector_from_name(type_name, len);
    }
    return 0;
}

int is_stl_list_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (type)
    {
        const char * type_name = ext_fcts.get_type_name(type);
        int len = strlen(type_name);
        return is_stl_list_from_name(type_name, len);
    }
    return 0;
}

int is_stl_map_or_multimap_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (type)
    {
        const char * type_name = ext_fcts.get_type_name(type);
        int len = strlen(type_name);
        return is_stl_map_or_multimap_from_name(type_name, len);
    }
    return 0;
}

int is_stl_set_or_multiset_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (type)
    {
        const char * type_name = ext_fcts.get_type_name(type);
        int len = strlen(type_name);
        return is_stl_set_or_multiset_from_name(type_name, len);
    }
    return 0;
}

int is_stl_deque_from_varobj(struct varobj * var)
{
    struct type * type = ext_fcts.get_varobj_type(var);
    if (type)
    {
        const char * type_name = ext_fcts.get_type_name(type);
        int len = strlen(type_name);
        return is_stl_deque_from_name(type_name, len);
    }
    return 0;
}

int type_handled(const char * type_name, int type_name_len)
{
    if (is_stl_vector_from_name(type_name, type_name_len)
            || is_stl_list_from_name(type_name, type_name_len)
            || is_stl_set_or_multiset_from_name(type_name, type_name_len)
            || is_stl_map_or_multimap_from_name(type_name, type_name_len)
            || is_stl_deque_from_name(type_name, type_name_len)
            || is_stl_string_from_name(type_name, type_name_len))
    {
        return 1;
    }
    return 0;
}

int get_num_children(struct varobj *varobj)
{
    if (is_stl_vector_from_varobj(varobj))
    {
        return get_stl_vector_size_from_varobj(varobj);
    }
    else if (is_stl_list_from_varobj(varobj))
    {
        return get_stl_list_size_from_varobj(varobj);
    }
    else if (is_stl_map_or_multimap_from_varobj(varobj))
    {
        return get_stl_map_or_multimap_size_from_varobj(varobj);
    }
    else if (is_stl_set_or_multiset_from_varobj(varobj))
    {
        return get_stl_set_or_multiset_size_from_varobj(varobj);
    }
    else if (is_stl_deque_from_varobj(varobj))
    {
        return get_stl_deque_size_from_varobj(varobj);
    }
    return 0;
}

int print(const char * type_name, int type_name_len, CORE_ADDR address, struct ui_file * stream, int format, int recurse, enum val_prettyprint pretty)
{
    if (is_stl_vector_from_name(type_name, type_name_len))
    {
        print_stl_vector(type_name, type_name_len, address, stream, format, recurse, pretty);
        return 1;
    }
    else if (is_stl_list_from_name(type_name, type_name_len))
    {
        print_stl_list(type_name, type_name_len, address, stream, format, recurse, pretty);
        return 1;
    }
    else if (is_stl_set_or_multiset_from_name(type_name, type_name_len))
    {
        print_stl_set(type_name, type_name_len, address, stream, format, recurse, pretty);
        return 1;
    }
    else if (is_stl_map_or_multimap_from_name(type_name, type_name_len))
    {
        print_stl_map(type_name, type_name_len, address, stream, format, recurse, pretty);
        return 1;
    }
    else if (is_stl_deque_from_name(type_name, type_name_len))
    {
        print_stl_deque(type_name, type_name_len, address, stream, format, recurse, pretty);
        return 1;
    }
    else if (is_stl_string_from_name(type_name, type_name_len))
    {
        print_stl_string(type_name, type_name_len, address, stream, format, recurse, pretty);
        return 1;
    }
    return 0;
}

int operator_handled(const char * type_name, int type_name_len, enum exp_opcode op)
{
    if (is_stl_vector_from_name(type_name, type_name_len)
            || is_stl_list_from_name(type_name, type_name_len)
            || is_stl_set_or_multiset_from_name(type_name, type_name_len)
            || is_stl_map_or_multimap_from_name(type_name, type_name_len)
            || is_stl_deque_from_name(type_name, type_name_len))
    {
        if (op == BINOP_SUBSCRIPT) return 1;
        if (op == UNOP_LENGTH)     return 1;
        if (op == UNOP_SIZEOF)     return 1;
    }
    return 0;
}

struct value * unary_operation(const char * type_name, int type_name_len, CORE_ADDR address, enum exp_opcode op)
{
    int size = 0;
    switch(op)
    {
        case UNOP_LENGTH:
        case UNOP_SIZEOF:
            if (is_stl_vector_from_name(type_name, type_name_len))
            {
                size = get_stl_vector_size(type_name, ext_fcts.get_current_block(), address);
            }
            else if (is_stl_list_from_name(type_name, type_name_len))
            {
                size = get_stl_list_size(type_name, ext_fcts.get_current_block(), address);
            }
            else if (is_stl_map_or_multimap_from_name(type_name, type_name_len))
            {
                size = get_stl_map_or_multimap_size(type_name, ext_fcts.get_current_block(), address);
            }
            else if (is_stl_set_or_multiset_from_name(type_name, type_name_len))
            {
                size = get_stl_set_or_multiset_size(type_name, ext_fcts.get_current_block(), address);
            }
            else if (is_stl_deque_from_name(type_name, type_name_len))
            {
                size = get_stl_deque_size(type_name, ext_fcts.get_current_block(), address);
            }
            if (stlsizeof == 0 && op == UNOP_SIZEOF)
            {
                char * inner_type = (char *)malloc(type_name_len + 1);
                get_stl_inner_type(type_name, inner_type);
                size *= ext_fcts.get_type_length(ext_fcts.get_type(inner_type, ext_fcts.get_current_block()));
                free(inner_type);
            }
            return ext_fcts.value_from_longest(ext_fcts.get_type("int", ext_fcts.get_current_block()), size);
        default:
            break;
    }
    return NULL;
}

struct value * binary_operation(const char * type_name, int type_name_len, CORE_ADDR address, struct value * other, enum exp_opcode op)
{
    switch(op)
    {
        case BINOP_SUBSCRIPT:
            if (is_stl_vector_from_name(type_name, type_name_len))
            {
                return get_stl_vector_item_at(type_name, type_name_len, address, ext_fcts.value_as_long(other));
            }
            else if (is_stl_list_from_name(type_name, type_name_len))
            {
                return get_stl_list_item_at(type_name, type_name_len, address, ext_fcts.value_as_long(other));
            }
            else if (is_stl_map_or_multimap_from_name(type_name, type_name_len))
            {
                return get_stl_map_pair_at(type_name, type_name_len, address, ext_fcts.value_as_long(other));
            }
            else if (is_stl_set_or_multiset_from_name(type_name, type_name_len))
            {
                return get_stl_set_item_at(type_name, type_name_len, address, ext_fcts.value_as_long(other));
            }
            else if (is_stl_deque_from_name(type_name, type_name_len))
            {
                return get_stl_deque_item_at(type_name, type_name_len, address, ext_fcts.value_as_long(other));
            }
            break;
        default:
            break;
    }
    return NULL;
}

struct type * get_child_item_type_at(struct varobj * varobj, int index)
{
    return get_stl_container_inner_type(varobj);
}

struct value * get_child_item_value_at(struct varobj * varobj, int index)
{
    struct type * type = ext_fcts.get_varobj_type(varobj);
    const char * type_name = ext_fcts.get_type_name(type);
    CORE_ADDR address = ext_fcts.get_value_address(ext_fcts.get_varobj_value(varobj));
    int type_name_len = strlen(type_name);

    if (is_stl_vector_from_name(type_name, type_name_len))
    {
        return get_stl_vector_item_at(type_name, type_name_len, address, index);
    }
    else if (is_stl_list_from_name(type_name, type_name_len))
    {
        return get_stl_list_item_at(type_name, type_name_len, address, index);
    }
    else if (is_stl_map_or_multimap_from_name(type_name, type_name_len))
    {
        return get_stl_map_pair_at(type_name, type_name_len, address, index);
    }
    else if (is_stl_set_or_multiset_from_name(type_name, type_name_len))
    {
        return get_stl_set_item_at(type_name, type_name_len, address, index);
    }
    else if (is_stl_deque_from_name(type_name, type_name_len))
    {
        return get_stl_deque_item_at(type_name, type_name_len, address, index);
    }
    return NULL;
}