/* Copyright (C) 2001-2023 Artifex Software, Inc.
   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or
   implied.

   This software is distributed under license and may not be copied,
   modified or distributed except as expressly authorized under the terms
   of the license contained in the file LICENSE in this distribution.

   Refer to licensing information at http://www.artifex.com or contact
   Artifex Software, Inc.,  39 Mesa Street, Suite 108A, San Francisco,
   CA 94129, USA, for further information.
*/


/* pldict.h */
/* Dictionary implementation for PCL parsers */

#include "memory_.h"
#include "gstypes.h"
#include "gsmemory.h"
#include "gsstruct.h"
#include "pldict.h"

/*
 * The current implementation of dictionaries is a simple linked list.  The
 * only concession to efficiency is that we store keys of up to
 * pl_dict_max_short_key characters in the node itself rather than a separately
 * allocated string.
 */
struct pl_dict_entry_s
{
    gs_const_string key;        /* data pointer = 0 if short key */
    void *value;
    pl_dict_entry_t *next;
    pl_dict_entry_t *link;      /* a link to the actual entry (supports aliases). */
    byte short_key[pl_dict_max_short_key];
};

#define entry_key_data(pde)\
  ((pde)->key.size <= pl_dict_max_short_key ? (pde)->short_key : (pde)->key.data)

/* GC descriptors */
public_st_pl_dict();
gs_private_st_composite(st_pl_dict_entry, pl_dict_entry_t, "pl_dict_entry_t",
                        pl_dict_entry_enum_ptrs, pl_dict_entry_reloc_ptrs);
#define pde ((pl_dict_entry_t *)vptr)
static
ENUM_PTRS_BEGIN(pl_dict_entry_enum_ptrs)
return 0;

     /* ENUM_CONST_STRING_PTR(0, pl_dict_entry_t, key); */
ENUM_PTR(1, pl_dict_entry_t, value);
ENUM_PTR(2, pl_dict_entry_t, next);
ENUM_PTR(3, pl_dict_entry_t, link);
     ENUM_PTRS_END static RELOC_PTRS_BEGIN(pl_dict_entry_reloc_ptrs)
{
    /*  RELOC_CONST_STRING_PTR(pl_dict_entry_t, key); */
    RELOC_PTR(pl_dict_entry_t, value);
    RELOC_PTR(pl_dict_entry_t, next);
    RELOC_PTR(pl_dict_entry_t, link);
} RELOC_PTRS_END
#undef pde
/* ---------------- Utilities ---------------- */
/* Provide a standard procedure for freeing a value. */
    static void
pl_dict_value_free(gs_memory_t * mem, void *value, client_name_t cname)
{
    gs_free_object(mem, value, cname);
}

/*
 * Look up an entry in a dictionary.  Return a pointer to the pointer to the
 * entry.
 */
static pl_dict_entry_t **
pl_dict_lookup_entry(pl_dict_t * pdict, const byte * kdata, uint ksize)
{
    pl_dict_entry_t **ppde = &pdict->entries;
    pl_dict_entry_t *pde;

    for (; (pde = *ppde) != 0; ppde = &pde->next) {
        if (pde->key.size == ksize &&
            !memcmp(entry_key_data(pde), kdata, ksize)
            )
            return ppde;
    }
    return 0;
}

/* Delete a dictionary entry. */
static void
pl_dict_free(pl_dict_t * pdict, pl_dict_entry_t ** ppde, client_name_t cname)
{
    pl_dict_entry_t *pde = *ppde;
    gs_memory_t *mem = pdict->memory;

    *ppde = pde->next;
    if (!pde->link)             /* values are not freed for links */
        (*pdict->free_proc) (mem, pde->value, cname);
    if (pde->key.size > pl_dict_max_short_key)
        gs_free_string(mem, (byte *) pde->key.data, pde->key.size, cname);
    gs_free_object(mem, pde, cname);
    pdict->entry_count--;
}

/* ---------------- API procedures ---------------- */

