Annotation of libaitio/src/sarray.c, revision 1.6.8.2

1.3       misho       1: /*************************************************************************
                      2: * (C) 2011 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
                      3: *  by Michael Pounov <misho@elwix.org>
                      4: *
                      5: * $Author: misho $
1.6.8.2 ! misho       6: * $Id: sarray.c,v 1.6.8.1 2012/05/23 11:49:35 misho Exp $
1.3       misho       7: *
                      8: **************************************************************************
                      9: The ELWIX and AITNET software is distributed under the following
                     10: terms:
                     11: 
                     12: All of the documentation and software included in the ELWIX and AITNET
                     13: Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>
                     14: 
1.6       misho      15: Copyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
1.3       misho      16:        by Michael Pounov <misho@elwix.org>.  All rights reserved.
                     17: 
                     18: Redistribution and use in source and binary forms, with or without
                     19: modification, are permitted provided that the following conditions
                     20: are met:
                     21: 1. Redistributions of source code must retain the above copyright
                     22:    notice, this list of conditions and the following disclaimer.
                     23: 2. Redistributions in binary form must reproduce the above copyright
                     24:    notice, this list of conditions and the following disclaimer in the
                     25:    documentation and/or other materials provided with the distribution.
                     26: 3. All advertising materials mentioning features or use of this software
                     27:    must display the following acknowledgement:
                     28: This product includes software developed by Michael Pounov <misho@elwix.org>
                     29: ELWIX - Embedded LightWeight unIX and its contributors.
                     30: 4. Neither the name of AITNET nor the names of its contributors
                     31:    may be used to endorse or promote products derived from this software
                     32:    without specific prior written permission.
                     33: 
                     34: THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
                     35: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     36: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     37: ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     38: FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     39: DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     40: OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     41: HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     42: LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     43: OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     44: SUCH DAMAGE.
                     45: */
