astrometry.net-0.85/util/bl.c

/*
 # This file is part of the Astrometry.net suite.
 # Licensed under a 3-clause BSD style license - see LICENSE
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <assert.h>

#include "bl.h"

#include "keywords.h"

#include "bl.ph"
#include "log.h"

static bl_node* bl_new_node(bl* list);
static void bl_remove_from_node(bl* list, bl_node* node,
                                bl_node* prev, int index_in_node);

// Defined in bl.ph (private header):
// free_node
// NODE_DATA
// NODE_CHARDATA
// NODE_INTDATA
// NODE_DOUBLEDATA

// Defined in bl.inc (inlined functions):
// bl_size
// bl_access
// il_size
// il_get

// NOTE!, if you make changes here, also see bl-sort.c !

//#define DEFINE_SORT 1
#define DEFINE_SORT 0
#define nl il
#define number int
#define NL_PRINT(x) printf("%i", x)
#include "bl-nl.c"
#undef nl
#undef number
#undef NL_PRINT

#define nl ll
#define number int64_t
#define NL_PRINT(x) printf("%lli", (long long int)x)
#include "bl-nl.c"
#undef nl
#undef number
#undef NL_PRINT

#define nl fl
#define number float
#define NL_PRINT(x) printf("%f", (float)x)
#include "bl-nl.c"
#undef nl
#undef number
#undef NL_PRINT

#define nl dl
#define number double
#define NL_PRINT(x) printf("%g", x)
#include "bl-nl.c"
#undef nl
#undef number
#undef NL_PRINT

#undef DEFINE_SORT
#define DEFINE_SORT 0
#define nl pl
#define number void*
#define NL_PRINT(x) printf("%p", x)
#include "bl-nl.c"
#undef nl
#undef number
#undef NL_PRINT
#undef DEFINE_SORT


Pure int bl_datasize(const bl* list) {
    if (!list)
        return 0;
    return list->datasize;
}


void bl_split(bl* src, bl* dest, size_t split) {
    bl_node* node;
    size_t nskipped;
    size_t ind;
    size_t ntaken = src->N - split;
    node = find_node(src, split, &nskipped);
    ind = split - nskipped;
    if (ind == 0) {
        // this whole node belongs to "dest".
        if (split) {
            // we need to get the previous node...
            bl_node* last = find_node(src, split-1, NULL);
            last->next = NULL;
            src->tail = last;
        } else {
            // we've removed everything from "src".
            src->head = NULL;
            src->tail = NULL;
        }
    } else {
        // create a new node to hold the second half of the items in "node".
        bl_node* newnode = bl_new_node(dest);
        newnode->N = (node->N - ind);
        newnode->next = node->next;
        memcpy(NODE_CHARDATA(newnode),
               NODE_CHARDATA(node) + (ind * src->datasize),
               newnode->N * src->datasize);
        node->N -= (node->N - ind);
        node->next = NULL;
        src->tail = node;
        // to make the code outside this block work...
        node = newnode;
    }

    // append it to "dest".
    if (dest->tail) {
        dest->tail->next = node;
        dest->N += ntaken;
    } else {
        dest->head = node;
        dest->tail = node;
        dest->N += ntaken;
    }

    // adjust "src".
    src->N -= ntaken;
    src->last_access = NULL;
}

void bl_init(bl* list, int blocksize, int datasize) {
    list->head = NULL;
    list->tail = NULL;
    list->N = 0;
    list->blocksize = blocksize;
    list->datasize  = datasize;
    list->last_access = NULL;
    list->last_access_n = 0;
}

bl* bl_new(int blocksize, int datasize) {
    bl* rtn;
    rtn = malloc(sizeof(bl));
    if (!rtn) {
        printf("Couldn't allocate memory for a bl.\n");
        return NULL;
    }
    bl_init(rtn, blocksize, datasize);
    return rtn;
}

void bl_free(bl* list) {
    if (!list) return;
    bl_remove_all(list);
    free(list);
}

void bl_remove_all(bl* list) {
    bl_node *n, *lastnode;
    lastnode = NULL;
    for (n=list->head; n; n=n->next) {
        if (lastnode)
            bl_free_node(lastnode);
        lastnode = n;
    }
    if (lastnode)
        bl_free_node(lastnode);
    list->head = NULL;
    list->tail = NULL;
    list->N = 0;
    list->last_access = NULL;
    list->last_access_n = 0;
}

void bl_remove_all_but_first(bl* list) {
    bl_node *n, *lastnode;
    lastnode = NULL;

    if (list->head) {
        for (n=list->head->next; n; n=n->next) {
            if (lastnode)
                bl_free_node(lastnode);
            lastnode = n;
        }
        if (lastnode)
            bl_free_node(lastnode);
        list->head->next = NULL;
        list->head->N = 0;
        list->tail = list->head;
    } else {
        list->head = NULL;
        list->tail = NULL;
    }
    list->N = 0;
    list->last_access = NULL;
    list->last_access_n = 0;
}

static void bl_remove_from_node(bl* list, bl_node* node,
                                bl_node* prev, int index_in_node) {
    // if we're removing the last element at this node, then
    // remove this node from the linked list.
    if (node->N == 1) {
        // if we're removing the first node...
        if (prev == NULL) {
            list->head = node->next;
            // if it's the first and only node...
            if (list->head == NULL) {
                list->tail = NULL;
            }
        } else {
            // if we're removing the last element from
            // the tail node...
            if (node == list->tail) {
                list->tail = prev;
            }
            prev->next = node->next;
        }
        bl_free_node(node);
    } else {
        int ncopy;
        // just remove this element...
        ncopy = node->N - index_in_node - 1;
        if (ncopy > 0) {
            memmove(NODE_CHARDATA(node) + index_in_node * list->datasize,
                    NODE_CHARDATA(node) + (index_in_node+1) * list->datasize,
                    ncopy * list->datasize);
        }
        node->N--;
    }
    list->N--;
}

void bl_remove_index(bl* list, size_t index) {
    // find the node (and previous node) at which element 'index'
    // can be found.
    bl_node *node, *prev;
    size_t nskipped = 0;
    for (node=list->head, prev=NULL;
         node;
         prev=node, node=node->next) {

        if (index < (nskipped + node->N))
            break;
        nskipped += node->N;
    }
    assert(node);
    bl_remove_from_node(list, node, prev, index-nskipped);
    list->last_access = NULL;
    list->last_access_n = 0;
}

void bl_remove_index_range(bl* list, size_t start, size_t length) {
    // find the node (and previous node) at which element 'start'
    // can be found.
    bl_node *node, *prev;
    size_t nskipped = 0;
    list->last_access = NULL;
    list->last_access_n = 0;
    for (node=list->head, prev=NULL;
         node;
         prev=node, node=node->next) {

        if (start < (nskipped + node->N))
            break;

        nskipped += node->N;
    }

    // begin by removing any indices that are at the end of a block.
    if (start > nskipped) {
        // we're not removing everything at this node.
        size_t istart;
        size_t n;
        istart = start - nskipped;
        if ((istart + length) < node->N) {
            // we're removing a chunk of elements from the middle of this
            // block.  move elements from the end into the removed chunk.
            memmove(NODE_CHARDATA(node) + istart * list->datasize,
                    NODE_CHARDATA(node) + (istart + length) * list->datasize,
                    (node->N - (istart + length)) * list->datasize);
            // we're done!
            node->N -= length;
            list->N -= length;
            return;
        } else {
            // we're removing everything from 'istart' to the end of this
            // block.  just change the "N" values.
            n = (node->N - istart);
            node->N -= n;
            list->N -= n;
            length -= n;
            start += n;
            nskipped = start;
            prev = node;
            node = node->next;
        }
    }

    // remove complete blocks.
    for (;;) {
        size_t n;
        bl_node* todelete;
        if (length == 0 || length < node->N)
            break;
        // we're skipping this whole block.
        n = node->N;
        length -= n;
        start += n;
        list->N -= n;
        nskipped += n;
        todelete = node;
        node = node->next;
        bl_free_node(todelete);
    }
    if (prev)
        prev->next = node;
    else
        list->head = node;

    if (!node)
        list->tail = prev;

    // remove indices from the beginning of the last block.
    // note that we may have removed everything from the tail of the list,
    // no "node" may be null.
    if (node && length>0) {
        //printf("removing %i from end.\n", length);
        memmove(NODE_CHARDATA(node),
                NODE_CHARDATA(node) + length * list->datasize,
                (node->N - length) * list->datasize);
        node->N -= length;
        list->N -= length;
    }
}

static void clear_list(bl* list) {
    list->head = NULL;
    list->tail = NULL;
    list->N = 0;
    list->last_access = NULL;
    list->last_access_n = 0;
}

void bl_append_list(bl* list1, bl* list2) {
    list1->last_access = NULL;
    list1->last_access_n = 0;
    if (list1->datasize != list2->datasize) {
        printf("Error: cannot append bls with different data sizes!\n");
        assert(0);
        exit(0);
    }
    if (list1->blocksize != list2->blocksize) {
        printf("Error: cannot append bls with different block sizes!\n");
        assert(0);
        exit(0);
    }

    // if list1 is empty, then just copy over list2's head and tail.
    if (list1->head == NULL) {
        list1->head = list2->head;
        list1->tail = list2->tail;
        list1->N = list2->N;
        // remove everything from list2 (to avoid sharing nodes)
        clear_list(list2);
        return;
    }

    // if list2 is empty, then do nothing.
    if (list2->head == NULL)
        return;

    // otherwise, append list2's head to list1's tail.
    list1->tail->next = list2->head;
    list1->tail = list2->tail;
    list1->N += list2->N;
    // remove everything from list2 (to avoid sharing nodes)
    clear_list(list2);
}

static bl_node* bl_new_node(bl* list) {
    bl_node* rtn;
    // merge the mallocs for the node and its data into one malloc.
    rtn = malloc(sizeof(bl_node) + list->datasize * list->blocksize);
    if (!rtn) {
        printf("Couldn't allocate memory for a bl node!\n");
        return NULL;
    }
    //rtn->data = (char*)rtn + sizeof(bl_node);
    rtn->N = 0;
    rtn->next = NULL;
    return rtn;
}

static void bl_append_node(bl* list, bl_node* node) {
    node->next = NULL;
    if (!list->head) {
        // first node to be added.
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }
    list->N += node->N;
}

/*
 * Append an item to this bl node.  If this node is full, then create a new
 * node and insert it into the list.
 *
 * Returns the location where the new item was copied.
 */
