/*****************************************************************************/
/*
                                   dict.c

A hash dictionary (associative array) of key-value pairs.  Both key and value
are commonly strings but actually can be any sized blob.  Keys that begin with
a digit have special meaning to response header processing and so should be
avoided in that type (especially).  Inserting a key that already exists
effectively replaces the previous value - unless - the uniquifier bit :-} is
set, in which case a dictionary-unique integer (followed by a colon) is
prefixed to the key allowing multiple entries having (essentially) the same
key.  As memory allocation can change due to value length increase any
reference to the entry or its value must be re-set.

All keys are pushed to lower-case on insertion, though key lookup is case
insensitive.  Each key has a "type", represented by a specific,
non-alphanumeric character.

  o  $  request processing (server internal)
  o  ~  meta configuration (DICT and SET DICT=..)
  o  >  request header field
  o  <  response header field

(There are others, some currently unused.)  These allow entries that can be
discriminated between quite simply.  For example, iterating through all request
header fields.  Some configuration uses of the dictionary (i.e. the DICT
directive and the mapping SET DICT=.. rule) will accept a key with a leading
non-alpha-numeric that allows a specific type key to be looked up and also
inserted.  This allows the perhaps dangerous changing of server internal,
request processing dictionary entries.  But hey, sysadmins know what they're
doing :-}

A load factor of 10 collision list entries to 1 hash table element
(empirically) seems to be a performance sweet spot so a table size of 32 means
up to some 300 entries will be efficiently handled (and theoretically, a table
of 512 elements would efficiently support 50k entries - though that's not the
design objective for this purpose).  For server request processing purposes the
table size is set at 32 although expected entries would number less than a
couple of dozen (request and response header fields predominating).

A dictionary built using request memory does not need to be explicitly
destroyed when RequestFreeHeap() is deployed.  If the request is just zeroized
then it does need destruction ready for any subsequent request.

With HTTP/1.n and HTTP/2 having fundamentally different header representations
there was a distinct need for an intermediate abstraction from which these both
could be interfaced with the server-internal requirements.  Although the
implementation is quite general purpose, the role of this WASD dictionary is to
act as a repository for request and response header field names and values,
internally used strings (and potentially binary objects), and a new
configuration and request processing (mapping/authorization) abstraction based
on matching key-value pairs.  (And it gave me a chance to play with an
associative array implementation :-)

The implementation is a bog-standard hash array with collision linked-list.  An
associated list allows iteration in order of insertion.  Each associative array
(dictionary) is dynamically allocated, as are entries in those arrays.  As the
entry behaviour seems mostly static after insertion (i.e. values do not change
often if at all) each entry is allocated with space enough for the entry data
structure, key and value.  One allocation per insertion.  Makes value length
increases a little more complex but that's the tradeoff.  Memory is generally
allocated from request heap zones and so disposes of itself when the request
structure is itself disposed of.


VERSION HISTORY
---------------
25-FEB-2018  MGD  'uniqifier' delimiter changed from period to colon
22-DEC-2015  MGD  initial
*/
/*****************************************************************************/

#ifdef WASD_VMS_V7
#undef _VMS__V6__SOURCE
#define _VMS__V6__SOURCE
#undef __VMS_VER
#define __VMS_VER 70000000
#undef __CRTL_VER
#define __CRTL_VER 70000000
#endif

#include <stdio.h>
#include <ctype.h>

#include "wasd.h"

#define WASD_MODULE "DICT"

/******************/
/* global storage */
/******************/

static uint  DictLookupHash,
             DictLookupKlen;

/********************/
/* external storage */
/********************/

extern int  ToLowerCase[],
            ToUpperCase[];

extern char  ErrorSanityCheck [];

extern CONFIG_STRUCT  Config;
extern WATCH_STRUCT  Watch;

/*****************************************************************************/
/*
Create a new dictionary.
*/

DICT_STRUCT* DictCreate
(
REQUEST_STRUCT *rqptr,
int size
)
{
   int  idx;
   DICT_STRUCT  *dicptr;

   /*********/
   /* begin */
   /*********/

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictCreate()");

    if (rqptr)
       dicptr = VmGetHeap (rqptr, sizeof(DICT_STRUCT));
    else
       dicptr = VmGet (sizeof(DICT_STRUCT));
    dicptr->RequestPtr = rqptr;

    if ((int)(dicptr->size = size) <= 0) dicptr->size = DICT_DEFAULT_SIZE;
    if (dicptr->size > 4096)
       ErrorExitVmsStatus (SS$_BUGCHECK, ErrorSanityCheck, FI_LI);
    dicptr->bytes = sizeof(DICT_ENTRY_STRUCT*) * dicptr->size;

    if (rqptr)
       dicptr->table = VmGetHeap (rqptr, dicptr->bytes);
    else
       dicptr->table = VmGet (dicptr->bytes);

    return (dicptr);
} 

