seglist.c

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 }