/** BEGIN COPYRIGHT BLOCK
 * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission.
 * Copyright (C) 2005 Red Hat, Inc.
 * All rights reserved.
 *
 * License: GPL (version 3 or any later version).
 * See LICENSE for details.
 * END COPYRIGHT BLOCK **/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif


#include "slapi-plugin.h"
#include "slapi-private.h"

/*
 * The "wrapper" placed around objects in our object set.
 */
typedef struct objset_object
{
    Object *obj;                /* pointer to actual object */
    struct objset_object *next; /* pointer to next object in list */
} objset_object;

/*
 * The object set itself.
 */
typedef struct objset
{
    objset_object *head; /* pointer to linked list of objects */
    objset_object *tail; /* pointer to tail of linked list */
    PRLock *lock;        /* Lock - protects addition/deletion from list */
    FNFree destructor;   /* Destructor callback for objset itself */
} objset;

/* Forward declarations */
static void unlinkObjsetObjectNoLock(Objset *o, objset_object *obj_to_unlink);


/*
 * Create a new, empty object set.
 * Returns a pointer to the new object set, or NULL if an error occurred.
 */
Objset *
objset_new(FNFree objset_destructor)
{
    objset *set;

    set = (objset *)slapi_ch_malloc(sizeof(objset));
    set->lock = PR_NewLock();
    if (NULL == set->lock) {
        slapi_ch_free((void **)&set);
    } else {
        set->head = set->tail = NULL;
        set->destructor = objset_destructor;
    }
    return set;
}


/*
 * Delete an object set. All references to contained objects
 * are released, and the objset is deleted.
 */
void
objset_delete(Objset **setp)
{
    objset_object *o, *o_next;
    Objset *set;

    PR_ASSERT(NULL != setp);
    set = *setp;
    PR_ASSERT(NULL != set);
    PR_Lock(set->lock);
    o = set->head;
    while (NULL != o) {
        o_next = o->next;
        object_release(o->obj);     /* release our reference */
        slapi_ch_free((void **)&o); /* Free wrapper */
        o = o_next;
    }
    PR_Unlock(set->lock);
    PR_DestroyLock(set->lock);
    if (NULL != set->destructor) {
        set->destructor((void **)setp);
    }
    slapi_ch_free((void **)setp);
}


/*
 * Add a new object to an object set.
 * Return values:
 * OBJSET_SUCCESS: the insertion was succesful.
 * OBJSET_ALREADY_EXISTS: the object already exists in the set.
 */
int
objset_add_obj(Objset *set, Object *object)
{
    objset_object *p;
    int exists = 0;
    int rc = OBJSET_SUCCESS;

    PR_ASSERT(NULL != set);
    PR_ASSERT(NULL != object);

    PR_Lock(set->lock);
    /* Make sure this object isn't already in the set */
    p = set->head;
    while (NULL != p) {
        if (p->obj == object) {
            exists = 1;
            break;
        }
        p = p->next;
    }
    if (exists) {
        rc = OBJSET_ALREADY_EXISTS;
    } else {
        objset_object *new_node = (objset_object *)slapi_ch_malloc(sizeof(objset_object));
        object_acquire(object); /* Record our reference */
        new_node->obj = object;
        new_node->next = NULL;

        if (NULL == set->head) {
            set->head = set->tail = new_node;
        } else {
            set->tail->next = new_node;
            set->tail = new_node;
        }
    }
    PR_Unlock(set->lock);
    return rc;
}


/*
 * Locate an object in an object set.
 *
 * Arguments:
 * set: the object set to search
 * compare_fn: a caller-provided function used to compare the
 *             name against an object. This function should return
 *             a negtive value, zero, or a positive value if the
 *             object's name is, respectively, less that, equal
 *             to, or greater than the provided name.
 * name: the name (value) to find.
 *
 * The returned object, if any, is referenced. The caller must
 * call object_release() when finished with the object.
 *
 * Returns the object, if found. Otherwise, returns NULL.
 * Implementation note: since we store objects in an unordered
 * linked list, all that's really important is that the compare_fn
 * return 0 when a match is found, and non-zero otherwise.
 * Other types of implementations might try to optimize the
 * storage, e.g. binary search.
 */
