source/fontsubset/list.cxx

/**************************************************************
 *
 * 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.
 *
 *************************************************************/


/*[]---------------------------------------------------[]*/
/*|                                                     |*/
/*|     list.c - bidirectional list class               |*/
/*|                                                     |*/
/*|                                                     |*/
/*|  Author: Alexander Gelfenbain                       |*/
/*[]---------------------------------------------------[]*/

#include <rtl/alloc.h>

#if OSL_DEBUG_LEVEL == 0
#  ifndef NDEBUG
#    define NDEBUG
#  endif
#endif

#include <assert.h>

/* #define TEST */
#include "list.h"

/*- private data types */
typedef struct _lnode {
    struct _lnode *next;
    struct _lnode *prev;

    void *value;

} lnode;

struct _list {
    lnode *head, *tail, *cptr;
    size_t aCount;
    list_destructor eDtor;
};

/*- private methods */

static lnode *newNode(void *el)
{
    lnode *ptr = (lnode*)rtl_allocateMemory(sizeof(lnode));
    assert(ptr != 0);

    ptr->value = el;

    return ptr;
}

static lnode *appendPrim(list pThis, void *el)
{
    lnode *ptr = newNode(el);
    lnode **flink, *blink;

    if (pThis->tail != 0) {
        flink = &(pThis->tail->next);
        blink = pThis->tail;
    } else {
        flink = &pThis->head;
        blink = 0;
        pThis->cptr = ptr;                         /*- list was empty - set current to pThis element */
    }

    *flink  = ptr;
    pThis->tail = ptr;

    ptr->prev = blink;
    ptr->next = 0;

    pThis->aCount++;
    return ptr;
}
#ifdef TEST
static lnode *prependPrim(list pThis, void *el)
{
    lnode *ptr = newNode(el);
    lnode *flink, **blink;

    if (pThis->head != 0) {
        blink = &(pThis->head->prev);
        flink = pThis->head;
    } else {
        blink = &pThis->tail;
        flink = 0;
        pThis->cptr  = ptr;                        /*- list was empty - set current to pThis element */
    }

    *blink = ptr;
    pThis->head   = ptr;

    ptr->next = flink;
    ptr->prev = 0;

    pThis->aCount++;
    return ptr;
}
#endif

/*- public methods  */
list listNewEmpty(void)                           /*- default ctor */
{
    list pThis = (list)rtl_allocateMemory(sizeof(struct _list));
    assert(pThis != 0);

    pThis->aCount = 0;
    pThis->eDtor = 0;
    pThis->head = pThis->tail = pThis->cptr = 0;

    return pThis;
}

#ifdef TEST
list listNewCopy(list l)                          /*- copy ctor */
{
    lnode *ptr, *c;
    list pThis;
    assert(l != 0);

    pThis = rtl_allocateMemory(sizeof(struct _list));
    assert(pThis != 0);

    ptr = l->head;

    pThis->aCount = 0;
    pThis->eDtor = 0;
    pThis->head = pThis->tail = pThis->cptr = 0;

    while (ptr) {
        c = appendPrim(pThis, ptr->value);
        if (ptr == l->cptr) pThis->cptr = c;
        ptr = ptr->next;
    }

    return pThis;
}
#endif

void listDispose(list pThis)                       /*- dtor */
{
    assert(pThis != 0);
    listClear(pThis);
    rtl_freeMemory(pThis);
}

void listSetElementDtor(list pThis, list_destructor f)
{
    assert(pThis != 0);
    pThis->eDtor = f;
}

/* calling this function on an empty list is a run-time error */
void *listCurrent(list pThis)
{
    assert(pThis != 0);
    assert(pThis->cptr != 0);
    return pThis->cptr->value;
}

int   listCount(list pThis)
{
    assert(pThis != 0);
    return pThis->aCount;
}

int   listIsEmpty(list pThis)
{
    assert(pThis != 0);
    return pThis->aCount == 0;
}


#ifdef TEST
int   listAtFirst(list pThis)
{
    assert(pThis != 0);
    return pThis->cptr == pThis->head;
}

int   listAtLast(list pThis)
{
    assert(pThis != 0);
    return pThis->cptr == pThis->tail;
}

int   listPosition(list pThis)
{
    int res = 0;
    lnode *ptr;
    assert(pThis != 0);

    ptr = pThis->head;

    while (ptr != pThis->cptr) {
        ptr = ptr->next;
        res++;
    }

    return res;
}
#endif
int    listFind(list pThis, void *el)
{
    lnode *ptr;
    assert(pThis != 0);

    ptr = pThis->head;

    while (ptr) {
        if (ptr->value == el) {
            pThis->cptr = ptr;
            return 1;
        }
        ptr = ptr->next;
    }

    return 0;
}

int    listNext(list pThis)
{
    return listSkipForward(pThis, 1);
}

int    listSkipForward(list pThis, int n)
{
    int m = 0;
    assert(pThis != 0);

    if (pThis->cptr == 0) return 0;

    while (n != 0) {
        if (pThis->cptr->next == 0) break;
        pThis->cptr = pThis->cptr->next;
        n--;
        m++;
    }
    return m;
}

int    listToFirst(list pThis)
{
    assert(pThis != 0);

    if (pThis->cptr != pThis->head) {
        pThis->cptr = pThis->head;
        return 1;
    }
    return 0;
}

