ptr_set.c

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2007-2011 Mike Kinghan, imk@strudl.org                  *
 *   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_set.h"
#include "memory.h"
#include "swiss_army.h"
#include <string.h>
#include <assert.h>
#include <stddef.h>



#define SOMEWHERE(loc)  ((loc) >= 0)

#define NOWHERE(loc)    ((loc) < 0)

#define POINTER(loc) (NOWHERE(loc) ? ~(loc) : (loc))

struct ptr_set {
    ptr_vector_h pv;
    comparator_t compare;
    locator_t cached_pos;
};

/* Helpers */

static int
default_comparator(void const *obj, void const *key, locator_t ignore)
{
    (void)ignore;
    return strcmp(obj,key);

}

static void
ptr_set_init(   ptr_set_h ps,
                comparator_t compare,
                dtor_t dtor,
                cloner_t cloner)
{
    ps->pv = ptr_vector_new(dtor,cloner);
    ps->compare = compare ? compare : default_comparator;
    ps->cached_pos = -1;
}

static void
ptr_set_copy_init(ptr_set_h dest, ptr_set_const_h src)
{
    dest->pv = ptr_vector_copy(src->pv);
    dest->compare = src->compare;
    dest->cached_pos = src->cached_pos;
}

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

ptr_set_h
ptr_set_new(comparator_t compare, dtor_t dtor, cloner_t cloner)
{
    ptr_set_h ps = allocate(sizeof(struct ptr_set));
    ptr_set_init(ps,compare,dtor,cloner);
    return ps;
}

void
ptr_set_dispose(ptr_set_h ps)
{
    if (ps) {
        ptr_vector_dispose(ps->pv);
        free(ps);
    }
}

ptr_set_h
ptr_set_copy(ptr_set_const_h src)
{
    ptr_set_h ps;
    assert(src);
    ps = allocate(sizeof(struct ptr_set));
    ptr_set_copy_init(ps,src);
    return ps;
}

void
ptr_set_swap(ptr_set_h lhs, ptr_set_h rhs)
{
    assert(lhs);
    assert(rhs);
    ptr_vector_swap(lhs->pv,rhs->pv);
    PODSWAP(comparator_t,&lhs->compare,&rhs->compare);
    PODSWAP(locator_t,&lhs->cached_pos,&rhs->cached_pos);
}

void
ptr_set_assign(ptr_set_h dest, ptr_set_const_h src)
{
    if (dest != src) {
        ptr_set_h tmp = ptr_set_copy(src);
        ptr_set_swap(dest,tmp);
        ptr_set_dispose(tmp);
    }
}

bool
ptr_set_equal(  ptr_set_const_h lhs,
                ptr_set_const_h rhs)
{
    bool eq = lhs == rhs;
    if (!eq) {
        eq = lhs->compare == rhs->compare;
        if (eq) {
            eq = ptr_vector_equal(lhs->pv,rhs->pv,lhs->compare);
        }
    }
    return eq;
}


comparator_t
ptr_set_comparator(ptr_set_const_h ps)
{
    assert(ps);
    return ps->compare;
}

dtor_t
ptr_set_dtor(ptr_set_const_h ps)
{
    return ptr_vector_dtor(ps->pv);
}

cloner_t
ptr_set_cloner(ptr_set_const_h ps)
{
    return ptr_vector_cloner(ps->pv);
}

size_t
ptr_set_count(ptr_set_const_h ps)
{
    return ptr_vector_count(ps->pv);
}

void *
ptr_set_search(ptr_set_h ps, char const *key, locator_t keylen)
{
    locator_t loc;
    assert(ps);
    loc = ptr_vector_search(ps->pv,key,keylen,ps->compare,true);
    if (NOWHERE(loc)) {
        ps->cached_pos = ~loc;
        return NULL;
    }
    ps->cached_pos = -1;
    return ptr_vector_at(ps->pv,(size_t)loc);
}

void const *
ptr_set_search_const(ptr_set_const_h ps, char const *key, locator_t keylen)
{
    return ptr_set_search((ptr_set_h)ps,key,keylen);
}


bool
ptr_set_insert(ptr_set_h ps, void const *obj)
{
        size_t nelems;
        locator_t loc;
    assert(ps);
    assert(obj);
    nelems = ptr_vector_count(ps->pv);
    loc = ps->cached_pos;
    ps->cached_pos = -1;
    if (!nelems) {
        ptr_vector_append(ps->pv,(void *)obj);
        return true;
    } else {
        if (SOMEWHERE(loc)) {
            int prev_comp = -1, next_comp = 1;
            void const *other;
            if (loc > 0) {
                other = ptr_vector_at(ps->pv,loc - 1);
                prev_comp = ps->compare(other,obj,0);
                if (!prev_comp) {
                    return false;
                }
            }
            if ((size_t)(loc + 1 )< nelems) {
                other = ptr_vector_at(ps->pv,loc + 1);
                next_comp = ps->compare(other,obj,0);
                if (!next_comp) {
                    return false;
                }
            }
            if (prev_comp > 0 || next_comp < 0) {
                loc = -1;
            }
        }
        if (NOWHERE(loc)) {
            loc = ptr_vector_search(ps->pv,obj,0,ps->compare,true);
            if (SOMEWHERE(loc)) {
                return false;
            }
            loc = ~loc;
        }
        ptr_vector_insert(ps->pv,loc,obj);
        return true;
    }
}

bool
ptr_set_delete(ptr_set_h ps, locator_t pos)
{
    assert(ps);
    return ptr_vector_delete(ps->pv,(size_t)pos);
}

void **
ptr_set_begin(ptr_set_const_h ps)
{
    assert(ps);
    return ptr_vector_begin(ps->pv);
}

void **
ptr_set_end(ptr_set_const_h ps)
{
    assert(ps);
    return ptr_vector_end(ps->pv);
}

void const **
ptr_set_begin_const(ptr_set_const_h ps)
{
    return (void const **)ptr_set_begin(ps);
}

void const **
ptr_set_end_const(ptr_set_const_h ps)
{
    return (void const **)ptr_set_end(ps);
}