src/array.c

   1 /*
   2  * array.c
   3  *
   4  * Copyright (c) 2010 project bchan
   5  *
   6  * This software is provided 'as-is', without any express or implied
   7  * warranty. In no event will the authors be held liable for any damages
   8  * arising from the use of this software.
   9  *
  10  * Permission is granted to anyone to use this software for any purpose,
  11  * including commercial applications, and to alter it and redistribute it
  12  * freely, subject to the following restrictions:
  13  *
  14  * 1. The origin of this software must not be misrepresented; you must not
  15  *    claim that you wrote the original software. If you use this software
  16  *    in a product, an acknowledgment in the product documentation would be
  17  *    appreciated but is not required.
  18  *
  19  * 2. Altered source versions must be plainly marked as such, and must not be
  20  *    misrepresented as being the original software.
  21  *
  22  * 3. This notice may not be removed or altered from any source
  23  *    distribution.
  24  *
  25  */
  26
  27 #include        <basic.h>
  28 #include        <bstdlib.h>
  29 #include        <bstdio.h>
  30 #include        <bsys/queue.h>
  31
  32 #include    "array.h"
  33
  34 #ifdef BCHAN_CONFIG_DEBUG
  35 # define DP(arg) printf arg
  36 # define DP_ER(msg, err) printf("%s (%d/%x)\n", msg, err>>16, err)
  37 #else
  38 # define DP(arg) /**/
  39 # define DP_ER(msg, err) /**/
  40 #endif
  41
  42 LOCAL arraybase_datanode_t* arraybase_datanode_next(arraybase_datanode_t *node)
  43 {
  44         return (arraybase_datanode_t *)node->queue.next;
  45 }
  46
  47 LOCAL arraybase_datanode_t* arraybase_datanode_prev(arraybase_datanode_t *node)
  48 {
  49         return (arraybase_datanode_t *)node->queue.prev;
  50 }
  51
  52 LOCAL VOID arraybase_datanode_insert(arraybase_datanode_t *node, arraybase_datanode_t *que)
  53 {
  54         QueInsert(&node->queue, &que->queue);
  55 }
  56
  57 LOCAL VOID arraybase_datanode_getunitbyindex(arraybase_datanode_t *node, W unitsize, W index, VP *p)
  58 {
  59         /* comparing index and data lentgh is this user. */
  60         *p = (VP)(node->data + unitsize * index);
  61 }
  62
  63 LOCAL VOID arraybase_datanode_writebyindex(arraybase_datanode_t *node, W unitsize, W index, VP p)
  64 {
  65         VP dest;
  66
  67         /* comparing index and data lentgh is this user. */
  68         arraybase_datanode_getunitbyindex(node, unitsize, index, &dest);
  69         memcpy(dest, p, unitsize);
  70 }
  71
  72 LOCAL W arraybase_datanode_initialize(arraybase_datanode_t *node, W unitsize, W denom)
  73 {
  74         QueInit(&node->queue);
  75         node->data = (UB*)malloc(sizeof(UB)*unitsize*denom);
  76         if (node->data == NULL) {
  77                 return -1; /* TODO */
  78         }
  79         return 0;
  80 }
  81
  82 LOCAL VOID arraybase_datanode_finalize(arraybase_datanode_t *node)
  83 {
  84         free(node->data);
  85         QueRemove(&node->queue);
  86 }
  87
  88 LOCAL arraybase_datanode_t* arraybase_datanode_new(W unitsize, W denom)
  89 {
  90         arraybase_datanode_t *node;
  91         W err;
  92
  93         node = (arraybase_datanode_t *)malloc(sizeof(arraybase_datanode_t));
  94         if (node == NULL) {
  95                 return NULL;
  96         }
  97         err = arraybase_datanode_initialize(node, unitsize, denom);
  98         if (err < 0) {
  99                 free(node);
 100         }
 101
 102         return node;
 103 }
 104
 105 LOCAL VOID arraybase_datanode_delete(arraybase_datanode_t *node)
 106 {
 107         arraybase_datanode_finalize(node);
 108         free(node);
 109 }
 110
 111 EXPORT Bool arraybase_getunitbyindex(arraybase_t *arraybase, W index, VP *p)
 112 {
 113         W i, i_num, i_data;
 114         arraybase_datanode_t *node;
 115
 116         if (index < 0) {
 117                 return False;
 118         }
 119         if (index >= arraybase->datanum) {
 120                 return False;
 121         }
 122
 123         i_num = index / arraybase->denom;
 124         i_data = index % arraybase->denom;
 125
 126         node = &arraybase->datalist;
 127         for (i = 0; i < i_num; i++) {
 128                 node = arraybase_datanode_next(node);
 129         }
 130
 131         arraybase_datanode_getunitbyindex(node, arraybase->unitsize, i_data, p);
 132
 133         return True;
 134 }
 135
 136 EXPORT Bool arraybase_getunitfirst(arraybase_t *arraybase, VP *p)
 137 {
 138         /* TODO: more efficient. */
 139         return arraybase_getunitbyindex(arraybase, 0, p);
 140 }
 141
 142 EXPORT Bool arraybase_getunitlast(arraybase_t *arraybase, VP *p)
 143 {
 144         /* TODO: more efficient. */
 145         return arraybase_getunitbyindex(arraybase, arraybase->datanum - 1, p);
 146 }
 147
 148 EXPORT W arraybase_appendunit(arraybase_t *arraybase, VP p)
 149 {
 150         arraybase_datanode_t *node;
 151         W i_data;
 152
 153         i_data = arraybase->datanum % arraybase->denom;
 154         if ((i_data == 0)&&(arraybase->datanum > 0)) {
 155                 node = arraybase_datanode_new(arraybase->unitsize, arraybase->denom);
 156                 if (node == NULL) {
 157                         return -1; /* TODO */
 158                 }
 159                 arraybase_datanode_insert(node, &arraybase->datalist);
 160         } else {
 161                 node = arraybase_datanode_prev(&arraybase->datalist);
 162         }
 163
 164         arraybase_datanode_writebyindex(node, arraybase->unitsize, i_data, p);
 165
 166         arraybase->datanum++;
 167
 168         return 0;
 169 }
 170
 171 EXPORT VOID arraybase_truncate(arraybase_t *arraybase, W newlength)
 172 {
 173         W i, i_num;
 174         arraybase_datanode_t *node, *newlast;
 175
 176         if (newlength >= arraybase->datanum) {
 177                 return;
 178         }
 179
 180         i_num = (newlength - 1) / arraybase->denom;
 181         node = &arraybase->datalist;
 182         for (i = 0; i < i_num; i++) {
 183                 node = arraybase_datanode_next(node);
 184         }
 185         newlast = node;
 186
 187         for (;;) {
 188                 node = arraybase_datanode_prev(&arraybase->datalist);
 189                 if (node == newlast) {
 190                         break;
 191                 }
 192                 arraybase_datanode_delete(node);
 193         }
 194
 195         arraybase->datanum = newlength;
 196 }
 197
 198 EXPORT W arraybase_length(arraybase_t *arraybase)
 199 {
 200         return arraybase->datanum;
 201 }
 202
 203 EXPORT W arraybase_initialize(arraybase_t *arraybase, W unitsize, W denom)
 204 {
 205         W err;
 206
 207         err = arraybase_datanode_initialize(&arraybase->datalist, unitsize, denom);
 208         if (err < 0) {
 209                 return err;
 210         }
 211         arraybase->unitsize = unitsize;
 212         arraybase->denom = denom;
 213         arraybase->datanum = 0;
 214
 215         return 0;
 216 }
 217
 218 EXPORT VOID arraybase_finalize(arraybase_t *arraybase)
 219 {
 220         arraybase_datanode_t *node;
 221
 222         for (;;) {
 223                 node = arraybase_datanode_prev(&arraybase->datalist);
 224                 if (node == &arraybase->datalist) {
 225                         break;
 226                 }
 227                 arraybase_datanode_delete(node);
 228         }
 229         arraybase_datanode_finalize(&arraybase->datalist);
 230 }