void* bl_node_append(bl* list, bl_node* node, const void* data) {
    void* dest;
    if (node->N == list->blocksize) {
        // create a new node and insert it after the current node.
        bl_node* newnode;
        newnode = bl_new_node(list);
        newnode->next = node->next;
        node->next = newnode;
        if (list->tail == node)
            list->tail = newnode;
        node = newnode;
    }
    // space remains at this node.  add item.
    dest = NODE_CHARDATA(node) + node->N * list->datasize;
    if (data)
        memcpy(dest, data, list->datasize);
    node->N++;
    list->N++;
    return dest;
}

void* bl_append(bl* list, const void* data) {
    if (!list->tail)
        // empty list; create a new node.
        bl_append_node(list, bl_new_node(list));
    // append the item to the tail.  if the tail node is full, a new tail node may be created.
    return bl_node_append(list, list->tail, data);
}

void* bl_push(bl* list, const void* data) {
    return bl_append(list, data);
}

void bl_pop(bl* list, void* into) {
    assert(list->N > 0);
    bl_get(list, list->N-1, into);
    bl_remove_index(list, list->N-1);
}

void bl_print_structure(bl* list) {
    bl_node* n;
    printf("bl: head %p, tail %p, N %zu\n", list->head, list->tail, list->N);
    for (n=list->head; n; n=n->next) {
        printf("[N=%i] ", n->N);
    }
    printf("\n");
}

