util/src/linked_list.c

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <axutil_linked_list.h>
#include <axutil_utils.h>

struct axutil_linked_list
{

    /**The number of elements in this list. */
    int size;

    /**
     * The first element in the list.
     */
    entry_t *first;

    /**
     * The last element in the list.
     */
    entry_t *last;

    /**
     * A count of the number of structural modifications that have been made to
     * the list (that is, insertions and removals). Structural modifications
     * are ones which change the list size or affect how iterations would
     * behave. This field is available for use by Iterator and ListIterator,
     * in order to set an error code in response
     * to the next op on the iterator. This <i>fail-fast</i> behavior
     * saves the user from many subtle bugs otherwise possible from concurrent
     * modification during iteration.
     * <p>
     *
     * To make lists fail-fast, increment this field by just 1 in the
     * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
     * Otherwise, this field may be ignored.
     */
    int mod_count;
};

AXIS2_EXTERN axutil_linked_list_t *AXIS2_CALL
axutil_linked_list_create(
    const axutil_env_t *env)
{
    axutil_linked_list_t *linked_list = NULL;

    AXIS2_ENV_CHECK(env, NULL);

    linked_list = AXIS2_MALLOC(env->allocator, sizeof(axutil_linked_list_t));
    if(!linked_list)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_MEMORY, AXIS2_FAILURE);
        AXIS2_LOG_ERROR(env->log, AXIS2_LOG_SI, "Out of memory");
        return NULL;
    }

    linked_list->size = 0;
    linked_list->mod_count = 0;
    linked_list->first = NULL;
    linked_list->last = NULL;

    return linked_list;
}

static entry_t *
axutil_linked_list_create_entry(
    const axutil_env_t *env,
    void *data)
{
    entry_t *entry = (entry_t *)AXIS2_MALLOC(env->allocator, sizeof(entry_t));
    if(!entry)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_MEMORY, AXIS2_FAILURE);
        AXIS2_LOG_ERROR(env->log, AXIS2_LOG_SI, "Out of memory");
        return NULL;
    }

    entry->data = data;
    entry->previous = NULL;
    entry->next = NULL;
    return entry;
}

static axis2_status_t
axutil_linked_list_add_last_entry(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    entry_t * e)
{
    AXIS2_PARAM_CHECK(env->error, e, AXIS2_FAILURE);

    linked_list->mod_count++;
    if(linked_list->size == 0)
    {
        linked_list->first = linked_list->last = e;
    }
    else
    {
        e->previous = linked_list->last;
        linked_list->last->next = e;
        linked_list->last = e;
    }
    linked_list->size++;

    return AXIS2_SUCCESS;
}

AXIS2_EXTERN void AXIS2_CALL
axutil_linked_list_free(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    entry_t *current = NULL, *next = NULL;

    current = linked_list->first;
    while(current)
    {
        next = current->next;
        AXIS2_FREE(env->allocator, current);
        current = next;
    }
    AXIS2_FREE(env->allocator, linked_list);
    linked_list = NULL;
}

AXIS2_EXTERN entry_t *AXIS2_CALL
axutil_linked_list_get_entry(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int n)
{
    entry_t *e = NULL;
    if(n < linked_list->size / 2)
    {
        e = linked_list->first;
        /* n less than size/2, iterate from start */
        while(n > 0)
        {
            e = e->next;
            n = n - 1;
        }
    }
    else
    {
        e = linked_list->last;
        /* n greater than size/2, iterate from end */
        while((n = n + 1) < linked_list->size)
        {
            e = e->previous;
        }
    }

    return e;
}