/*****************************************************************************/
/*
Delete all dictionary items and then the dictionary itself.
Returns a NULL pointer.
*/

DICT_STRUCT* DictDestroy (DICT_STRUCT *dicptr)

{
   DICT_ENTRY_STRUCT  *denptr, *flink;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictDestroy()");

   for (denptr = dicptr->head; denptr != NULL; denptr = flink)
   {
      flink = denptr->flink;
      if (rqptr)
         VmFreeFromHeap (rqptr, denptr, FI_LI);
      else
         VmFree (denptr, FI_LI);
   }

   if (rqptr)
      VmFreeFromHeap (rqptr, dicptr, FI_LI);
   else
      VmFree (dicptr, FI_LI);

   return (NULL);
} 

/*****************************************************************************/
/*
Return the value of the dirty flag and reset.
*/

uint DictDirty (DICT_STRUCT *dicptr)

{
   uint  dirty;

   /*********/
   /* begin */
   /*********/

   if (dicptr == NULL) return (NULL);

   dirty = dicptr->dirty;
   dicptr->dirty = 0;
   return (dirty);
} 

/*****************************************************************************/
/*
Return a pointer to an exact duplicate of the supplied dictionary.  If the
request pointer is supplied it is duplicated into that request.  This can be
the same request as the dictionary being duplicated or another.  If the
request pointer is NULL then it is duplicated into global memory, and of
course that may be where the original dictionary also resides.  It can be
duplicated in any combination.
*/

DICT_STRUCT* DictDuplicate
(
REQUEST_STRUCT *rqptr,
DICT_STRUCT *dicptr
)
{
   DICT_STRUCT  *duptr;
   DICT_ENTRY_STRUCT  *denptr, *nxtptr;

   /*********/
   /* begin */
   /*********/

   if (dicptr == NULL) return (NULL);

   duptr = DictCreate (rqptr, dicptr->size);
   nxtptr = dicptr->head;
   while ((denptr = nxtptr) != NULL)
   {
      nxtptr = denptr->flink;
      DictInsert (duptr, denptr->type, denptr->key, denptr->klen,
                                       denptr->value, denptr->vlen);
   }
   return (duptr);
} 

/*****************************************************************************/
/*
Expand the specified entry's available value space by the specified quantity,
copying any existing content to the new memory.  As the memory allocation is
likely to change any reference to the entry or its value must be re-set.
*/

DICT_ENTRY_STRUCT* DictExpandEntry
(
DICT_ENTRY_STRUCT *denptr,
uint bytes
)
{
   ulong  hash;
   uchar  *cptr, *sptr, *zptr;
   DICT_STRUCT  *dicptr;
   DICT_ENTRY_STRUCT  *newptr, *tmptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   dicptr = denptr->DictPtr;
   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictExpandEntry()");

   /* this is *additional* value space */
   bytes += denptr->bytes;

   /* plus two terminating nulls and some "elbow-room" */
   if (rqptr)
      newptr = VmGetHeap (rqptr, sizeof(DICT_ENTRY_STRUCT) + bytes + 8);
   else
      newptr = VmGet (sizeof(DICT_ENTRY_STRUCT) + bytes + 8);

   newptr->bytes = bytes;
   newptr->hash = hash = denptr->hash;
   newptr->type[0] = denptr->type[0];
   newptr->DictPtr = denptr->DictPtr;

   /* reproduce the key */
   newptr->klen = denptr->klen;
   zptr = (sptr = newptr->key = newptr->buffer) + newptr->klen;
   for (cptr = denptr->key; sptr < zptr; *sptr++ = *cptr++);

   /* reproduce any value (see DictInsert() "just a little too clever") */
   newptr->value = newptr->buffer + newptr->klen + 1;
   /* if just reserving space (still valid with an expansion) */
   if (denptr->value == NULL)
      newptr->vlen = 0;
   else
   {
      zptr = (sptr = newptr->value) + (newptr->vlen = denptr->vlen);
      for (cptr = denptr->value; sptr < zptr; *sptr++ = *cptr++);
   }

   /* adjust the hash table / collision list */
   if (dicptr->table[hash] == denptr)
      dicptr->table[hash] = newptr;
   else
   {
      for (tmptr = dicptr->table[hash];
           tmptr->clink != denptr;
           tmptr = tmptr->clink);
      tmptr->clink = newptr;
   }
   newptr->clink = denptr->clink;

   /* adjust the ordered list */
   if (dicptr->head == denptr) dicptr->head = newptr;
   if (dicptr->tail == denptr) dicptr->tail = newptr;
   if (denptr->flink != NULL) denptr->flink->blink = newptr;
   if (denptr->blink != NULL) denptr->blink->flink = newptr;
   newptr->flink = denptr->flink;
   newptr->blink = denptr->blink;

   /* if necessary adjust the iterator */
   if (dicptr->next == denptr) dicptr->next = newptr;

   if (rqptr)
      VmFreeFromHeap (rqptr, denptr, FI_LI);
   else
      VmFree (denptr, FI_LI);

   return (newptr);
} 

