list.c

来自「The Kannel Open Source WAP and SMS gatew」· C语言 代码 · 共 652 行 · 第 1/2 页

    while (i < list->len) {
        if (cmp(GET(list, i), pat)) {
            list_append(new_list, GET(list, i));
            delete_items_from_list(list, i, 1);
        } else
            ++i;
    }
    unlock(list);

    if (list_len(new_list) == 0) {
        list_destroy(new_list, NULL);
        return NULL;
    }
    return new_list;
}


void list_lock(List *list)
{
    gw_assert(list != NULL);
    mutex_lock(list->permanent_lock);
}


void list_unlock(List *list)
{
    gw_assert(list != NULL);
    mutex_unlock(list->permanent_lock);
}


int list_wait_until_nonempty(List *list)
{
    int ret;

    lock(list);
    while (list->len == 0 && list->num_producers > 0) {
        list->single_operation_lock->owner = -1;
        pthread_cond_wait(&list->nonempty,
                          &list->single_operation_lock->mutex);
        list->single_operation_lock->owner = gwthread_self();
    }
    if (list->len > 0)
        ret = 1;
    else
        ret = -1;
    unlock(list);
    return ret;
}


void list_add_producer(List *list)
{
    lock(list);
    ++list->num_producers;
    unlock(list);
}


int list_producer_count(List *list)
{
    int ret;
    lock(list);
    ret = list->num_producers;
    unlock(list);
    return ret;
}


void list_remove_producer(List *list)
{
    lock(list);
    gw_assert(list->num_producers > 0);
    --list->num_producers;
    pthread_cond_broadcast(&list->nonempty);
    unlock(list);
}


void list_produce(List *list, void *item)
{
    list_append(list, item);
}


void *list_consume(List *list)
{
    void *item;

    lock(list);
    while (list->len == 0 && list->num_producers > 0) {
        list->single_operation_lock->owner = -1;
        pthread_cond_wait(&list->nonempty,
                          &list->single_operation_lock->mutex);
        list->single_operation_lock->owner = gwthread_self();
    }
    if (list->len > 0) {
        item = GET(list, 0);
        delete_items_from_list(list, 0, 1);
    } else {
        item = NULL;
    }
    unlock(list);
    return item;
}


void *list_search(List *list, void *pattern, int (*cmp)(void *, void *))
{
    void *item;
    long i;

    lock(list);
    item = NULL;
    for (i = 0; i < list->len; ++i) {
        item = GET(list, i);
        if (cmp(item, pattern)) {
            break;
        }
    }
    if (i == list->len) {
        item = NULL;
    }
    unlock(list);

    return item;
}



List *list_search_all(List *list, void *pattern, int (*cmp)(void *, void *))
{
    List *new_list;
    void *item;
    long i;

    new_list = list_create();

    lock(list);
    item = NULL;
    for (i = 0; i < list->len; ++i) {
        item = GET(list, i);
        if (cmp(item, pattern))
            list_append(new_list, item);
    }
    unlock(list);

    if (list_len(new_list) == 0) {
        list_destroy(new_list, NULL);
        new_list = NULL;
    }

    return new_list;
}


void list_sort(List *list, int(*cmp)(const void *, const void *))
{
    gw_assert(list != NULL && cmp != NULL);

    list_lock(list);
    if (list->len == 0) {
        /* nothing to sort */
        list_unlock(list);
        return;
    }
    qsort(&GET(list, 0), list->len, sizeof(void*), cmp);
    list_unlock(list);
}


/*************************************************************************/

static void lock(List *list)
{
    gw_assert(list != NULL);
    mutex_lock(list->single_operation_lock);
}

static void unlock(List *list)
{
    gw_assert(list != NULL);
    mutex_unlock(list->single_operation_lock);
}


/*
 * Make the array bigger. It might be more efficient to make the size
 * bigger than what is explicitly requested.
 *
 * Assume list has been locked for a single operation already.
 */
