diff options
Diffstat (limited to 'util/src/linked_list.c')
-rw-r--r-- | util/src/linked_list.c | 573 |
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; +} + |