/*****************************************************************************/
/*
Extract the specified entry from its dictionary.
*/

DICT_ENTRY_STRUCT* DictExtractEntry (DICT_ENTRY_STRUCT *denptr)

{
   uint  hash;
   DICT_STRUCT  *dicptr;
   DICT_ENTRY_STRUCT *tmptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   dicptr = denptr->DictPtr;
   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictExtractEntry()");

   /* extract from the hash table / collision list */
   hash = denptr->hash;
   if (dicptr->table[hash] == denptr)
      dicptr->table[hash] = denptr->clink;
   else
   {
      for (tmptr = dicptr->table[hash];
           tmptr->clink != denptr;
           tmptr = tmptr->clink);
      tmptr->clink = denptr->clink;
   }

   /* remove from the ordered list */
   if (dicptr->head == denptr) dicptr->head = denptr->flink;
   if (dicptr->tail == denptr) dicptr->tail = denptr->blink;
   if (denptr->flink != NULL) denptr->flink->blink = denptr->blink;
   if (denptr->blink != NULL) denptr->blink->flink = denptr->flink;

   /* if necessary adjust the iterator */
   if (dicptr->next == denptr) dicptr->next = denptr->flink;

   dicptr->count--;
   dicptr->bytes -= denptr->bytes;
   dicptr->dirty++;

   /* for detecting any subsequent (re)insertion */
   denptr->extract = dicptr->size;

   return (denptr);
} 

/*****************************************************************************/
/*
Insert the specified key and value into the specified dictionary.  If the key
already exists then that entry will be removed and replaced with this one.  If
the type has the DICT_TYPE_UNIQUE bit set then unique entries are created by
prefixing the key with a number 1..n and period (e.g. "10:example").  Generally
the digits and colon leading the supplied key need to be excised before use.
*/

