Norimasa Okamoto
/
pymite
python-on-a-chip online compiler
Embed:
(wiki syntax)
Show/hide line numbers
seglist.c
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 #undef __FILE_ID__ 00010 #define __FILE_ID__ 0x10 00011 00012 00013 /** 00014 * \file 00015 * \brief Segmented list data type and operations 00016 * 00017 * The segmented list is used to implement the Python 00018 * List and Dict data types. 00019 * The segmented list is used in preference to the linked list 00020 * in order to reduce the memory overhead. 00021 * 00022 * Unused slots in the segments are expected to contain C_NULL. 00023 * 00024 * List implementation: 00025 * When used in a List, the Seglist.currseg field points 00026 * to the last segment in the list. 00027 * The function seglist_appendItem() should be used to append 00028 * items to the List. 00029 * Inserting and deleting List items is a more complicated 00030 * matter. 00031 * 00032 * Dict implementation: 00033 * The currseg field is meaningless since rootseg always 00034 * points to the current active segment. 00035 * The function seglist_pushItem() should be used to put 00036 * items in the Dict. 00037 * A Dict uses one Seglist for keys and another for values. 00038 * A Dict entry's (key, value) pair share the same index in 00039 * the Seglist. 00040 */ 00041 00042 00043 #include "pm.h" 00044 00045 00046 /** 00047 * Set this to 1 if seglist_clear() should manually free its segments. 00048 * Set this to 0 if seglist_clear() should do nothing 00049 * and let the GC reclaim objects. 00050 */ 00051 #define SEGLIST_CLEAR_SEGMENTS 1 00052 00053 00054 PmReturn_t 00055 seglist_appendItem(pSeglist_t pseglist, pPmObj_t pobj) 00056 { 00057 return seglist_insertItem(pseglist, pobj, pseglist->sl_length); 00058 } 00059 00060 00061 PmReturn_t 00062 seglist_clear(pSeglist_t pseglist) 00063 { 00064 pSegment_t pseg1 = C_NULL; 00065 pSegment_t pseg2 = C_NULL; 00066 00067 #if SEGLIST_CLEAR_SEGMENTS 00068 /* Deallocate all linked segments */ 00069 pseg1 = ((pSeglist_t)pseglist)->sl_rootseg; 00070 while (pseg1 != C_NULL) 00071 { 00072 pseg2 = pseg1->next; 00073 PM_RETURN_IF_ERROR(heap_freeChunk((pPmObj_t)pseg1)); 00074 pseg1 = pseg2; 00075 } 00076 #endif 00077 00078 /* Clear seglist fields */ 00079 ((pSeglist_t)pseglist)->sl_rootseg = C_NULL; 00080 ((pSeglist_t)pseglist)->sl_lastseg = C_NULL; 00081 ((pSeglist_t)pseglist)->sl_length = 0; 00082 00083 return PM_RET_OK; 00084 } 00085 00086 00087 PmReturn_t 00088 seglist_findEqual(pSeglist_t pseglist, pPmObj_t pobj, int16_t *r_index) 00089 { 00090 pSegment_t pseg; 00091 int8_t i = 0; 00092 uint8_t segindex; 00093 00094 C_ASSERT(pseglist != C_NULL); 00095 C_ASSERT(pobj != C_NULL); 00096 C_ASSERT((*r_index >= 0)); 00097 C_ASSERT((*r_index == 0) || (*r_index < pseglist->sl_length)); 00098 00099 /* Walk out to the starting segment */ 00100 pseg = pseglist->sl_rootseg; 00101 for (i = (*r_index / SEGLIST_OBJS_PER_SEG); i > (int8_t)0; i--) 00102 { 00103 C_ASSERT(pseg != C_NULL); 00104 pseg = pseg->next; 00105 } 00106 00107 /* Set the starting index within the segment */ 00108 segindex = *r_index % SEGLIST_OBJS_PER_SEG; 00109 00110 /* Search the remaining segments */ 00111 for (; pseg != C_NULL; pseg = pseg->next) 00112 { 00113 while (segindex < SEGLIST_OBJS_PER_SEG) 00114 { 00115 /* If past the end of the seglist, return no item found */ 00116 if (*r_index >= pseglist->sl_length) 00117 { 00118 return PM_RET_NO; 00119 } 00120 00121 /* If items are equal, return with index of found item */ 00122 if (obj_compare(pobj, pseg->s_val[segindex]) == C_SAME) 00123 { 00124 return PM_RET_OK; 00125 } 00126 00127 /* Proceed to next item */ 00128 segindex++; 00129 (*r_index)++; 00130 } 00131 00132 /* Proceed to next segment */ 00133 segindex = 0; 00134 } 00135 return PM_RET_NO; 00136 } 00137 00138 00139 PmReturn_t 00140 seglist_getItem(pSeglist_t pseglist, int16_t index, pPmObj_t *r_pobj) 00141 { 00142 pSegment_t pseg; 00143 int16_t i; 00144 00145 C_ASSERT(pseglist != C_NULL); 00146 C_ASSERT(index >= 0); 00147 C_ASSERT(index < pseglist->sl_length); 00148 00149 /* Walk out to the proper segment */ 00150 pseg = pseglist->sl_rootseg; 00151 C_ASSERT(pseg != C_NULL); 00152 for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--) 00153 { 00154 pseg = pseg->next; 00155 C_ASSERT(pseg != C_NULL); 00156 } 00157 00158 /* Return ptr to obj in this seg at the index */ 00159 *r_pobj = pseg->s_val[index % SEGLIST_OBJS_PER_SEG]; 00160 return PM_RET_OK; 00161 } 00162 00163 00164 PmReturn_t 00165 seglist_insertItem(pSeglist_t pseglist, pPmObj_t pobj, int16_t index) 00166 { 00167 PmReturn_t retval = PM_RET_OK; 00168 pSegment_t pseg = C_NULL; 00169 pPmObj_t pobj1 = C_NULL; 00170 pPmObj_t pobj2 = C_NULL; 00171 int8_t indx = (int8_t)0; 00172 int16_t i = 0; 00173 uint8_t *pchunk; 00174 00175 C_ASSERT(index <= pseglist->sl_length); 00176 00177 /* If a new seg is needed */ 00178 if ((pseglist->sl_length % SEGLIST_OBJS_PER_SEG) == 0) 00179 { 00180 /* Alloc and init new segment */ 00181 retval = heap_getChunk(sizeof(Segment_t), &pchunk); 00182 PM_RETURN_IF_ERROR(retval); 00183 pseg = (pSegment_t)pchunk; 00184 OBJ_SET_TYPE(pseg, OBJ_TYPE_SEG); 00185 sli_memset((unsigned char *)pseg->s_val, 00186 0, SEGLIST_OBJS_PER_SEG * sizeof(pPmObj_t)); 00187 pseg->next = C_NULL; 00188 00189 /* If this is the first seg, set as root */ 00190 if (pseglist->sl_rootseg == C_NULL) 00191 { 00192 pseglist->sl_rootseg = pseg; 00193 } 00194 00195 /* Else append the seg to the end */ 00196 else 00197 { 00198 pseglist->sl_lastseg->next = pseg; 00199 } 00200 00201 /* Either way, this is now the last segment */ 00202 pseglist->sl_lastseg = pseg; 00203 } 00204 00205 /* Walk out to the segment for insertion */ 00206 pseg = pseglist->sl_rootseg; 00207 C_ASSERT(pseg != C_NULL); 00208 for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--) 00209 { 00210 pseg = pseg->next; 00211 C_ASSERT(pseg != C_NULL); 00212 } 00213 00214 /* Insert obj and ripple copy all those afterward */ 00215 indx = index % SEGLIST_OBJS_PER_SEG;; 00216 pobj1 = pobj; 00217 while (pobj1 != C_NULL) 00218 { 00219 pobj2 = pseg->s_val[indx]; 00220 pseg->s_val[indx] = pobj1; 00221 pobj1 = pobj2; 00222 indx++; 00223 00224 /* If indx exceeds this seg, go to next seg */ 00225 if ((indx >= SEGLIST_OBJS_PER_SEG) && (pobj1 != C_NULL)) 00226 { 00227 pseg = pseg->next; 00228 C_ASSERT(pseg != C_NULL); 00229 indx = (int8_t)0; 00230 } 00231 } 00232 pseglist->sl_length++; 00233 return retval; 00234 } 00235 00236 00237 PmReturn_t 00238 seglist_new(pSeglist_t *r_pseglist) 00239 { 00240 PmReturn_t retval = PM_RET_OK; 00241 00242 retval = heap_getChunk(sizeof(Seglist_t), (uint8_t **)r_pseglist); 00243 PM_RETURN_IF_ERROR(retval); 00244 00245 OBJ_SET_TYPE(*r_pseglist, OBJ_TYPE_SGL); 00246 (*r_pseglist)->sl_rootseg = C_NULL; 00247 (*r_pseglist)->sl_lastseg = C_NULL; 00248 (*r_pseglist)->sl_length = 0; 00249 return retval; 00250 } 00251 00252 00253 PmReturn_t 00254 seglist_setItem(pSeglist_t pseglist, pPmObj_t pobj, int16_t index) 00255 { 00256 pSegment_t pseg; 00257 int16_t i; 00258 00259 C_ASSERT(index <= pseglist->sl_length); 00260 00261 /* Walk out to the proper segment */ 00262 pseg = pseglist->sl_rootseg; 00263 C_ASSERT(pseg != C_NULL); 00264 for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--) 00265 { 00266 pseg = pseg->next; 00267 C_ASSERT(pseg != C_NULL); 00268 } 00269 00270 /* Set item in this seg at the index */ 00271 pseg->s_val[index % SEGLIST_OBJS_PER_SEG] = pobj; 00272 return PM_RET_OK; 00273 } 00274 00275 00276 PmReturn_t 00277 seglist_removeItem(pSeglist_t pseglist, uint16_t index) 00278 { 00279 pSegment_t pseg; 00280 int16_t i, 00281 k; 00282 00283 C_ASSERT(index < pseglist->sl_length); 00284 00285 /* Walk through the segments */ 00286 pseg = pseglist->sl_rootseg; 00287 C_ASSERT(pseg != C_NULL); 00288 for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--) 00289 { 00290 pseg = pseg->next; 00291 C_ASSERT(pseg != C_NULL); 00292 } 00293 00294 /* 00295 * pseg now points to the correct segment of the item to be removed, so 00296 * start ripple copying all following items up to the last 00297 * in the last segment 00298 */ 00299 00300 for (i = index; i < ((pseglist->sl_length) - 1); i++) 00301 { 00302 k = i % SEGLIST_OBJS_PER_SEG; 00303 00304 /* Copy element i+1 to slot i */ 00305 if ((k + 1) == SEGLIST_OBJS_PER_SEG) 00306 { 00307 /* Source is first item in next segment */ 00308 pseg->s_val[i % SEGLIST_OBJS_PER_SEG] = (pseg->next)->s_val[0]; 00309 pseg = pseg->next; 00310 } 00311 else 00312 { 00313 /* Source and target are in the same segment */ 00314 pseg->s_val[k] = pseg->s_val[k + 1]; 00315 } 00316 } 00317 00318 pseglist->sl_length -= 1; 00319 00320 /* Remove the last segment if it was emptied */ 00321 if (pseglist->sl_length % SEGLIST_OBJS_PER_SEG == 0) 00322 { 00323 pseg = pseglist->sl_rootseg; 00324 00325 /* Find the segment before the last */ 00326 for (i = 0; i < ((pseglist->sl_length - 1) / SEGLIST_OBJS_PER_SEG); 00327 i++) 00328 { 00329 pseg = pseg->next; 00330 C_ASSERT(pseg != C_NULL); 00331 } 00332 if (pseg->next == C_NULL) 00333 { 00334 /* 00335 * Seglist is now completely empty and the last segment can be 00336 * recycled. 00337 */ 00338 #if SEGLIST_CLEAR_SEGMENTS 00339 PM_RETURN_IF_ERROR(heap_freeChunk((pPmObj_t)pseg)); 00340 #endif 00341 pseglist->sl_lastseg = C_NULL; 00342 pseglist->sl_rootseg = C_NULL; 00343 } 00344 else 00345 { 00346 /* At least one segment remains */ 00347 pseglist->sl_lastseg = pseg; 00348 pseg->next = C_NULL; 00349 } 00350 } 00351 else 00352 { 00353 /* Zero out the now unused slot */ 00354 pseg->s_val[pseglist->sl_length % SEGLIST_OBJS_PER_SEG] = C_NULL; 00355 } 00356 00357 return PM_RET_OK; 00358 }
Generated on Tue Jul 12 2022 23:13:47 by 1.7.2