void bl_get(bl* list, size_t n, void* dest) {
    assert(list->N > 0);
    char* src = bl_access(list, n);
    memcpy(dest, src, list->datasize);
}

static void bl_find_ind_and_element(bl* list, const void* data,
                                    int (*compare)(const void* v1, const void* v2),
                                    void** presult, ptrdiff_t* pindex) {
    ptrdiff_t lower, upper;
    int cmp = -2;
    void* result;
    lower = -1;
    upper = list->N;
    while (lower < (upper-1)) {
        ptrdiff_t mid;
        mid = (upper + lower) / 2;
        cmp = compare(data, bl_access(list, mid));
        if (cmp >= 0) {
            lower = mid;
        } else {
            upper = mid;
        }
    }
    if (lower == -1 || compare(data, (result = bl_access(list, lower)))) {
        *presult = NULL;
        if (pindex)
            *pindex = -1;
        return;
    }
    *presult = result;
    if (pindex)
        *pindex = lower;
}

/**
 * Finds a node for which the given compare() function
 * returns zero when passed the given 'data' pointer
 * and elements from the list.
 */
void* bl_find(bl* list, const void* data,
              int (*compare)(const void* v1, const void* v2)) {
    void* rtn;
    bl_find_ind_and_element(list, data, compare, &rtn, NULL);
    return rtn;
}

