list.c

The Kannel Open Source WAP and SMS gateway works as both an SMS gateway, for implementing keyword b

/* ==================================================================== 
 * The Kannel Software License, Version 1.0 
 * 
 * Copyright (c) 2001-2004 Kannel Group  
 * Copyright (c) 1998-2001 WapIT Ltd.   
 * All rights reserved. 
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met: 
 * 
 * 1. Redistributions of source code must retain the above copyright 
 *    notice, this list of conditions and the following disclaimer. 
 * 
 * 2. Redistributions in binary form must reproduce the above copyright 
 *    notice, this list of conditions and the following disclaimer in 
 *    the documentation and/or other materials provided with the 
 *    distribution. 
 * 
 * 3. The end-user documentation included with the redistribution, 
 *    if any, must include the following acknowledgment: 
 *       "This product includes software developed by the 
 *        Kannel Group (http://www.kannel.org/)." 
 *    Alternately, this acknowledgment may appear in the software itself, 
 *    if and wherever such third-party acknowledgments normally appear. 
 * 
 * 4. The names "Kannel" and "Kannel Group" must not be used to 
 *    endorse or promote products derived from this software without 
 *    prior written permission. For written permission, please  
 *    contact [e-mail]. 
 * 
 * 5. Products derived from this software may not be called "Kannel", 
 *    nor may "Kannel" appear in their name, without prior written 
 *    permission of the Kannel Group. 
 * 
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
 * DISCLAIMED.  IN NO EVENT SHALL THE KANNEL GROUP OR ITS CONTRIBUTORS 
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,  
 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT  
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR  
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,  
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE  
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,  
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 * ==================================================================== 
 * 
 * This software consists of voluntary contributions made by many 
 * individuals on behalf of the Kannel Group.  For more information on  
 * the Kannel Group, please see <http://www.kannel.org/>. 
 * 
 * Portions of this software are based upon software originally written at  
 * WapIT Ltd., Helsinki, Finland for the Kannel project.  
 */ 

/*
 * list.c - generic dynamic list
 *
 * This module implements the generic list. See list.h for an explanation
 * of how to use the list.
 *
 * The list is implemented as an array, a starting index into the array,
 * and an integer giving the length of the list. The list's element i is
 * not necessarily at array element i, but instead it is found at element
 *
 *	(start + i) % len
 *
 * This is because we need to make it fast to use the list as a queue,
 * meaning that adding elements to the end and removing them from the
 * beginning must be very fast. Insertions into the middle of the list
 * need not be fast, however. It would be possible to implement the list
 * with a linked list, of course, but this would cause many more memory
 * allocations: every time an item is added to the list, a new node would
 * need to be allocated, and when it is removed, it would need to be freed.
 * Using an array lets us reduce the number of allocations. It also lets
 * us access an arbitrary element in constant time, which is specially
 * useful since it lets us simplify the list API by not adding iterators
 * or an explicit list item type.
 *
 * If insertions and deletions into the middle of the list become common,
 * it would be more efficient to use a buffer gap implementation, but
 * there's no point in doing that until the need arises.
 *
 * Lars Wirzenius <[e-mail]>
 */

#include "gw-config.h"

#include <string.h>
#include <unistd.h>
#include <stdlib.h>

#include "gwassert.h"
#include "list.h"
#include "log.h"
#include "thread.h"
#include "gwmem.h"


struct List
{
    void **tab;
    long tab_size;
    long start;
    long len;
    Mutex *single_operation_lock;
    Mutex *permanent_lock;
    pthread_cond_t nonempty;
    long num_producers;
};

#define INDEX(list, i)	(((list)->start + i) % (list)->tab_size)
#define GET(list, i)	((list)->tab[INDEX(list, i)])


long gwthread_self(void);

static void lock(List *list);
static void unlock(List *list);
static void make_bigger(List *list, long items);
static void delete_items_from_list(List *list, long pos, long count);