DICT_ENTRY_STRUCT* DictInsert
(
DICT_STRUCT *dicptr,
uchar *type,
uchar *key,
int klen,
uchar *value,
int vlen
)
{
   static char  type2 [2];
   static char  KeyBuf [256];
   static $DESCRIPTOR (KeyBufDsc, KeyBuf);
   static $DESCRIPTOR (KeyFaoDsc, "!UL:!#AZ");

   BOOL  reuse;
   int  cnt, len;
   ushort  slen;
   ulong  bytes, hash;
   uchar  *cptr, *sptr, *zptr;
   DICT_ENTRY_STRUCT  *denptr, *tmptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER,
                 "DictInsert() !&C !SL !#AZ = !SL !#AZ",
                 type[0], klen, klen, key, vlen, vlen, value);

   /* cannot use an empty key */
   if (klen == 0 || !key[0]) return (NULL);

   if (vlen < 0)
   {
      for (cptr = value; *cptr; cptr++);
      vlen = cptr - value;
   }

   /* buffer a type that's free of any potential "uniquifier bit" */
   type2[0] = type[0] & ~DICT_TYPE_UNIQUE;

   denptr = DictLookup (dicptr, type2, key, klen);

   /* cannot use a silly (buggy?) sized key (allowing for enumeration) */
   if ((klen = DictLookupKlen) > sizeof(KeyBuf)-8) return (NULL);

   /* generated by DictLookup() no need to do it again */
   hash = DictLookupHash;

   if (denptr != NULL)
   {
      /* entry already exists */
      if ((type[0] & DICT_TYPE_UNIQUE) &&
          type2[0] != DICT_TYPE_OPAQUE_KEY)
      {
         /* enumerated (unique) entries */
         sys$fao (&KeyFaoDsc, &slen, &KeyBufDsc, ++dicptr->unique, klen, key);
         KeyBuf[slen] = '\0';
         key = KeyBuf;
         klen = slen;
         /* compute the hash */
         hash = type2[0];
         for (cptr = key; slen--; cptr++) hash = hash * DICT_HASH_MULT + *cptr;
         hash = hash % dicptr->size;
         /* need a fresh one */
         denptr = NULL;
         reuse = false;
      }
      else
      {
         /* can the entry's value buffer be reused */
         if (klen + vlen > denptr->bytes)
         {
            /* won't fit, expand using new value (just a little too clever) */
            denptr->value = value;
            denptr->vlen = vlen;
            denptr = DictExpandEntry (denptr, (klen + vlen) - denptr->bytes);
            return (denptr);
         }
         /* existing entry can contain the new value */
         reuse = true;
      }
   }

   /* if entry did not already exist allocate and initialise a fresh one */
   if (denptr == NULL)
   {
      bytes = klen + vlen;
      /* to (perhaps) improve memory management impose a minimum sized chunk */
      if (bytes < DICT_MIN_BYTES) bytes = DICT_MIN_BYTES;

      /* plus two terminating nulls and some "elbow-room" */
      if (rqptr)
         denptr = VmGetHeap (rqptr, sizeof(DICT_ENTRY_STRUCT) + bytes + 8);
      else
         denptr = VmGet (sizeof(DICT_ENTRY_STRUCT) + bytes + 8);

      denptr->bytes = bytes;
      denptr->hash = hash;
      denptr->type[0] = type2[0];
      denptr->DictPtr = dicptr;

      denptr->klen = klen;
      zptr = (sptr = denptr->key = denptr->buffer) + klen;
      /* push key to lower-case! (no null required in zeroed memory) */
      for (cptr = key; sptr < zptr; *sptr++ = TOLO(*cptr++));
      reuse = false;
   }

   denptr->value = denptr->buffer + denptr->klen + 1;
   /* if the value is NULL then just reserving space */
   if (value == NULL)
      denptr->vlen = 0;
   else
   {
      zptr = (sptr = denptr->value) + (denptr->vlen = vlen);
      for (cptr = value; sptr < zptr; *sptr++ = *cptr++);
      /* in case a shorter value is being overwritten */
      *sptr = '\0';
   }

   if (reuse)
      dicptr->dirty++;
   else
      DictInsertEntry (dicptr, denptr);

   return (denptr);
} 

/*****************************************************************************/
/*
Insert the specified entry into the specified dictionary.
*/

DICT_ENTRY_STRUCT* DictInsertEntry
(
DICT_STRUCT *dicptr,
DICT_ENTRY_STRUCT *denptr
)
{
   int  len;
   ulong  hash;
   uchar  *cptr;
   DICT_ENTRY_STRUCT  *tmptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictInsertEntry()");

   /* if extracted from a(nother) dictionary */
   if (denptr->extract)
   {
      /* check that the memory belongs to the same environment */
      if (dicptr->RequestPtr != denptr->DictPtr->RequestPtr)
         ErrorExitVmsStatus (SS$_BUGCHECK, ErrorSanityCheck, FI_LI);

      /* check if there's an existing entry and remove as required */
      if (tmptr = DictLookup (dicptr, denptr->type, denptr->key, denptr->klen))
         DictRemoveEntry (tmptr);

      /* we've certainly done this! */
      denptr->DictPtr = dicptr;

      if (denptr->extract != dicptr->size);
      {
         /* need to recalculate the hash */
         hash = denptr->type[0];
         len = denptr->klen;
         for (cptr = denptr->key; len--; cptr++)
            hash = hash * DICT_HASH_MULT + *cptr;
         denptr->hash = hash % dicptr->size;
      }

      /* reset the extraction indicator (size of original dictionary) */
      denptr->extract = 0;
   }

   /* insert into the hash table / collision list */
   hash = denptr->hash;
   if (dicptr->table[hash] == NULL)
      dicptr->table[hash] = denptr;
   else
   {
      for (tmptr = dicptr->table[hash];
           tmptr->clink != NULL;
           tmptr = tmptr->clink);
      tmptr->clink = denptr;
   }
   /* in case it's been extracted from another dictionary */
   denptr->clink = NULL;

   /* append to the tail of the ordered list */
   if (dicptr->head == NULL) dicptr->head = denptr;
   if (dicptr->tail != NULL)
   {
      dicptr->tail->flink = denptr;
      denptr->blink = dicptr->tail;
   }
   dicptr->tail = denptr;
   /* in case it's been extracted from another dictionary */
   denptr->flink = NULL;

   dicptr->dirty++;
   dicptr->count++;
   dicptr->bytes += sizeof(DICT_ENTRY_STRUCT) + denptr->bytes;

   return (denptr);
} 