ptrdiff_t bl_find_index(bl* list, const void* data,
                        int (*compare)(const void* v1, const void* v2)) {
    void* val;
    ptrdiff_t ind;
    bl_find_ind_and_element(list, data, compare, &val, &ind);
    return ind;
}

size_t bl_insert_sorted(bl* list, const void* data,
                        int (*compare)(const void* v1, const void* v2)) {
    ptrdiff_t lower, upper;
    lower = -1;
    upper = list->N;
    while (lower < (upper-1)) {
        ptrdiff_t mid;
        int cmp;
        mid = (upper + lower) / 2;
        cmp = compare(data, bl_access(list, mid));
        if (cmp >= 0) {
            lower = mid;
        } else {
            upper = mid;
        }
    }
    bl_insert(list, lower+1, data);
    return lower+1;
}

ptrdiff_t bl_insert_unique_sorted(bl* list, const void* data,
                                  int (*compare)(const void* v1, const void* v2)) {
    // This is just straightforward binary search - really should
    // use the block structure...
    ptrdiff_t lower, upper;
    lower = -1;
    upper = list->N;
    while (lower < (upper-1)) {
        ptrdiff_t mid;
        int cmp;
        mid = (upper + lower) / 2;
        cmp = compare(data, bl_access(list, mid));
        if (cmp >= 0) {
            lower = mid;
        } else {
            upper = mid;
        }
    }

    if (lower >= 0) {
        if (compare(data, bl_access(list, lower)) == 0) {
            return BL_NOT_FOUND;
        }
    }
    bl_insert(list, lower+1, data);
    return lower+1;
}

void bl_set(bl* list, size_t index, const void* data) {
    bl_node* node;
    size_t nskipped;
    void* dataloc;

    node = find_node(list, index, &nskipped);
    dataloc = NODE_CHARDATA(node) + (index - nskipped) * list->datasize;
    memcpy(dataloc, data, list->datasize);
    // update the last_access member...
    list->last_access = node;
    list->last_access_n = nskipped;
}

/**
 * Insert the element "data" into the list, such that its index is "index".
 * All elements that previously had indices "index" and above are moved
 * one position to the right.
 */
