/*
** Copyright (C) 2005-2006 by Carnegie Mellon University.
**
** @OPENSOURCE_HEADER_START@
**
** Use of the SILK system and related source code is subject to the terms
** of the following licenses:
**
** GNU Public License (GPL) Rights pursuant to Version 2, June 1991
** Government Purpose License Rights (GPLR) pursuant to DFARS 252.225-7013
**
** NO WARRANTY
**
** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER
** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY
** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN
** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY
** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT
** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE,
** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE
** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT,
** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY
** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF
** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES.
** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF
** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON
** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE
** DELIVERABLES UNDER THIS LICENSE.
**
** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie
** Mellon University, its trustees, officers, employees, and agents from
** all claims or demands made against them (and any related losses,
** expenses, or attorney's fees) arising out of, or relating to Licensee's
** and/or its sub licensees' negligent use or willful misuse of or
** negligent conduct or willful misconduct regarding the Software,
** facilities, or other rights or assistance granted by Carnegie Mellon
** University under this License, including, but not limited to, any
** claims of product liability, personal injury, death, damage to
** property, or violation of any laws or regulations.
**
** Carnegie Mellon University Software Engineering Institute authored
** documents are sponsored by the U.S. Department of Defense under
** Contract F19628-00-C-0003. Carnegie Mellon University retains
** copyrights in all material produced under this contract. The U.S.
** Government retains a non-exclusive, royalty-free license to publish or
** reproduce these documents, or allow others to do so, for U.S.
** Government purposes only pursuant to the copyright license under the
** contract clause at 252.227.7013.
**
** @OPENSOURCE_HEADER_END@
*/

#include "silk.h"

RCSIDENT("$SiLK: skstringmap.c 4285 2006-07-18 18:03:13Z mthomas $");

#include "utils.h"
#include "skstringmap.h"
#include "sklinkedlist.h"


static sk_stringmap_status_t _skStringMapAllocEntry(
    sk_stringmap_entry_t  **map_entry);

static sk_stringmap_status_t _skStringMapFreeEntry(
    sk_stringmap_entry_t   *map_entry);

static sk_stringmap_status_t _skStringMapCheckValidName(
    sk_stringmap_t         *str_map,
    const char             *name);

static sk_stringmap_status_t _skStringMapParseList(
    sk_link_list_t        **token_list,
    char                  **bad_token,
    const char             *user_string);

static sk_stringmap_status_t _skStringMapExpandRanges(
    sk_link_list_t         *str_map,
    char                  **bad_token,
    char                    range_delimiter);

static sk_stringmap_status_t _skStringMapFindEntry(
    sk_stringmap_entry_t  **map_entry,
    const sk_stringmap_t   *str_map,
    const char             *token);

static sk_stringmap_status_t _skStringMapTokenize(
    sk_link_list_t         *result_list,
    const char             *user_string,
    const char              delimiter);

/*
 * The width of a print buffer needed to represent an integer.  A
 * 64-bit integer fits in 20 digits, plus an additional digit for the
 * NUL.  I added one more on top of that, just to be safe, and in
 * case we want to parse signed numbers in the future.
 */
#define SKSTRING_PRINT_DIGITS 22



/*
 *  _skStringMapAllocEntry(entry)
 *
 *    Allocate memory for a new entry in the StringMap
 *
 *  Arguments
 *
 *    sk_stringmap_entry_t **map_entry - A pointer to be modified to
 *    contain a pointer to the newly allocated entry.
 */
static sk_stringmap_status_t _skStringMapAllocEntry(
    sk_stringmap_entry_t  **map_entry)
{
    assert(map_entry != NULL);

    *map_entry = calloc(1, sizeof(sk_stringmap_entry_t));
    if (*map_entry == NULL) {
        return SKSTRINGMAP_ERR_MEM;
    }

    return SKSTRINGMAP_OK;
}


/* wrapper for _skStringMapFreeEntry() */
static void skStringMapFreeEntry(void *map_entry)
{
    if (map_entry != NULL) {
        (void)_skStringMapFreeEntry(map_entry);
    }
}