Object *
objset_find(Objset *set, CMPFn compare_fn, const void *name)
{
    objset_object *found = NULL;

    PR_ASSERT(NULL != set);
    PR_ASSERT(NULL != name);
    PR_ASSERT(NULL != compare_fn);

    PR_Lock(set->lock);
    found = set->head;
    while (NULL != found) {
        if (compare_fn(found->obj, name) == 0) {
            break;
        }
        found = found->next;
    }
    if (NULL != found) {
        /* acquire object */
        object_acquire(found->obj);
    }
    PR_Unlock(set->lock);
    return found == NULL ? NULL : found->obj;
}


/*
 * Remove an object from an objset.
 * Returns OBJSET_SUCCESS if the object was found and removed, or
 * OBJSET_NO_SUCH_OBJECT if the object was not found in the list.
 */
int
objset_remove_obj(Objset *set, Object *object)
{
    int rc = OBJSET_SUCCESS;
    objset_object *found;

    PR_ASSERT(NULL != set);
    PR_ASSERT(NULL != object);

    PR_Lock(set->lock);
    found = set->head;
    while (NULL != found) {
        if (found->obj == object) {
            break;
        }
        found = found->next;
    }
    if (NULL == found) {
        rc = OBJSET_NO_SUCH_OBJECT;
    } else {
        Object *saved = found->obj;

        /* Unlink from list */
        unlinkObjsetObjectNoLock(set, found);

        /* Release reference on object */
        object_release(saved);
    }
    PR_Unlock(set->lock);
    return rc;
}


/*
 * Prepare for iteration across an object set. Returns the first
 * object in the set. The returned object is referenced, therefore
 * the caller must either release the object, or
 * pass it to an objset_next_obj call, which will
 * implicitly release the object.
 * Returns the first object, or NULL if the objset contains no
 * objects.
 */
Object *
objset_first_obj(Objset *set)
{
    Object *return_object;

    /* Be tolerant (for the replication plugin) */
    if (set == NULL)
        return NULL;

    PR_Lock(set->lock);
    if (NULL == set->head) {
        return_object = NULL;
    } else {
        object_acquire(set->head->obj);
        return_object = set->head->obj;
    }
    PR_Unlock(set->lock);
    return return_object;
}


/*
 * Return the next object in an object set, or NULL if there are
 * no more objects.
 * The returned object is referenced, therefore
 * the caller must either release the object, or
 * pass it to an objset_next_ob call, which will
 * implicitly release the object.
 */
Object *
objset_next_obj(Objset *set, Object *previous)
{
    Object *return_object = NULL;
    objset_object *p;

    PR_ASSERT(NULL != set);
    PR_Lock(set->lock);

    /* First, find the current object */
    p = set->head;
    while (NULL != p && p->obj != previous) {
        p = p->next;
    }
    /* Find the next object */
    if (NULL != p && NULL != p->next) {
        return_object = p->next->obj;
        object_acquire(return_object);
    }
    PR_Unlock(set->lock);
    object_release(previous); /* Release the previous object */
    return return_object;
}


/*
 * Return a non-zero value if the object set is empty, or
 * zero if the object set is empty.
 */
int
objset_is_empty(Objset *set)
{
    int return_value;

    PR_ASSERT(NULL != set);

    PR_Lock(set->lock);
    return_value = (set->head == NULL);
    PR_Unlock(set->lock);
    return return_value;
}


/*
 * Return the count of objects in the object set.
 */
int
objset_size(Objset *set)
{
    int count = 0;
    objset_object *p;

    PR_ASSERT(NULL != set);
    PR_Lock(set->lock);
    for (p = set->head; p; p = p->next)
        count++;
    PR_Unlock(set->lock);
    return count;
}


/*
 * Utility function: remove object from list.
 * This needs to be called with the objset locked.
 */
static void
unlinkObjsetObjectNoLock(Objset *o, objset_object *obj_to_unlink)
{

    objset_object *p = o->head;

    PR_ASSERT(NULL != o->head);
    /* Unlink from list */
    if (o->head == obj_to_unlink) {
        /* Object to unlink was at head of list */
        p = o->head->next;
        o->head = obj_to_unlink->next;
    } else {
        while (NULL != p->next && p->next != obj_to_unlink) {
            p = p->next;
        }
        if (NULL != p->next) {
            /* p points to object prior to one being removed */
            p->next = p->next->next;
        }
    }
    if (o->tail == obj_to_unlink) {
        o->tail = p;
    }

    /* Free the wrapper */
    slapi_ch_free((void **)&obj_to_unlink);
}