AXIS2_EXTERN axis2_status_t AXIS2_CALL
axutil_linked_list_remove_entry(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    entry_t *e)
{
    AXIS2_PARAM_CHECK(env->error, e, AXIS2_FAILURE);
    linked_list->mod_count++;
    linked_list->size--;
    if(linked_list->size == 0)
    {
        linked_list->first = linked_list->last = NULL;
    }
    else
    {
        if(e == linked_list->first)
        {
            linked_list->first = e->next;
            e->next->previous = NULL;
        }
        else if(e == linked_list->last)
        {
            linked_list->last = e->previous;
            e->previous->next = NULL;
        }
        else
        {
            e->next->previous = e->previous;
            e->previous->next = e->next;
        }
    }
    return AXIS2_SUCCESS;
}

AXIS2_EXTERN axis2_bool_t AXIS2_CALL
axutil_linked_list_check_bounds_inclusive(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int index)
{
    if(index < 0 || index > linked_list->size)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_INDEX_OUT_OF_BOUNDS, AXIS2_FAILURE);
        return AXIS2_FALSE;
    }
    return AXIS2_TRUE;
}

AXIS2_EXTERN axis2_bool_t AXIS2_CALL
axutil_linked_list_check_bounds_exclusive(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int index)
{
    if(index < 0 || index >= linked_list->size)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_INDEX_OUT_OF_BOUNDS, AXIS2_FAILURE);
        return AXIS2_FALSE;
    }
    return AXIS2_TRUE;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_get_first(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    if(linked_list->size == 0)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_SUCH_ELEMENT, AXIS2_FAILURE);
        return NULL;
    }

    return linked_list->first->data;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_get_last(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    if(linked_list->size == 0)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_SUCH_ELEMENT, AXIS2_FAILURE);
        return NULL;
    }

    return linked_list->last->data;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_remove_first(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    void *r;

    if(linked_list->size == 0)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_SUCH_ELEMENT, AXIS2_FAILURE);
        return NULL;
    }

    linked_list->mod_count++;
    linked_list->size--;
    r = linked_list->first->data;

    if(linked_list->first->next)
    {
        linked_list->first->next->previous = NULL;
    }
    else
    {
        linked_list->last = NULL;
    }

    entry_t * orphan = linked_list->first;
    linked_list->first = linked_list->first->next;
    AXIS2_FREE(env->allocator, orphan);

    return r;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_remove_last(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    void *r = NULL;

    if(linked_list->size == 0)
    {
        AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_SUCH_ELEMENT, AXIS2_FAILURE);
        return NULL;
    }

    linked_list->mod_count++;
    linked_list->size--;
    r = linked_list->last->data;

    if(linked_list->last->previous)
    {
        linked_list->last->previous->next = NULL;
    }
    else
    {
        linked_list->first = NULL;
    }

    entry_t * orphan = linked_list->last;
    linked_list->last = linked_list->last->previous;
    AXIS2_FREE(env->allocator, orphan);

    return r;
}

AXIS2_EXTERN axis2_status_t AXIS2_CALL
axutil_linked_list_add_first(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FAILURE);

    e = axutil_linked_list_create_entry(env, o);

    linked_list->mod_count++;
    if(linked_list->size == 0)
    {
        linked_list->first = linked_list->last = e;
    }
    else
    {
        e->next = linked_list->first;
        linked_list->first->previous = e;
        linked_list->first = e;
    }
    linked_list->size++;

    return AXIS2_SUCCESS;
}

AXIS2_EXTERN axis2_status_t AXIS2_CALL
axutil_linked_list_add_last(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FAILURE);

    e = axutil_linked_list_create_entry(env, o);
    return axutil_linked_list_add_last_entry(linked_list, env, e);
}

AXIS2_EXTERN axis2_bool_t AXIS2_CALL
axutil_linked_list_contains(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FALSE);

    e = linked_list->first;
    while(e)
    {
        if(o == e->data)
            return AXIS2_TRUE;
        e = e->next;
    }
    return AXIS2_FALSE;
}

AXIS2_EXTERN int AXIS2_CALL
axutil_linked_list_size(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    return linked_list->size;
}