void bl_insert(bl* list, size_t index, const void* data) {
    bl_node* node;
    size_t nskipped;

    if (list->N == index) {
        bl_append(list, data);
        return;
    }

    node = find_node(list, index, &nskipped);

    list->last_access = node;
    list->last_access_n = nskipped;

    // if the node is full:
    //   if we're inserting at the end of this node, then create a new node.
    //   else, shift all but the last element, add in this element, and
    //     add the last element to a new node.
    if (node->N == list->blocksize) {
        int localindex, nshift;
        bl_node* next = node->next;
        bl_node* destnode;
        localindex = index - nskipped;

        // if the next node exists and is not full, then insert the overflowing
        // element at the front.  otherwise, create a new node.
        if (next && (next->N < list->blocksize)) {
            // shift the existing elements up by one position...
            memmove(NODE_CHARDATA(next) + list->datasize,
                    NODE_CHARDATA(next),
                    next->N * list->datasize);
            destnode = next;
        } else {
            // create and insert a new node.
            bl_node* newnode = bl_new_node(list);
            newnode->next = next;
            node->next = newnode;
            if (!newnode->next)
                list->tail = newnode;
            destnode = newnode;
        }

        if (localindex == node->N) {
            // the new element becomes the first element in the destination node.
            memcpy(NODE_CHARDATA(destnode), data, list->datasize);
        } else {
            // the last element in this node is added to the destination node.
            memcpy(NODE_CHARDATA(destnode), NODE_CHARDATA(node) + (node->N-1)*list->datasize, list->datasize);
            // shift the end portion of this node up by one...
            nshift = node->N - localindex - 1;
            memmove(NODE_CHARDATA(node) + (localindex+1) * list->datasize,
                    NODE_CHARDATA(node) + localindex * list->datasize,
                    nshift * list->datasize);
            // insert the new element...
            memcpy(NODE_CHARDATA(node) + localindex * list->datasize, data, list->datasize);
        }

        destnode->N++;
        list->N++;

    } else {
        // shift...
        int localindex, nshift;
        localindex = index - nskipped;
        nshift = node->N - localindex;
        memmove(NODE_CHARDATA(node) + (localindex+1) * list->datasize,
                NODE_CHARDATA(node) + localindex * list->datasize,
                nshift * list->datasize);
        // insert...
        memcpy(NODE_CHARDATA(node) + localindex * list->datasize,
               data, list->datasize);
        node->N++;
        list->N++;
    }
}

void* bl_access_const(const bl* list, size_t n) {
    bl_node* node;
    size_t nskipped;
    node = find_node(list, n, &nskipped);
    // grab the element.
    return NODE_CHARDATA(node) + (n - nskipped) * list->datasize;
}

void bl_copy(bl* list, size_t start, size_t length, void* vdest) {
    bl_node* node;
    size_t nskipped;
    char* dest;
    if (length <= 0)
        return;
    node = find_node(list, start, &nskipped);

    // we've found the node containing "start".  keep copying elements and
    // moving down the list until we've copied all "length" elements.
    dest = vdest;
    while (length > 0) {
        size_t take, avail;
        char* src;
        // number of elements we want to take.
        take = length;
        // number of elements available at this node.
        avail = node->N - (start - nskipped);
        if (take > avail)
            take = avail;
        src = NODE_CHARDATA(node) + (start - nskipped) * list->datasize;
        memcpy(dest, src, take * list->datasize);

        dest += take * list->datasize;
        start += take;
        length -= take;
        nskipped += node->N;
        node = node->next;
    }
    // update the last_access member...
    list->last_access = node;
    list->last_access_n = nskipped;
}

int bl_check_consistency(bl* list) {
    bl_node* node;
    size_t N;
    int tailok = 1;
    int nempty = 0;
    int nnull = 0;

    // if one of head or tail is NULL, they had both better be NULL!
    if (!list->head)
        nnull++;
    if (!list->tail)
        nnull++;
    if (nnull == 1) {
        fprintf(stderr, "bl_check_consistency: head is %p, and tail is %p.\n",
                list->head, list->tail);
        return 1;
    }

    N = 0;
    for (node=list->head; node; node=node->next) {
        N += node->N;
        if (!node->N) {
            // this block is empty.
            nempty++;
        }
        // are we at the last node?
        if (!node->next) {
            tailok = (list->tail == node) ? 1 : 0;
        }
    }
    if (!tailok) {
        fprintf(stderr, "bl_check_consistency: tail pointer is wrong.\n");
        return 1;
    }
    if (nempty) {
        fprintf(stderr, "bl_check_consistency: %i empty blocks.\n", nempty);
        return 1;
    }
    if (N != list->N) {
        fprintf(stderr, "bl_check_consistency: list->N is %zu, but sum of blocks is %zu.\n",
                list->N, N);
        return 1;
    }
    return 0;
}

int bl_check_sorted(bl* list,
                    int (*compare)(const void* v1, const void* v2),
                    int isunique) {
    size_t i, N;
    size_t nbad = 0;
    void* v2 = NULL;
    N = bl_size(list);
    if (N)
        v2 = bl_access(list, 0);
    for (i=1; i<N; i++) {
        void* v1;
        int cmp;
        v1 = v2;
        v2 = bl_access(list, i);
        cmp = compare(v1, v2);
        if (isunique) {
            if (cmp >= 0) {
                nbad++;
            }
        } else {
            if (cmp > 0) {
                nbad++;
            }
        }
    }
    if (nbad) {
        fprintf(stderr, "bl_check_sorted: %zu are out of order.\n", nbad);
        return 1;
    }
    return 0;
}

