Norimasa Okamoto
/
pymite
python-on-a-chip online compiler
Embed:
(wiki syntax)
Show/hide line numbers
seglist.h
Go to the documentation of this file.
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__ */
Generated on Tue Jul 12 2022 23:13:47 by 1.7.2