/* Initialize a dictionary. */
void
pl_dict_init(pl_dict_t * pdict, gs_memory_t * mem,
             pl_dict_value_free_proc_t free_proc)
{
    pdict->memory = mem;
    pdict->free_proc = (free_proc ? free_proc : pl_dict_value_free);
    pdict->entries = 0;
    pdict->entry_count = 0;
    pdict->parent = 0;
}

/*
 * Look up an entry in a dictionary, optionally searching the stack, and
 * optionally returning a pointer to the actual dictionary where the
 * entry was found.  Return true, setting *pvalue (and, if ppdict is not
 * NULL, *ppdict), if found.  Note that this is the only routine that
 * searches the stack.
 */
bool
pl_dict_lookup(pl_dict_t * pdict, const byte * kdata, uint ksize,
               void **pvalue, bool with_stack, pl_dict_t ** ppdict)
{
    pl_dict_t *pdcur = pdict;
    pl_dict_entry_t **ppde;

    while ((ppde = pl_dict_lookup_entry(pdcur, kdata, ksize)) == 0) {
        if (!with_stack || (pdcur = pdcur->parent) == 0)
            return false;
    }
    *pvalue = (*ppde)->value;
    if (ppdict)
        *ppdict = pdcur;
    return true;
}

/*
 * make a new dictionary entry.
 */
static int
pl_dict_build_new_entry(pl_dict_t * pdict, const byte * kdata, uint ksize,
                        void *value, pl_dict_entry_t * link)
{                               /* Make a new entry. */
    byte *kstr;
    gs_memory_t *mem = pdict->memory;
    pl_dict_entry_t *pde;

    pde = gs_alloc_struct(mem, pl_dict_entry_t, &st_pl_dict_entry,
                          "pl_dict_put(entry)");
    kstr = (ksize <= pl_dict_max_short_key ? pde->short_key :
            gs_alloc_string(mem, ksize, "pl_dict_put(key)"));
    if (pde == 0 || kstr == 0) {
        if (kstr && kstr != pde->short_key)
            gs_free_string(mem, kstr, ksize, "pl_dict_put(key)");
        gs_free_object(mem, pde, "pl_dict_put(entry)");
        return -1;
    }
    memcpy(kstr, kdata, ksize);
    pde->key.data = (ksize <= pl_dict_max_short_key ? 0 : kstr);
    pde->key.size = ksize;
    pde->link = link;
    pde->value = value;
    pde->next = pdict->entries;
    pdict->entries = pde;
    pdict->entry_count++;
    return 0;
}

/*
 * Add an entry to a dictionary.  Return 1 if it replaces an existing entry.
 * Return -1 if we couldn't allocate memory.  pl_dict_put copies the key
 * string, but takes ownership of the value object (i.e., it will free it
 * when the entry is deleted, using the free_proc).
 */
int
pl_dict_put(pl_dict_t * pdict, const byte * kdata, uint ksize, void *value)
{
    pl_dict_entry_t **ppde = pl_dict_lookup_entry(pdict, kdata, ksize);

    if (!ppde) {
        void *link = 0;
        int code = pl_dict_build_new_entry(pdict, kdata, ksize, value, link);

        if (code < 0)
            (*pdict->free_proc) (pdict->memory, value, "pl_dict_put(new value)");

        return code;
    } else {                    /* Replace the value in an existing entry. */
        pl_dict_entry_t *pde;

        pde = *ppde;
        (*pdict->free_proc) (pdict->memory, pde->value,
                             "pl_dict_put(old value)");
        pde->value = value;
        return 1;
    }
}

/*
 * link entry or alias
 */
