Moriyoshi Koizumi
moriy****@users*****
2002年 12月 31日 (火) 04:02:12 JST
moriyoshi 02/12/31 04:02:12
Modified: mbfl mbfl_arraylist.c mbfl_list.c mbfl_arraylist.h
mbfl_list.h mbfl_mutex.c
Log:
Did significant enhancement of array list implementation
Revision Changes Path
1.3 +110 -79 libmbfl/mbfl/mbfl_arraylist.c
Index: mbfl_arraylist.c
===================================================================
RCS file: /cvsroot/php-i18n/libmbfl/mbfl/mbfl_arraylist.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- mbfl_arraylist.c 30 Dec 2002 16:43:15 -0000 1.2
+++ mbfl_arraylist.c 30 Dec 2002 19:02:12 -0000 1.3
@@ -68,10 +68,12 @@
#define MBFL_AL_ENT_SIZE(objsize) ((sizeof(mbfl_arraylist_entry)-sizeof(((mbfl_arraylist_entry*)0)->obj))+objsize)
static int _mbfl_arraylist_insert_item_at(mbfl_arraylist *al_d, void *obj, unsigned int size, mbfl_collection_item_dtor_func item_dtor, int idx);
+static int _mbfl_arraylist_update_item_at(mbfl_arraylist *al_d, void *obj, unsigned int size, mbfl_collection_item_dtor_func item_dtor, int idx);
static int _mbfl_arraylist_get_item_at(mbfl_arraylist *al_d, void **pobj, unsigned int *pobj_size, int idx);
static int _mbfl_arraylist_remove_item_at(mbfl_arraylist *al_d, int idx);
static int _mbfl_arraylist_index_of(mbfl_arraylist *al_d, int *pretval, void *obj, unsigned int size);
static mbfl_iterator *_mbfl_arraylist_create_iter(mbfl_arraylist *al_d);
+static int _mbfl_arraylist_prepare_space(mbfl_arraylist *al_d, unsigned int size, int num_items);
MBFLAPI int mbfl_arraylist_ctor(mbfl_arraylist *al_d)
{
@@ -94,6 +96,7 @@
al_d->_super._super.create_iter_op = (mbfl_collection_create_iter_func)_mbfl_arraylist_create_iter;
al_d->_super._super.dtor = (mbfl_collection_dtor_func)_mbfl_arraylist_dtor;
al_d->_super.insert_item_at_op = (mbfl_list_insert_item_at_func)_mbfl_arraylist_insert_item_at;
+ al_d->_super.update_item_at_op = (mbfl_list_update_item_at_func)_mbfl_arraylist_update_item_at;
al_d->_super.get_item_at_op = (mbfl_list_get_item_at_func)_mbfl_arraylist_get_item_at;
al_d->_super.remove_item_at_op = (mbfl_list_remove_item_at_func)_mbfl_arraylist_remove_item_at;
al_d->_super.index_of_op = (mbfl_list_index_of_func)_mbfl_arraylist_index_of;
@@ -117,118 +120,146 @@
_mbfl_list_dtor(&(al_d->_super));
}
-static int _mbfl_arraylist_insert_item_at(mbfl_arraylist *al_d, void *obj, unsigned int size, mbfl_collection_item_dtor_func item_dtor, int idx)
+static int _mbfl_arraylist_prepare_space(mbfl_arraylist *al_d, unsigned int size, int num_items)
{
- unsigned int aligned_size;
- unsigned int ent_size;
- int err = 0;
- mbfl_arraylist_entry *new_entry;
-
-#ifdef ENABLE_THREADS
- int mutex_locked = 0;
-#endif
-
- assert(al_d != NULL);
-#ifdef ENABLE_THREADS
- assert(al_d->mutex != NULL);
-#endif
+ unsigned int aligned_size, new_ent_size, current_ent_size, required_size;
+ int i;
aligned_size = (size + 7) & ~7;
+ current_ent_size = MBFL_AL_ENT_SIZE(al_d->max_obj_size);
- ent_size = MBFL_AL_ENT_SIZE(al_d->max_obj_size);
-
- if (aligned_size > al_d->max_obj_size) {
- unsigned int i;
- unsigned int new_ent_size;
- unsigned int required_size;
-#ifdef ENABLE_THREADS
- if (mbfl_mutex_lock(al_d->mutex) != 0) {
- err = -1;
- goto out;
- }
- mutex_locked = 1;
-#endif
- required_size = MBFL_AL_ENT_SIZE(aligned_size) * (al_d->_super._super.num_items+1);
+ new_ent_size = (aligned_size > al_d->max_obj_size ? MBFL_AL_ENT_SIZE(aligned_size) : current_ent_size);
+ required_size = new_ent_size * num_items;
- if (required_size > al_d->allocated_size) {
- unsigned int new_size = (al_d->allocated_size == 0 ? MBFL_AL_ENT_SIZE(aligned_size): al_d->allocated_size);
- void *new_entries;
-
- while (new_size < required_size) {
- new_size *= 2;
- }
+ if (required_size > al_d->allocated_size) {
+ unsigned int new_size;
+ void *new_entries;
- if ((new_entries = mbfl_realloc(al_d->entries, new_size)) == NULL) {
- err = -1;
- goto out;
+ new_size = (al_d->allocated_size > 0 ? al_d->allocated_size : aligned_size);
+ while (new_size < required_size) {
+ if ((new_size << 1) < new_size) {
+ return -1;
}
-
- al_d->entries = new_entries;
- al_d->allocated_size = new_size;
+ new_size <<= 1;
}
- new_ent_size = MBFL_AL_ENT_SIZE(aligned_size);
+ if ((new_entries = mbfl_realloc(al_d->entries, new_size)) == NULL) {
+ return -1;
+ }
- i = al_d->_super._super.num_items;
+ al_d->entries = new_entries;
+ al_d->allocated_size = new_size;
+ }
- while (i-- > 0) {
- memmove(((char *)al_d->entries + i * new_ent_size),
- ((char *)al_d->entries + i * ent_size),
- ent_size);
+ if (new_ent_size > current_ent_size) {
+ for (i = al_d->_super._super.num_items; i > 0; i--) {
+ memmove(((char *)al_d->entries) + i * new_ent_size,
+ ((char *)al_d->entries) + i * current_ent_size,
+ current_ent_size);
}
- ent_size = new_ent_size;
-
al_d->max_obj_size = aligned_size;
}
- al_d->entries_size = ent_size * al_d->_super._super.num_items;
+ i = num_items - al_d->_super._super.num_items;
- if (al_d->entries_size >= al_d->allocated_size) {
- unsigned int new_size;
- void *new_entries;
+ if (i > 0) {
+ memset(((char *)al_d->entries) + al_d->_super._super.num_items * new_ent_size, 0, i * new_ent_size);
+ }
+
+ al_d->entries_size = new_ent_size * num_items;
+ al_d->_super._super.num_items = num_items;
+ return 0;
+}
+
+static int _mbfl_arraylist_insert_item_at(mbfl_arraylist *al_d, void *obj, unsigned int size, mbfl_collection_item_dtor_func item_dtor, int idx)
+{
+ int err = 0;
+ unsigned int offset;
+ unsigned int ent_size;
+ mbfl_arraylist_entry *new_entry;
+ int mutex_locked = 0;
+
+ assert(al_d != NULL);
#ifdef ENABLE_THREADS
- if (!mutex_locked) {
- if (mbfl_mutex_lock(al_d->mutex) != 0) {
- err = -1;
- goto out;
- }
- mutex_locked = 1;
- }
+ assert(al_d->mutex != NULL);
#endif
- new_size = al_d->entries_size;
+#ifdef ENABLE_THREADS
+ if (mbfl_mutex_lock(al_d->mutex) != 0) {
+ err = -1;
+ goto out;
+ }
+#endif
+ mutex_locked = 1;
- new_size = (new_size == 0 ? ent_size: new_size * 2);
+ if (idx < 0) {
+ idx = al_d->_super._super.num_items;
+ }
- if ((new_entries = mbfl_realloc(al_d->entries, new_size)) == NULL) {
- err = -1;
- goto out;
- }
+ if ((err = _mbfl_arraylist_prepare_space(al_d, size, al_d->_super._super.num_items + 1)) != 0) {
+ goto out;
+ }
- al_d->entries = new_entries;
- al_d->allocated_size = new_size;
+ ent_size = MBFL_AL_ENT_SIZE(al_d->max_obj_size);
+ offset = ent_size * idx;
+
+ new_entry = ((mbfl_arraylist_entry *)((char *)al_d->entries + offset));
+
+ if (offset < al_d->entries_size) {
+ memmove(new_entry + ent_size, new_entry, al_d->entries_size - offset - ent_size);
}
+ new_entry->size = size;
+ new_entry->item_dtor = item_dtor;
+
+ memcpy(new_entry->obj, obj, size);
+
+out:
#ifdef ENABLE_THREADS
- if (!mutex_locked) {
- if (mbfl_mutex_lock(al_d->mutex) != 0) {
- return -1;
- }
- mutex_locked = 1;
+ if (mutex_locked && mbfl_mutex_unlock(al_d->mutex) != 0) {
+ return -1;
}
#endif
+ return err;
+}
- new_entry = ((mbfl_arraylist_entry *)((char *)al_d->entries + al_d->entries_size));
+static int _mbfl_arraylist_update_item_at(mbfl_arraylist *al_d, void *obj, unsigned int size, mbfl_collection_item_dtor_func item_dtor, int idx)
+{
+ int err = 0;
+ unsigned int offset;
+ unsigned int ent_size;
+ mbfl_arraylist_entry *entry_updated;
+ int mutex_locked = 0;
- new_entry->size = size;
- new_entry->item_dtor = item_dtor;
+ assert(al_d != NULL);
+#ifdef ENABLE_THREADS
+ assert(al_d->mutex != NULL);
+#endif
- memcpy(new_entry->obj, obj, size);
+ if (idx < 0) {
+ err = 1;
+ goto out;
+ }
+
+#ifdef ENABLE_THREADS
+ if (mbfl_mutex_lock(al_d->mutex) != 0) {
+ err = -1;
+ goto out;
+ }
+#endif
+ mutex_locked = 1;
+
+ _mbfl_arraylist_prepare_space(al_d, size, (idx >= al_d->_super._super.num_items ? idx + 1: al_d->_super._super.num_items));
+
+ ent_size = MBFL_AL_ENT_SIZE(al_d->max_obj_size);
+ offset = ent_size * idx;
- al_d->entries_size += ent_size;
- al_d->_super._super.num_items++;
+ entry_updated = ((mbfl_arraylist_entry *)((char *)al_d->entries + offset));
+ entry_updated->size = size;
+ entry_updated->item_dtor = item_dtor;
+ memcpy(entry_updated->obj, obj, size);
out:
#ifdef ENABLE_THREADS
1.2 +1 -0 libmbfl/mbfl/mbfl_list.c
Index: mbfl_list.c
===================================================================
RCS file: /cvsroot/php-i18n/libmbfl/mbfl/mbfl_list.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- mbfl_list.c 29 Dec 2002 06:41:49 -0000 1.1
+++ mbfl_list.c 30 Dec 2002 19:02:12 -0000 1.2
@@ -26,6 +26,7 @@
}
listd->insert_item_at_op = NULL;
+ listd->update_item_at_op = NULL;
listd->get_item_at_op = NULL;
listd->index_of_op = NULL;
listd->_super.add_item_op = (mbfl_collection_add_item_func)_mbfl_list_add_item;
1.2 +2 -1 libmbfl/mbfl/mbfl_arraylist.h
Index: mbfl_arraylist.h
===================================================================
RCS file: /cvsroot/php-i18n/libmbfl/mbfl/mbfl_arraylist.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- mbfl_arraylist.h 29 Dec 2002 06:41:49 -0000 1.1
+++ mbfl_arraylist.h 30 Dec 2002 19:02:12 -0000 1.2
@@ -23,7 +23,8 @@
#define mbfl_arraylist_remove(a, b, c) mbfl_list_remove(&((a)->_super),(b), (c))
#define mbfl_arraylist_contains(a, b, c) mbfl_list_contains(&((a)->_super),(b), (c))
#define mbfl_arraylist_create_iter(a) mbfl_list_create_iter(&((a)->_super))
-#define mbfl_arraylist_insert_item_at(a, b, c, d, e) mbfl_list_insert_item(&((a)->_super), (b), (c), (d), (e))
+#define mbfl_arraylist_insert_item_at(a, b, c, d, e) mbfl_list_insert_item_at(&((a)->_super), (b), (c), (d), (e))
+#define mbfl_arraylist_update_item_at(a, b, c, d, e) mbfl_list_update_item_at(&((a)->_super), (b), (c), (d), (e))
#define mbfl_arraylist_get_item_at(a, b, c, d) mbfl_list_get_item_at(&((a)->_super), (b), (c), (d))
#define mbfl_arraylist_remove_item_at(a, b) mbfl_list_remove_item_at(&((a)->_super), (b))
#define mbfl_arraylist_index_of(a, b, c, d) mbfl_list_index_of(&((a)->_super), (b), (c), (d))
1.2 +3 -0 libmbfl/mbfl/mbfl_list.h
Index: mbfl_list.h
===================================================================
RCS file: /cvsroot/php-i18n/libmbfl/mbfl/mbfl_list.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- mbfl_list.h 29 Dec 2002 06:41:49 -0000 1.1
+++ mbfl_list.h 30 Dec 2002 19:02:12 -0000 1.2
@@ -6,6 +6,7 @@
struct _mbfl_list;
typedef int (*mbfl_list_insert_item_at_func)(struct _mbfl_list *, void *, unsigned int, mbfl_collection_item_dtor_func item_dtor, int);
+typedef int (*mbfl_list_update_item_at_func)(struct _mbfl_list *, void *, unsigned int, mbfl_collection_item_dtor_func item_dtor, int);
typedef int (*mbfl_list_remove_item_at_func)(struct _mbfl_list *, int);
typedef int (*mbfl_list_get_item_at_func)(struct _mbfl_list *, void **, unsigned int *, int);
typedef int (*mbfl_list_index_of_func)(struct _mbfl_list *, int *, void *, unsigned int);
@@ -13,6 +14,7 @@
typedef struct _mbfl_list {
mbfl_collection _super;
mbfl_list_insert_item_at_func insert_item_at_op;
+ mbfl_list_update_item_at_func update_item_at_op;
mbfl_list_get_item_at_func get_item_at_op;
mbfl_list_remove_item_at_func remove_item_at_op;
mbfl_list_index_of_func index_of_op;
@@ -23,6 +25,7 @@
#define mbfl_list_contains(a, b, c) mbfl_collection_contains(&((a)->_super),(b), (c))
#define mbfl_list_create_iter(a) mbfl_collection_create_iter(&((a)->_super))
#define mbfl_list_insert_item_at(a, b, c, d, e) (a)->insert_item_at_op((a), (b), (c), (d), (e))
+#define mbfl_list_update_item_at(a, b, c, d, e) (a)->update_item_at_op((a), (b), (c), (d), (e))
#define mbfl_list_get_item_at(a, b, c, d) (a)->get_item_at_op((a), (b), (c), (d))
#define mbfl_list_remove_item_at(a, b) (a)->remove_item_at_op((a), (b))
#define mbfl_list_index_of(a, b, c, d) (a)->index_of_op((a), (b), (c), (d))
1.2 +5 -6 libmbfl/mbfl/mbfl_mutex.c
Index: mbfl_mutex.c
===================================================================
RCS file: /cvsroot/php-i18n/libmbfl/mbfl/mbfl_mutex.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- mbfl_mutex.c 29 Dec 2002 06:41:49 -0000 1.1
+++ mbfl_mutex.c 30 Dec 2002 19:02:12 -0000 1.2
@@ -2,6 +2,8 @@
#include "config.h"
#endif
+#ifdef ENABLE_THREADS
+
#ifdef HAVE_STDDEF_H
#include <stddef.h>
#endif
@@ -14,13 +16,13 @@
#include <unistd.h>
#endif
-#if defined(USE_PTHREAD)
+#if USE_PTHREAD
#if defined(HAVE_PTHREAD)
#include <pthread.h>
#else
#error "pthread is not available"
#endif
-#elif defined(USE_WIN32_NATIVE_THREAD)
+#elif USE_WIN32_NATIVE_THREAD
#if defined(__WIN32__)
#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
@@ -36,8 +38,6 @@
#include "mbfl_allocators.h"
#include "mbfl_mutex.h"
-#ifdef _REENTRANT
-
MBFLAPI mbfl_mutex *mbfl_mutex_new(void)
{
#if defined(USE_PTHREAD)
@@ -112,5 +112,4 @@
mbfl_free(mutex);
}
-#endif /* _REENTRANT */
-
+#endif /* ENABLE_THREADS */