/*****************************************************************************/
/*
Iterate through dictionary entries.  List is ordered first to last insertion. 
Second parameter as NULL resets to head, "*" selects all, "<char>\0" those of
that type, and "<expression>\0" a string match.  Return a pointer to the entry
or NULL on exhaustion or empty dictionary.  On reset the returned pointer
should only be considered informational as to empty or not.
*/

DICT_ENTRY_STRUCT* DictIterate
(
DICT_STRUCT *dicptr,
uchar *which
)
{
   DICT_ENTRY_STRUCT  *denptr;

   /*********/
   /* begin */
   /*********/

   if (which != NULL)
   {
      while ((denptr = dicptr->next) != NULL)
      {
         dicptr->next = denptr->flink;
         if (!which[0] || MATCH2 (which, "*")) break;
         if (which[0] && !which[1])
            if (denptr->type[0] == which[0])
               break;
            else
               continue;
         if (StringMatch (NULL, denptr->key, which)) break;
      }
      return (denptr);
   }

   /* reset to start */
   return (dicptr->next = dicptr->head);
} 

/*****************************************************************************/
/*
Look in the specified dictionary for the specified key.  If key length is -1
then assume key is null-terminated string, otherwise some other opaque blob. 
String key matching is case-insensitive.  Lookup includes the entry type. 
Return a pointer to the dictionary item found or NULL if not.
*/

DICT_ENTRY_STRUCT* DictLookup
(
DICT_STRUCT *dicptr,
uchar *type,
uchar *key,
int klen
)
{
   uint  len;
   ulong  hash;
   uchar  *cptr, *sptr, *zptr;
   DICT_ENTRY_STRUCT  *denptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER,
                 "DictLookup() !&C !SL !#AZ", type[0], klen, klen, key);

   /* cannot use an empty key */
   if (klen == 0 || (klen < 0 && !key[0])) return (NULL);

   /* make the type character part of the hash */
   hash = type[0];
   if (klen < 0)
   {
      for (cptr = key; *cptr; cptr++) hash = hash * DICT_HASH_MULT + *cptr;
      klen = cptr - key;
   }
   else
   {
      len = klen;
      for (cptr = key; len--; cptr++) hash = hash * DICT_HASH_MULT + *cptr;
   }
   hash = hash % dicptr->size;

   /* save these so that they don't need to be generated again */
   DictLookupHash = hash;
   DictLookupKlen = klen;

   zptr = key + klen;
   for (denptr = dicptr->table[hash]; denptr != NULL; denptr = denptr->clink)
   {
      if (denptr->type[0] != type[0]) continue;
      if (denptr->klen != klen) continue;
      cptr = key;
      sptr = denptr->key;
      if (denptr->type[0] == DICT_TYPE_OPAQUE_KEY)
         while (cptr < zptr && *cptr == *sptr) { cptr++; sptr++; }
      else
         /* all keys are pushed to lower-case on insertion */
         while (cptr < zptr && TOLO(*cptr) == *sptr) { cptr++; sptr++; }
      if (cptr == zptr && sptr == denptr->key + denptr->klen) break;
   }

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "denptr:!&X", denptr);

   if (denptr != NULL) return (denptr);

   return (NULL);
} 

/*****************************************************************************/
/*
Delete the specified key from the dictionary.  Returns NULL if the key was not
found or a pointer to the entry if the key was found.  The pointer is
informational and must not subsequently be accessed. 
*/

DICT_ENTRY_STRUCT* DictRemove
(
DICT_STRUCT *dicptr,
uchar *type,
uchar *key,
int klen
)
{
   uint  hash;
   DICT_ENTRY_STRUCT  *denptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER,
                 "DictRemove() !AZ !&Z", type, key);

   if ((denptr = DictLookup (dicptr, type, key, klen)) == NULL) return (NULL);

   DictExtractEntry (denptr);

   if (rqptr)
      VmFreeFromHeap (rqptr, denptr, FI_LI);
   else
      VmFree (denptr, FI_LI);

   return (denptr);
} 

/*****************************************************************************/
/*
Delete the specified entry from the dictionary.  Returns the freed pointer,
which is informational and must not subsequently be accessed. 
*/

DICT_ENTRY_STRUCT* DictRemoveEntry (DICT_ENTRY_STRUCT *denptr)

{
   DICT_STRUCT  *dicptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   dicptr = denptr->DictPtr;
   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictRemoveEntry()");

   DictExtractEntry (denptr);

   if (rqptr)
      VmFreeFromHeap (rqptr, denptr, FI_LI);
   else
      VmFree (denptr, FI_LI);

   return (denptr);
} 