/*
 *  _skStringMapFreeEntry
 *
 *    Internal helper function to free a single entry from a StringMap.
 *
 *  Arguments
 *
 *    sk_stringmap_entry_t *map_entry - A pointer to the StringMap
 *    entry to deallocate
 */
static sk_stringmap_status_t _skStringMapFreeEntry(
    sk_stringmap_entry_t   *map_entry)
{
    assert(map_entry);

    /* free char string in entry */
    if (map_entry->name != NULL) {
        free(map_entry->name);
        map_entry->name = NULL;
    }
    /* free entry itself */
    free(map_entry);

    return SKSTRINGMAP_OK;
}


/* Create a new string map */
sk_stringmap_status_t skStringMapCreate(
    sk_stringmap_t        **out_str_map)
{
    sk_link_err_t rv;

    rv = skLinkAllocList(out_str_map, &skStringMapFreeEntry);
    switch (rv) {
      case SKLINK_OK:
        return SKSTRINGMAP_OK;
      case SKLINK_ERR_MEM:
        return SKSTRINGMAP_ERR_MEM;
      case SKLINK_ERR_INPUT:
      default:
        return SKSTRINGMAP_ERR_INPUT;
    }

    return SKSTRINGMAP_ERR_INPUT; /*NOTREACHED*/
}


/* Destroy a string map */
sk_stringmap_status_t skStringMapDestroy(
    sk_stringmap_t         *str_map)
{
    if (SKLINK_OK == skLinkFreeList(str_map)) {
        return SKSTRINGMAP_OK;
    }

    return SKSTRINGMAP_ERR_INPUT;
}


/* add a key to a StringMap */
sk_stringmap_status_t skStringMapAddID(
    sk_stringmap_t         *str_map,
    const char             *name,
    sk_stringmap_id_t       id)
{
    sk_link_err_t rv_list;
    sk_stringmap_status_t rv;
    sk_stringmap_entry_t *map_entry = NULL;
    char *list_owned_name = NULL;

    /* check inputs */
    if (str_map == NULL || name == NULL)
    {
        return SKSTRINGMAP_ERR_INPUT;
    }

    /* check to see if the ID is valid */
    rv = _skStringMapCheckValidName(str_map, name);
    if (rv != SKSTRINGMAP_OK) {
        return rv;
    }

    /* allocate entry */
    rv = _skStringMapAllocEntry(&map_entry);
    if (rv != SKSTRINGMAP_OK) {
        goto ERROR;
    }

    /* duplicate string for our own use */
    list_owned_name = strdup(name);
    if (list_owned_name == NULL) {
        rv = SKSTRINGMAP_ERR_MEM;
        goto ERROR;
    }

    /* set entry values */
    map_entry->name = list_owned_name;
    map_entry->id = id;

    /* add entry to end of list */
    rv_list = skLinkAppendData(str_map, (void *) map_entry);
    if (rv_list != SKLINK_OK) {
        rv = SKSTRINGMAP_ERR_LIST;
        goto ERROR;
    }

    return SKSTRINGMAP_OK;

  ERROR:
    if (map_entry != NULL) {
        rv = _skStringMapFreeEntry(map_entry);
    }

    if (list_owned_name != NULL) {
        free(list_owned_name);
    }
    return rv;
}