1.2       misho      46: #include "global.h"
                     47: 
                     48: 
                     49: /*
                     50:  * io_sarrInit() - Create and initialize dynamic split-order array
1.6       misho      51:  *
1.2       misho      52:  * @numItems = Number of Items
                     53:  * @segLen = Length of segment
                     54:  * return: NULL error, != NULL allocated memory for array
                     55:  */
                     56: inline sarr_t *
                     57: io_sarrInit(int numItems, int segLen)
                     58: {
                     59:        sarr_t *arr = NULL;
                     60: 
                     61:        if (segLen < 1)
                     62:                return NULL;
                     63: 
1.6.8.2 ! misho      64:        arr = io_malloc(sizeof(sarr_t));
1.2       misho      65:        if (!arr) {
                     66:                LOGERR;
                     67:                return NULL;
                     68:        }
                     69: 
                     70:        arr->sarr_num = numItems;
                     71:        arr->sarr_seg = segLen;
                     72:        arr->sarr_siz = numItems / segLen + 1;
1.6.8.2 ! misho      73:        arr->sarr_data = io_calloc(arr->sarr_siz, sizeof(sarr_seg_t));
1.2       misho      74:        if (!arr->sarr_data) {
                     75:                LOGERR;
1.6.8.2 ! misho      76:                io_free(arr);
1.2       misho      77:                return NULL;
                     78:        } else
                     79:                memset(arr->sarr_data, 0, arr->sarr_siz * sizeof(sarr_seg_t));
                     80: 
                     81:        return arr;
                     82: }
                     83: 
                     84: /*
                     85:  * io_sarrDestroy() - Free all data in dynamic split-order array and Destroy array
1.6       misho      86:  *
1.2       misho      87:  * @parr = Array
                     88:  * return: none
                     89:  */
                     90: inline void
                     91: io_sarrDestroy(sarr_t ** __restrict parr)
                     92: {
                     93:        register int i;
                     94: 
1.4       misho      95:        if (!parr || !*parr)
1.2       misho      96:                return;
                     97: 
                     98:        for (i = 0; i < (*parr)->sarr_siz; i++)
                     99:                if ((*parr)->sarr_data[i]) {
1.6.8.2 ! misho     100:                        io_free((*parr)->sarr_data[i]);
1.2       misho     101:                        (*parr)->sarr_data[i] = NULL;
                    102:                }
                    103: 
                    104:        if ((*parr)->sarr_data)
1.6.8.2 ! misho     105:                io_free((*parr)->sarr_data);
        !           106:        io_free(*parr);
1.2       misho     107:        *parr = NULL;
                    108: }
                    109: 
                    110: /*
1.5       misho     111:  * io_sarrCopy() Copy source split array to destination split array
1.6       misho     112:  *
1.5       misho     113:  * @dest = Destination split array, after use free with io_sarrDestroy()
                    114:  * @src = Source split array
                    115:  * return: -1 error; >0 count of destination split array
                    116:  */
                    117: int
                    118: io_sarrCopy(sarr_t ** __restrict dest, sarr_t * __restrict src)
                    119: {
                    120:        assert(dest);
                    121:        assert(src);
                    122:        if (!dest || !src)
                    123:                return -1;
                    124: 
                    125:        *dest = io_sarrInit(io_sarrSize(src), io_sarrSeg(src));
                    126:        if (!*dest)
                    127:                return -1;
                    128: 
                    129:        memcpy((*dest)->sarr_data, src->sarr_data, (*dest)->sarr_siz * sizeof(sarr_seg_t));
                    130:        return io_sarrSize(*dest);
                    131: }
                    132: 
                    133: /*
1.2       misho     134:  * io_sarrVacuum() - Vacuum dynamic split-order array, empty segments will be freed
1.6       misho     135:  *
1.2       misho     136:  * @arr = Array
                    137:  * return: -1 error, >-1 freed segments
                    138:  */
                    139: int
                    140: io_sarrVacuum(sarr_t * __restrict arr)
                    141: {
                    142:        register int i, j;
                    143:        int cx = 0;
                    144:        sarr_seg_t seg;
                    145: 
                    146:        if (!arr)
                    147:                return -1;
                    148: 
                    149:        for (i = 0; i < arr->sarr_siz; i++)
                    150:                if (arr->sarr_data[i]) {
                    151:                        for (j = 0, seg = arr->sarr_data[i]; j < arr->sarr_seg; j++)
                    152:                                if (seg[j])
                    153:                                        break;
                    154:                        if (j == arr->sarr_seg) {
1.6.8.2 ! misho     155:                                io_free(arr->sarr_data[i]);
1.2       misho     156:                                arr->sarr_data[i] = NULL;
                    157:                                cx++;
                    158:                        }
                    159:                }
                    160: 
                    161:        return cx;
                    162: }
                    163: 
                    164: /*
                    165:  * io_sarrGrow() - Grow/Shrink dynamic split-order array, Use with care when it shrink!!!
1.6       misho     166:  *
1.2       misho     167:  * @arr = Array
                    168:  * @newNumItems = Number of Items
                    169:  * return: -1 error, 0 ok
                    170:  */
                    171: int
                    172: io_sarrGrow(sarr_t * __restrict arr, int newNumItems)
                    173: {
                    174:        sarr_seg_t *data;
                    175:        int seg, n = 0;
                    176:        register int i;
                    177: 
                    178:        if (!arr)
                    179:                return -1;
                    180: 
                    181:        arr->sarr_num = newNumItems;
                    182:        seg = newNumItems / arr->sarr_seg + 1;
                    183:        if (arr->sarr_siz == seg)
                    184:                return n;
                    185:        if (arr->sarr_siz < seg)
                    186:                n = seg - arr->sarr_siz;
                    187:        else
                    188:                for (i = seg; i < arr->sarr_siz; i++)
                    189:                        if (arr->sarr_data[i])
1.6.8.2 ! misho     190:                                io_free(arr->sarr_data[i]);
1.2       misho     191: 
                    192:        arr->sarr_siz = seg;
1.6.8.2 ! misho     193:        data = io_realloc(arr->sarr_data, arr->sarr_siz * sizeof(sarr_seg_t));
1.2       misho     194:        if (!data) {
                    195:                LOGERR;
                    196:                return -1;
                    197:        } else
                    198:                arr->sarr_data = data;
                    199:        memset(arr->sarr_data + (arr->sarr_siz - n), 0, n * sizeof(sarr_seg_t));
                    200: 
                    201:        return 0;
                    202: }
                    203: 
                    204: /*
                    205:  * io_sarrGet() - Get element from dynamic split-order array
1.6       misho     206:  *
1.2       misho     207:  * @arr = Array
                    208:  * @idx = Index (warning 1st element is at position 1)
                    209:  * return: NULL not found, !=NULL element
                    210:  */
                    211: inline void *
                    212: io_sarrGet(sarr_t * __restrict arr, u_int idx)
                    213: {
                    214:        void *ret = NULL;
                    215:        sarr_seg_t seg;
                    216: 
                    217:        if (!arr || idx < 1 || arr->sarr_num < idx)
                    218:                return ret;
                    219: 
                    220:        seg = arr->sarr_data[idx / arr->sarr_seg];
                    221:        if (seg)
                    222:                ret = seg[idx % arr->sarr_seg];
                    223: 
                    224:        return ret;
                    225: }
                    226: 
                    227: /*
                    228:  * io_sarrGet2() - Always get element from dynamic split-order array
                    229:  *     Function automatic grow array. Good use for Hash tables! 
1.6       misho     230:  *
1.2       misho     231:  * @arr = Array
                    232:  * @idx = Index (warning 1st element is at position 1)
                    233:  * return: NULL not found, !=NULL element
                    234:  */
                    235: void *
                    236: io_sarrGet2(sarr_t * __restrict arr, u_int idx)
                    237: {
                    238:        if (!arr || idx < 1)
                    239:                return NULL;
                    240:        if (arr->sarr_num < idx)
                    241:                if (io_sarrGrow(arr, idx))
                    242:                        return NULL;
                    243:        return io_sarrGet(arr, idx);
                    244: }
                    245: 
                    246: /*
                    247:  * io_sarrSet() - Set element to dynamic split-order array
1.6       misho     248:  *
1.2       misho     249:  * @arr = Array
                    250:  * @idx = Index (warning 1st element is at position 1)
                    251:  * @data = Value
                    252:  * return: NULL error or empty, !=NULL old value in element
                    253:  */
                    254: inline void *
                    255: io_sarrSet(sarr_t * __restrict arr, u_int idx, void *data)
                    256: {
                    257:        void *ret = NULL;
                    258:        sarr_seg_t seg;
                    259:        register int pos;
                    260: 
                    261:        if (!arr || idx < 1 || arr->sarr_num < idx)
                    262:                return ret;
                    263: 
                    264:        seg = arr->sarr_data[idx / arr->sarr_seg];
                    265:        if (!seg) {
1.6.8.2 ! misho     266:                seg = io_calloc(arr->sarr_seg, sizeof(void*));
1.2       misho     267:                if (!seg) {
                    268:                        LOGERR;
                    269:                        return ret;
                    270:                } else
                    271:                        memset(seg, 0, arr->sarr_seg * sizeof(void*));
                    272:                arr->sarr_data[idx / arr->sarr_seg] = seg;
                    273:        }
                    274: 
                    275:        pos = idx % arr->sarr_seg;
                    276:        ret = seg[pos];
                    277:        seg[pos] = data;
                    278: 
                    279:        return ret;
                    280: }
