src/intlist.c

   1 /*
   2 Copyright (C) 2001-2008, The Perl Foundation.
   3 $Id$
   4
   5 =head1 NAME
   6
   7 src/intlists.c - Regex stack handling routines
   8
   9 =head1 DESCRIPTION
  10
  11 intlist emulation code, calls routines in F<src/list.c>.
  12
  13 Here is the original documentation for intlist:
  14
  15 The basic data structure is a variant of a doubly-linked list
  16 of 'chunks', where a chunk is a C<Buffer> header subclass
  17 containing the link pointers and other metadata for the chunk.
  18 As expected from it being a C<Buffer> header, the C<PObj_bufstart>
  19 field points to the actual array of C<INTVAL>s. The handle used by
  20 external code for one of these IntLists is just a pointer to a
  21 chunk, always called 'list' in this code.
  22
  23 For now, all of the chunks are fixed-length in size. (That
  24 could easily be changed, at the cost of another integer in each
  25 header.)
  26
  27 Notice that I said 'variant' of a doubly-linked list. That is
  28 because if you start at 'list' and follow prev pointers, you
  29 will loop through all the used nodes of the list, as usual. But
  30 if you follow next pointers instead, you might find a spare
  31 node hanging off the last node in the list (the last node is
  32 always C<< list->prev >>, so if there is a spare node, it will be at
  33 C<< list->prev->next >>. If no spare exists, then
  34 C<< list->prev->next==list >>.)
  35
  36 The first node in the list may be partly full; the intermediate
  37 nodes are always completely full; and the last node may be
  38 partly full. Each node has a C<.start> field, giving the offset of
  39 the first valid element (always zero except for possibly the
  40 first node), and a C<.end> field, giving one past the offset of
  41 the last valid element (always equal to C<INTLIST_CHUNK_SIZE>
  42 except for possibly the last node).
  43
  44 To make it concrete, let's walk through some sample operations.
  45 To push onto the end of the list, first find the last chunk:
  46 C<< list->prev >>. Then if C<< chunk->end < INTLIST_CHUNK_SIZE >>, there is
  47 space to fit another element and so just stick it in. If not,
  48 we must add a chunk to the end of the list. If there is a
  49 spare, just link it fully into the list (forming a conventional
  50 doubly-linked list). Otherwise, create a new chunk and link it
  51 fully into the list. Easy enough.
  52
  53 To pop something off the end, first go to the end chunk
  54 (C<< list->prev >>). Pop off an element and decrement C<.end> if the
  55 chunk is nonempty. If it is empty, make that last chunk into
  56 the spare (discarding the previous spare). Then go to the
  57 previous chunk, which is guaranteed to have C<.end> set to
  58 C<INTLIST_CHUNK_SIZE>, and return C<data[.end--]>.
  59
  60 The length of the list is always cached in the overall header
  61 chunk. If an operation changes which chunk is the header (i.e.,
  62 shift or unshift), then the length is copied to the new header.
  63
  64 Invariants:
  65
  66 There is always space in C<< list->prev >> to insert an element.
  67
  68 The 'list' chunk is never empty unless the entire list is
  69 empty.
  70
  71 In combination, the above invariants imply that the various
  72 operations are implemented as:
  73
  74 =over 4
  75
  76 =item C<push>
  77
  78 Write element, push a new chunk if necessary.
  79
  80 =item C<pop>
  81
  82 Check to see if we have to back up a chunk, read element.
  83
  84 =item C<shift>
  85
  86 Read element, discard chunk and advance if necessary.
  87
  88 =item C<unshift>
  89
  90 Unshift a chunk if necessary, write element.
  91
  92 =back
  93
  94 Direct aka indexed access of intlist data:
  95
  96 The classic method would be to walk the C<< intlist->next >> pointers
  97 (or optimized, the C<< ->prev >> pointers if an index near the end is
  98 requested) and locate the chunk, that holds the wanted list
  99 item.
 100
 101 To speed things up, especially for bigger lists, there are
 102 additional fields in the 'list' (the head chunk):
 103
 104 =over 4
 105
 106 =item C<chunk_list>
 107
 108 Holds pointers to individual chunks.
 109
 110 =item C<collect_runs>
 111
 112 C<collect_runs> counter, when C<chunk_list> was rebuilt last.
 113
 114 =item C<n_chunks>
 115
 116 Used length in C<chunk_list>
 117
 118 =back
 119
 120 If on any indexed access interpreter's collect_runs is
 121 different, the chunks might have been moved, so the chunk_list
 122 has to be rebuilt.
 123
 124 Getting data outside the array dimensions will
 125 return the value C<NULL>, which will C<SIGSEGV>, the intlist did
 126 an explicit exception, so there is not much difference.
 127 Of course, a check for valid pointers could be added here.
 128
 129 =head2 Functions
 130
 131 =over 4
 132
 133 =cut
 134
 135 */
 136
 137 #include "parrot/parrot.h"
 138
 139 /* HEADERIZER HFILE: include/parrot/intlist.h */
 140
 141 /*
 142
 143 =item C<void intlist_mark>
 144
 145 Marks the list as live.
 146
 147 =cut
 148
 149 */
 150
 151 void
 152 intlist_mark(PARROT_INTERP, ARGMOD(IntList *l))
 153 {
 154     list_mark(interp, (List *)l);
 155 }
 156
 157 /*
 158
 159 =item C<IntList * intlist_clone>
 160
 161 Returns a clone of the list.
 162
 163 =cut
 164
 165 */
 166
 167 PARROT_WARN_UNUSED_RESULT
 168 PARROT_CANNOT_RETURN_NULL
 169 IntList *
 170 intlist_clone(PARROT_INTERP, ARGIN(const IntList *list))
 171 {
 172     return (IntList *)list_clone(interp, (const List *)list);
 173 }
 174
 175 /*
 176
 177 =item C<IntList * intlist_new>
 178
 179 Returns a new list.
 180
 181 =cut
 182
 183 */
 184
 185 PARROT_WARN_UNUSED_RESULT
 186 PARROT_CANNOT_RETURN_NULL
 187 IntList *
 188 intlist_new(PARROT_INTERP)
 189 {
 190     return (IntList *)list_new(interp, enum_type_INTVAL);
 191 }
 192
 193 /*
 194
 195 =item C<INTVAL intlist_length>
 196
 197 Returns the length of the list.
 198
 199 =cut
 200
 201 */
 202
 203 PARROT_WARN_UNUSED_RESULT
 204 PARROT_PURE_FUNCTION
 205 INTVAL
 206 intlist_length(SHIM_INTERP, ARGIN(const IntList *list))
 207 {
 208     return ((const List *)list)->length;
 209 }
 210
 211 /*
 212
 213 =item C<void intlist_assign>
 214
 215 Assigns <val> to the item at C<idx>.
 216
 217 =cut
 218
 219 */
 220
 221 void
 222 intlist_assign(PARROT_INTERP, ARGMOD(IntList *l), INTVAL idx, INTVAL val)
 223 {
 224     list_assign(interp, (List *)l, idx, INTVAL2PTR(void *, val), enum_type_INTVAL);
 225 }
 226
 227 /*
 228
 229 =item C<void intlist_push>
 230
 231 Pushes C<val> on the end of the list.
 232
 233 =cut
 234
 235 */
 236
 237 void
 238 intlist_push(PARROT_INTERP, ARGMOD(IntList *l), INTVAL val)
 239 {
 240     list_push(interp, (List *)l, INTVAL2PTR(void *, val), enum_type_INTVAL);
 241 }
 242
 243 /*
 244
 245 =item C<void intlist_unshift>
 246
 247 Pushes C<val> on the front of the list.
 248
 249 =cut
 250
 251 */
 252
 253 void
 254 intlist_unshift(PARROT_INTERP, ARGMOD(IntList **l), INTVAL val)
 255 {
 256     list_unshift(interp, (List *)*l, INTVAL2PTR(void *, val), enum_type_INTVAL);
 257 }
 258
 259 /*
 260
 261 =item C<INTVAL intlist_pop>
 262
 263 Popping/shifting into a sparse hole returns 0.
 264
 265 =cut
 266
 267 */
 268
 269 INTVAL
 270 intlist_pop(PARROT_INTERP, ARGMOD(IntList *l))
 271 {
 272     void * const ret = list_pop(interp, (List *)l, enum_type_INTVAL);
 273     const INTVAL retval = ret == (void *)-1 ? 0 : *(INTVAL *)ret;
 274     return retval;
 275 }
 276
 277 /*
 278
 279 =item C<INTVAL intlist_shift>
 280
 281 Removes and returns the first item on the list.
 282
 283 =cut
 284
 285 */
 286
 287 INTVAL
 288 intlist_shift(PARROT_INTERP, ARGMOD(IntList **l))
 289 {
 290     void * const ret = list_shift(interp, (List *)*l, enum_type_INTVAL);
 291     const INTVAL retval = ret == (void *)-1 ? 0 : *(INTVAL *)ret;
 292     return retval;
 293 }
 294
 295 /*
 296
 297 =item C<INTVAL intlist_get>
 298
 299 Returns the item at C<idx>.
 300
 301 =cut
 302
 303 */
 304
 305 PARROT_WARN_UNUSED_RESULT
 306 INTVAL
 307 intlist_get(PARROT_INTERP, ARGMOD(IntList *list), INTVAL idx)
 308 {
 309     void * const ret = list_get(interp, (List *)list, idx, enum_type_INTVAL);
 310     if (ret)
 311         return *(INTVAL *)ret;
 312
 313     return (INTVAL)0;
 314 }
 315
 316 /*
 317
 318 =back
 319
 320 =head1 SEE ALSO
 321
 322 F<include/parrot/intlist.h>, F<src/list.c> and F<include/parrot/list.h>.
 323
 324 =cut
 325
 326 */
 327
 328
 329 /*
 330  * Local variables:
 331  *   c-file-style: "parrot"
 332  * End:
 333  * vim: expandtab shiftwidth=4:
 334  */