seglist.h

00001 /*
00002 # This file is Copyright 2003, 2006, 2007, 2009 Dean Hall.
00003 #
00004 # This file is part of the PyMite VM.
00005 # The PyMite VM is free software: you can redistribute it and/or modify
00006 # it under the terms of the GNU GENERAL PUBLIC LICENSE Version 2.
00007 #
00008 # The PyMite VM is distributed in the hope that it will be useful,
00009 # but WITHOUT ANY WARRANTY; without even the implied warranty of
00010 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00011 # A copy of the GNU GENERAL PUBLIC LICENSE Version 2
00012 # is seen in the file COPYING in this directory.
00013 */
00014 
00015 
00016 #ifndef __SEGLIST_H__
00017 #define __SEGLIST_H__
00018 
00019 
00020 /**
00021  * \file
00022  * \brief Segmented List data structure
00023  *
00024  * A seglist is a linked list of segments.
00025  * A segment is an array of ptrs to objects
00026  * (with a pointer to the next segment).
00027  * Seglists are used to implement Lists and Dicts.
00028  *
00029  * This implementation of Seglist is straight.
00030  * That is, the next pointer in the final segment
00031  * contains C_NULL.
00032  *
00033  * This implementation of Seglist is dense.
00034  * That is, there are no gaps in a segment.
00035  * All entries point to an object, except entries
00036  * that are beyond the index of the last item.
00037  */
00038 
00039 
00040 /** Defines the length of the object array in a segment */
00041 #define SEGLIST_OBJS_PER_SEG 8
00042 
00043 
00044 /** Segment - an array of ptrs to objs */
00045 typedef struct Segment_s
00046 {
00047     /** object descriptor */
00048     PmObjDesc_t od;
00049     /** array of ptrs to objs */
00050     pPmObj_t s_val[SEGLIST_OBJS_PER_SEG];
00051     /** ptr to next segment */
00052     struct Segment_s *next;
00053 } Segment_t,
00054  *pSegment_t;
00055 
00056 
00057 /** Seglist - linked list of segments with current index info */
00058 typedef struct Seglist_s
00059 {
00060     /** object descriptor */
00061     PmObjDesc_t od;
00062     /** ptr to first segment in list */
00063     pSegment_t sl_rootseg;
00064     /** ptr to last segment */
00065     pSegment_t sl_lastseg;
00066     /** index of (one past) last obj in last segment */
00067     int16_t sl_length;
00068 } Seglist_t,
00069  *pSeglist_t;
00070 
00071 
00072 /**
00073  * Puts the new object at the end of the list.
00074  * This is intended for the List type where
00075  * the List index matches the order of the Seglist index.
00076  * Makes room if necessary by adding new segments.
00077  *
00078  * @param pseglist Ptr to seglist
00079  * @param pobj Pointer to object to append
00080  * @return Return status
00081  */
00082 PmReturn_t seglist_appendItem(pSeglist_t pseglist, pPmObj_t pobj);
00083 
00084 /**
00085  * Clears the the seglist by unlinking the root segment.
00086  *
00087  * @param pseglist Ptr to seglist to empty
00088  */
00089 PmReturn_t seglist_clear(pSeglist_t pseglist);
00090 
00091 /**
00092  * Finds the first obj equal to pobj in the seglist.
00093  * Starts searching the list at the given segnum and indx.
00094  *
00095  * @param   pseglist The seglist to search
00096  * @param   pobj The object to match
00097  * @param   r_index Return arg; the index of where to start the search.
00098  *          If a match is found, return the index by reference.
00099  *          If no match is found, this value is undefined.
00100  * @return  Return status; PM_RET_OK means a matching object
00101  *          was found.  PM_RET_ERR otherwise.
00102  */
00103 PmReturn_t seglist_findEqual(pSeglist_t pseglist,
00104                              pPmObj_t pobj, int16_t *r_index);
00105 
00106 /**
00107  * Gets the item in the seglist at the given coordinates.
00108  * The segment number and the index within the segment
00109  * are the coordinates of the object to get.
00110  *
00111  * @param   pseglist Ptr to seglist to scan
00112  * @param   index Index of item to get
00113  * @param   r_pobj Return arg; Ptr to object at the index
00114  * @return  Return status; PM_RET_OK if object found.
00115  *          PM_RET_ERR otherwise.
00116  */
00117 PmReturn_t seglist_getItem(pSeglist_t pseglist,
00118                            int16_t index, pPmObj_t *r_pobj);
00119 
00120 /**
00121  * Allocates a new empty seglist
00122  *
00123  * @param   r_pseglist return; Address of ptr to new seglist
00124  * @return  Return status
00125  */
00126 PmReturn_t seglist_new(pSeglist_t *r_pseglist);
00127 
00128 
00129 /**
00130  * Puts the item in the next available slot in the first available segment.
00131  * This is intended for the Dict type where
00132  * the Seglist index is insignificant.
00133  * Pushing an object assures it will be found early
00134  * during a call to seglist_findEqual().
00135  *
00136  * @param   pseglist Ptr to seglist in which object is placed.
00137  * @param   pobj Ptr to object which is inserted.
00138  * @param   index Index into seglist before which item is inserted
00139  * @return  Return status; PM_RET_OK if the item was inserted.
00140  *              Any error condition comes from heap_getChunk.
00141  */
00142 PmReturn_t seglist_insertItem(pSeglist_t pseglist,
00143                               pPmObj_t pobj, int16_t index);
00144 
00145 /**
00146  * Puts the item in the designated slot and segment.
00147  * This is intended to be used after seglist_findEqual()
00148  * returns the proper indeces.
00149  *
00150  * @param   pseglist Ptr to seglist in which object is placed.
00151  * @param   pobj Ptr to object which is set.
00152  * @param   index Index into seglist of where to put object.
00153  * @return  Return status; PM_RET_OK if object is set.
00154  *              PM_RET_ERR otherwise.
00155  */
00156 PmReturn_t seglist_setItem(pSeglist_t pseglist, pPmObj_t pobj, int16_t index);
00157 
00158 /**
00159  * Removes the item at the given index.
00160  *
00161  * @param   pseglist Ptr to seglist in which object is removed.
00162  * @param   index Index into seglist of where to put object.
00163  * @return  Return status
00164  */
00165 PmReturn_t seglist_removeItem(pSeglist_t pseglist, uint16_t index);
00166 
00167 #endif /* __SEGLIST_H__ */