1.4       misho     281: 
                    282: /*
                    283:  * io_sarr2array() - Convert from split-order array to dynamic array
1.6       misho     284:  *
1.4       misho     285:  * @sa = split array
                    286:  * @sarrFree = after convert split array !=0 will be destroyed sarray
                    287:  * return: NULL error or != NULL new array
                    288:  */
                    289: array_t *
                    290: io_sarr2array(sarr_t ** __restrict sa, int sarrFree)
                    291: {
                    292:        array_t *arr = NULL;
                    293:        int el;
                    294:        register int i;
                    295: 
                    296:        assert(sa && *sa);
                    297:        if (!sa || !*sa)
                    298:                return NULL;
                    299: 
                    300:        el = io_sarrSize(*sa);
                    301:        arr = io_arrayInit(el);
                    302:        if (!arr)
                    303:                return NULL;
                    304: 
                    305:        for (i = 0; i < el; i++)
                    306:                io_arraySet(arr, i, io_sarrGet(*sa, i + 1));
                    307: 
                    308:        if (sarrFree) {
1.6.8.2 ! misho     309:                io_free(*sa);
1.4       misho     310:                *sa = NULL;
                    311:        }
                    312:        return arr;
                    313: }
                    314: 
                    315: /*
                    316:  * io_array2sarr() - Convert from dynamic array to split-order array
1.6       misho     317:  *
1.4       misho     318:  * @a = array
                    319:  * @segLen = Length of segment
                    320:  * @arrFree = after convert array !=0 will be destroyed
                    321:  * return: NULL error or != NULL new sarr
                    322:  */
                    323: sarr_t *
                    324: io_array2sarr(array_t ** __restrict a, int segLen, int arrFree)
                    325: {
                    326:        sarr_t *sa = NULL;
                    327:        int el;
                    328:        register int i;
                    329: 
                    330:        assert(a && *a);
                    331:        if (!a || !*a)
                    332:                return NULL;
                    333: 
                    334:        el = io_arraySize(*a);
                    335:        sa = io_sarrInit(el, segLen);
                    336:        if (!sa)
                    337:                return NULL;
                    338: 
                    339:        for (i = 0; i < el; i++)
                    340:                io_sarrSet(sa, i + 1, io_arrayGet(*a, i));
                    341: 
                    342:        if (arrFree) {
1.6.8.2 ! misho     343:                io_free(*a);
1.4       misho     344:                *a = NULL;
                    345:        }
                    346:        return sa;
                    347: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>