static void make_bigger(List *list, long items)
{
    long old_size, new_size;
    long len_at_beginning, len_at_end;

    if (list->len + items <= list->tab_size)
        return;

    old_size = list->tab_size;
    new_size = old_size + items;
    list->tab = gw_realloc(list->tab, new_size * sizeof(void *));
    list->tab_size = new_size;

    /*
     * Now, one of the following situations is in effect
     * (* is used, empty is unused element):
     *
     * Case 1: Used area did not wrap. No action is necessary.
     * 
     *			   old_size              new_size
     *			   v                     v
     * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     * | |*|*|*|*|*|*| | | | | | | | | | | | | | | | |
     * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     *   ^           ^
     *   start       start+len
     * 
     * Case 2: Used area wrapped, but the part at the beginning
     * of the array fits into the new area. Action: move part
     * from beginning to new area.
     * 
     *			   old_size              new_size
     *			   v                     v
     * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     * |*|*| | | | | | | |*|*|*| | | | | | | | | | | |
     * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     *     ^             ^
     *     start+len     start
     * 
     * Case 3: Used area wrapped, and the part at the beginning
     * of the array does not fit into the new area. Action: move
     * as much as will fit from beginning to new area and move
     * the rest to the beginning.
     * 
     *				      old_size   new_size
     *					     v   v
     * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     * |*|*|*|*|*|*|*|*|*| | | | | | | | |*|*|*|*| | |
     * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     *		     ^               ^
     *		     start+len       start
     */

    gw_assert(list->start < old_size ||
              (list->start == 0 && old_size == 0));
    if (list->start + list->len > old_size) {
        len_at_end = old_size - list->start;
        len_at_beginning = list->len - len_at_end;
        if (len_at_beginning <= new_size - old_size) {
            /* This is Case 2. */
            memmove(list->tab + old_size,
                    list->tab,
                    len_at_beginning * sizeof(void *));
        } else {
            /* This is Case 3. */
            memmove(list->tab + old_size,
                    list->tab,
                    (new_size - old_size) * sizeof(void *));
            memmove(list->tab,
                    list->tab + (new_size - old_size),
                    (len_at_beginning - (new_size - old_size))
                    * sizeof(void *));
        }
    }
}


/*
 * Remove items `pos' through `pos+count-1' from list. Assume list has
 * been locked by caller already.
 */
static void delete_items_from_list(List *list, long pos, long count)
{
    long i, from, to;

    gw_assert(pos >= 0);
    gw_assert(pos < list->len);
    gw_assert(count >= 0);
    gw_assert(pos + count <= list->len);

    /*
     * There are four cases:
     *
     * Case 1: Deletion at beginning of list. Just move start
     * marker forwards (wrapping it at end of array). No need
     * to move any items.
     *
     * Case 2: Deletion at end of list. Just shorten the length
     * of the list. No need to move any items.
     *
     * Case 3: Deletion in the middle so that the list does not
     * wrap in the array. Move remaining items at end of list
     * to the place of the deletion.
     *
     * Case 4: Deletion in the middle so that the list does indeed
     * wrap in the array. Move as many remaining items at the end
     * of the list as will fit to the end of the array, then move
     * the rest to the beginning of the array.
     */
    if (pos == 0) {
        list->start = (list->start + count) % list->tab_size;
        list->len -= count;
    } else if (pos + count == list->len) {
        list->len -= count;
    } else if (list->start + list->len < list->tab_size) {
        memmove(list->tab + list->start + pos,
                list->tab + list->start + pos + count,
                (list->len - pos - count) * sizeof(void *));
        list->len -= count;
    } else {
        /*
         * This is not specially efficient, but it's simple and
         * works. Faster methods would have to take more special
         * cases into account. 
         */
        for (i = 0; i < list->len - count - pos; ++i) {
            from = INDEX(list, pos + i + count);
            to = INDEX(list, pos + i);
            list->tab[to] = list->tab[from];
        }
        list->len -= count;
    }
}