List *list_create_real(void)
{
    List *list;

    list = gw_malloc(sizeof(List));
    list->tab = NULL;
    list->tab_size = 0;
    list->start = 0;
    list->len = 0;
    list->single_operation_lock = mutex_create();
    list->permanent_lock = mutex_create();
    pthread_cond_init(&list->nonempty, NULL);
    list->num_producers = 0;
    return list;
}


void list_destroy(List *list, list_item_destructor_t *destructor)
{
    void *item;

    if (list == NULL)
        return;

    if (destructor != NULL) {
        while ((item = list_extract_first(list)) != NULL)
            destructor(item);
    }

    mutex_destroy(list->permanent_lock);
    mutex_destroy(list->single_operation_lock);
    pthread_cond_destroy(&list->nonempty);
    gw_free(list->tab);
    gw_free(list);
}


long list_len(List *list)
{
    long len;

    if (list == NULL)
        return 0;
    lock(list);
    len = list->len;
    unlock(list);
    return len;
}


void list_append(List *list, void *item)
{
    lock(list);
    make_bigger(list, 1);
    list->tab[INDEX(list, list->len)] = item;
    ++list->len;
    pthread_cond_signal(&list->nonempty);
    unlock(list);
}


void list_append_unique(List *list, void *item, int (*cmp)(void *, void *))
{
    void *it;
    long i;

    lock(list);
    it = NULL;
    for (i = 0; i < list->len; ++i) {
        it = GET(list, i);
        if (cmp(it, item)) {
            break;
        }
    }
    if (i == list->len) {
        /* not yet in list, so add it */
        make_bigger(list, 1);
        list->tab[INDEX(list, list->len)] = item;
        ++list->len;
        pthread_cond_signal(&list->nonempty);
    }
    unlock(list);
}
        

void list_insert(List *list, long pos, void *item)
{
    long i;

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

    make_bigger(list, 1);
    for (i = list->len; i > pos; --i)
        list->tab[(list->start + i) % list->tab_size] =
            list->tab[(list->start + i - 1) % list->tab_size];
    list->tab[(list->start + pos) % list->tab_size] = item;
    ++list->len;
    pthread_cond_signal(&list->nonempty);
    unlock(list);
}


void list_delete(List *list, long pos, long count)
{
    lock(list);
    delete_items_from_list(list, pos, count);
    unlock(list);
}


long list_delete_matching(List *list, void *pat, list_item_matches_t *matches)
{
    long i;
    long count;

    lock(list);

    /* XXX this could be made more efficient by noticing
       consecutive items to be removed, but leave that for later.
       --liw */
    i = 0;
    count = 0;
    while (i < list->len) {
        if (matches(GET(list, i), pat)) {
            delete_items_from_list(list, i, 1);
            count++;
        } else {
            ++i;
        }
    }
    unlock(list);

    return count;
}


long list_delete_equal(List *list, void *item)
{
    long i;
    long count;

    lock(list);

    /* XXX this could be made more efficient by noticing
       consecutive items to be removed, but leave that for later.
       --liw */
    i = 0;
    count = 0;
    while (i < list->len) {
        if (GET(list, i) == item) {
            delete_items_from_list(list, i, 1);
            count++;
        } else {
            ++i;
        }
    }
    unlock(list);

    return count;
}


void *list_get(List *list, long pos)
{
    void *item;

    lock(list);
    gw_assert(pos >= 0);
    gw_assert(pos < list->len);
    item = GET(list, pos);
    unlock(list);
    return item;
}


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

    gw_assert(list != NULL);
    lock(list);
    if (list->len == 0)
        item = NULL;
    else {
        item = GET(list, 0);
        delete_items_from_list(list, 0, 1);
    }
    unlock(list);
    return item;
}


List *list_extract_matching(List *list, void *pat, list_item_matches_t *cmp)
{
    List *new_list;
    long i;

    new_list = list_create();
    lock(list);
    i = 0;