static void memswap(void* v1, void* v2, int len) {
    unsigned char tmp;
    unsigned char* c1 = v1;
    unsigned char* c2 = v2;
    int i;
    for (i=0; i<len; i++) {
        tmp = *c1;
        *c1 = *c2;
        *c2 = tmp;
        c1++;
        c2++;
    }
}

void bl_reverse(bl* list) {
    // reverse each block, and reverse the order of the blocks.
    pl* blocks;
    bl_node* node;
    bl_node* lastnode;
    int i;

    // reverse each block
    blocks = pl_new(256);
    for (node=list->head; node; node=node->next) {
        for (i=0; i<(node->N/2); i++) {
            memswap(NODE_CHARDATA(node) + i * list->datasize,
                    NODE_CHARDATA(node) + (node->N - 1 - i) * list->datasize,
                    list->datasize);
        }
        pl_append(blocks, node);
    }

    // reverse the blocks
    lastnode = NULL;
    for (i=pl_size(blocks)-1; i>=0; i--) {
        node = pl_get(blocks, i);
        if (lastnode)
            lastnode->next = node;
        lastnode = node;
    }
    if (lastnode)
        lastnode->next = NULL;
    pl_free(blocks);

    // swap head and tail
    node = list->head;
    list->head = list->tail;
    list->tail = node;

    list->last_access = NULL;
    list->last_access_n = 0;
}

void* bl_extend(bl* list) {
    return bl_append(list, NULL);
}


// special-case pointer list accessors...
int bl_compare_pointers_ascending(const void* v1, const void* v2) {
    void* p1 = *(void**)v1;
    void* p2 = *(void**)v2;
    if (p1 > p2) return 1;
    else if (p1 < p2) return -1;
    else return 0;
}

void  pl_free_elements(pl* list) {
    size_t i;
    for (i=0; i<pl_size(list); i++) {
        free(pl_get(list, i));
    }
}

size_t pl_insert_sorted(pl* list, const void* data, int (*compare)(const void* v1, const void* v2)) {
    // we don't just call bl_insert_sorted because then we end up passing
    // "void**" rather than "void*" args to the compare function, which
    // violates the principle of least surprise.
    ptrdiff_t lower, upper;
    lower = -1;
    upper = list->N;
    while (lower < (upper-1)) {
        ptrdiff_t mid;
        int cmp;
        mid = (upper + lower) / 2;
        cmp = compare(data, pl_get(list, mid));
        if (cmp >= 0) {
            lower = mid;
        } else {
            upper = mid;
        }
    }
    bl_insert(list, lower+1, &data);
    return lower+1;
}

/*
 void pl_set(pl* list, int index, void* data) {
 int i;
 int nadd = (index+1) - list->N;
 if (nadd > 0) {
 // enlarge the list to hold 'nadd' more entries.
 for (i=0; i<nadd; i++) {
 pl_append(list, NULL);
 }
 }
 bl_set(list, index, &data);
 }
 */

void sl_remove_duplicates(sl* lst) {
    size_t i, j;
    for (i=0; i<sl_size(lst); i++) {
        const char* s1 = sl_get(lst, i);
        for (j=i+1; j<sl_size(lst); j++) {
            const char* s2 = sl_get(lst, j);
            if (strcmp(s1, s2) == 0) {
                sl_remove(lst, j);
                j--;
            }
        }
    }
}

sl* sl_new(int blocksize) {
    pl* lst = pl_new(blocksize);
    assert(lst);
    return lst;
}

void sl_init2(sl* list, int blocksize) {
    pl_init(list, blocksize);
}

void sl_free2(sl* list) {
    size_t i;
    if (!list) return;
    for (i=0; i<sl_size(list); i++)
        free(sl_get(list, i));
    bl_free(list);
}