/* add multiple keys to a StringMap */
sk_stringmap_status_t skStringMapAddIDArray(
    sk_stringmap_t             *str_map,
    int                         entryc,
    const sk_stringmap_entry_t *entryv)
{
    sk_stringmap_status_t rv;
    int i;

    /* check inputs */
    if (str_map == NULL || entryv == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    if (entryc < 0) {
        /* a null-terminated array; get the element count */
        entryc = 0;
        while (entryv[entryc].name) {
            ++entryc;
        }
    }

    for (i = 0; i < entryc; ++i) {
        rv = skStringMapAddID(str_map, entryv[i].name, entryv[i].id);
        if (rv != SKSTRINGMAP_OK) {
            return rv;
        }
    }

    return SKSTRINGMAP_OK;
}


/* remove a key from a StringMap */
sk_stringmap_status_t skStringMapRemoveByName(
    sk_stringmap_t     *str_map,
    const char         *name)
{
    sk_link_err_t rv_list;
    sk_link_item_t *map_node;
    sk_link_item_t *map_node_next;
    sk_stringmap_entry_t *map_entry;

    /* check inputs */
    if (str_map == NULL || name == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    rv_list = skLinkGetHead(&map_node, str_map);
    switch (rv_list) {
      case SKLINK_OK:
        /* do nothing, normal status */
        break;
      case SKLINK_ERR_INPUT:
        /* list is null */
        /* FALLTHROUGH */
      case SKLINK_ERR_NOT_FOUND:
        /* list is empty */
        return SKSTRINGMAP_ERR_INPUT;
      default:
        /* should never reach this case */
        assert(0);
        return SKSTRINGMAP_ERR_INPUT;
    }

    while (map_node != NULL) {
        rv_list = skLinkGetNext(&map_node_next, map_node);
        switch (rv_list) {
          case SKLINK_OK:
            /* do nothing, normal status */
            break;
          case SKLINK_ERR_INPUT:
            /* should never reach this case */
            return SKSTRINGMAP_ERR_INPUT;
          case SKLINK_ERR_NOT_FOUND:
            /* end of list */
            map_node_next = NULL;
            break;
          default:
            /* should never reach this case */
            assert(0);
            return SKSTRINGMAP_ERR_INPUT;
        }

        rv_list = skLinkGetData((void *) &map_entry, map_node);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_INPUT;
        }

        if (strcmp(map_entry->name, name) == 0) {
            rv_list = skLinkRemoveNode(str_map, map_node);
            switch (rv_list) {
              case SKLINK_OK:
                /* do nothing, normal status */
                break;
              case SKLINK_ERR_INPUT:
                /* should never reach this case */
                return SKSTRINGMAP_ERR_INPUT;
              default:
                /* should never reach this case */
                assert(0);
                return SKSTRINGMAP_ERR_INPUT;
            }
        }

        map_node = map_node_next;
    }

    return SKSTRINGMAP_OK;
}


/* remove all entries have given ID from a StringMap */
sk_stringmap_status_t skStringMapRemoveByID(
    sk_stringmap_t     *str_map,
    sk_stringmap_id_t   id)
{
    sk_link_err_t rv_list;
    sk_link_item_t *map_node;
    sk_link_item_t *map_node_next;
    sk_stringmap_entry_t *map_entry;

    /* check inputs */
    if (str_map == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    rv_list = skLinkGetHead(&map_node, str_map);
    switch (rv_list) {
      case SKLINK_OK:
        /* do nothing, normal status */
        break;
      case SKLINK_ERR_INPUT:
        /* list is null */
        /* FALLTHROUGH */
      case SKLINK_ERR_NOT_FOUND:
        /* list is empty */
        return SKSTRINGMAP_ERR_INPUT;
      default:
        /* should never reach this case */
        assert(0);
        return SKSTRINGMAP_ERR_INPUT;
    }

    while (map_node != NULL) {
        rv_list = skLinkGetNext(&map_node_next, map_node);
        switch (rv_list) {
          case SKLINK_OK:
            /* do nothing, normal status */
            break;
          case SKLINK_ERR_INPUT:
            /* should never reach this case */
            return SKSTRINGMAP_ERR_INPUT;
          case SKLINK_ERR_NOT_FOUND:
            /* end of list */
            map_node_next = NULL;
            break;
          default:
            /* should never reach this case */
            assert(0);
            return SKSTRINGMAP_ERR_INPUT;
        }

        rv_list = skLinkGetData((void *) &map_entry, map_node);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_INPUT;
        }

        if (id == map_entry->id) {
            rv_list = skLinkRemoveNode(str_map, map_node);
            switch (rv_list) {
              case SKLINK_OK:
                /* do nothing, normal status */
                break;
              case SKLINK_ERR_INPUT:
                /* should never reach this case */
                return SKSTRINGMAP_ERR_INPUT;
              default:
                /* should never reach this case */
                assert(0);
                return SKSTRINGMAP_ERR_INPUT;
            }
        }

        map_node = map_node_next;
    }

    return SKSTRINGMAP_OK;
}


/* remove multiple keys from a StringMap */
sk_stringmap_status_t skStringMapRemoveIDArray(
    sk_stringmap_t             *str_map,
    int                         entryc,
    const sk_stringmap_entry_t *entryv)
{
    int i;
    sk_stringmap_status_t rv;

    /* check inputs */
    if (str_map == NULL || entryv == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    for (i = 0; i < entryc; ++i) {
        rv = skStringMapRemoveByName(str_map, entryv[i].name);
        if (rv != SKSTRINGMAP_OK) {
            return rv;
        }
    }

    return SKSTRINGMAP_OK;
}


/*
 *  _skStringMapFindEntry(&found_match, str_map, token_string);
 *
 *    Search in 'str_map' for an entry that matches 'token_string'.
 *    If found, set found_match to that entry and return
 *    SKSTRINGMAP_OK.  If an ambiguous entry is found, return
 *    SKSTRINGMAP_PARSE_AMBIGUOUS and set found_match to one of the
 *    ambiguous entries; if no match, return
 *    SKSTRINGMAP_PARSE_NO_MATCH, and set *found_match to NULL.
 */
static sk_stringmap_status_t _skStringMapFindEntry(
    sk_stringmap_entry_t  **found_match,
    const sk_stringmap_t   *str_map,
    const char             *token_string)
{
    sk_link_err_t rv_list;
    sk_link_item_t *map_node;
    sk_stringmap_entry_t *map_entry;
    size_t len;

    assert(found_match);
    assert(str_map);
    assert(token_string);

    len = strlen(token_string);
    *found_match = NULL;

    /* check the token against each entry in the map */
    for (rv_list = skLinkGetHead(&map_node, str_map);
         rv_list == SKLINK_OK;
         rv_list = skLinkGetNext(&map_node, map_node))
    {
        rv_list = skLinkGetData((void *)&map_entry, map_node);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_LIST;
        }

        if (0 != strncmp(map_entry->name, token_string, len)) {
            /* no match, try next entry in the map */
            continue;
        }

        /* first 'len' chars match.  see if exact match by comparing
         * string lengths */
        if (len == strlen(map_entry->name)) {
            /* exact match; set found_match here and return */
            *found_match = map_entry;
            return SKSTRINGMAP_OK;
        }
        /* else not an exact match. */

        if (isdigit((int)*token_string)) {
            /* partial number match doesn't make sense; try again */
            continue;
        }
        /* else partial match. */

        /* If '*found_match' has not been set, set it to this location
         * as a potential match.  Else if '*found_match' is set,
         * compare the IDs on the current entry and *found_match and
         * if they are different, return 'ambiguous'. */
        if (*found_match == NULL) {
            *found_match = map_entry;
        } else if ((*found_match)->id != map_entry->id) {
            /* The token_string matches two entries with different
             * IDs; return 'ambiguous' */
            return SKSTRINGMAP_PARSE_AMBIGUOUS;
        }
        /* else token matches two entries that map to same ID, so
         * allow it and don't complain. */
    }

    /* did we find a match? */
    if (*found_match == NULL) {
        return SKSTRINGMAP_PARSE_NO_MATCH;
    }

    return SKSTRINGMAP_OK;
}


/* match a single key against a StringMap, filling out_entry with a
 * pointer to the entry. */
sk_stringmap_status_t skStringMapGetEntry(
    sk_stringmap_entry_t  **out_entry,
    const sk_stringmap_t   *str_map,
    const char             *user_string)
{
    sk_stringmap_status_t rv;
    sk_stringmap_entry_t *found_match;

    /* check inputs */
    if (out_entry == NULL || str_map == NULL || user_string == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    rv = _skStringMapFindEntry(&found_match, str_map, user_string);
    if (rv == SKSTRINGMAP_OK) {
        *out_entry = found_match;
    }

    return rv;
}


/* parse a user string for a list of keys, and match those keys
 * againts a StringMap */
sk_stringmap_status_t skStringMapMatch(
    sk_vector_t            *v_result,
    char                  **bad_token,
    const sk_stringmap_t   *str_map,
    const char             *user_string)
{
    sk_stringmap_status_t rv;
    sk_link_err_t rv_list;

    /* for parsing from comma delimited string into list of tokens */
    sk_link_list_t *token_list = NULL;
    sk_link_item_t *token;

    /* for parsing list of tokens into individual names/ids */
    char *token_string;

    /* matching against string map */
    sk_stringmap_entry_t *found_match;

    /* check inputs */
    if (str_map == NULL || v_result == NULL || user_string == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    if (skVectorGetElementSize(v_result) != sizeof(sk_stringmap_entry_t*)) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    /* convert the user's input into a linked list of tokens */
    rv = _skStringMapParseList(&token_list, bad_token, user_string);
    if (rv != SKSTRINGMAP_OK) {
        return rv;
    }

    /* loop over the tokens we got from the user's input */
    for (rv_list = skLinkGetHead(&token, token_list);
         rv_list == SKLINK_OK;
         rv_list = skLinkGetNext(&token, token))
    {
        rv_list = skLinkGetData((void *)&token_string, token);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_LIST;
        }

        /* check the token against each entry in the map */
        rv = _skStringMapFindEntry(&found_match, str_map, token_string);
        switch (rv) {
          case SKSTRINGMAP_OK:
            /* found a single match; add it to vector */
            if (0 != skVectorAppendValue(v_result, &found_match)) {
                rv = SKSTRINGMAP_ERR_MEM;
                goto END;
            }
            break;

          case SKSTRINGMAP_PARSE_AMBIGUOUS:
          case SKSTRINGMAP_PARSE_NO_MATCH:
            if (bad_token != NULL) {
                /* let the user know where things failed. */
                *bad_token = strdup(token_string);
            }
            goto END;

          default:
            /* bad news */
            goto END;
        }

    } /* outer for-loop over tokens  */

    /* success */
    rv = SKSTRINGMAP_OK;

  END:
    if (token_list != NULL) {
        /* ignoring return value, since we are in shutdown anyway */
        skLinkFreeList(token_list);
    }

    return rv;
}


/* add to a list the string names which map to a particular value */
sk_stringmap_status_t skStringMapGetNames(
    sk_vector_t            *out_vec,
    const sk_stringmap_t   *str_map,
    sk_stringmap_id_t       id)
{
    sk_link_err_t rv_list;
    sk_link_item_t *map_node;
    sk_stringmap_entry_t *map_entry;

    /* check inputs */
    if (out_vec == NULL || str_map == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }
    if (skVectorGetElementSize(out_vec) != sizeof(sk_stringmap_entry_t*)) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    for (rv_list = skLinkGetHead(&map_node, str_map);
         rv_list == SKLINK_OK;
         rv_list = skLinkGetNext(&map_node, map_node))
    {
        /* get data for current node */
        rv_list = skLinkGetData((void *)&map_entry, map_node);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_LIST;
        }

        /* add name if the id matches */
        if (map_entry->id == id) {
            if (0 != skVectorAppendValue(out_vec, &map_entry)) {
                return SKSTRINGMAP_ERR_MEM;
            }
        }
    }

    return SKSTRINGMAP_OK; /* NOTREACHED */
}


/*
 * Helper functions
 */

/* print the StringMap to an output stream in human-readable form */
sk_stringmap_status_t skStringMapPrintMap(
    FILE                   *outstream,
    const sk_stringmap_t   *str_map)
{
    sk_link_err_t rv_list;
    sk_link_item_t *map_node;
    sk_stringmap_entry_t *map_entry;
    int first_entry_skip_comma = 1;

    if (str_map == NULL || outstream == NULL) {
        return SKSTRINGMAP_ERR_INPUT;
    }

    fprintf(outstream, "{");
    for (rv_list = skLinkGetHead(&map_node, str_map);
         rv_list == SKLINK_OK;
         rv_list = skLinkGetNext(&map_node, map_node))
    {
        rv_list = skLinkGetData((void *) &map_entry, map_node);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_LIST;
        }

        if (!first_entry_skip_comma) {
            fprintf(outstream, ", ");
        } else {
            first_entry_skip_comma = 0;
        }

        fprintf(outstream, " \"%s\" : %u", map_entry->name, map_entry->id);
    }
    fprintf(outstream, " }");

    return SKSTRINGMAP_OK;
}


