ptr_vector.c

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2004, 2006 Symbian Software Ltd.                        *
 *   All rights reserved.                                                  *
 *                                                                         *
 *   Contributed originally by Mike Kinghan, imk@strudl.org                *
 *                                                                         *
 *   Redistribution and use in source and binary forms, with or without    *
 *   modification, are permitted provided that the following conditions    *
 *   are met:                                                              *
 *                                                                         *
 *   Redistributions of source code must retain the above copyright        *
 *   notice, this list of conditions and the following disclaimer.         *
 *                                                                         *
 *   Redistributions in binary form must reproduce the above copyright     *
 *   notice, this list of conditions and the following disclaimer in the   *
 *   documentation and/or other materials provided with the distribution.  *
 *                                                                         *
 *   Neither the name of Symbian Software Ltd. nor the names of its        *
 *   contributors may be used to endorse or promote products derived from  *
 *   this software without specific prior written permission.              *
 *                                                                         *
 *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS   *
 *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT     *
 *   LIMITED TO, THE IMPLIED WARRANTIES OF  MERCHANTABILITY AND FITNESS    *
 *   FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE        *
 *   COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,   *
 *   INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,  *
 *   BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS *
 *   OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED    *
 *   AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,*
 *   OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF *
 *   THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH  *
 *   DAMAGE.                                                               *
 *                                                                         *
 **************************************************************************/
#include "ptr_vector.h"
#include "report.h"
#include "swiss_army.h"


struct ptr_vector {
    size_t tranch;
    size_t count;
    size_t cap;
    dtor_t dtor;
    cloner_t cloner;
    void **ptrs;
};

static void *
default_cloner(void const * src)
{
    return clone(src,0);
}

static void
ptr_vector_init(ptr_vector_h pv, dtor_t dtor, cloner_t cloner)
{
    pv->cap = pv->count = 0;
    pv->tranch = 16 * sizeof(void *);
    pv->dtor = dtor ? dtor : free;
    pv->cloner = cloner ? cloner : default_cloner;
    pv->ptrs = NULL;
}

static void
ptr_vector_copy_init(ptr_vector_h dest, ptr_vector_const_h src)
{
    void const ** begin = ptr_vector_begin_const(src);
    void const **end = ptr_vector_end_const(src);
    cloner_t cloner = src->cloner;
    ptr_vector_init(dest,src->dtor,src->cloner);
    begin = ptr_vector_begin_const(src);
    end = ptr_vector_end_const(src);
    for (       ; begin != end; ++begin) {
        ptr_vector_append(dest,cloner(*begin));
    }
}

static void
ptr_vector_finis(ptr_vector_h pv)
{
    if (pv->ptrs) {
        void **begin = pv->ptrs;
        void **end = pv->ptrs + pv->count;
        for (   ; begin != end; ++begin) {
            pv->dtor(*begin);
        }
        free(pv->ptrs);
        pv->ptrs = NULL;
    }
}

/* API **************************************************************/


ptr_vector_h
ptr_vector_new(dtor_t dtor, cloner_t cloner)
{
    ptr_vector_h  pv = zallocate(sizeof(struct ptr_vector));
    ptr_vector_init(pv,dtor,cloner);
    return pv;
}

void
ptr_vector_dispose(ptr_vector_h pv)
{
    if (pv) {
        ptr_vector_finis(pv);
        free(pv);
    }
}

void
ptr_vector_drop(ptr_vector_h pv)
{
    if (pv) {
        free(pv);
    }
}

ptr_vector_h
ptr_vector_copy(ptr_vector_const_h src)
{
    ptr_vector_h pv;
    assert(src);
    pv = zallocate(sizeof(struct ptr_vector));
    ptr_vector_copy_init(pv,src);
    return pv;
}

void
ptr_vector_swap(ptr_vector_h lhs, ptr_vector_h rhs)
{
    assert(lhs);
    assert(rhs);
    PODSWAP(size_t,&lhs->tranch,&rhs->tranch);
    PODSWAP(size_t,&lhs->count,&rhs->count);
    PODSWAP(size_t,&lhs->cap,&rhs->cap);
    PODSWAP(dtor_t,&lhs->dtor,&rhs->dtor);
    PODSWAP(cloner_t,&lhs->cloner,&rhs->cloner);
    PODSWAP(void **,&lhs->ptrs,&rhs->ptrs);
}

