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