/*
 *  _skStringMapCheckValidName(name, map);
 *
 *    Parse a key to be inserted into a StringMap to determine if it is
 *    legal or not.  Assumes arguments are non-NULL.
 *
 *  Arguments
 *
 *   const char *name - the key to check
 *
 *   sk_stringmap_t *str_map - the StringMap against whose contents the
 *   string key should be validated
 *
 * Return Values
 *
 *   if name is the empty string, returns
 *   SKSTRINGMAP_ZERO_LENGTH_ENTRY
 *
 *   if name starts with a number, but does not contain all numeric
 *   characters (e.g., "34yh"), returns
 *   SKSTRINGMAP_ERR_NUMERIC_START_ENTRY
 *
 *   if name does not start with a alpha-numeric, return
 *   SKSTRINGMAP_ERR_ALPHANUM_START_ENTRY
 *
 *   if name already exists in the StringMap, returns
 *   SKSTRINGMAP_DUPLICATE_ENTRY
 *
 */
static sk_stringmap_status_t _skStringMapCheckValidName(
    sk_stringmap_t         *str_map,
    const char             *name)
{
    sk_link_err_t rv_list;
    sk_link_item_t *map_node;
    sk_stringmap_entry_t *map_entry;
    size_t i;

    assert(name != NULL);
    assert(str_map != NULL);

    if (name[0] == '\0') {
        return SKSTRINGMAP_ERR_ZERO_LENGTH_ENTRY;
    }

    if (isdigit((int)name[0])) {
        /* if the first character is a digit, they ALL have to be digits */
        for (i = strlen(name) - 1; i > 0; --i) {
            if ( !isdigit((int)name[i])) {
                return SKSTRINGMAP_ERR_NUMERIC_START_ENTRY;
            }
        }
    } else if (!isalpha((int)name[0])) {
        return SKSTRINGMAP_ERR_ALPHANUM_START_ENTRY;
    }

    for (rv_list = skLinkGetHead(&map_node, str_map);
         rv_list == SKLINK_OK;
         rv_list = skLinkGetNext(&map_node, map_node))
    {
        rv_list = skLinkGetData((void**)&map_entry, map_node);
        if (rv_list != SKLINK_OK) {
            return SKSTRINGMAP_ERR_LIST;
        }
        if (0 == strcmp(map_entry->name, name)) {
            return SKSTRINGMAP_ERR_DUPLICATE_ENTRY;
        }
    }

    return SKSTRINGMAP_OK;
}


