src/svgtiny_list.c

   1 /*
   2  * This file is part of Libsvgtiny
   3  * Licensed under the MIT License,
   4  *                http://opensource.org/licenses/mit-license.php
   5  * Copyright 2008 James Bursa <james@semichrome.net>
   6  */
   7
   8 /**
   9  * A svgtiny_list is a managed array of objects. It grows in chunks to reduce
  10  * calls to realloc(), but keeps wasted space low.
  11  */
  12
  13 #include <assert.h>
  14 #include <stdlib.h>
  15 #include "svgtiny.h"
  16 #include "svgtiny_internal.h"
  17
  18
  19 struct svgtiny_list {
  20         unsigned int size;      /* number of slots used */
  21         unsigned int allocated; /* number of slots allocated (>= size) */
  22         size_t item_size;       /* size of each slot / bytes */
  23         char *items;            /* array of slots */
  24 };
  25
  26
  27 /**
  28  * Create an empty svgtiny_list.
  29  */
  30
  31 struct svgtiny_list *svgtiny_list_create(size_t item_size)
  32 {
  33         struct svgtiny_list *list = malloc(sizeof *list);
  34         if (!list)
  35                 return 0;
  36         list->size = 0;
  37         list->allocated = 0;
  38         list->item_size = item_size;
  39         list->items = 0;
  40         return list;
  41 }
  42
  43
  44 /**
  45  * Return the number of objects in a list.
  46  */
  47
  48 unsigned int svgtiny_list_size(struct svgtiny_list *list)
  49 {
  50         return list->size;
  51 }
  52
  53
  54 /**
  55  * Set the number of objects in a list. If the size is increased, the new
  56  * objects are not initialized in any way.
  57  *
  58  * The allocation size formula is taken from Python's list:
  59  * http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup
  60  *
  61  * Objects may have moved after this call. Use svgtiny_list_get() to get new
  62  * pointers.
  63  */
  64
  65 svgtiny_code svgtiny_list_resize(struct svgtiny_list *list,
  66                 unsigned int new_size)
  67 {
  68         unsigned int new_allocated;
  69         void *new_items;
  70
  71         if (new_size <= list->allocated) {
  72                 list->size = new_size;
  73                 return svgtiny_OK;
  74         }
  75
  76         new_allocated = (new_size >> 3) + (new_size < 9 ? 3 : 6) + new_size;
  77         if (new_size == 0)
  78                 new_allocated = 0;
  79         new_items = realloc(list->items, new_allocated * list->item_size);
  80         if (!new_items)
  81                 return svgtiny_OUT_OF_MEMORY;
  82
  83         list->size = new_size;
  84         list->allocated = new_allocated;
  85         list->items = new_items;
  86
  87         return svgtiny_OK;
  88 }
  89
  90
  91 /**
  92  * Return a pointer to an object in a list.
  93  */
  94
  95 void *svgtiny_list_get(struct svgtiny_list *list,
  96                 unsigned int i)
  97 {
  98         assert(i < list->size);
  99         return (void *) (list->items + i * list->item_size);
 100 }
 101
 102
 103 /**
 104  * Add space for one object to a list and return a pointer to it.
 105  */
 106
 107 void *svgtiny_list_push(struct svgtiny_list *list)
 108 {
 109         svgtiny_code code;
 110         code = svgtiny_list_resize(list, list->size + 1);
 111         if (code != svgtiny_OK)
 112                 return 0;
 113         return svgtiny_list_get(list, list->size - 1);
 114 }
 115
 116
 117 /**
 118  * Free an entire list.
 119  */
 120
 121 void svgtiny_list_free(struct svgtiny_list *list)
 122 {
 123         free(list->items);
 124         free(list);
 125 }
 126