seglist.c

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