/*
 *  status = _skStringMapParseList(&token_list, user_string);
 *
 *    Parse the user_string into a list of tokens, then do
 *    number-range expansion on each token.  Put the resulting tokens
 *    into the linked list pointed at by 'token_list'.
 */
static sk_stringmap_status_t _skStringMapParseList(
    sk_link_list_t        **token_list,
    char                  **bad_token,
    const char             *user_string)
{
    sk_stringmap_status_t rv;
    sk_link_err_t rv_list;

    assert(token_list);
    assert(user_string);

    /* tokenize input using comma as a delimiter.  each entry in the
     * list will be a string name, a string id, or a string range of
     * ids. */

    /* create list of comma-delimited tokens */
    rv_list = skLinkAllocList(token_list, skLinkGenericDeallocator);
    if (rv_list != SKLINK_OK) {
        rv = SKSTRINGMAP_ERR_MEM;
        goto END;
    }

    rv = _skStringMapTokenize(*token_list, user_string, ',');
    if (rv != SKSTRINGMAP_OK) {
        goto END;
    }

    /* parse tokens representing ranges into individual numbers */
    rv = _skStringMapExpandRanges(*token_list, bad_token, '-');
    if (rv != SKSTRINGMAP_OK) {
        goto END;
    }

  END:
    if (rv != SKSTRINGMAP_OK) {
        if (*token_list != NULL) {
            skLinkFreeList(*token_list);
            *token_list = NULL;
        }
    }

    return rv;
}


