1 files changed, 573 insertions, 0 deletions
diff --git a/util/src/linked_list.c b/util/src/linked_list.c
new file mode 100644
index 0000000..7ba83f8
--- /dev/null
+++ b/util/src/linked_list.c
@@ -0,0 +1,573 @@
+/*
+ * 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;
+    }
+
+    linked_list->first = linked_list->first->next;
+
+    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;
+    }
+
+    linked_list->last = linked_list->last->previous;
+
+    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);
+    return e->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;
+}
+