/*****************************************************************************/
/*
Set the value length of the specified entry.  Check the size is within the
storage allocated.  Adjustments to the value string can be made (within
constraints) because it's stored at the trailing end of the buffer space
following the key.
*/

void DictValueLength 
(
DICT_ENTRY_STRUCT *denptr,
uint length
)
{
   DICT_STRUCT  *dicptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   dicptr = denptr->DictPtr;
   rqptr = dicptr->RequestPtr;

   if (WATCHMOD (rqptr, WATCH_MOD__OTHER))
      WatchThis (WATCHITM(rqptr), WATCH_MOD__OTHER, "DictValueSize()");

   if (denptr->klen + length > denptr->bytes)
      ErrorExitVmsStatus (SS$_BUGCHECK, ErrorSanityCheck, FI_LI);

   denptr->vlen = length;
} 

/*****************************************************************************/
/*
WATCH the contents of the dictionary.  If |which| is NULL all entries are
reported.  If |which| is a single character string then it should be an entry
type character and only matching entries are reported. If |which| is a string
beginning and entry type character and followed by a key string then report
only that entry.
*/

void DictWatch
(
DICT_STRUCT *dicptr,
uchar *type,
uchar *which
)
{
   char  *cptr;
   DICT_ENTRY_STRUCT  *denptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   rqptr = dicptr->RequestPtr;

   if (which == NULL || (type == NULL && which[0] == '*'))
   {
      WatchThis (WATCHITM(rqptr), WATCH_INTERNAL,
                 "DICTIONARY size:!UL count:!UL bytes:!UL",
                 dicptr->size, dicptr->count, dicptr->bytes);
      DictWatchEntry (NULL);
   }

   if (which && which[1])
   {
      if (type == NULL) type = DICT_TYPE_INTERNAL;
      denptr = DictLookup (rqptr->rqDictPtr, type, which, -1);
      if (denptr != NULL) DictWatchEntry (denptr);
      return;
   }

   for (denptr = dicptr->head; denptr != NULL; denptr = denptr->flink)
      if (which == NULL || type == NULL || type[0] == denptr->type[0])
         DictWatchEntry (denptr);
} 

/*****************************************************************************/
/*
WATCH the specified entry.  Entry pointer as NULL resets the counter.
*/

void DictWatchEntry (DICT_ENTRY_STRUCT *denptr)

{
   static int  count = 0;

   char  *cptr, *sptr;
   DICT_STRUCT  *dicptr;

   /*********/
   /* begin */
   /*********/

   if (denptr == NULL)
   {
      count = 0;
      return;
   }

   dicptr = denptr->DictPtr;

   if (denptr == dicptr->table[denptr->hash])
      cptr = "[]";
   else
      cptr = "..";

   if (denptr->type[0] == DICT_TYPE_OPAQUE ||
       denptr->type[0] == DICT_TYPE_OPAQUE_KEY)
      WatchDataFormatted ("ENTRY !3ZL !&C!3ZL!&C !&C {!UL}!-!#&H={!UL}!-!#&H\n",
                          ++count, cptr[0], denptr->hash, cptr[1],
                          denptr->type[0], denptr->klen, denptr->key,
                          denptr->vlen, denptr->value);
   else
   {
      if (denptr->vlen && denptr->value[denptr->vlen-1] == '\n')
         sptr = "";
      else
         sptr = "\n";
      WatchDataFormatted ("ENTRY !3ZL !&C!3ZL!&C !&C {!UL}!-!#AZ={!UL}!-!#AZ!AZ",
                          ++count, cptr[0], denptr->hash, cptr[1],
                          denptr->type[0], denptr->klen, denptr->key,
                          denptr->vlen, denptr->value, sptr);
   }
} 

