flight/libraries/PyMite/vm/seglist.c

   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 #undef __FILE_ID__
  17 #define __FILE_ID__ 0x10
  18
  19
  20 /**
  21  * \file
  22  * \brief Segmented list data type and operations
  23  *
  24  * The segmented list is used to implement the Python
  25  * List and Dict data types.
  26  * The segmented list is used in preference to the linked list
  27  * in order to reduce the memory overhead.
  28  *
  29  * Unused slots in the segments are expected to contain C_NULL.
  30  *
  31  * List implementation:
  32  * When used in a List, the Seglist.currseg field points
  33  * to the last segment in the list.
  34  * The function seglist_appendItem() should be used to append
  35  * items to the List.
  36  * Inserting and deleting List items is a more complicated
  37  * matter.
  38  *
  39  * Dict implementation:
  40  * The currseg field is meaningless since rootseg always
  41  * points to the current active segment.
  42  * The function seglist_pushItem() should be used to put
  43  * items in the Dict.
  44  * A Dict uses one Seglist for keys and another for values.
  45  * A Dict entry's (key, value) pair share the same index in
  46  * the Seglist.
  47  */
  48
  49
  50 #include "pm.h"
  51
  52
  53 /**
  54  * Set this to 1 if seglist_clear() should manually free its segments.
  55  * Set this to 0 if seglist_clear() should do nothing
  56  * and let the GC reclaim objects.
  57  */
  58 #define SEGLIST_CLEAR_SEGMENTS 1
  59
  60
  61 PmReturn_t
  62 seglist_appendItem(pSeglist_t pseglist, pPmObj_t pobj)
  63 {
  64     return seglist_insertItem(pseglist, pobj, pseglist->sl_length);
  65 }
  66
  67
  68 PmReturn_t
  69 seglist_clear(pSeglist_t pseglist)
  70 {
  71     pSegment_t pseg1 = C_NULL;
  72     pSegment_t pseg2 = C_NULL;
  73
  74 #if SEGLIST_CLEAR_SEGMENTS
  75     /* Deallocate all linked segments */
  76     pseg1 = ((pSeglist_t)pseglist)->sl_rootseg;
  77     while (pseg1 != C_NULL)
  78     {
  79         pseg2 = pseg1->next;
  80         PM_RETURN_IF_ERROR(heap_freeChunk((pPmObj_t)pseg1));
  81         pseg1 = pseg2;
  82     }
  83 #endif
  84
  85     /* Clear seglist fields */
  86     ((pSeglist_t)pseglist)->sl_rootseg = C_NULL;
  87     ((pSeglist_t)pseglist)->sl_lastseg = C_NULL;
  88     ((pSeglist_t)pseglist)->sl_length = 0;
  89
  90     return PM_RET_OK;
  91 }
  92
  93
  94 PmReturn_t
  95 seglist_findEqual(pSeglist_t pseglist, pPmObj_t pobj, int16_t *r_index)
  96 {
  97     pSegment_t pseg;
  98     int8_t i = 0;
  99     uint8_t segindex;
 100
 101     C_ASSERT(pseglist != C_NULL);
 102     C_ASSERT(pobj != C_NULL);
 103     C_ASSERT((*r_index >= 0));
 104     C_ASSERT((*r_index == 0) || (*r_index < pseglist->sl_length));
 105
 106     /* Walk out to the starting segment */
 107     pseg = pseglist->sl_rootseg;
 108     for (i = (*r_index / SEGLIST_OBJS_PER_SEG); i > (int8_t)0; i--)
 109     {
 110         C_ASSERT(pseg != C_NULL);
 111         pseg = pseg->next;
 112     }
 113
 114     /* Set the starting index within the segment */
 115     segindex = *r_index % SEGLIST_OBJS_PER_SEG;
 116
 117     /* Search the remaining segments */
 118     for (; pseg != C_NULL; pseg = pseg->next)
 119     {
 120         while (segindex < SEGLIST_OBJS_PER_SEG)
 121         {
 122             /* If past the end of the seglist, return no item found */
 123             if (*r_index >= pseglist->sl_length)
 124             {
 125                 return PM_RET_NO;
 126             }
 127
 128             /* If items are equal, return with index of found item */
 129             if (obj_compare(pobj, pseg->s_val[segindex]) == C_SAME)
 130             {
 131                 return PM_RET_OK;
 132             }
 133
 134             /* Proceed to next item */
 135             segindex++;
 136             (*r_index)++;
 137         }
 138
 139         /* Proceed to next segment */
 140         segindex = 0;
 141     }
 142     return PM_RET_NO;
 143 }
 144
 145
 146 PmReturn_t
 147 seglist_getItem(pSeglist_t pseglist, int16_t index, pPmObj_t *r_pobj)
 148 {
 149     pSegment_t pseg;
 150     int16_t i;
 151
 152     C_ASSERT(pseglist != C_NULL);
 153     C_ASSERT(index >= 0);
 154     C_ASSERT(index < pseglist->sl_length);
 155
 156     /* Walk out to the proper segment */
 157     pseg = pseglist->sl_rootseg;
 158     C_ASSERT(pseg != C_NULL);
 159     for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--)
 160     {
 161         pseg = pseg->next;
 162         C_ASSERT(pseg != C_NULL);
 163     }
 164
 165     /* Return ptr to obj in this seg at the index */
 166     *r_pobj = pseg->s_val[index % SEGLIST_OBJS_PER_SEG];
 167     return PM_RET_OK;
 168 }
 169
 170
 171 PmReturn_t
 172 seglist_insertItem(pSeglist_t pseglist, pPmObj_t pobj, int16_t index)
 173 {
 174     PmReturn_t retval = PM_RET_OK;
 175     pSegment_t pseg = C_NULL;
 176     pPmObj_t pobj1 = C_NULL;
 177     pPmObj_t pobj2 = C_NULL;
 178     int8_t indx = (int8_t)0;
 179     int16_t i = 0;
 180     uint8_t *pchunk;
 181
 182     C_ASSERT(index <= pseglist->sl_length);
 183
 184     /* If a new seg is needed */
 185     if ((pseglist->sl_length % SEGLIST_OBJS_PER_SEG) == 0)
 186     {
 187         /* Alloc and init new segment */
 188         retval = heap_getChunk(sizeof(Segment_t), &pchunk);
 189         PM_RETURN_IF_ERROR(retval);
 190         pseg = (pSegment_t)pchunk;
 191         OBJ_SET_TYPE(pseg, OBJ_TYPE_SEG);
 192         sli_memset((unsigned char *)pseg->s_val,
 193                    0, SEGLIST_OBJS_PER_SEG * sizeof(pPmObj_t));
 194         pseg->next = C_NULL;
 195
 196         /* If this is the first seg, set as root */
 197         if (pseglist->sl_rootseg == C_NULL)
 198         {
 199             pseglist->sl_rootseg = pseg;
 200         }
 201
 202         /* Else append the seg to the end */
 203         else
 204         {
 205             pseglist->sl_lastseg->next = pseg;
 206         }
 207
 208         /* Either way, this is now the last segment */
 209         pseglist->sl_lastseg = pseg;
 210     }
 211
 212     /* Walk out to the segment for insertion */
 213     pseg = pseglist->sl_rootseg;
 214     C_ASSERT(pseg != C_NULL);
 215     for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--)
 216     {
 217         pseg = pseg->next;
 218         C_ASSERT(pseg != C_NULL);
 219     }
 220
 221     /* Insert obj and ripple copy all those afterward */
 222     indx = index % SEGLIST_OBJS_PER_SEG;;
 223     pobj1 = pobj;
 224     while (pobj1 != C_NULL)
 225     {
 226         pobj2 = pseg->s_val[indx];
 227         pseg->s_val[indx] = pobj1;
 228         pobj1 = pobj2;
 229         indx++;
 230
 231         /* If indx exceeds this seg, go to next seg */
 232         if ((indx >= SEGLIST_OBJS_PER_SEG) && (pobj1 != C_NULL))
 233         {
 234             pseg = pseg->next;
 235             C_ASSERT(pseg != C_NULL);
 236             indx = (int8_t)0;
 237         }
 238     }
 239     pseglist->sl_length++;
 240     return retval;
 241 }
 242
 243
 244 PmReturn_t
 245 seglist_new(pSeglist_t *r_pseglist)
 246 {
 247     PmReturn_t retval = PM_RET_OK;
 248
 249     retval = heap_getChunk(sizeof(Seglist_t), (uint8_t **)r_pseglist);
 250     PM_RETURN_IF_ERROR(retval);
 251
 252     OBJ_SET_TYPE(*r_pseglist, OBJ_TYPE_SGL);
 253     (*r_pseglist)->sl_rootseg = C_NULL;
 254     (*r_pseglist)->sl_lastseg = C_NULL;
 255     (*r_pseglist)->sl_length = 0;
 256     return retval;
 257 }
 258
 259
 260 PmReturn_t
 261 seglist_setItem(pSeglist_t pseglist, pPmObj_t pobj, int16_t index)
 262 {
 263     pSegment_t pseg;
 264     int16_t i;
 265
 266     C_ASSERT(index <= pseglist->sl_length);
 267
 268     /* Walk out to the proper segment */
 269     pseg = pseglist->sl_rootseg;
 270     C_ASSERT(pseg != C_NULL);
 271     for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--)
 272     {
 273         pseg = pseg->next;
 274         C_ASSERT(pseg != C_NULL);
 275     }
 276
 277     /* Set item in this seg at the index */
 278     pseg->s_val[index % SEGLIST_OBJS_PER_SEG] = pobj;
 279     return PM_RET_OK;
 280 }
 281
 282
 283 PmReturn_t
 284 seglist_removeItem(pSeglist_t pseglist, uint16_t index)
 285 {
 286     pSegment_t pseg;
 287     int16_t i,
 288       k;
 289
 290     C_ASSERT(index < pseglist->sl_length);
 291
 292     /* Walk through the segments */
 293     pseg = pseglist->sl_rootseg;
 294     C_ASSERT(pseg != C_NULL);
 295     for (i = (index / SEGLIST_OBJS_PER_SEG); i > 0; i--)
 296     {
 297         pseg = pseg->next;
 298         C_ASSERT(pseg != C_NULL);
 299     }
 300
 301     /*
 302      * pseg now points to the correct segment of the item to be removed, so
 303      * start ripple copying all following items up to the last
 304      * in the last segment
 305      */
 306
 307     for (i = index; i < ((pseglist->sl_length) - 1); i++)
 308     {
 309         k = i % SEGLIST_OBJS_PER_SEG;
 310
 311         /* Copy element i+1 to slot i */
 312         if ((k + 1) == SEGLIST_OBJS_PER_SEG)
 313         {
 314             /* Source is first item in next segment */
 315             pseg->s_val[i % SEGLIST_OBJS_PER_SEG] = (pseg->next)->s_val[0];
 316             pseg = pseg->next;
 317         }
 318         else
 319         {
 320             /* Source and target are in the same segment */
 321             pseg->s_val[k] = pseg->s_val[k + 1];
 322         }
 323     }
 324
 325     pseglist->sl_length -= 1;
 326
 327     /* Remove the last segment if it was emptied */
 328     if (pseglist->sl_length % SEGLIST_OBJS_PER_SEG == 0)
 329     {
 330         pseg = pseglist->sl_rootseg;
 331
 332         /* Find the segment before the last */
 333         for (i = 0; i < ((pseglist->sl_length - 1) / SEGLIST_OBJS_PER_SEG);
 334              i++)
 335         {
 336             pseg = pseg->next;
 337             C_ASSERT(pseg != C_NULL);
 338         }
 339         if (pseg->next == C_NULL)
 340         {
 341             /*
 342              * Seglist is now completely empty and the last segment can be
 343              * recycled.
 344              */
 345 #if SEGLIST_CLEAR_SEGMENTS
 346             PM_RETURN_IF_ERROR(heap_freeChunk((pPmObj_t)pseg));
 347 #endif
 348             pseglist->sl_lastseg = C_NULL;
 349             pseglist->sl_rootseg = C_NULL;
 350         }
 351         else
 352         {
 353             /* At least one segment remains */
 354             pseglist->sl_lastseg = pseg;
 355             pseg->next = C_NULL;
 356         }
 357     }
 358     else
 359     {
 360         /* Zero out the now unused slot */
 361         pseg->s_val[pseglist->sl_length % SEGLIST_OBJS_PER_SEG] = C_NULL;
 362     }
 363
 364     return PM_RET_OK;
 365 }