seglist.h

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