void
ptr_vector_assign(ptr_vector_h dest, ptr_vector_const_h src)
{
    if (dest != src) {
        ptr_vector_h tmp = ptr_vector_copy(src);
        ptr_vector_swap(dest,tmp);
        ptr_vector_dispose(tmp);
    }
}

void
ptr_vector_insert(ptr_vector_h pv, size_t pos, void const *ptr)
{
    if (pv->count == pv->cap) {
        pv->cap += pv->tranch;
        pv->ptrs = reallocate(pv->ptrs,pv->cap * sizeof(void *));
        pv->tranch <<= 1;
    }
    if (pos >= pv->count) {
        pv->ptrs[pv->count++] = (void*)ptr;
    } else {
        memmove(pv->ptrs + pos + 1,
                pv->ptrs + pos,
                ((pv->count - pos) * sizeof(void *)));
        pv->ptrs[pos] = (void *)ptr;
        ++pv->count;
    }
}

bool
ptr_vector_delete(ptr_vector_h pv, size_t pos)
{
    if (pos < pv->count) {
        memmove(pv->ptrs + pos,
        pv->ptrs + pos + 1,
        ((pv->count - 1 + pos) * sizeof(void *)));
        --pv->count;
        return true;
    }
    return false;
}

bool
ptr_vector_equal(       ptr_vector_const_h lhs,
                    ptr_vector_const_h rhs,
                    comparator_t compare)
{
    if (lhs != rhs) {
        assert(lhs);
        assert(rhs);
        if (lhs->dtor == rhs->dtor && lhs->cloner == rhs->cloner) {
            if (ptr_vector_count(lhs) == ptr_vector_count(rhs)) {
                void const ** lh_iter = ptr_vector_begin_const(lhs);
                void const ** rh_iter = ptr_vector_begin_const(rhs);
                void const ** lh_end = ptr_vector_end_const(lhs);
                for     (       ; lh_iter != lh_end; ++lh_iter,++rh_iter) {
                    if (compare(*lh_iter,*rh_iter,0)) {
                        return false;
                    }
                }
                return true;
            }
        }
        return false;
    }
    return true;
}

dtor_t
ptr_vector_dtor(ptr_vector_const_h pv)
{
    assert(pv);
    return pv->dtor;
}

cloner_t
ptr_vector_cloner(ptr_vector_const_h pv)
{
    assert(pv);
    return pv->cloner;
}


void
ptr_vector_append(ptr_vector_h pv, void *ptr)
{
    ptr_vector_insert(pv,(size_t)-1,ptr);
}

size_t
ptr_vector_count(ptr_vector_const_h pv)
{
    return pv->count;
}

void **
ptr_vector_begin(ptr_vector_h pv)
{
    return pv->ptrs;
}

void const **
ptr_vector_begin_const(ptr_vector_const_h pv)
{
    return (void const **)ptr_vector_begin((ptr_vector_h)pv);
}

void **
ptr_vector_end(ptr_vector_h pv)
{
    return pv->ptrs + pv->count;
}

void const **
ptr_vector_end_const(ptr_vector_const_h pv)
{
    return (void const **)ptr_vector_end((ptr_vector_h)pv);
}

void *
ptr_vector_at(ptr_vector_h pv, size_t pos)
{
    return (pos < pv->count) ? pv->ptrs[pos] : 0;
}

void const *
ptr_vector_at_const(ptr_vector_const_h pv, size_t pos)
{
    return (void const *)ptr_vector_at((ptr_vector_h)pv,pos);
}

locator_t
ptr_vector_search(      ptr_vector_const_h pv,
                    void const *key,
                    locator_t keylen,
                    comparator_t compare,
                    bool ordered)
{
    locator_t comp = 1;
    void const ** begin = ptr_vector_begin_const(pv);
    void const ** end = ptr_vector_end_const(pv);
    void const ** iter = begin;
    if (!ordered) {
        for ( iter = begin; iter != end; ++iter) {
            comp = compare(*iter,key,keylen);
            if (!comp) {
                break;
            }
        }
    } else {
        for ( iter = begin; iter != end; ++iter) {
            comp = compare(*iter,key,keylen);
            if (comp >= 0) {
                break;
            }
        }
    }
    comp = comp ? ~(iter - begin) : iter - begin;
    return comp;
}

/* EOF*/