int    listToLast(list pThis)
{
    assert(pThis != 0);

    if (pThis->cptr != pThis->tail) {
        pThis->cptr = pThis->tail;
        return 1;
    }
    return 0;
}

int    listPositionAt(list pThis, int n)                     /*- returns the actual position number */
{
    int m = 0;
    assert(pThis != 0);

    pThis->cptr = pThis->head;
    while (n != 0) {
        if (pThis->cptr->next == 0) break;
        pThis->cptr = pThis->cptr->next;
        n--;
        m++;
    }
    return m;
}

list   listAppend(list pThis, void *el)
{
    assert(pThis != 0);

    appendPrim(pThis, el);
    return pThis;
}
#ifdef TEST
list   listPrepend(list pThis, void *el)
{
    assert(pThis != 0);

    prependPrim(pThis, el);
    return pThis;
}

list   listInsertAfter(list pThis, void *el)
{
    lnode *ptr;
    assert(pThis != 0);

    if (pThis->cptr == 0) return listAppend(pThis, el);

    ptr = newNode(el);

    ptr->prev  = pThis->cptr;
    ptr->next  = pThis->cptr->next;
    pThis->cptr->next = ptr;

    if (ptr->next != 0) {
        ptr->next->prev = ptr;
    } else {
        pThis->tail = ptr;
    }
    pThis->aCount++;
    return pThis;
}

list   listInsertBefore(list pThis, void *el)
{
    lnode *ptr;
    assert(pThis != 0);

    if (pThis->cptr == 0) return listAppend(pThis, el);

    ptr = newNode(el);

    ptr->prev  = pThis->cptr->prev;
    ptr->next  = pThis->cptr;
    pThis->cptr->prev = ptr;

    if (ptr->prev != 0) {
        ptr->prev->next = ptr;
    } else {
        pThis->head = ptr;
    }
    pThis->aCount++;
    return pThis;
}
#endif
list   listRemove(list pThis)
{
    lnode *ptr = 0;
    if (pThis->cptr == 0) return pThis;

    if (pThis->cptr->next != 0) {
        ptr  = pThis->cptr->next;
        pThis->cptr->next->prev = pThis->cptr->prev;
    } else {
        pThis->tail = pThis->cptr->prev;
    }

    if (pThis->cptr->prev != 0) {
        if (ptr == 0) ptr = pThis->cptr->prev;
        pThis->cptr->prev->next = pThis->cptr->next;
    } else {
        pThis->head = pThis->cptr->next;
    }

    if (pThis->eDtor) pThis->eDtor(pThis->cptr->value);        /* call the dtor callback */

    rtl_freeMemory(pThis->cptr);
    pThis->aCount--;
    pThis->cptr = ptr;
    return pThis;
}

list   listClear(list pThis)
{
    lnode *node = pThis->head, *ptr;

    while (node) {
        ptr = node->next;
        if (pThis->eDtor) pThis->eDtor(node->value);           /* call the dtor callback */
        rtl_freeMemory(node);
        pThis->aCount--;
        node = ptr;
    }

    pThis->head = pThis->tail = pThis->cptr = 0;
    assert(pThis->aCount == 0);
    return pThis;
}

#ifdef TEST

void   listForAll(list pThis, void (*f)(void *))
{
    lnode *ptr = pThis->head;
    while (ptr) {
        f(ptr->value);
        ptr = ptr->next;
    }
}


#include <stdio.h>

void printlist(list l)
{
    int saved;
    assert(l != 0);
    saved = listPosition(l);

    printf("[ ");

    if (!listIsEmpty(l)) {
        listToFirst(l);
        do {
            printf("%d ", (int) listCurrent(l));
        } while (listNext(l));
    }

    printf("]\n");

    listPositionAt(l, saved);
}

void printstringlist(list l)
{
    int saved;
    assert(l != 0);
    saved = listPosition(l);

    printf("[ ");

    if (!listIsEmpty(l)) {
        listToFirst(l);
        do {
            printf("'%s' ", (char *) listCurrent(l));
        } while (listNext(l));
    }

    printf("]\n");

    listPositionAt(l, saved);
}

void printstat(list l)
{
    printf("count: %d, position: %d, isEmpty: %d, atFirst: %d, atLast: %d.\n",
           listCount(l), listPosition(l), listIsEmpty(l), listAtFirst(l), listAtLast(l));
}

void allfunc(void *e)
{
    printf("%d ", e);
}

void edtor(void *ptr)
{
    printf("element dtor: 0x%08x\n", ptr);
    rtl_freeMemory(ptr);
}

int main()
{
    list l1, l2;
    char *ptr;
    int i;

    l1 = listNewEmpty();
    printstat(l1);

    listAppend(l1, 1);
    printstat(l1);

    listAppend(l1, 2);
    printstat(l1);

    listAppend(l1, 3);
    printstat(l1);

    printlist(l1);

    listToFirst(l1);
    listInsertBefore(l1, -5);
    printlist(l1);

    l2 = listNewCopy(l1);
    printlist(l2);

    listForAll(l2, allfunc);
    printf("\n");

    listClear(l1);
    listSetElementDtor(l1, edtor);

    for(i=0; i<10; i++) {
        ptr = rtl_allocateMemory(20);
        snprintf(ptr, 20, "element # %d", i);
        listAppend(l1, ptr);
    }

    printstringlist(l1);


    listDispose(l1);
    listDispose(l2);


    return 0;
}
#endif