flight/libraries/PyMite/vm/seglist.h

   1 /*
   2 # This file is Copyright 2003, 2006, 2007, 2009, 2010 Dean Hall.
   3 #
   4 # This file is part of the PyMite VM.
   5 # The PyMite VM is free software: you can redistribute it and/or modify
   6 # it under the terms of the GNU GENERAL PUBLIC LICENSE Version 2.
   7 #
   8 # The PyMite VM is distributed in the hope that it will be useful,
   9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  11 # A copy of the GNU GENERAL PUBLIC LICENSE Version 2
  12 # is seen in the file COPYING in this directory.
  13 */
  14
  15
  16 #ifndef __SEGLIST_H__
  17 #define __SEGLIST_H__
  18
  19
  20 /**
  21  * \file
  22  * \brief Segmented List data structure
  23  *
  24  * A seglist is a linked list of segments.
  25  * A segment is an array of ptrs to objects
  26  * (with a pointer to the next segment).
  27  * Seglists are used to implement Lists and Dicts.
  28  *
  29  * This implementation of Seglist is straight.
  30  * That is, the next pointer in the final segment
  31  * contains C_NULL.
  32  *
  33  * This implementation of Seglist is dense.
  34  * That is, there are no gaps in a segment.
  35  * All entries point to an object, except entries
  36  * that are beyond the index of the last item.
  37  */
  38
  39
  40 /** Defines the length of the object array in a segment */
  41 #define SEGLIST_OBJS_PER_SEG 8
  42
  43
  44 /** Segment - an array of ptrs to objs */
  45 typedef struct Segment_s
  46 {
  47     /** object descriptor */
  48     PmObjDesc_t od;
  49     /** array of ptrs to objs */
  50     pPmObj_t s_val[SEGLIST_OBJS_PER_SEG];
  51     /** ptr to next segment */
  52     struct Segment_s *next;
  53 } Segment_t,
  54  *pSegment_t;
  55
  56
  57 /** Seglist - linked list of segments with current index info */
  58 typedef struct Seglist_s
  59 {
  60     /** object descriptor */
  61     PmObjDesc_t od;
  62     /** ptr to first segment in list */
  63     pSegment_t sl_rootseg;
  64     /** ptr to last segment */
  65     pSegment_t sl_lastseg;
  66     /** index of (one past) last obj in last segment */
  67     int16_t sl_length;
  68 } Seglist_t,
  69  *pSeglist_t;
  70
  71
  72 /**
  73  * Puts the new object at the end of the list.
  74  * This is intended for the List type where
  75  * the List index matches the order of the Seglist index.
  76  * Makes room if necessary by adding new segments.
  77  *
  78  * @param pseglist Ptr to seglist
  79  * @param pobj Pointer to object to append
  80  * @return Return status
  81  */
  82 PmReturn_t seglist_appendItem(pSeglist_t pseglist, pPmObj_t pobj);
  83
  84 /**
  85  * Clears the the seglist by unlinking the root segment.
  86  *
  87  * @param pseglist Ptr to seglist to empty
  88  */
  89 PmReturn_t seglist_clear(pSeglist_t pseglist);
  90
  91 /**
  92  * Finds the first obj equal to pobj in the seglist.
  93  * Starts searching the list at the given segnum and indx.
  94  *
  95  * @param   pseglist The seglist to search
  96  * @param   pobj The object to match
  97  * @param   r_index Return arg; the index of where to start the search.
  98  *          If a match is found, return the index by reference.
  99  *          If no match is found, this value is undefined.
 100  * @return  Return status; PM_RET_OK means a matching object
 101  *          was found.  PM_RET_ERR otherwise.
 102  */
 103 PmReturn_t seglist_findEqual(pSeglist_t pseglist,
 104                              pPmObj_t pobj, int16_t *r_index);
 105
 106 /**
 107  * Gets the item in the seglist at the given coordinates.
 108  * The segment number and the index within the segment
 109  * are the coordinates of the object to get.
 110  *
 111  * @param   pseglist Ptr to seglist to scan
 112  * @param   index Index of item to get
 113  * @param   r_pobj Return arg; Ptr to object at the index
 114  * @return  Return status; PM_RET_OK if object found.
 115  *          PM_RET_ERR otherwise.
 116  */
 117 PmReturn_t seglist_getItem(pSeglist_t pseglist,
 118                            int16_t index, pPmObj_t *r_pobj);
 119
 120 /**
 121  * Allocates a new empty seglist
 122  *
 123  * @param   r_pseglist return; Address of ptr to new seglist
 124  * @return  Return status
 125  */
 126 PmReturn_t seglist_new(pSeglist_t *r_pseglist);
 127
 128
 129 /**
 130  * Puts the item in the next available slot in the first available segment.
 131  * This is intended for the Dict type where
 132  * the Seglist index is insignificant.
 133  * Pushing an object assures it will be found early
 134  * during a call to seglist_findEqual().
 135  *
 136  * @param   pseglist Ptr to seglist in which object is placed.
 137  * @param   pobj Ptr to object which is inserted.
 138  * @param   index Index into seglist before which item is inserted
 139  * @return  Return status; PM_RET_OK if the item was inserted.
 140  *              Any error condition comes from heap_getChunk.
 141  */
 142 PmReturn_t seglist_insertItem(pSeglist_t pseglist,
 143                               pPmObj_t pobj, int16_t index);
 144
 145 /**
 146  * Puts the item in the designated slot and segment.
 147  * This is intended to be used after seglist_findEqual()
 148  * returns the proper indeces.
 149  *
 150  * @param   pseglist Ptr to seglist in which object is placed.
 151  * @param   pobj Ptr to object which is set.
 152  * @param   index Index into seglist of where to put object.
 153  * @return  Return status; PM_RET_OK if object is set.
 154  *              PM_RET_ERR otherwise.
 155  */
 156 PmReturn_t seglist_setItem(pSeglist_t pseglist, pPmObj_t pobj, int16_t index);
 157
 158 /**
 159  * Removes the item at the given index.
 160  *
 161  * @param   pseglist Ptr to seglist in which object is removed.
 162  * @param   index Index into seglist of where to put object.
 163  * @return  Return status
 164  */
 165 PmReturn_t seglist_removeItem(pSeglist_t pseglist, uint16_t index);
 166
 167 #endif /* __SEGLIST_H__ */