int
pl_dict_put_synonym(pl_dict_t * pdict, const byte * old_kdata, uint old_ksize,
                    const byte * new_kdata, uint new_ksize)
{
    pl_dict_entry_t **old_ppde =
        pl_dict_lookup_entry(pdict, old_kdata, old_ksize);
    pl_dict_entry_t *old_pde;
    pl_dict_entry_t **new_ppde =
        pl_dict_lookup_entry(pdict, new_kdata, new_ksize);
    /* old value doesn't exist or new value does exist */
    if (!old_ppde || new_ppde)
        return -1;
    /* find the original data if this is a link to a link */
    old_pde = *old_ppde;
    if (old_pde->link != 0)
        old_pde = old_pde->link;

    return pl_dict_build_new_entry(pdict, new_kdata, new_ksize,
                                   old_pde->value, old_pde);
}

/*
 * Purge alias entries.  A bit tricky but this doesn't fowl the
 * enumeration code since links are always prior to their entries.  We
 * insert at the head of the list and a real entry must be present to
 * insert a link.  Also deleting an entry deletes *all* associated
 * links and deleting a link deletes the corresponding entry.
 */
void
pl_dict_undef_purge_synonyms(pl_dict_t * pdict, const byte * kdata,
                             uint ksize)
{
    pl_dict_entry_t **ppde = &pdict->entries;
    pl_dict_entry_t **pptarget = pl_dict_lookup_entry(pdict, kdata, ksize);
    pl_dict_entry_t *pde;
    pl_dict_entry_t *ptarget;

    if (!pptarget)
        return;
    ptarget = *pptarget;
    /* get the real entry if this is a link. */
    if (ptarget->link)
        ptarget = ptarget->link;
#define dict_get_key_data(entry)  ((entry)->key.size > pl_dict_max_short_key ?\
  (entry)->key.data : (entry)->short_key)
    pl_dict_undef(pdict, dict_get_key_data(ptarget), ptarget->key.size);
    /* delete links to the target */
    pde = *ppde;
    while (pde) {
        pl_dict_entry_t *npde = pde->next;      /* next entry */

        if (pde->link && pde->link == ptarget)
            pl_dict_undef(pdict, dict_get_key_data(pde), pde->key.size);
        pde = npde;
    }
#undef dict_get_key_data
}

/*
 * Remove an entry from a dictionary.  Return true if the entry was present.
 */
bool
pl_dict_undef(pl_dict_t * pdict, const byte * kdata, uint ksize)
{
    pl_dict_entry_t **ppde = pl_dict_lookup_entry(pdict, kdata, ksize);

    if (!ppde)
        return false;
    pl_dict_free(pdict, ppde, "pl_dict_undef");
    return true;
}

/*
 * Return the number of entries in a dictionary.
 */
uint
pl_dict_length(const pl_dict_t * pdict, bool with_stack)
{
    uint count = pdict->entry_count;

    if (with_stack) {
        const pl_dict_t *pdcur;

        for (pdcur = pdict->parent; pdcur != 0; pdcur = pdcur->parent)
            count += pdcur->entry_count;
    }
    return count;
}

/*
 * Enumerate a dictionary with or without its stack.
 * See pldict.h for details.
 */
void
pl_dict_enum_stack_begin(const pl_dict_t * pdict, pl_dict_enum_t * penum,
                         bool with_stack)
{
    penum->pdict = pdict;
    penum->next = 0;
    penum->first = true;
    penum->next_dict = (with_stack ? pdict->parent : 0);
}

bool
pl_dict_enum_next(pl_dict_enum_t * penum, gs_const_string * pkey,
                  void **pvalue)
{
    pl_dict_entry_t *pde;

    while ((pde = (penum->first ? penum->pdict->entries : penum->next)) == 0) {
        if (penum->next_dict == 0)
            return false;
        penum->next_dict = (penum->pdict = penum->next_dict)->parent;
        penum->first = true;
    }
    pkey->data = entry_key_data(pde);
    pkey->size = pde->key.size;
    *pvalue = pde->value;
    penum->next = pde->next;
    penum->first = false;
    return true;
}

/*
 * Release a dictionary by freeing all keys, values, and other storage.
 */
void
pl_dict_release(pl_dict_t * pdict)
{
    while (pdict->entries)
        pl_dict_free(pdict, &pdict->entries, "pl_dict_release");
}