include/parrot/list.h

   1 /*
   2  * list.h
   3  *  Copyright (C) 2002-2008, Parrot Foundation.
   4  *  License:  Artistic 2.0, see README and LICENSE for details
   5  *  SVN Info
   6  *     $Id$
   7  *  Overview:
   8  *     list aka array routines for Parrot
   9  *     s. list.c for more
  10  */
  11
  12 #include "parrot/parrot.h"
  13
  14 #ifndef PARROT_LIST_H_GUARD
  15 #define PARROT_LIST_H_GUARD
  16
  17 typedef struct List_chunk {
  18     Buffer             data;        /* item store, Buffer must be first element in struct*/
  19     struct List_chunk *next;
  20     struct List_chunk *prev;
  21     UINTVAL            flags;       /* chunk flags */
  22     UINTVAL            items;       /* items in this chunk */
  23     UINTVAL            n_chunks;    /* # of chunks with grow policy in flags */
  24     UINTVAL            n_items;     /* # of items  with grow policy in flags */
  25 } List_chunk;
  26
  27 #define sparse      PObj_private0_FLAG
  28 #define no_power_2  PObj_private1_FLAG
  29 #define fixed_items PObj_private2_FLAG
  30 #define grow_items  PObj_private3_FLAG
  31
  32 typedef struct List {
  33     Buffer           chunk_list;      /* pointers to chunks */
  34     PMC             *container;       /* the Array PMC */
  35     List_chunk      *first;           /* first chunk holding data */
  36     List_chunk      *last;            /* last chunk */
  37     UINTVAL          length;          /* number of items in list */
  38     UINTVAL          start;           /* offset, where array[0] is */
  39     PARROT_DATA_TYPE item_type;       /* item type */
  40     UINTVAL          cap;             /* list capacity in items */
  41     UINTVAL          collect_runs;    /* counter, when chunklist was built */
  42     UINTVAL          n_chunks;        /* number of chunks */
  43     int              grow_policy;     /* fixed / variable len */
  44     int              items_per_chunk; /* override defaults */
  45     int              item_size;       /* item size */
  46 } List;
  47
  48 typedef enum {
  49     enum_grow_unknown,          /* at beginning, or after emptying list */
  50     enum_grow_mixed = 1,        /* other */
  51     enum_grow_fixed = fixed_items,        /* fixed maximum size */
  52     enum_grow_growing = grow_items        /* growing at begin of list */
  53 } ARRAY_GROW_TYPE;
  54
  55 typedef enum {
  56     enum_add_at_start,          /* don't swap these */
  57     enum_add_at_end
  58 } ARRAY_ADD_POS;
  59
  60
  61 #ifdef LIST_TEST
  62 #  define MIN_ITEMS 4           /* smallest chunk can hold */
  63 #  define LD_MAX 4              /* log2(MAX_ITEMS) */
  64 #  define MAX_ITEMS 16          /* biggest chunk can hold */
  65 #else
  66 #  define MIN_ITEMS 16          /* smallest chunk can hold */
  67 #  define LD_MAX 10             /* log2(MAX_ITEMS) */
  68 #  define MAX_ITEMS 1024        /* biggest chunk can hold */
  69 #endif /* LIST_TEST */
  70 #define MAX_MASK (MAX_ITEMS-1)
  71
  72 /*
  73  * bigger MAX_ITEMS didn't improve much in my tests
  74  * 10^6 list_get, MAX_ITEMS 1024: 0.34s, 2048: 0.33s
  75  */
  76
  77
  78 /* HEADERIZER BEGIN: src/list.c */
  79 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END.  Your changes will be lost. */
  80
  81 PARROT_EXPORT
  82 PARROT_CONST_FUNCTION
  83 PARROT_WARN_UNUSED_RESULT
  84 UINTVAL ld(UINTVAL x);
  85
  86 PARROT_EXPORT
  87 void Parrot_pmc_array_assign(PARROT_INTERP,
  88     ARGMOD(List *list),
  89     INTVAL idx,
  90     ARGIN_NULLOK(void *item),
  91     int type)
  92         __attribute__nonnull__(1)
  93         __attribute__nonnull__(2)
  94         FUNC_MODIFIES(*list);
  95
  96 PARROT_EXPORT
  97 PARROT_WARN_UNUSED_RESULT
  98 PARROT_CANNOT_RETURN_NULL
  99 List * Parrot_pmc_array_clone(PARROT_INTERP, ARGIN(const List *other))
 100         __attribute__nonnull__(1)
 101         __attribute__nonnull__(2);
 102
 103 PARROT_EXPORT
 104 void Parrot_pmc_array_delete(PARROT_INTERP,
 105     ARGMOD(List *list),
 106     INTVAL idx,
 107     INTVAL n_items)
 108         __attribute__nonnull__(1)
 109         __attribute__nonnull__(2)
 110         FUNC_MODIFIES(*list);
 111
 112 PARROT_EXPORT
 113 PARROT_CAN_RETURN_NULL
 114 PARROT_WARN_UNUSED_RESULT
 115 void * Parrot_pmc_array_get(PARROT_INTERP,
 116     ARGMOD(List *list),
 117     INTVAL idx,
 118     int type)
 119         __attribute__nonnull__(1)
 120         __attribute__nonnull__(2)
 121         FUNC_MODIFIES(*list);
 122
 123 PARROT_EXPORT
 124 void Parrot_pmc_array_insert(PARROT_INTERP,
 125     ARGMOD(List *list),
 126     INTVAL idx,
 127     INTVAL n_items)
 128         __attribute__nonnull__(1)
 129         __attribute__nonnull__(2)
 130         FUNC_MODIFIES(*list);
 131
 132 PARROT_EXPORT
 133 void Parrot_pmc_array_mark(PARROT_INTERP, ARGMOD(List *list))
 134         __attribute__nonnull__(1)
 135         __attribute__nonnull__(2)
 136         FUNC_MODIFIES(*list);
 137
 138 PARROT_EXPORT
 139 PARROT_WARN_UNUSED_RESULT
 140 PARROT_CANNOT_RETURN_NULL
 141 List * Parrot_pmc_array_new(PARROT_INTERP, PARROT_DATA_TYPE type)
 142         __attribute__nonnull__(1);
 143
 144 PARROT_EXPORT
 145 PARROT_WARN_UNUSED_RESULT
 146 PARROT_CANNOT_RETURN_NULL
 147 List * Parrot_pmc_array_new_init(PARROT_INTERP,
 148     PARROT_DATA_TYPE type,
 149     ARGIN(PMC *init))
 150         __attribute__nonnull__(1)
 151         __attribute__nonnull__(3);
 152
 153 PARROT_EXPORT
 154 void Parrot_pmc_array_pmc_new(PARROT_INTERP, ARGMOD(PMC *container))
 155         __attribute__nonnull__(1)
 156         __attribute__nonnull__(2)
 157         FUNC_MODIFIES(*container);
 158
 159 PARROT_EXPORT
 160 void Parrot_pmc_array_pmc_new_init(PARROT_INTERP,
 161     ARGMOD(PMC *container),
 162     ARGIN(PMC *init))
 163         __attribute__nonnull__(1)
 164         __attribute__nonnull__(2)
 165         __attribute__nonnull__(3)
 166         FUNC_MODIFIES(*container);
 167
 168 PARROT_EXPORT
 169 PARROT_CAN_RETURN_NULL
 170 void * Parrot_pmc_array_pop(PARROT_INTERP, ARGMOD(List *list), int type)
 171         __attribute__nonnull__(1)
 172         __attribute__nonnull__(2)
 173         FUNC_MODIFIES(*list);
 174
 175 PARROT_EXPORT
 176 void Parrot_pmc_array_push(PARROT_INTERP,
 177     ARGMOD(List *list),
 178     ARGIN_NULLOK(void *item),
 179     int type)
 180         __attribute__nonnull__(1)
 181         __attribute__nonnull__(2)
 182         FUNC_MODIFIES(*list);
 183
 184 PARROT_EXPORT
 185 void Parrot_pmc_array_set_length(PARROT_INTERP,
 186     ARGMOD(List *list),
 187     INTVAL len)
 188         __attribute__nonnull__(1)
 189         __attribute__nonnull__(2)
 190         FUNC_MODIFIES(*list);
 191
 192 PARROT_EXPORT
 193 PARROT_CAN_RETURN_NULL
 194 void * Parrot_pmc_array_shift(PARROT_INTERP, ARGMOD(List *list), int type)
 195         __attribute__nonnull__(1)
 196         __attribute__nonnull__(2)
 197         FUNC_MODIFIES(*list);
 198
 199 PARROT_EXPORT
 200 void Parrot_pmc_array_splice(PARROT_INTERP,
 201     ARGMOD(List *list),
 202     ARGMOD_NULLOK(List *value_list),
 203     INTVAL offset,
 204     INTVAL count)
 205         __attribute__nonnull__(1)
 206         __attribute__nonnull__(2)
 207         FUNC_MODIFIES(*list)
 208         FUNC_MODIFIES(*value_list);
 209
 210 PARROT_EXPORT
 211 void Parrot_pmc_array_unshift(PARROT_INTERP,
 212     ARGMOD(List *list),
 213     ARGIN(void *item),
 214     int type)
 215         __attribute__nonnull__(1)
 216         __attribute__nonnull__(2)
 217         __attribute__nonnull__(3)
 218         FUNC_MODIFIES(*list);
 219
 220 PARROT_EXPORT
 221 void Parrot_pmc_array_visit(PARROT_INTERP,
 222     ARGIN(List *list),
 223     ARGMOD(void *pinfo))
 224         __attribute__nonnull__(1)
 225         __attribute__nonnull__(2)
 226         __attribute__nonnull__(3)
 227         FUNC_MODIFIES(*pinfo);
 228
 229 PARROT_WARN_UNUSED_RESULT
 230 PARROT_PURE_FUNCTION
 231 INTVAL Parrot_pmc_array_length(SHIM_INTERP, ARGIN(const List *list))
 232         __attribute__nonnull__(2);
 233
 234 #define ASSERT_ARGS_ld __attribute__unused__ int _ASSERT_ARGS_CHECK = (0)
 235 #define ASSERT_ARGS_Parrot_pmc_array_assign __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 236        PARROT_ASSERT_ARG(interp) \
 237     , PARROT_ASSERT_ARG(list))
 238 #define ASSERT_ARGS_Parrot_pmc_array_clone __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 239        PARROT_ASSERT_ARG(interp) \
 240     , PARROT_ASSERT_ARG(other))
 241 #define ASSERT_ARGS_Parrot_pmc_array_delete __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 242        PARROT_ASSERT_ARG(interp) \
 243     , PARROT_ASSERT_ARG(list))
 244 #define ASSERT_ARGS_Parrot_pmc_array_get __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 245        PARROT_ASSERT_ARG(interp) \
 246     , PARROT_ASSERT_ARG(list))
 247 #define ASSERT_ARGS_Parrot_pmc_array_insert __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 248        PARROT_ASSERT_ARG(interp) \
 249     , PARROT_ASSERT_ARG(list))
 250 #define ASSERT_ARGS_Parrot_pmc_array_mark __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 251        PARROT_ASSERT_ARG(interp) \
 252     , PARROT_ASSERT_ARG(list))
 253 #define ASSERT_ARGS_Parrot_pmc_array_new __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 254        PARROT_ASSERT_ARG(interp))
 255 #define ASSERT_ARGS_Parrot_pmc_array_new_init __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 256        PARROT_ASSERT_ARG(interp) \
 257     , PARROT_ASSERT_ARG(init))
 258 #define ASSERT_ARGS_Parrot_pmc_array_pmc_new __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 259        PARROT_ASSERT_ARG(interp) \
 260     , PARROT_ASSERT_ARG(container))
 261 #define ASSERT_ARGS_Parrot_pmc_array_pmc_new_init __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 262        PARROT_ASSERT_ARG(interp) \
 263     , PARROT_ASSERT_ARG(container) \
 264     , PARROT_ASSERT_ARG(init))
 265 #define ASSERT_ARGS_Parrot_pmc_array_pop __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 266        PARROT_ASSERT_ARG(interp) \
 267     , PARROT_ASSERT_ARG(list))
 268 #define ASSERT_ARGS_Parrot_pmc_array_push __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 269        PARROT_ASSERT_ARG(interp) \
 270     , PARROT_ASSERT_ARG(list))
 271 #define ASSERT_ARGS_Parrot_pmc_array_set_length __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 272        PARROT_ASSERT_ARG(interp) \
 273     , PARROT_ASSERT_ARG(list))
 274 #define ASSERT_ARGS_Parrot_pmc_array_shift __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 275        PARROT_ASSERT_ARG(interp) \
 276     , PARROT_ASSERT_ARG(list))
 277 #define ASSERT_ARGS_Parrot_pmc_array_splice __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 278        PARROT_ASSERT_ARG(interp) \
 279     , PARROT_ASSERT_ARG(list))
 280 #define ASSERT_ARGS_Parrot_pmc_array_unshift __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 281        PARROT_ASSERT_ARG(interp) \
 282     , PARROT_ASSERT_ARG(list) \
 283     , PARROT_ASSERT_ARG(item))
 284 #define ASSERT_ARGS_Parrot_pmc_array_visit __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 285        PARROT_ASSERT_ARG(interp) \
 286     , PARROT_ASSERT_ARG(list) \
 287     , PARROT_ASSERT_ARG(pinfo))
 288 #define ASSERT_ARGS_Parrot_pmc_array_length __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
 289        PARROT_ASSERT_ARG(list))
 290 /* Don't modify between HEADERIZER BEGIN / HEADERIZER END.  Your changes will be lost. */
 291 /* HEADERIZER END: src/list.c */
 292
 293 #endif /* PARROT_LIST_H_GUARD */
 294
 295
 296 /*
 297  * Local variables:
 298  *   c-file-style: "parrot"
 299  * End:
 300  * vim: expandtab shiftwidth=4:
 301  */