/*
 * _skStringExpandRanges
 *
 * Takes a sklinkedlist, where each data pointer points at a string.
 * Goes through the list and expands any entries which match an
 * unsigned integer range (e.g., "2-5" or "7-30") and removes it.  In
 * its place, it inserts multiple string entries for each integer in
 * the range (e.g., "2-5" becomes four nodes, "2" "3" "4" "5")
 *
 * Arguments
 *
 *   sk_link_list_t *str_map - a pointer to the list whose ranges are to
 *   be expanded.
 *
 *   char range_delimiter - the character used to delimit a range of
 *   values.  Traditionally, this character is a hyphen (e.g., "4-5").
 */
static sk_stringmap_status_t _skStringMapExpandRanges(
    sk_link_list_t     *str_map,
    char              **bad_token,
    char                range_delimiter)
{
    sk_stringmap_status_t rv;
    sk_link_err_t rv_list;

    sk_link_item_t *map_node;
    sk_link_item_t *map_node_next;
    char *string = NULL;
    char *hyphen;

    int rv_int;
    uint32_t start_number;
    uint32_t end_number;

    uint32_t i;

    int chars_printed;
    char print_buffer[SKSTRING_PRINT_DIGITS];
    char *final_buffer;

    rv_list = skLinkGetHead(&map_node, str_map);
    if (rv_list != SKLINK_OK) {
        if (rv_list == SKLINK_ERR_NOT_FOUND) {
            map_node = NULL;
        } else {
            /* should never reach here */
            assert(0);
            return SKSTRINGMAP_ERR_INPUT;
        }
    }

    while (map_node != NULL) {
        rv_list = skLinkGetNext(&map_node_next, map_node);
        if (rv_list != SKLINK_OK) {
            if (rv_list == SKLINK_ERR_NOT_FOUND) {
                map_node_next = NULL;
            } else {
                /* should never reach here */
                assert(0);
                return SKSTRINGMAP_ERR_INPUT;
            }
        }

        rv_list = skLinkGetData((void *) &string, map_node);
        if ((rv_list != SKLINK_OK) || (string == NULL)) {
            return SKSTRINGMAP_ERR_PARSER;
        }

        /* Don't treat the delimiter specially unless this token is a
         * number or the token begins with the delimiter character. */
        if (!isdigit((int)string[0]) && string[0] != range_delimiter) {
            map_node = map_node_next;
            continue;
        }

        /*
        ** find range delimiter in string.  if it exists, then
        ** something looks like a range and we try to parse the
        ** numbers on either side to get the starting and ending
        ** points of the range.  if they don't parse, return an error.
        */

        hyphen = strchr(string, range_delimiter);
        if (hyphen != NULL) {

            /*
            ** parse the start number (we should have cruft after the
            ** range parsing, namely, the hyphen
            */
            rv_int = skStringParseUint32(&start_number, string, 0, 0);
            /* rv_int shouldn't be zero, because of the hyphen */
            if (rv_int <= 0) {
                rv = SKSTRINGMAP_PARSE_UNPARSABLE;
                goto END;
            }

            /*
            ** this check handles the case where there is a number,
            ** followed by some cruft, followed by the hyphen (e.g.,
            ** "4jg-6" should be unparsable, not parsed as "4-6"
            */
            if (string + rv_int - 1 != hyphen) {
                rv = SKSTRINGMAP_PARSE_UNPARSABLE;
                goto END;
            }

            /* parse the end number */
            rv_int = skStringParseUint32(&end_number, hyphen + 1, 0, 0);
            if (rv_int < 0) {
                rv = SKSTRINGMAP_PARSE_UNPARSABLE;
                goto END;
            }

            /*
            ** this check handles the case where there is cruft after
            ** the second number. (e.g. "4-6g")
            */
            if (rv_int > 0) {
                rv = SKSTRINGMAP_PARSE_UNPARSABLE;
                goto END;
            }

            /* not a valid range */
            if (end_number < start_number) {
                rv = SKSTRINGMAP_PARSE_UNPARSABLE;
                goto END;
            }

            /*
            ** add entries for each number in the range
            */
            for (i = start_number; i <= end_number; ++i) {
                chars_printed =
                    snprintf(print_buffer, SKSTRING_PRINT_DIGITS, "%u", i);

                /* we should never run out of buffer space.  if we
                   do, the buffer should be enlarged. */
                assert(chars_printed < SKSTRING_PRINT_DIGITS);

                final_buffer = (char *) malloc(chars_printed + 1);
                if (final_buffer == NULL) {
                    rv = SKSTRINGMAP_ERR_MEM;
                    goto END;
                }
                memcpy(final_buffer, print_buffer, chars_printed + 1);

                rv_list = skLinkInsertPrev(str_map, map_node,
                                           (void *) final_buffer);
                switch (rv_list) {
                  case SKLINK_OK:
                    break;

                  case SKLINK_ERR_MEM:
                    rv = SKSTRINGMAP_ERR_MEM;
                    goto END;

                  case SKLINK_ERR_INPUT:
                    rv = SKSTRINGMAP_ERR_PARSER;
                    goto END;

                  default:
                    /* we should never reach this case */
                    assert(0);
                    return SKSTRINGMAP_ERR_INPUT;
                }
            }

            /*
            ** remove item containing the range and continue
            */
            rv_list = skLinkRemoveNode(str_map, map_node);

            switch (rv_list) {
              case SKLINK_OK:
                break;

              case SKLINK_ERR_INPUT:
                return SKSTRINGMAP_ERR_PARSER;

              default:
                /* we should never reach this case */
                assert(0);
                return SKSTRINGMAP_ERR_INPUT;
            }

        }

        map_node = map_node_next;
    }

    rv = SKSTRINGMAP_OK;

  END:
    if (rv != SKSTRINGMAP_OK) {
        if ((bad_token != NULL) && (string != NULL)) {
            *bad_token = strdup(string);
        }
    }

    return rv;
}


