Annotation of libelwix/src/sarray.c, revision 1.2.28.1

1.1       misho       1: /*************************************************************************
                      2: * (C) 2011 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
                      3: *  by Michael Pounov <misho@elwix.org>
                      4: *
                      5: * $Author: misho $
1.2.28.1! misho       6: * $Id: sarray.c,v 1.2 2013/05/30 09:07:33 misho Exp $
1.1       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.2.28.1! misho      15: Copyright 2004 - 2014
1.1       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: */
                     46: #include "global.h"
                     47: 
                     48: 
                     49: /*
                     50:  * sarr_Init() - Create and initialize dynamic split-order array
                     51:  *
                     52:  * @numItems = Number of Items
                     53:  * @segLen = Length of segment
                     54:  * return: NULL error, != NULL allocated memory for array
                     55:  */
                     56: sarr_t *
                     57: sarr_Init(int numItems, int segLen)
                     58: {
                     59:        sarr_t *arr = NULL;
                     60: 
                     61:        if (segLen < 1)
                     62:                return NULL;
                     63: 
                     64:        arr = e_malloc(sizeof(sarr_t));
                     65:        if (!arr)
                     66:                return NULL;
                     67: 
                     68:        arr->sarr_num = numItems;
                     69:        arr->sarr_seg = segLen;
                     70:        arr->sarr_siz = numItems / segLen + 1;
                     71:        arr->sarr_data = e_calloc(arr->sarr_siz, sizeof(sarr_seg_t));
                     72:        if (!arr->sarr_data) {
                     73:                e_free(arr);
                     74:                return NULL;
                     75:        } else
                     76:                memset(arr->sarr_data, 0, arr->sarr_siz * sizeof(sarr_seg_t));
                     77: 
                     78:        return arr;
                     79: }
                     80: 
                     81: /*
                     82:  * sarr_Destroy() - Free all data in dynamic split-order array and Destroy array
                     83:  *
                     84:  * @parr = Array
                     85:  * return: none
                     86:  */
                     87: void
                     88: sarr_Destroy(sarr_t ** __restrict parr)
                     89: {
                     90:        register int i;
                     91: 
                     92:        if (!parr || !*parr)
                     93:                return;
                     94: 
                     95:        for (i = 0; i < (*parr)->sarr_siz; i++)
                     96:                if ((*parr)->sarr_data[i]) {
                     97:                        e_free((*parr)->sarr_data[i]);
                     98:                        (*parr)->sarr_data[i] = NULL;
                     99:                }
                    100: 
                    101:        if ((*parr)->sarr_data)
                    102:                e_free((*parr)->sarr_data);
                    103:        e_free(*parr);
                    104:        *parr = NULL;
                    105: }
                    106: 
                    107: /*
                    108:  * sarr_Copy() Copy source split array to destination split array
                    109:  *
                    110:  * @dest = Destination split array, after use free with sarr_Destroy()
                    111:  * @src = Source split array
                    112:  * return: -1 error; >0 count of destination split array
                    113:  */
                    114: int
                    115: sarr_Copy(sarr_t ** __restrict dest, sarr_t * __restrict src)
                    116: {
                    117:        if (!dest || !src)
                    118:                return -1;
                    119: 
                    120:        *dest = sarr_Init(sarr_Size(src), sarr_Seg(src));
                    121:        if (!*dest)
                    122:                return -1;
                    123: 
                    124:        memcpy((*dest)->sarr_data, src->sarr_data, (*dest)->sarr_siz * sizeof(sarr_seg_t));
                    125:        return sarr_Size(*dest);
                    126: }
                    127: 
                    128: /*
                    129:  * sarr_Vacuum() - Vacuum dynamic split-order array, empty segments will be freed
                    130:  *
                    131:  * @arr = Array
                    132:  * return: -1 error, >-1 freed segments
                    133:  */
                    134: int
                    135: sarr_Vacuum(sarr_t * __restrict arr)
                    136: {
                    137:        register int i, j;
                    138:        int cx = 0;
                    139:        sarr_seg_t seg;
                    140: 
                    141:        if (!arr)
                    142:                return -1;
                    143: 
                    144:        for (i = 0; i < arr->sarr_siz; i++)
                    145:                if (arr->sarr_data[i]) {
                    146:                        for (j = 0, seg = arr->sarr_data[i]; j < arr->sarr_seg; j++)
                    147:                                if (seg[j])
                    148:                                        break;
                    149:                        if (j == arr->sarr_seg) {
                    150:                                e_free(arr->sarr_data[i]);
                    151:                                arr->sarr_data[i] = NULL;
                    152:                                cx++;
                    153:                        }
                    154:                }
                    155: 
                    156:        return cx;
                    157: }
                    158: 
                    159: /*
                    160:  * sarr_Grow() - Grow/Shrink dynamic split-order array, Use with care when it shrink!!!
                    161:  *
                    162:  * @arr = Array
                    163:  * @newNumItems = Number of Items
                    164:  * return: -1 error, 0 ok
                    165:  */
                    166: int
                    167: sarr_Grow(sarr_t * __restrict arr, int newNumItems)
                    168: {
                    169:        sarr_seg_t *data;
                    170:        int seg, n = 0;
                    171:        register int i;
                    172: 
                    173:        if (!arr)
                    174:                return -1;
                    175: 
                    176:        arr->sarr_num = newNumItems;
                    177:        seg = newNumItems / arr->sarr_seg + 1;
                    178:        if (arr->sarr_siz == seg)
                    179:                return n;
                    180:        if (arr->sarr_siz < seg)
                    181:                n = seg - arr->sarr_siz;
                    182:        else
                    183:                for (i = seg; i < arr->sarr_siz; i++)
                    184:                        if (arr->sarr_data[i])
                    185:                                e_free(arr->sarr_data[i]);
                    186: 
                    187:        arr->sarr_siz = seg;
                    188:        data = e_realloc(arr->sarr_data, arr->sarr_siz * sizeof(sarr_seg_t));
                    189:        if (!data)
                    190:                return -1;
                    191:        else
                    192:                arr->sarr_data = data;
                    193:        memset(arr->sarr_data + (arr->sarr_siz - n), 0, n * sizeof(sarr_seg_t));
                    194: 
                    195:        return 0;
                    196: }
                    197: 
                    198: /*
                    199:  * sarr_Get() - Get element from dynamic split-order array
                    200:  *
                    201:  * @arr = Array
                    202:  * @idx = Index (warning 1st element is at position 1)
                    203:  * return: NULL not found, !=NULL element
                    204:  */