sl* sl_split(sl* lst, const char* str, const char* sepstring) {
    int seplen;
    const char* s;
    char* next_sep;
    if (!lst)
        lst = sl_new(4);
    seplen = strlen(sepstring);
    s = str;
    while (s && *s) {
        next_sep = strstr(s, sepstring);
        if (!next_sep) {
            sl_append(lst, s);
            break;
        }
        //logverb("Appending: '%.*s'\n", (int)(next_sep - s), s);
        sl_appendf(lst, "%.*s", (int)(next_sep - s), s);
        s = next_sep + seplen;
    }
    return lst;
}

void sl_free_nonrecursive(sl* list) {
    bl_free(list);
}

void sl_append_contents(sl* dest, sl* src) {
    size_t i;
    if (!src)
        return;
    for (i=0; i<sl_size(src); i++) {
        char* str = sl_get(src, i);
        sl_append(dest, str);
    }
}

ptrdiff_t sl_index_of(sl* lst, const char* str) {
    size_t i;
    for (i=0; i<sl_size(lst); i++) {
        char* s = sl_get(lst, i);
        if (strcmp(s, str) == 0)
            return i;
    }
    return BL_NOT_FOUND;
}

ptrdiff_t sl_last_index_of(sl* lst, const char* str) {
    ptrdiff_t i;
    for (i=sl_size(lst)-1; i>=0; i--) {
        char* s = sl_get(lst, i);
        if (strcmp(s, str) == 0)
            return i;
    }
    return BL_NOT_FOUND;
}

// Returns 0 if the string is not in the sl, 1 otherwise.
// (same as sl_index_of(lst, str) > -1)
int sl_contains(sl* lst, const char* str) {
    return (sl_index_of(lst, str) > -1);
}

void sl_reverse(sl* list) {
    bl_reverse(list);
}

char* sl_append(sl* list, const char* data) {
    char* copy;
    if (data) {
        copy = strdup(data);
        assert(copy);
    } else
        copy = NULL;
    pl_append(list, copy);
    return copy;
}

void sl_append_array(sl* list, const char**strings, size_t n) {
    size_t i;
    for (i=0; i<n; i++)
        sl_append(list, strings[i]);
}

void sl_append_nocopy(sl* list, const char* data) {
    pl_append(list, data);
}

char* sl_push(sl* list, const char* data) {
    char* copy = strdup(data);
    pl_push(list, copy);
    return copy;
}

char* sl_pop(sl* list) {
    return pl_pop(list);
}

char* sl_get(sl* list, size_t n) {
    return pl_get(list, n);
}

char* sl_get_const(const sl* list, size_t n) {
    return pl_get_const(list, n);
}

char* sl_set(sl* list, size_t index, const char* value) {
    char* copy;
    assert(index >= 0);
    copy = strdup(value);
    if (index < list->N) {
        // we're replacing an existing value - free it!
        free(sl_get(list, index));
        bl_set(list, index, &copy);
    } else {
        // pad
        size_t i;
        for (i=list->N; i<index; i++)
            sl_append_nocopy(list, NULL);
        sl_append(list, copy);
    }
    return copy;
}

int sl_check_consistency(sl* list) {
    return bl_check_consistency(list);
}

char* sl_insert(sl* list, size_t indx, const char* data) {
    char* copy = strdup(data);
    bl_insert(list, indx, &copy);
    return copy;
}

void sl_insert_nocopy(sl* list, size_t indx, const char* str) {
    bl_insert(list, indx, &str);
}

void sl_remove_from(sl* list, size_t start) {
    sl_remove_index_range(list, start, sl_size(list) - start);
}

ptrdiff_t sl_remove_string(sl* list, const char* string) {
    return pl_remove_value(list, string);
}

char* sl_remove_string_bycaseval(sl* list, const char* string) {
    size_t N = sl_size(list);
    size_t i;
    for (i=0; i<N; i++) {
        char* str = sl_get(list, i);
        if (strcasecmp(str, string) == 0) {
            char* s = sl_get(list, i);
            sl_remove(list, i);
            return s;
        }
    }
    return NULL;
}

ptrdiff_t sl_remove_string_byval(sl* list, const char* string) {
    size_t N = sl_size(list);
    size_t i;
    for (i=0; i<N; i++) {
        char* str = sl_get(list, i);
        if (strcmp(str, string) == 0) {
            sl_remove(list, i);
            return i;
        }
    }
    return BL_NOT_FOUND;
}

