memory.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include <unistd.h>
#include "utils/memory.h"
#include "tree.h"

Include dependency graph for memory.c:

Go to the source code of this file.

Data Structures
struct	memSegment

Macros
#define	_GNU_SOURCE

Functions
struct memSegment *	newElement (size_t size)
struct memSegment *	findElement (struct memSegment *tree, size_t size)
struct memSegment *	grandparent (struct memSegment *node)
struct memSegment *	uncle (struct memSegment *node)
struct memSegment *	sibling (struct memSegment *node)
void	rotateLeft (struct memSegment **tree, struct memSegment *node)
void	rotateRight (struct memSegment **tree, struct memSegment *node)
void	replaceNode (struct memSegment **tree, struct memSegment *node1, struct memSegment *node2)
struct memSegment *	insertElement (struct memSegment **tree, struct memSegment *element)
struct memSegment *	findInOrderSuccessor (struct memSegment *tree)
struct memSegment *	deleteElement (struct memSegment **tree, struct memSegment *element)
void	traverse (struct memSegment *tree, void(*cb)(struct memSegment *, int))
void	post (struct memSegment *tree, void(*cb)(struct memSegment *, int))
void	printElement (struct memSegment *node, int depth)
void	cleanup (struct memSegment *node, int depth)
static void	segmentFree (struct memSegment *segment, int depth)
void *	memNewRef (void *mem)
void *	memMalloc (size_t size)
void *	memCalloc (size_t nmemb, size_t size)
void	memFree (void **mem)
size_t	memGetSize (void *mem)
void	memCleanup ()

Variables
struct memSegment *	segments = NULL

---

Data Structure Documentation

struct memSegment

Definition at line 60 of file memory.c.

Collaboration diagram for memSegment:

Data Fields
enum rbColor	color
struct memSegment *	last
struct memSegment *	left
struct memSegment *	next
struct memSegment *	parent
void *	ptr
size_t	ref_count
struct memSegment *	right
size_t	size

Macro Definition Documentation

#define _GNU_SOURCE

Definition at line 47 of file memory.c.

Function Documentation

void cleanup	(	struct memSegment *	node,
		int	depth
	)

Definition at line 747 of file memory.c.

References memSegment::next.

{
    while (NULL != node) {
        struct memSegment * next = node->next;
        free(node);
        node = next;
    }
}

struct memSegment* deleteElement	(	struct memSegment **	tree,
		struct memSegment *	element
	)

Definition at line 389 of file memory.c.

References memSegment::color, findInOrderSuccessor(), memSegment::last, memSegment::left, memSegment::next, memSegment::parent, rbBlack, rbRed, replaceNode(), memSegment::right, rotateLeft(), rotateRight(), sibling(), and memSegment::size.

Referenced by memMalloc().