1.2       misho     205: void *
1.1       misho     206: sarr_Get(sarr_t * __restrict arr, u_int idx)
                    207: {
                    208:        void *ret = NULL;
                    209:        sarr_seg_t seg;
                    210: 
                    211:        if (!arr || idx < 1 || arr->sarr_num < idx)
                    212:                return ret;
                    213: 
                    214:        seg = arr->sarr_data[idx / arr->sarr_seg];
                    215:        if (seg)
                    216:                ret = seg[idx % arr->sarr_seg];
                    217: 
                    218:        return ret;
                    219: }
                    220: 
                    221: /*
                    222:  * sarr_Get2() - Always get element from dynamic split-order array
                    223:  *     Function automatic grow array. Good use for Hash tables! 
                    224:  *
                    225:  * @arr = Array
                    226:  * @idx = Index (warning 1st element is at position 1)
                    227:  * return: NULL not found, !=NULL element
                    228:  */
                    229: void *
                    230: sarr_Get2(sarr_t * __restrict arr, u_int idx)
                    231: {
                    232:        if (!arr || idx < 1)
                    233:                return NULL;
                    234:        if (arr->sarr_num < idx)
                    235:                if (sarr_Grow(arr, idx))
                    236:                        return NULL;
                    237:        return sarr_Get(arr, idx);
                    238: }
                    239: 
                    240: /*
                    241:  * sarr_Set() - Set element to dynamic split-order array
                    242:  *
                    243:  * @arr = Array
                    244:  * @idx = Index (warning 1st element is at position 1)
                    245:  * @data = Value
                    246:  * return: NULL error or empty, !=NULL old value in element
                    247:  */
1.2       misho     248: void *
1.1       misho     249: sarr_Set(sarr_t * __restrict arr, u_int idx, void *data)
                    250: {
                    251:        void *ret = NULL;
                    252:        sarr_seg_t seg;
                    253:        register int pos;
                    254: 
                    255:        if (!arr || idx < 1 || arr->sarr_num < idx)
                    256:                return ret;
                    257: 
                    258:        seg = arr->sarr_data[idx / arr->sarr_seg];
                    259:        if (!seg) {
                    260:                seg = e_calloc(arr->sarr_seg, sizeof(void*));
                    261:                if (!seg)
                    262:                        return ret;
                    263:                else
                    264:                        memset(seg, 0, arr->sarr_seg * sizeof(void*));
                    265:                arr->sarr_data[idx / arr->sarr_seg] = seg;
                    266:        }
                    267: 
                    268:        pos = idx % arr->sarr_seg;
                    269:        ret = seg[pos];
                    270:        seg[pos] = data;
                    271: 
                    272:        return ret;
                    273: }
                    274: 
                    275: /*
                    276:  * sarr_sarr2array() - Convert from split-order array to dynamic array
                    277:  *
                    278:  * @sa = split array
                    279:  * @sarrFree = after convert split array !=0 will be destroyed sarray
                    280:  * return: NULL error or != NULL new array
                    281:  */
                    282: array_t *
                    283: sarr_sarr2array(sarr_t ** __restrict sa, int sarrFree)
                    284: {
                    285:        array_t *arr = NULL;
                    286:        int el;
                    287:        register int i;
                    288: 
                    289:        if (!sa || !*sa)
                    290:                return NULL;
                    291: 
                    292:        el = sarr_Size(*sa);
                    293:        arr = array_Init(el);
                    294:        if (!arr)
                    295:                return NULL;
                    296: 
                    297:        for (i = 0; i < el; i++)
                    298:                array_Set(arr, i, sarr_Get(*sa, i + 1));
                    299: 
                    300:        if (sarrFree) {
                    301:                e_free(*sa);
                    302:                *sa = NULL;
                    303:        }
                    304:        return arr;
                    305: }
                    306: 
                    307: /*
                    308:  * sarr_array2sarr() - Convert from dynamic array to split-order array
                    309:  *
                    310:  * @a = array
                    311:  * @segLen = Length of segment
                    312:  * @arrFree = after convert array !=0 will be destroyed
                    313:  * return: NULL error or != NULL new sarr
                    314:  */
                    315: sarr_t *
                    316: sarr_array2sarr(array_t ** __restrict a, int segLen, int arrFree)
                    317: {
                    318:        sarr_t *sa = NULL;
                    319:        int el;
                    320:        register int i;
                    321: 
                    322:        if (!a || !*a)
                    323:                return NULL;
                    324: 
                    325:        el = array_Size(*a);
                    326:        sa = sarr_Init(el, segLen);
                    327:        if (!sa)
                    328:                return NULL;
                    329: 
                    330:        for (i = 0; i < el; i++)
                    331:                sarr_Set(sa, i + 1, array_Get(*a, i));
                    332: 
                    333:        if (arrFree) {
                    334:                e_free(*a);
                    335:                *a = NULL;
                    336:        }
                    337:        return sa;
                    338: }

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