/*****************************************************************************/
/*
Exercise the dictionary functions.  Provide some indicative timings.
fname=<filename> should be a list of words such as found at:
https://raw.githubusercontent.com/first20hours/google-10000-english/master/20k.txt

Some results on an Alpha PWS500 OpenVMS V8.3.

$! 8 hash, 1,000 additions results in a rate of 85k insertions/sec
$ httpd /tests dictionary=size=8,count=10000,fname=20kwords.txt
8< snip 8<
size:8 count:1000 max:0 min:0
total:1000 klen0:62 failures:62 duplicates:53 expands:32 deletions:0 duration:0.011718 85338.797/sec 0.000012/each
table:[0]100 [1]99 [2]123 [3]119 [4]108 [5]109 [6]114 [7]103

$! 16 hash, 1,000 additions results in 102k insertions/sec
$ httpd /tests dictionary=size=16,count=10000,fname=20kwords.txt
8< snip 8<
size:16 count:1000 max:0 min:0
total:1000 klen0:57 failures:57 duplicates:52 expands:49 deletions:0 duration:0.009765 102406.555/sec 0.000010/each
table:[0]57 [1]59 [2]61 [3]55 [4]48 [5]67 [6]51 [7]57 [8]56 [9]52 [10]44 [11]67 [12]51 [13]63 [14]39 [15]51

$! 32 hash, 100 additions, results in 114k insertions/sec
$ httpd /tests dictionary=size=32,count=1000,fname=20kwords.txt
8< snip 8<
size:32 count:1000 max:0 min:0
total:1000 klen0:58 failures:58 duplicates:46 expands:46 deletions:0 duration:0.008788 113785.062/sec 0.000009/each
table:[0]28 [1]37 [2]25 [3]23 [4]30 [5]32 [6]31 [7]23 [8]30 [9]26 [10]28 [11]23 [12]25 [13]29 [14]27 [15]27 [16]28 [17]25 [18]27
[19]34 [20]30 [21]33 [22]19 [23]29 [24]25 [25]29 [26]27 [27]30 [28]22 [29]22 [30]35 [31]28

$! 64 hash, 100 additions, results in 114k insertions/sec
$ httpd /tests dictionary=size=32,count=1000,fname=20kwords.txt
8< snip 8<
size:64 count:1000 max:0 min:0
total:1000 klen0:60 failures:60 duplicates:51 expands:39 deletions:0 duration:0.008788 113785.062/sec 0.000009/each
table:[0]14 [1]12 [2]13 [3]20 [4]17 [5]12 [6]14 [7]12 [8]13 [9]13 [10]16 [11]10 [12]11 [13]20 [14]13 [15]16 [16]14 [17]12 [18]10
[19]14 [20]16 [21]15 [22]16 [23]8 [24]15 [25]9 [26]15 [27]10 [28]11 [29]14 [30]9 [31]11 [32]10 [33]16 [34]9 [35]13 [36]10 [37]15
[38]12 [39]15 [40]5 [41]17 [42]14 [43]13 [44]21 [45]20 [46]18 [47]20 [48]17 [49]12 [50]16 [51]12 [52]10 [53]14 [54]12 [55]14
[56]12 [57]17 [58]15 [59]18 [60]13 [61]17 [62]16 [63]13
*/

#if WATCH_MOD

void DictTest (char *cliptr)

