OpenGL/util/idpool.c

/* Copyright (c) 2001, Stanford University
 * All rights reserved
 *
 * See the file LICENSE.txt for information on redistributing this software.
 */

#include "chromium.h"
#include "cr_error.h"
#include "cr_mem.h"
#include "cr_idpool.h"


#define CR_MAXUINT             ((GLuint) 0xFFFFFFFF)

typedef struct FreeElemRec {
    GLuint min;
    GLuint max;
    struct FreeElemRec *next;
    struct FreeElemRec *prev;
} FreeElem;

struct CRIdPoolRec {
    FreeElem *freeList;
};


CRIdPool *crAllocIdPool( void )
{
    CRIdPool *pool = (CRIdPool *) crCalloc(sizeof(CRIdPool));
    pool->freeList = (FreeElem *) crCalloc(sizeof(FreeElem));
    pool->freeList->min = 1;
    pool->freeList->max = CR_MAXUINT;
    pool->freeList->next = NULL;
    pool->freeList->prev = NULL;
    return pool;
}

void crFreeIdPool( CRIdPool *pool )
{
    FreeElem *i, *next;
    for (i = pool->freeList; i; i = next)
    {
        next = i->next;
        crFree(i);
    }
    crFree(pool);
}

/*
 * Allocate a block of <count> IDs.  Return index of first one.
 * Return 0 if we fail.
 */
GLuint crIdPoolAllocBlock( CRIdPool *pool, GLuint count )
{
    FreeElem *f;
    GLuint ret;

    CRASSERT(count > 0);

    f = pool->freeList;
    while (f)
    {
        if (f->max - f->min + 1 >= (GLuint) count)
        {
            /* found a sufficiently large enough block */
            ret = f->min;
            f->min += count;

            if (f->min == f->max)
            {
                /* remove this block from linked list */
                if (f == pool->freeList)
                {
                    /* remove from head */
                    pool->freeList = pool->freeList->next;
                    pool->freeList->prev = NULL;
                }
                else
                {
                    /* remove from elsewhere */
                    f->prev->next = f->next;
                    f->next->prev = f->prev;
                }
                crFree(f);
            }

#ifdef DEBUG
            /* make sure the IDs really are allocated */
            {
                GLuint i;
                for (i = 0; i < count; i++)
                {
                    CRASSERT(crIdPoolIsIdUsed(pool, ret + i));
                }
            }
#endif

            return ret;
        }
        else {
            f = f->next;
        }
    }

    /* failed to find free block */
    return 0;
}


/*
 * Free a block of <count> IDs starting at <first>.
 */
void crIdPoolFreeBlock( CRIdPool *pool, GLuint first, GLuint count )
{
    FreeElem *i;
    FreeElem *newelem;

    /*********************************/
    /* Add the name to the freeList  */
    /* Find the bracketing sequences */

    for (i = pool->freeList; i && i->next && i->next->min < first; i = i->next)
    {
        /* EMPTY BODY */
    }

    /* j will always be valid */
    if (!i)
        return;
    if (!i->next && i->max == first)
        return;

    /* Case:  j:(~,first-1) */
    if (i->max + 1 == first)
    {
        i->max += count;
        if (i->next && i->max+1 >= i->next->min)
        {
            /* Collapse */
            i->next->min = i->min;
            i->next->prev = i->prev;
            if (i->prev)
            {
                i->prev->next = i->next;
            }
            if (i == pool->freeList)
            {
                pool->freeList = i->next;
            }
            crFree(i);
        }
        return;
    }

    /* Case: j->next: (first+1, ~) */
    if (i->next && i->next->min - count == first)
    {
        i->next->min -= count;
        if (i->max + 1 >= i->next->min)
        {
            /* Collapse */
            i->next->min = i->min;
            i->next->prev = i->prev;
            if (i->prev)
            {
                i->prev->next = i->next;
            }
            if (i == pool->freeList)
            {
                pool->freeList = i->next;
            }
            crFree(i);
        }
        return;
    }

    /* Case: j: (first+1, ~) j->next: null */
    if (!i->next && i->min - count == first)
    {
        i->min -= count;
        return;
    }

    /* allocate a new FreeElem node */
    newelem = (FreeElem *) crCalloc(sizeof(FreeElem));
    newelem->min = first;
    newelem->max = first + count - 1;

    /* Case: j: (~,first-(2+))  j->next: (first+(2+), ~) or null */
    if (first > i->max)
    {
        newelem->prev = i;
        newelem->next = i->next;
        if (i->next)
        {
            i->next->prev = newelem;
        }
        i->next = newelem;
        return;
    }

    /* Case: j: (first+(2+), ~) */
    /* Can only happen if j = t->freeList! */
    if (i == pool->freeList && i->min > first)
    {
        newelem->next = i;
        newelem->prev = i->prev;
        i->prev = newelem;
        pool->freeList = newelem;
        return;
    }
}


/*
 * Mark the given Id as being allocated.
 */
void crIdPoolAllocId( CRIdPool *pool, GLuint id )
{
    FreeElem *f;

    CRASSERT(id > 0);

    f = pool->freeList;
    while (f)
    {
        if (id >= f->min && id <= f->max)
        {
            /* found the block */
            if (id == f->min)
            {
                f->min++;
            }
            else if (id == f->max)
            {
                f->max--;
            }
            else
            {
                /* somewhere in the middle - split the block */
                FreeElem *newelem = (FreeElem *) crCalloc(sizeof(FreeElem));
                newelem->min = id + 1;
                newelem->max = f->max;
                f->max = id - 1;
                newelem->next = f->next;
                if (f->next)
                   f->next->prev = newelem;
                newelem->prev = f;
                f->next = newelem;
            }
            return;
        }
        f = f->next;
    }

    /* if we get here, the ID was already allocated - that's OK */
}


/*
 * Determine if the given id is free.  Return GL_TRUE if so.
 */
GLboolean crIdPoolIsIdFree( const CRIdPool *pool, GLuint id )
{
    FreeElem *i;

    /* First find which region it fits in */
    for (i = pool->freeList; i && !(i->min <= id && id <= i->max); i=i->next)
    {
        /* EMPTY BODY */
    }

    if (i)
        return GL_TRUE;
    else
        return GL_FALSE;
}


/*
 * Determine if the given id is used.  Return GL_TRUE if so.
 */
GLboolean crIdPoolIsIdUsed( const CRIdPool *pool, GLuint id )
{
    return (GLboolean) !crIdPoolIsIdFree( pool, id);
}