AXIS2_EXTERN axis2_bool_t AXIS2_CALL
axutil_linked_list_add(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FALSE);
    e = axutil_linked_list_create_entry(env, o);
    return axutil_linked_list_add_last_entry(linked_list, env, e);
}

AXIS2_EXTERN axis2_bool_t AXIS2_CALL
axutil_linked_list_remove(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FALSE);

    e = linked_list->first;
    while(e)
    {
        if(o == e->data)
        {
            return axutil_linked_list_remove_entry(linked_list, env, e);
        }
        e = e->next;
    }
    return AXIS2_FALSE;
}

AXIS2_EXTERN axis2_status_t AXIS2_CALL
axutil_linked_list_clear(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    if(linked_list->size > 0)
    {
        linked_list->mod_count++;
        linked_list->first = NULL;
        linked_list->last = NULL;
        linked_list->size = 0;
    }

    return AXIS2_SUCCESS;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_get(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int index)
{
    axutil_linked_list_check_bounds_exclusive(linked_list, env, index);
    return axutil_linked_list_get_entry(linked_list, env, index)->data;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_set(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int index,
    void *o)
{
    entry_t *e;
    void *old;
    AXIS2_PARAM_CHECK(env->error, o, NULL);
    axutil_linked_list_check_bounds_exclusive(linked_list, env, index);
    e = axutil_linked_list_get_entry(linked_list, env, index);
    old = e->data;
    e->data = o;
    return old;
}

AXIS2_EXTERN axis2_status_t AXIS2_CALL
axutil_linked_list_add_at_index(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int index,
    void *o)
{
    entry_t *after = NULL;
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FAILURE);

    axutil_linked_list_check_bounds_inclusive(linked_list, env, index);
    e = axutil_linked_list_create_entry(env, o);

    if(index < linked_list->size)
    {
        linked_list->mod_count++;
        after = axutil_linked_list_get_entry(linked_list, env, index);
        e->next = after;
        e->previous = after->previous;
        if(after->previous == NULL)
            linked_list->first = e;
        else
            after->previous->next = e;
        after->previous = e;
        linked_list->size++;
    }
    else
    {
        axutil_linked_list_add_last_entry(linked_list, env, e);
    }

    return AXIS2_SUCCESS;
}

AXIS2_EXTERN void *AXIS2_CALL
axutil_linked_list_remove_at_index(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    int index)
{
    entry_t *e;
    axutil_linked_list_check_bounds_exclusive(linked_list, env, index);
    e = axutil_linked_list_get_entry(linked_list, env, index);
    axutil_linked_list_remove_entry(linked_list, env, e);
    void *data = e->data;
    AXIS2_FREE(env->allocator, e);
    return data;
}

AXIS2_EXTERN int AXIS2_CALL
axutil_linked_list_index_of(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    int index = 0;
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FAILURE);

    e = linked_list->first;
    while(e)
    {
        if(o == e->data)
            return index;
        index++;
        e = e->next;
    }
    return -1;
}

AXIS2_EXTERN int AXIS2_CALL
axutil_linked_list_last_index_of(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env,
    void *o)
{
    int index;
    entry_t *e;
    AXIS2_PARAM_CHECK(env->error, o, AXIS2_FAILURE);

    index = linked_list->size - 1;
    e = linked_list->last;
    while(e)
    {
        if(o == e->data)
            return index;
        index--;
        e = e->previous;
    }
    return -1;
}

AXIS2_EXTERN void **AXIS2_CALL
axutil_linked_list_to_array(
    axutil_linked_list_t *linked_list,
    const axutil_env_t *env)
{
    int i = 0;
    void **array;
    entry_t *e;
    array = (void **)AXIS2_MALLOC(env->allocator, linked_list->size * sizeof(void *));
    e = linked_list->first;
    for(i = 0; i < linked_list->size; i++)
    {
        array[i] = e->data;
        e = e->next;
    }
    return array;
}