root/trunk/thune/list.c

/*============================================================================
    Urlan Interpreter
    Copyright (C) 2005-2007  Karl Robillard

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
===========================================================================*/


#include "urlan.h"
#include "list.h"


UIndex ur_makeList( UThread* ut, int len, UBlock** blkPtr )
{
    UIndex blkN;
    UBlock* blk;
    UCell* it;
    UCell* end;
    //UCell* next;

    len = len * 2 + 2;

    blkN = ur_makeBlock( len );
    blk = ur_blockPtr( blkN );
    blk->used = 2;

    it  = blk->ptr.cells;
    end = it + len;

    ur_initType( it, UT_UNSET );
    it->list.prev = -1;
    it->list.next = LIST_TAIL;
    it->list.free = 0;
    //it->list.free = (len == 2) ? 0 : 2;
    ++it;

    ur_initType( it, UT_UNSET );
    it->list.prev = LIST_HEAD;
    it->list.next = 0;
    it->list.free = -1;
#if 0
    ++it;

    // Disabled initialization of free list because the free nodes cannot
    // be used until they fall within blk->used range.

    while( it != end )
    {
        next = it + 2;

        ur_initType( it, UT_UNSET );
        it->list.prev = -1;
        it->list.next = -1;
        it->list.free = (next == end) ? 0 : next - blk->ptr.cells;

        it = next;
    }
#endif

    if( blkPtr )
        *blkPtr = blk;

    return blkN;
}


void ur_listInsertValue( UBlock* blk, UIndex nodeIndex, UCell* newVal )
{
    UIndex nodeN;
    UCell* node;
    UCell* prev;
    UCell* it = blk->ptr.cells;

    nodeN = it->list.free;
    if( nodeN )
    {
        it->list.free = it[ nodeN ].list.free;
    }
    else
    {
        ur_arrayReserve( blk, sizeof(UCell), blk->used + 2 );
        nodeN = blk->used;
        blk->used += 2;
        it = blk->ptr.cells;
    }

    it += nodeIndex;

    prev = blk->ptr.cells + it->list.prev;
    prev->list.next = nodeN;
    it->list.prev = nodeN;

    node = blk->ptr.cells + nodeN;
    ur_initType( node, UT_UNSET );
    node->list.linked = 1;
    node->list.prev   = prev - blk->ptr.cells;
    node->list.next   = it - blk->ptr.cells;
    node->list.free   = -1;

    ++node;
    ur_copyCell( node, *newVal );
}


/*
   Returns next series.it or -1 if node is not linked to the list.
*/
UIndex ur_listRemove( UBlock* blk, UIndex nodeIndex )
{
    UIndex nextI;
    UCell* it;
    UCell* cells = blk->ptr.cells;
    UCell* node = cells + nodeIndex;

    if( ! node->list.linked )       // Includes head & tail.
        return -1;

    nextI = node->list.next;

    it = cells + node->list.prev;
    it->list.next = node->list.next;

    it = cells + node->list.next;
    it->list.prev = node->list.prev;

    node->list.linked = 0;
    node->list.prev   = -1;
    node->list.next   = -1;
    node->list.free   = cells->list.free;

    cells->list.free = nodeIndex;

    /*
    ++node;
    ur_initType( node, UT_UNSET );
    */

    // NOTE: If this is the last node in the block we can
    // optimize GC by moving blk->used down until a used node
    // is found.

    return nextI;
}


/*
   Returns previous series.it or -1 if node is not linked to the list.
*/
UIndex ur_listClear( UBlock* blk, UIndex nodeIndex )
{
    UCell* it;

    if( nodeIndex == LIST_TAIL )
        return LIST_TAIL;

    it = blk->ptr.cells + nodeIndex;
    if( it->list.linked )
    {
        UIndex next;
        UIndex prevI = it->list.prev;
        UCell* cells = blk->ptr.cells;

        cells[ prevI ].list.next = LIST_TAIL;
        cells[ LIST_TAIL ].list.prev = prevI;

        do
        {
            next = it->list.next;

            it->list.linked = 0;
            it->list.prev   = -1;
            it->list.next   = -1;
            it->list.free   = (next == LIST_TAIL) ? cells->list.free : next;

            /*
            ++it;
            ur_initType( it, UT_UNSET );
            */

            it = cells + next;
        }
        while( it->list.next > 0 );

        cells->list.free = nodeIndex;

        return LIST_TAIL;
    }
    return -1;
}


/*EOF*/