/*******************************************************************************
* apps/graphics/traveler/src/trv_planelist.c
* This file contains the logic to manage world plane lists.
*
* Copyright (C) 2014 Gregory Nutt. All rights reserved.
* Author: Gregory Nutt <gnutt@nuttx.org>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
* 3. Neither the name NuttX nor the names of its contributors may be
* used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
****************************************************************************/
/****************************************************************************
* Included files
****************************************************************************/
#include "trv_types.h"
#include "trv_mem.h"
#include "trv_plane.h"
/****************************************************************************
* Public Data
****************************************************************************/
/* The is the world!!! The world is described by lists of rectangles, one
* for each of the X, Y, and Z planes.
*/
struct trv_rect_head_s g_xplane; /* list of X=plane rectangles */
struct trv_rect_head_s g_yplane; /* list of Y=plane rectangles */
struct trv_rect_head_s g_zplane; /* list of Z=plane rectangles */
/* "Deallocated" planes are retained in a free list */
FAR struct trv_rect_list_s *g_rect_freelist;
/****************************************************************************
* Private Functions
****************************************************************************/
/****************************************************************************
* Name: trv_release_worldplane
*
* Description:
* This function deallocates one plane of the world
*
***************************************************************************/
static void trv_release_worldplane(FAR struct trv_rect_list_s *rect)
{
FAR struct trv_rect_list_s *next;
while (rect)
{
next = rect->flink;
trv_free((void *) rect);
rect = next;
}
}
/****************************************************************************
* Public Functions
****************************************************************************/
/****************************************************************************
* Name: trv_initialize_planes
*
* Description:
*
***************************************************************************/
int trv_initialize_planes(void)
{
g_xplane.head = NULL;
g_xplane.tail = NULL;
g_yplane.head = NULL;
g_yplane.tail = NULL;
g_zplane.head = NULL;
g_zplane.tail = NULL;
g_rect_freelist = NULL;
return OK;
}
/****************************************************************************
* Name: trv_add_plane
*
* Description:
* This function adds a plane to a world plane list
*
***************************************************************************/
void trv_add_plane(FAR struct trv_rect_list_s *rect,
FAR struct trv_rect_head_s *list)
{
struct trv_rect_list_s *next;
struct trv_rect_list_s *prev;
/* Search the list to find the location to insert the new rectangle. Each
* is list is maintained in ascending plane order.
*/
for (next = list->head;
((next) && (next->d.plane < rect->d.plane));
next = next->flink);
/* Add the 'rect' to the spot found in the list. Check if the 'rect' lies
* at the end of the list.
*/
if (!next)
{
/* No rectangle with plane larger than the one to be added was found
* in the list. The 'rect' goes at the end of the list.
*/
prev = list->tail;
if (!prev)
{
/* Special case: The list is empty */
rect->flink = NULL;
rect->blink = NULL;
list->head = rect;
list->tail = rect;
}
else
{
rect->flink = NULL;
rect->blink = prev;
prev->flink = rect;
list->tail = rect;
}
}
else
{
/* The 'rect' goes just before 'next' */
prev = next->blink;
if (!prev)
{
/* Special case: Insert at the head of the list */
rect->flink = next;
rect->blink = NULL;
next->blink = rect;
list->head = rect;
}
else
{
/* Insert in the middle of the list */
rect->flink = next;
rect->blink = prev;
prev->flink = rect;
next->blink = rect;
}
}
}
/****************************************************************************
* Name: trv_move_plane
*
* Description:
*
* This function removes the specified plane from the world plane srclist
* then adds it to the world plane destlist
*
***************************************************************************/
void trv_move_plane(FAR struct trv_rect_list_s *rect,
FAR struct trv_rect_head_s *destlist,
FAR struct trv_rect_head_s *srclist)
{
/* Un-hook the backward link to the rect */
if (rect->flink)
{
rect->flink->blink = rect->blink;
}
else
{
srclist->tail = rect->blink;
}
/* Un-hook the forward link to the rect */
if (rect->blink)
{
rect->blink->flink = rect->flink;
}
else
{
srclist->head = rect->flink;
}
/* Then add the rect to the specified list */
trv_add_plane(rect, destlist);
}
/****************************************************************************
* Name: trv_merge_planelists
*
* Description:
* This function concatenates two world plane lists
*
***************************************************************************/
void trv_merge_planelists(FAR struct trv_rect_head_s *outlist,
FAR struct trv_rect_head_s *inlist)
{
struct trv_rect_list_s *inrect;
struct trv_rect_list_s *nextin;
struct trv_rect_list_s *outrect;
struct trv_rect_list_s *prevout;
/* Initialize the inner plane search loop */
outrect = outlist->head;
/* Process every plane in the input plane list */
for (inrect = inlist->head; (inrect); inrect = nextin)
{
nextin = inrect->flink;
/* Search the output plane list to find the location to insert the
* input rectangle. Each is list is maintained in ascending plane
* order.
*/
for (;
outrect && outrect->d.plane < inrect->d.plane;
outrect = outrect->flink);
/* Add the 'inrect' to the spot found in the list. Check if the
* 'inrect' goes at the one of the ends of the list.
*/
if (!outrect)
{
/* No rectangle with plane larger than the one to be added
* was found in the list. The 'inrect' goes at the end of
* the list.
*/
prevout = outlist->tail;
if (!prevout)
{
/* Special case: The list is empty */
inrect->flink = NULL;
inrect->blink = NULL;
outlist->head = inrect;
outlist->tail = inrect;
}
else
{
inrect->flink = NULL;
inrect->blink = prevout;
prevout->flink = inrect;
outlist->tail = inrect;
}
}
else
{
/* The 'inrect' goes just before 'outrect' */
prevout = outrect->blink;
if (!prevout)
{
/* Special case: Insert at the head of the list */
inrect->flink = outrect;
inrect->blink = NULL;
outrect->blink = inrect;
outlist->head = inrect;
}
else
{
/* Insert in the middle of the list */
inrect->flink = outrect;
inrect->blink = prevout;
prevout->flink = inrect;
outrect->blink = inrect;
}
}
/* Set up for the next time through */
outrect = inrect;
}
/* Mark the input list empty */
inlist->head = NULL;
inlist->tail = NULL;
}
/*************************************************************************
* Function: trv_new_plane
*
* Description:
* This function allocates memory for a new plane rectangle.
*
************************************************************************/
FAR struct trv_rect_list_s *trv_new_plane(void)
{
FAR struct trv_rect_list_s *rect;
/* Try to get the new structure from the free list */
rect = g_rect_freelist;
if (rect)
{
/* Got get... remove it from the g_rect_freelist; */
g_rect_freelist = rect->flink;
}
else
{
/* Nothing on the free list. Allocate a new one */
rect = (FAR struct trv_rect_list_s*)trv_malloc(sizeof(struct trv_rect_list_s));
}
return rect;
}
/*************************************************************************
* Name: trv_release_planes
*
* Description:
*
* This function deallocates the entire world.
*
************************************************************************/
void trv_release_planes(void)
{
/* Release all world planes */
trv_release_worldplane(g_xplane.head);
trv_release_worldplane(g_yplane.head);
trv_release_worldplane(g_zplane.head);
trv_release_worldplane(g_rect_freelist);
/* Re-initialize the world plane lists */
trv_initialize_planes();
}