/*
 * skStringMapTokenize
 *
 * Take a string and tokenize it based on a particular delimiter.
 * Each token string is duplicated and stored in a linked list.  The
 * original string is not modified in any way.
 *
 * Arguments
 *
 *   sk_link_list_t *result_list - pointer to the result list to which
 *   to add the token string entries
 *
 *   const char *user_string - the string to tokenize
 *
 *   const char delimiter - the character to use as the delimiter
 */
static sk_stringmap_status_t _skStringMapTokenize(
    sk_link_list_t     *result_list,
    const char         *user_string,
    const char          delimiter)
{
    sk_stringmap_status_t rv;
    sk_link_err_t rv_list;
    char *token;
    const char *cp;
    const char *ep;
    size_t len;

    /* check inputs */
    assert(result_list != NULL);
    assert(user_string != NULL);

    /* loop through string, tokenizing as we go */
    cp = user_string;
    while (*cp) {
        ep = strchr(cp, (int)delimiter);
        if (ep == NULL) {
            /* at end of string; get its length and put 'ep' on the
             * final \0. */
            len = strlen(cp);
            ep = cp + len;
        } else if (ep == cp) {
            /* double delimiter; ignore */
            ++cp;
            continue;
        } else {
            /* found a token; get its length and move 'ep' to start of
             * next token. */
            len = ep - cp;
            ++ep;
        }

        /* copy the token; add 1 for the \0. */
        token = malloc((1 + len) * sizeof(char));
        if (token == NULL) {
            rv = SKSTRINGMAP_ERR_MEM;
            goto END;
        }
        strncpy(token, cp, len);
        token[len] = '\0';
        cp = ep;

        /* add to list */
        rv_list = skLinkAppendData(result_list, (void*)token);
        if (rv_list != SKLINK_OK) {
            rv = SKSTRINGMAP_ERR_MEM;
            goto END;
        }
    }

    rv = SKSTRINGMAP_OK;

  END:
    return rv;
}