{
#define KEY_SIZE 31
#define KEY_VARY(ran) (ran & 0x1f)
#define VALUE_SIZE 127
#define VALUE_VARY(ran) (ran & 0x7f)

#include <stat.h>
#include <errno.h>

   int  count, deletions, duplicates, expands, failures,
        klen, klen0, max, min, size, status, total, vlen;
#ifdef __VAX
   ulong  random;
#else
   __int64  random;
#endif
   ulong  DeltaTime [2],
          NowTime [2],
          ThenTime [2];
   uchar  ch;
   uchar  *bptr, *cptr, *fname, *sptr, *wptr, *zptr;
   uchar  key [KEY_SIZE+1],
          value [VALUE_SIZE+1];
   float  fsecs;
   stat_t  statbuf;
   FILE  *fptr;
   DICT_STRUCT *dicptr;
   DICT_ENTRY_STRUCT  *denptr;
   REQUEST_STRUCT  *rqptr;

   /*********/
   /* begin */
   /*********/

   for (cptr = cliptr; *cptr; cptr++) *cptr = tolower(*cptr);

   size = 0;
   cptr = strstr (cliptr, "size=");
   if (cptr) size = atoi(cptr+5);
   if (size <= 0) size = DICT_DEFAULT_SIZE;

   count = 0;
   cptr = strstr (cliptr, "count=");
   if (cptr) count = atoi(cptr+6);
   if (count <= 0) count = size * 10;

   /* maximum number of entries before a deletion cycle */
   max = 0;
   cptr = strstr (cliptr, "max=");
   if (cptr) max = atoi(cptr+4);

   /* minimum number of entries at end of delete cycle */
   min = 0;
   cptr = strstr (cliptr, "min=");
   if (cptr) min = atoi(cptr+4);
   if (min < 0) min = 32;
   if (max < min) max = min * 2;

   cptr = strstr (cliptr, "fname=");
   if (cptr) fname = cptr+6;

   /* read in the file of strings */
   if (stat (fname, &statbuf) < 0) exit (vaxc$errno);
   if ((fptr = fopen (fname, "r")) == NULL) exit (vaxc$errno);
   bptr = calloc (1, statbuf.st_size);
   if ((wptr = bptr) == NULL) exit (vaxc$errno);
   while (fgets (wptr, 256, fptr) != NULL)
   {
      while (*wptr && *wptr != '\n') wptr++;
      *wptr++ = ' ';
      *wptr = '\0';
   }
   fclose (fptr);
   if (!*bptr) exit (SS$_ABORT);

   VmRequestInit ();
   rqptr = VmGetRequest ();
   if (Watch.CliEnabled)
   {
      Watch.Category = Watch.Module = -1;
      WatchSetWatch (rqptr, WATCH_NEW_ITEM); 
   }

   dicptr = DictCreate (rqptr, size);

   sys$gettim (&ThenTime);
   random = ThenTime[0] & ThenTime[1];

   deletions = duplicates = expands = failures = klen0 = 0;
   for (total = 0; total < count; total++)
   {
      random = random * 69069 + 1;
      /* ensure 5% (or so) are duplicate keys to exercise that aspect */
      if (random % 21)
      {
         zptr = sptr = key;
         zptr += KEY_VARY(random) - 1;  /* vary size */
         while (sptr < zptr)
         {
            if (!*wptr) wptr = bptr;
            *sptr++ = *wptr++;
         }
         *sptr = '\0';
         klen = sptr - key;
      }
      else
         duplicates++;

      /* generate random value */
      random = random * 69069 + 1;
      zptr = sptr = value;
      zptr += VALUE_VARY(random) - 1;  /* vary size */
      while (sptr < zptr)
      {
         if (!*wptr) wptr = bptr;
         *sptr++ = *wptr++;
      }
      *sptr = '\0';
      vlen = sptr - value;

      /* insert the key into the dictionary either of the two calls */
      if (random % 2)
         denptr = DictInsert (dicptr, DICT_TYPE_INTERNAL, key, -1, value, -1);
      else
         denptr = DictInsert (dicptr, DICT_TYPE_INTERNAL, key, klen, value, vlen);

      /* a zero length key should fail */
      if (denptr == NULL) failures++;
      if (klen == 0) klen0++;

      /* ensure another small percentage are expanded by 100% */
      if ((random % 21) == 0)
         if (denptr != NULL)
         {
            DictExpandEntry (denptr, DICT_GET_BYTES(denptr) * 2);
            expands++;
         }

      /* if no deletion cycle */
      if (!(max && min))
         if (total < count)
            continue;
         else
            break;

      if (dicptr->count > max || total >= count)
      {
         DictIterate (dicptr, NULL);
         while (dicptr->count > min)
         {
            /* trim back down to min by choosing entries at random */
            random = random * 69069 + 1;
            for (int cnt = (random & 0xf) + 1; cnt; cnt--)
            {
               while (denptr = DictIterate (dicptr, "*"));
               if (denptr) break;
               if ((denptr = DictIterate (dicptr, NULL)) == NULL) break;
            }
            if (denptr == NULL) break;
            if (dicptr->count % 2)
               DictRemove (dicptr, DICT_TYPE_INTERNAL, denptr->key, -1);
            else
               DictRemove (dicptr, DICT_TYPE_INTERNAL,
                           denptr->key, denptr->klen);
            deletions++;
         }
         if (denptr == NULL) break;
      }
      if (denptr == NULL) break;
   }

   sys$gettim (&NowTime);
   status = lib$sub_times (&NowTime, &ThenTime, &DeltaTime);
   fsecs = FloatDeltaTime (&DeltaTime);
   if (VMSnok (status)) ErrorExitVmsStatus (status, NULL, FI_LI);

   Watch.StdoutOnly = true;
   Watch.Category = WATCH_INTERNAL;
   DictWatch (dicptr, NULL, NULL);

   fprintf (stdout,
"size:%d count:%d max:%d min:%d\n\
total:%d klen0:%d failures:%d duplicates:%d expands:%d deletions:%d \
duration:%s %3.3f/sec %f/each\n",
            size, count, max, min,
            total, klen0, failures, duplicates, expands, deletions,
            DurationString(rqptr,&DeltaTime),
            (float)total/fsecs, fsecs/(float)total);

   fputs ("table:", stdout);
   for (int idx = 0; idx < dicptr->size; idx++)
   {
      int cnt = 0;
      for (denptr = dicptr->table[idx]; denptr != NULL; denptr = denptr->clink)
         cnt++;
      fprintf (stdout, "[%d]%d ", idx, cnt);
   }
   fputs ("\n", stdout);

   DictDestroy (dicptr);
} 

#endif /* WATCH_MOD */

/*****************************************************************************/