{
    struct memSegment * node = *tree;
    struct memSegment * del_node;
    struct memSegment * child;
    struct memSegment * s;

    // find the relevant node and it's parent
    while (NULL != node) {

        if (element->size < node->size) {
            node = node->left;
        } else if (element->size > node->size) {
            node = node->right;
        } else {
            if (NULL != node->next) {
                if (NULL != node->parent) {
                    if (node == node->parent->left) {
                        node->parent->left = node->next;
                    } else {
                        node->parent->right = node->next;
                    }
                } else {
                    *tree = node->next;
                }

                if (NULL != node->left) {
                    node->left->parent = node->next;
                }

                if (NULL != node->right) {
                    node->right->parent = node->next;
                }
                
                node->next->last   = node->last;
                node->next->color  = node->color;
                node->next->parent = node->parent;
                node->next->left   = node->left;
                node->next->right  = node->right;

                return node;
            }
            break;
        }
    }

    // element not found
    if (NULL == node) {
        return node;
    }

    del_node = node;

    // now our cases follows...the first one is the same as with
    // simple binary search trees. Two non null children.

    // case 1: two children
    if (NULL != node->left && NULL != node->right) {
        struct memSegment * successor = findInOrderSuccessor(node);

        enum rbColor tmpcolor      = successor->color;
        struct memSegment * tmpparent = successor->parent;
        struct memSegment * tmpleft   = successor->left;
        struct memSegment * tmpright  = successor->right;

        replaceNode(tree, node, successor);

        successor->color        = node->color;
        successor->left         = node->left;
        successor->left->parent = successor;
        // the right one might be successor...
        if (node->right == successor) {
            successor->right = node;
            node->parent     = successor;
        } else {
            successor->right    = node->right;
            node->right->parent = successor;
            node->parent        = tmpparent;
            tmpparent->left     = node;
        }

        node->color  = tmpcolor;
        node->left   = tmpleft;
        node->right  = tmpright;
    }

    // Precondition: n has at most one non-null child.
    child = (NULL == node->right) ? node->left : node->right;
    replaceNode(tree, node, child);

    // delete one child case
    // TODO this is overly complex as simply derived from the function...
    // maybe this can be simplified. Maybe not...check.
    if (node->color == rbBlack) {
        if (NULL != child && child->color == rbRed) {
            child->color = rbBlack;
            // done despite modifying tree itself if neccessary..
            return del_node;
        } else {
            if (NULL != child) {
                node = child;
            } else {
                node->color = rbBlack;
                node->left  = NULL;
                node->right = NULL;
            }
        }
    } else {
        return del_node;
    }

    // delete and rb rebalance...
    while(1) {
        // case 1
        if (NULL == node->parent) {
            // done again
            break;
        }

        // case 2
        s = sibling(node);

        if (NULL != s && s->color == rbRed) {
            node->parent->color = rbRed;
            s->color            = rbBlack;

            /*
             * detect which child we are...assumption
             * if we are not parent->right and parent->right is not
             * null we must be left, even if its set to NULL previously
             */
            if (NULL != node->parent->right && node != node->parent->right) {
                rotateLeft(tree, node->parent);
            } else {
                rotateRight(tree, node->parent);
            }
        }

        s = sibling(node);
        // case 3 / 4
        if (NULL == s || ((s->color == rbBlack) &&
                    (NULL == s->left || s->left->color == rbBlack) &&
                    (NULL == s->right || s->right->color == rbBlack))) {

            if (NULL != s) {
                s->color = rbRed;
            }

            if (node->parent->color == rbBlack) {
                // case 3
                node = node->parent;
                continue;
            } else {
                // case 4
                node->parent->color = rbBlack;
                // and done again...
                break;
            }
        }

        // case 5
        if  (NULL != s && s->color == rbBlack) {
            // this if statement is trivial,
            // due to case 2 (even though case 2 changed the sibling to a
            // sibling's child,
            // the sibling's child can't be red, since no red parent can
            // have a red child).
            //
            // the following statements just force the red to be on the
            // left of the left of the parent,
            // or right of the right, so case 6 will rotate correctly.
            if ((node == node->parent->left) &&
                    (NULL == s->right || s->right->color == rbBlack) &&
                    (NULL != s->left && s->left->color == rbRed)) {

                // this last test is trivial too due to cases 2-4.
                s->color       = rbRed;
                s->left->color = rbBlack;

                rotateRight(tree, s);
            } else if ((node == node->parent->right) &&
                    (NULL == s->left || s->left->color == rbBlack) &&
                    (NULL != s->right && s->right->color == rbRed)) {
                // this last test is trivial too due to cases 2-4.
                s->color        = rbRed;
                s->right->color = rbBlack;

                rotateLeft(tree, s);
            }
        }

        s = sibling(node);
        // case 6
        if (NULL != s) {
            s->color = node->parent->color;
        }

        if (NULL != node && NULL != node->parent) {
            node->parent->color = rbBlack;

            /*
             * detect which child we are...assumption
             * if we are not parent->right and parent->right is not
             * null we must be left, even if its set to NULL previously
             */
            if (NULL != node->parent->right && node != node->parent->right) {
                if (NULL != s->right) {
                    s->right->color = rbBlack;
                }
                rotateLeft(tree, node->parent);
            } else {
                if (NULL != s->left) {
                    s->left->color = rbBlack;
                }
                rotateRight(tree, node->parent);
            }
        }

        // done...
        break;
    }
 
    return del_node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct memSegment* findElement	(	struct memSegment *	tree,
		size_t	size
	)

find element in tree

Definition at line 100 of file memory.c.

References memSegment::left, memSegment::right, and memSegment::size.

Referenced by memMalloc().

{
    struct memSegment * fitting = NULL;

    while (NULL != tree) {
        if (tree->size == size) {
            fitting = tree;
            break;
        }

        if (size > tree->size) {
            tree = tree->right;
        } else {
            fitting = tree;
            tree    = tree->left;
        }
    }

    return fitting;
}

Here is the caller graph for this function:

struct memSegment* findInOrderSuccessor

(

struct memSegment *

tree

)

delete element from tree

here multiple functions are involved....

find minimum of the right subtree aka leftmost leaf of right subtree aka left in-order successor. We return the parent of the element in the out argument parent. This can be NULL wenn calling.

2: *successor = {size = 80, ptr = 0x603ae0, color = rbRed, parent = 0x603160, left = 0x0, right = 0x0} 1: *node = {size = 70, ptr = 0x603a60, color = rbBlack, parent = 0x603070, left = 0x6030e0, right = 0x6031e0}

Definition at line 377 of file memory.c.

References memSegment::left, and memSegment::right.

Referenced by deleteElement().

{
    struct memSegment * node = tree->right;

    while (NULL != node->left) {
        node = node->left;
    }

    return node;
}

Here is the caller graph for this function:

struct memSegment* grandparent

(

struct memSegment *

node

)

Definition at line 126 of file memory.c.

References memSegment::parent.

Referenced by insertElement(), and uncle().

{
    if (NULL != node && NULL != node->parent) {
        return node->parent->parent;
    }

    return NULL;
}

Here is the caller graph for this function:

struct memSegment* insertElement	(	struct memSegment **	tree,
		struct memSegment *	element
	)

insert element in tree

Definition at line 246 of file memory.c.

References memSegment::color, grandparent(), memSegment::last, memSegment::left, memSegment::next, memSegment::parent, rbBlack, rbRed, memSegment::right, rotateLeft(), rotateRight(), memSegment::size, and uncle().

Referenced by memFree().

{
    struct memSegment * node     = *tree;
    struct memSegment * new_node = NULL;
    struct memSegment * u;
    struct memSegment * g;

    element->next   = NULL;
    element->last   = NULL;

    element->color  = rbRed;
    element->parent = NULL;
    element->left   = NULL;
    element->right  = NULL;

    // if tree is empty it's simple... :)
    if (NULL == node) {
        *tree = node = new_node = element;
    } else {
        // normal binary tree add....
        while (NULL != node) {
            if (element->size < node->size) {
                if (NULL == node->left) {
                    node->left         = element;
                    node->left->parent = node;
                    new_node = node = node->left;
                    break;
                } else {
                    node = node->left;
                }
            } else if (element->size > node->size) {
                if (NULL == node->right) {
                    node->right         = element;
                    node->right->parent = node;
                    new_node = node = node->right;
                    break;
                } else {
                    node = node->right;
                }
            } else {
                if (NULL == node->next) {
                    node->next = element;
                    node->last = element;
                } else {
                    node->last->next = element;
                    node->last       = element;
                }
                return node;
            }
        }
    }

    if (NULL != new_node) {
        /* 
         * handle reballancing rb style
         */
        while (1) {
            // case 1
            if (node->parent == NULL) {
                node->color = rbBlack;
                // we're done.... :)
                break;
            }

            // case 2
            if (node->parent->color == rbBlack) {
                // Tree is still valid ... wow, again we're done... :)
                break;
            }

            // case 3
            u = uncle(node);
            g = grandparent(node);

            if (u != NULL && u->color == rbRed) {
                node->parent->color = rbBlack;
                u->color            = rbBlack;
                g->color            = rbRed;

                node = g;
                continue;
            }

            // case 4
            if (node == node->parent->right && node->parent == g->left) {
                rotateLeft(tree, node->parent);
                node = node->left; 
            } else if (node == node->parent->left && node->parent == g->right) {

                rotateRight(tree, node->parent);
                node = node->right; 
            }

            // case 5
            g = grandparent(node);

            node->parent->color = rbBlack;
            g->color            = rbRed;

            if (node == node->parent->left) {
                rotateRight(tree, g);
            } else {
                rotateLeft(tree, g);
            }

            // we're done..
            break;
        }
    }

    return new_node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* memCalloc	(	size_t	nmemb,
		size_t	size
	)

this is a really memory wasting solution....just to be able to use calloc, which might be faster then malloc/memset solution.

Maybe this is a bad idea, as we need to memset the buffer anyway if it comes from our tree, which hopefully should be the majority of cases.

Definition at line 818 of file memory.c.

References memMalloc(), and size.

Referenced by applicationCtor(), applicationSessionCleanup(), classClone(), classNewParams(), hash_pw(), httpMessageCtor(), httpResponseCtor(), and serverCtor().

{
    size_t   _size = nmemb * size;
    void   * mem   = memMalloc(_size);

    memset(mem, 0, _size);

    return mem;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void memCleanup

(

)

Definition at line 862 of file memory.c.

References post(), and segmentFree().

Referenced by main().

{
#ifdef MEM_OPT
    post(segments, segmentFree);
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

void memFree

(

void **

mem

)

Definition at line 829 of file memory.c.

References insertElement(), and memSegment::ref_count.

{
    if (NULL != *mem) {
        struct memSegment * seg = (*mem - sizeof(struct memSegment));

        if (1 < seg->ref_count) {
            seg->ref_count--;
        } else {
#ifdef MEM_OPT
            insertElement(&segments, seg);
#else
            free(seg);
#endif
        }

        *mem = NULL;
    }
}

Here is the call graph for this function:

size_t memGetSize

(

void *

mem

)

Definition at line 849 of file memory.c.

References memSegment::size.

Referenced by httpWriterWrite().

{
    struct memSegment * segment;

    if (NULL == mem) {
        return 0;
    }

    segment = (struct memSegment *)(mem - sizeof(struct memSegment));
    return segment->size;
}

Here is the caller graph for this function:

void* memMalloc

(

size_t

size

)

Definition at line 783 of file memory.c.

References deleteElement(), findElement(), newElement(), memSegment::ptr, and size.

Referenced by authLdapCtor(), cbufCtor(), configCtor(), configValueCtor(), controllerCurrentuserRead(), controllerLocRead(), controllerRandvalRead(), controllerSessinfoRead(), controllerUserRead(), controllerVersionRead(), credentialCtor(), hashValueCtor(), httpCookieCtor(), httpHeaderCtor(), httpParserHeader(), httpParserParse(), httpParserRequestVars(), httpRequestCtor(), httpResponse404(), httpResponse500(), httpResponseJson(), httpWorkerCtor(), httpWriterWrite(), loggerLog(), memCalloc(), newEle(), storageCtor(), storageGet(), userCtor(), userSerialize(), and userUnserialize().

{
    struct memSegment * seg = NULL;
    //long                psize = sysconf(_SC_PAGESIZE);
    long                psize = 64;

    size += sizeof(struct memSegment);

    /* allocate only blocks of a multiple of pagesize, similar to cbuf */
    size  = (0>=size)?1:(0!=size%psize)?(size/psize)+1:size/psize;
    size *= psize;

#ifdef MEM_OPT
    seg = findElement(segments, size);
#endif

    if (NULL == seg) {
        seg = newElement(size);
    } else {
        // remove the found one from the tree as we use it now.
        seg = deleteElement(&segments, seg);
    }

    return seg->ptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* memNewRef

(

void *

mem

)

Definition at line 770 of file memory.c.

References memSegment::ref_count.

{
    struct memSegment * seg = (mem - sizeof(struct memSegment));

    seg->ref_count++;

    return mem;
}

struct memSegment* newElement

(

size_t

size

)

Definition at line 77 of file memory.c.

References memSegment::color, memSegment::last, memSegment::left, memSegment::next, memSegment::parent, memSegment::ptr, rbRed, memSegment::ref_count, memSegment::right, size, and memSegment::size.

Referenced by memMalloc().

{
    struct memSegment * element = malloc(size);

    element->ref_count = 1;
    element->size      = size;
    element->ptr       = (void*)element + sizeof(struct memSegment);

    element->next      = NULL;
    element->last      = NULL;

    element->color     = rbRed;
    element->parent    = NULL;
    element->left      = NULL;
    element->right     = NULL;

    return element;
}

Here is the caller graph for this function:

void post	(	struct memSegment *	tree,
		void(*)(struct memSegment *, int)	cb
	)

Definition at line 666 of file memory.c.

References cb, memSegment::left, memSegment::parent, and memSegment::right.

Referenced by memCleanup().

{
    struct memSegment * previous = tree;
    struct memSegment * node     = tree;
    int              depth    = 1;

    /*
     * I think this has something like O(n+log(n)) on a ballanced
     * tree because I have to traverse back the rightmost leaf to
     * the root to get a break condition.
     */
    while (node) {
        /*
         * If we come from the right so nothing and go to our
         * next parent.
         */
        if (((NULL == node->left || previous == node->left)
                    && NULL == node->right)
                || previous == node->right) {

            struct memSegment * parent = node->parent;

            cb(node, depth);

            previous = node;
            node     = parent;
            depth--;
            continue;
        }

        if ((NULL == node->left || previous == node->left)) {
            /*
             * If there are no more elements to the left or we
             * came from the left, process data.
             */
            previous = node;

            if (NULL != node->right) {
                node = node->right;
                depth++;
            } else {
                node = node->parent;
                depth--;
            }
        } else {
            /*
             * if there are more elements to the left go there.
             */
            previous = node;
            node     = node->left;
            depth++;
        }
    }
}

Here is the caller graph for this function:

void printElement	(	struct memSegment *	node,
		int	depth
	)

Definition at line 721 of file memory.c.

References memSegment::color, memSegment::next, memSegment::ptr, rbRed, and memSegment::size.

{
    int  i;

    printf("%s %010zu:%p(%02d)",
            (node->color==rbRed)?"R":"B",
            node->size,
            node->ptr,
            depth);
    for (i=0; i<depth; i++) printf("-");
    puts("");

    node = node->next;
    while (NULL != node) {
        printf("  %s %010zu:%p(%02d)",
                (node->color==rbRed)?"R":"B",
                node->size,
                node->ptr,
                depth);
        for (i=0; i<depth; i++) printf("-");
        puts("");
        node = node->next;
    }
}

void replaceNode	(	struct memSegment **	tree,
		struct memSegment *	node1,
		struct memSegment *	node2
	)

Definition at line 221 of file memory.c.

References memSegment::left, memSegment::parent, and memSegment::right.

Referenced by deleteElement().

{
    if (NULL != node1->parent) {
        if (node1 == node1->parent->left) {
            node1->parent->left = node2;
        } else {
            node1->parent->right = node2;
        }
    } else {
        *tree = node2;
    }

    if (NULL != node2) {
        node2->parent = node1->parent;
    }
}

Here is the caller graph for this function:

void rotateLeft	(	struct memSegment **	tree,
		struct memSegment *	node
	)

Definition at line 169 of file memory.c.

References memSegment::left, memSegment::parent, and memSegment::right.

Referenced by deleteElement(), and insertElement().

{
    struct memSegment * rightChild = node->right;
    struct memSegment * rcLeftSub  = node->right->left;

    rightChild->left   = node;
    rightChild->parent = node->parent;
    node->right        = rcLeftSub;
    if (NULL != rcLeftSub) {
        rcLeftSub->parent  = node;
    }

    if (node->parent) {
        if (node->parent->left == node) {
            node->parent->left = rightChild;
        } else {
            node->parent->right = rightChild;
        }
    } else {
        *tree = rightChild;
    }

    node->parent = rightChild;
}

Here is the caller graph for this function:

void rotateRight	(	struct memSegment **	tree,
		struct memSegment *	node
	)

Definition at line 195 of file memory.c.

References memSegment::left, memSegment::parent, and memSegment::right.

Referenced by deleteElement(), and insertElement().

{
    struct memSegment * leftChild  = node->left;
    struct memSegment * lcRightSub = node->left->right;

    leftChild->right   = node;
    leftChild->parent  = node->parent;
    node->left         = lcRightSub;
    if (NULL != lcRightSub) {
        lcRightSub->parent = node;
    }

    if (node->parent) {
        if (node->parent->left == node) {
            node->parent->left = leftChild;
        } else {
            node->parent->right = leftChild;
        }
    } else {
        *tree = leftChild;
    }

    node->parent = leftChild;
}

Here is the caller graph for this function:

static void segmentFree ( struct memSegment *  segment, int  depth  )

static

Definition at line 760 of file memory.c.

References memSegment::next.

Referenced by memCleanup().

{
    while (NULL != segment) {
        struct memSegment * next = segment->next;
        free(segment);
        segment = next;
    }
}

Here is the caller graph for this function:

struct memSegment* sibling

(

struct memSegment *

node

)

Definition at line 152 of file memory.c.

References memSegment::left, memSegment::parent, and memSegment::right.

Referenced by deleteElement().

{
    if (NULL == node) {
        return NULL;
    }

    if (NULL == node->parent->left || node == node->parent->left) {
        return node->parent->right;
    } else {
        return node->parent->left;
    }
}

Here is the caller graph for this function:

void traverse	(	struct memSegment *	tree,
		void(*)(struct memSegment *, int)	cb
	)

Definition at line 616 of file memory.c.

References cb, memSegment::left, memSegment::parent, and memSegment::right.

{
    struct memSegment * previous = tree;
    struct memSegment * node     = tree;
    int              depth    = 1;

    /*
     * I think this has something like O(n+log(n)) on a ballanced
     * tree because I have to traverse back the rightmost leaf to
     * the root to get a break condition.
     */
    while (node) {
        /*
         * If we come from the right so nothing and go to our
         * next parent.
         */
        if (previous == node->right) {
            previous = node;
            node     = node->parent;
            depth--;
            continue;
        }

        if ((NULL == node->left || previous == node->left)) {
            /*
             * If there are no more elements to the left or we
             * came from the left, process data.
             */
            cb(node, depth);
            previous = node;

            if (NULL != node->right) {
                node = node->right;
                depth++;
            } else {
                node = node->parent;
                depth--;
            }
        } else {
            /*
             * if there are more elements to the left go there.
             */
            previous = node;
            node     = node->left;
            depth++;
        }
    }
}

struct memSegment* uncle

(

struct memSegment *

node

)

Definition at line 136 of file memory.c.

References grandparent(), memSegment::left, memSegment::parent, and memSegment::right.

Referenced by insertElement().

{
    struct memSegment * gp = grandparent(node);

    if (NULL == gp) {
        return NULL;
    }

    if (node->parent == gp->left) {
        return gp->right;
    }

    return gp->left;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

struct memSegment* segments = NULL

Definition at line 756 of file memory.c.