void sl_remove_index_range(sl* list, size_t start, size_t length) {
    size_t i;
    assert(list);
    assert(start + length <= list->N);
    assert(start >= 0);
    assert(length >= 0);
    for (i=0; i<length; i++) {
        char* str = sl_get(list, start + i);
        free(str);
    }
    bl_remove_index_range(list, start, length);
}

void sl_remove(sl* list, size_t index) {
    bl_remove_index(list, index);
}

void  sl_remove_all(sl* list) {
    size_t i;
    if (!list) return;
    for (i=0; i<sl_size(list); i++)
        free(pl_get(list, i));
    bl_remove_all(list);
}

void   sl_merge_lists(sl* list1, sl* list2) {
    bl_append_list(list1, list2);
}

void sl_print(sl* list) {
    bl_node* n;
    int i;
    for (n=list->head; n; n=n->next) {
        printf("[\n");
        for (i=0; i<n->N; i++)
            printf("  \"%s\"\n", ((char**)NODE_DATA(n))[i]);
        printf("]\n");
    }
}

static char* sljoin(sl* list, const char* join, int forward) {
    size_t start, end, inc;

    size_t len = 0;
    size_t i, N;
    char* rtn;
    size_t offset;
    size_t JL;

    if (sl_size(list) == 0)
        return strdup("");

    // step through the list forward or backward?
    if (forward) {
        start = 0;
        end = sl_size(list);
        inc = 1;
    } else {
        start = sl_size(list) - 1;
        end = -1;
        inc = -1;
    }

    JL = strlen(join);
    N = sl_size(list);
    for (i=0; i<N; i++)
        len += strlen(sl_get(list, i));
    len += ((N-1) * JL);
    rtn = malloc(len + 1);
    if (!rtn)
        return rtn;
    offset = 0;
    for (i=start; i!=end; i+= inc) {
        char* str = sl_get(list, i);
        size_t L = strlen(str);
        if (i != start) {
            memcpy(rtn + offset, join, JL);
            offset += JL;
        }
        memcpy(rtn + offset, str, L);
        offset += L;
    }
    assert(offset == len);
    rtn[offset] = '\0';
    return rtn;
}

char*  sl_join(sl* list, const char* join) {
    return sljoin(list, join, 1);
}

char*  sl_join_reverse(sl* list, const char* join) {
    return sljoin(list, join, 0);
}

char*  sl_implode(sl* list, const char* join) {
    return sl_join(list, join);
}

char* sl_appendf(sl* list, const char* format, ...) {
    char* str;
    va_list lst;
    va_start(lst, format);
    str = sl_appendvf(list, format, lst);
    va_end(lst);
    return str;
}

char* sl_appendvf(sl* list, const char* format, va_list va) {
    char* str;
    if (vasprintf(&str, format, va) == -1)
        return NULL;
    sl_append_nocopy(list, str);
    return str;
}

char* sl_insert_sortedf(sl* list, const char* format, ...) {
    va_list lst;
    char* str;
    va_start(lst, format);
    if (vasprintf(&str, format, lst) == -1)
        return NULL;
    sl_insert_sorted_nocopy(list, str);
    va_end(lst);
    return str;
}

char* sl_insertf(sl* list, size_t index, const char* format, ...) {
    va_list lst;
    char* str;
    va_start(lst, format);
    if (vasprintf(&str, format, lst) == -1)
        return NULL;
    sl_insert_nocopy(list, index, str);
    va_end(lst);
    return str;
}

int bl_compare_strings_ascending(const void* v1, const void* v2) {
    const char* str1 = v1;
    const char* str2 = v2;
    return strcoll(str1, str2);
}

void sl_insert_sorted_nocopy(sl* list, const char* string) {
    pl_insert_sorted(list, string, bl_compare_strings_ascending);
}

char* sl_insert_sorted(sl* list, const char* string) {
    char* copy = strdup(string);
    pl_insert_sorted(list, copy, bl_compare_strings_ascending);
    return copy;
}

#define InlineDefine InlineDefineC
#include "bl.inc"
#undef InlineDefine