//hashtable.c - hash tables

//

// © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved.

//

/*

 * This file is part of zsh, the Z shell.

 *

 * Copyright (c) 1992-1997 Paul Falstad

 * All rights reserved.

 *

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and to distribute modified versions of this software for any

 * purpose, provided that the above copyright notice and the following

 * two paragraphs appear in all copies of this software.

 *

 * In no event shall Paul Falstad or the Zsh Development Group be liable

 * to any party for direct, indirect, special, incidental, or consequential

 * damages arising out of the use of this software and its documentation,

 * even if Paul Falstad and the Zsh Development Group have been advised of

 * the possibility of such damage.

 *

 * Paul Falstad and the Zsh Development Group specifically disclaim any

 * warranties, including, but not limited to, the implied warranties of

 * merchantability and fitness for a particular purpose.  The software

 * provided hereunder is on an "as is" basis, and Paul Falstad and the

 * Zsh Development Group have no obligation to provide maintenance,

 * support, updates, enhancements, or modifications.

 *

 */

#include "config.h"

#ifdef __SYMBIAN32__

#ifdef __WINSCW__

#pragma warn_unusedarg off

#endif//__WINSCW__

#endif//__SYMBIAN32__

#ifdef ZSH_HASH_DEBUG

# define HASHTABLE_DEBUG_MEMBERS \

    /* Members of struct hashtable used for debugging hash tables */ \

    HashTable next, last;	/* linked list of all hash tables           */ \

    char *tablename;		/* string containing name of the hash table */ \

    PrintTableStats printinfo;	/* pointer to function to print table stats */

#else /* !ZSH_HASH_DEBUG */

# define HASHTABLE_DEBUG_MEMBERS

#endif /* !ZSH_HASH_DEBUG */

#define HASHTABLE_INTERNAL_MEMBERS \

    ScanStatus scan;		/* status of a scan over this hashtable     */ \

    HASHTABLE_DEBUG_MEMBERS

typedef struct scanstatus *ScanStatus;

#include "zsh.mdh"

#include "hashtable.pro"

/* Structure for recording status of a hashtable scan in progress.  When a *

 * scan starts, the .scan member of the hashtable structure points to one  *

 * of these.  That member being non-NULL disables resizing of the          *

 * hashtable (when adding elements).  When elements are deleted, the       *

 * contents of this structure is used to make sure the scan won't stumble  *

 * into the deleted element.                                               */

struct scanstatus {

    int sorted;

    union {

	struct {

	    HashNode *tab;

	    int ct;

	} s;

	HashNode u;

    } u;

};

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

/* Generic Hash Table functions */

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

#ifdef ZSH_HASH_DEBUG

static HashTable firstht, lastht;

#endif /* ZSH_HASH_DEBUG */

/* Generic hash function */

/**/

mod_export unsigned

hasher(char *str)

{

    unsigned hashval = 0, c;

    while ((c = *((unsigned char *) str++)))

	hashval += (hashval << 5) + c;

    return hashval;

}

/* Get a new hash table */

/**/

mod_export HashTable

newhashtable(int size, UNUSED(char const *name), UNUSED(PrintTableStats printinfo))

{

    HashTable ht;

    ht = (HashTable) zshcalloc(sizeof *ht);

#ifdef ZSH_HASH_DEBUG

    ht->next = NULL;

    if(!firstht)

	firstht = ht;

    ht->last = lastht;

    if(lastht)

	lastht->next = ht;

    lastht = ht;

    ht->printinfo = printinfo ? printinfo : printhashtabinfo;

    ht->tablename = ztrdup(name);

#endif /* ZSH_HASH_DEBUG */

    ht->nodes = (HashNode *) zshcalloc(size * sizeof(HashNode));

    ht->hsize = size;

    ht->ct = 0;

    ht->scan = NULL;

    ht->scantab = NULL;

    return ht;

}

/* Delete a hash table.  After this function has been used, any *

 * existing pointers to the hash table are invalid.             */

/**/

mod_export void

deletehashtable(HashTable ht)

{

    ht->emptytable(ht);

#ifdef ZSH_HASH_DEBUG

    if(ht->next)

	ht->next->last = ht->last;

    else

	lastht = ht->last;

    if(ht->last)

	ht->last->next = ht->next;

    else

	firstht = ht->next;

    zsfree(ht->tablename);

#endif /* ZSH_HASH_DEBUG */

    zfree(ht->nodes, ht->hsize * sizeof(HashNode));

    zfree(ht, sizeof(*ht));

}

/* Add a node to a hash table.                          *

 * nam is the key to use in hashing.  nodeptr points    *

 * to the node to add.  If there is already a node in   *

 * the table with the same key, it is first freed, and  *

 * then the new node is added.  If the number of nodes  *

 * is now greater than twice the number of hash values, *

 * the table is then expanded.                          */

/**/

mod_export void

addhashnode(HashTable ht, char *nam, void *nodeptr)

{

    HashNode oldnode = addhashnode2(ht, nam, nodeptr);

    if (oldnode)

	ht->freenode(oldnode);

}

/* Add a node to a hash table, returning the old node on replacement. */

/**/

HashNode

addhashnode2(HashTable ht, char *nam, void *nodeptr)

{

    unsigned hashval;

    HashNode hn, hp, hq;

    hn = (HashNode) nodeptr;

    hn->nam = nam;

    hashval = ht->hash(hn->nam) % ht->hsize;

    hp = ht->nodes[hashval];

    /* check if this is the first node for this hash value */

    if (!hp) {

	hn->next = NULL;

	ht->nodes[hashval] = hn;

	if (++ht->ct >= ht->hsize * 2 && !ht->scan)

	    expandhashtable(ht);

	return NULL;

    }

    /* else check if the first node contains the same key */

    if (ht->cmpnodes(hp->nam, hn->nam) == 0) {

	ht->nodes[hashval] = hn;

	replacing:

	hn->next = hp->next;

	if(ht->scan) {

	    if(ht->scan->sorted) {

		HashNode *tab = ht->scan->u.s.tab;

		int i;

		for(i = ht->scan->u.s.ct; i--; )

		    if(tab[i] == hp)

			tab[i] = hn;

	    } else if(ht->scan->u.u == hp)

		ht->scan->u.u = hn;

	}

	return hp;

    }

    /* else run through the list and check all the keys */

    hq = hp;

    hp = hp->next;

    for (; hp; hq = hp, hp = hp->next) {

	if (ht->cmpnodes(hp->nam, hn->nam) == 0) {

	    hq->next = hn;

	    goto replacing;

	}

    }

    /* else just add it at the front of the list */

    hn->next = ht->nodes[hashval];

    ht->nodes[hashval] = hn;

    if (++ht->ct >= ht->hsize * 2 && !ht->scan)

        expandhashtable(ht);

    return NULL;

}

/* Get an enabled entry in a hash table.  *

 * If successful, it returns a pointer to *

 * the hashnode.  If the node is DISABLED *

 * or isn't found, it returns NULL        */

/**/

mod_export HashNode

gethashnode(HashTable ht, char *nam)

{

    unsigned hashval;

    HashNode hp;

    hashval = ht->hash(nam) % ht->hsize;

    for (hp = ht->nodes[hashval]; hp; hp = hp->next) {

	if (ht->cmpnodes(hp->nam, nam) == 0) {

	    if (hp->flags & DISABLED)

		return NULL;

	    else

		return hp;

	}

    }

    return NULL;

}

/* Get an entry in a hash table.  It will *

 * ignore the DISABLED flag and return a  *

 * pointer to the hashnode if found, else *

 * it returns NULL.                       */

/**/

mod_export HashNode

gethashnode2(HashTable ht, char *nam)

{

    unsigned hashval;

    HashNode hp;

    hashval = ht->hash(nam) % ht->hsize;

    for (hp = ht->nodes[hashval]; hp; hp = hp->next) {

	if (ht->cmpnodes(hp->nam, nam) == 0)

	    return hp;

    }

    return NULL;

}

/* Remove an entry from a hash table.           *

 * If successful, it removes the node from the  *

 * table and returns a pointer to it.  If there *

 * is no such node, then it returns NULL        */

/**/

mod_export HashNode

removehashnode(HashTable ht, char *nam)

{

    unsigned hashval;

    HashNode hp, hq;

    hashval = ht->hash(nam) % ht->hsize;

    hp = ht->nodes[hashval];

    /* if no nodes at this hash value, return NULL */

    if (!hp)

	return NULL;

    /* else check if the key in the first one matches */

    if (ht->cmpnodes(hp->nam, nam) == 0) {

	ht->nodes[hashval] = hp->next;

	gotit:

	ht->ct--;

	if(ht->scan) {

	    if(ht->scan->sorted) {

		HashNode *tab = ht->scan->u.s.tab;

		int i;

		for(i = ht->scan->u.s.ct; i--; )

		    if(tab[i] == hp)

			tab[i] = NULL;

	    } else if(ht->scan->u.u == hp)

		ht->scan->u.u = hp->next;

	}

	return hp;

    }

    /* else run through the list and check the rest of the keys */

    hq = hp;

    hp = hp->next;

    for (; hp; hq = hp, hp = hp->next) {

	if (ht->cmpnodes(hp->nam, nam) == 0) {

	    hq->next = hp->next;

	    goto gotit;

	}

    }

    /* else it is not in the list, so return NULL */

    return NULL;

}

/* Disable a node in a hash table */

/**/

void

disablehashnode(HashNode hn, UNUSED(int flags))

{

    hn->flags |= DISABLED;

}

/* Enable a node in a hash table */

/**/

void

enablehashnode(HashNode hn, UNUSED(int flags))

{

    hn->flags &= ~DISABLED;

}

/* Compare two hash table entries by name */

/**/

static int

hnamcmp(const void *ap, const void *bp)

{

    HashNode a = *(HashNode *)ap;

    HashNode b = *(HashNode *)bp;

    return ztrcmp((unsigned char *) a->nam, (unsigned char *) b->nam);

}

/* Scan the nodes in a hash table and execute scanfunc on nodes based on

 * the flags that are set/unset.  scanflags is passed unchanged to

 * scanfunc (if executed).

 *

 * If sorted != 0, then sort entries of hash table before scanning.

 * If flags1 > 0, then execute scanfunc on a node only if at least one of

 *                these flags is set.

 * If flags2 > 0, then execute scanfunc on a node only if all of

 *                these flags are NOT set.

 * The conditions above for flags1/flags2 must both be true.

 *

 * It is safe to add, remove or replace hash table elements from within

 * the scanfunc.  Replaced elements will appear in the scan exactly once,

 * the new version if it was not scanned before the replacement was made.

 * Added elements might or might not appear in the scan.

 */

/**/

mod_export void

scanhashtable(HashTable ht, int sorted, int flags1, int flags2, ScanFunc scanfunc, int scanflags)

{

    struct scanstatus st;

    if (ht->scantab) {

	ht->scantab(ht, scanfunc, scanflags);

	return;

    }

    if (sorted) {

	int i, ct = ht->ct;

	VARARR(HashNode, hnsorttab, ct);

	HashNode *htp, hn;

	for (htp = hnsorttab, i = 0; i < ht->hsize; i++)

	    for (hn = ht->nodes[i]; hn; hn = hn->next)

		*htp++ = hn;

	qsort((void *)hnsorttab, ct, sizeof(HashNode), hnamcmp);

	st.sorted = 1;

	st.u.s.tab = hnsorttab;

	st.u.s.ct = ct;

	ht->scan = &st;

	for (htp = hnsorttab, i = 0; i < ct; i++, htp++)

	    if (*htp && ((*htp)->flags & flags1) + !flags1 &&

		!((*htp)->flags & flags2))

		scanfunc(*htp, scanflags);

	ht->scan = NULL;

    } else {

	int i, hsize = ht->hsize;

	HashNode *nodes = ht->nodes;

	st.sorted = 0;

	ht->scan = &st;

	for (i = 0; i < hsize; i++)

	    for (st.u.u = nodes[i]; st.u.u; ) {

		HashNode hn = st.u.u;

		st.u.u = st.u.u->next;

		if ((hn->flags & flags1) + !flags1 && !(hn->flags & flags2))

		    scanfunc(hn, scanflags);

	    }

	ht->scan = NULL;

    }

}

/* Scan all nodes in a hash table and executes scanfunc on the *

 * nodes which meet all the following criteria:                *

 * The hash key must match the glob pattern given by `com'.    *

 * If (flags1 > 0), then any flag in flags1 must be set.       *

 * If (flags2 > 0), then all flags in flags2 must NOT be set.  *

 *                                                             *

 * scanflags is passed unchanged to scanfunc (if executed).    *

 * The return value is the number of matches.                  */

/**/

int

scanmatchtable(HashTable ht, Patprog pprog, int flags1, int flags2, ScanFunc scanfunc, int scanflags)

{

    int i, hsize = ht->hsize;

    HashNode *nodes = ht->nodes;

    int match = 0;

    struct scanstatus st;

    st.sorted = 0;

    ht->scan = &st;

    for (i = 0; i < hsize; i++)

	for (st.u.u = nodes[i]; st.u.u; ) {

	    HashNode hn = st.u.u;

	    st.u.u = st.u.u->next;

	    if ((hn->flags & flags1) + !flags1 && !(hn->flags & flags2) &&

		pattry(pprog, hn->nam)) {

		scanfunc(hn, scanflags);

		match++;

	    }

	}

    ht->scan = NULL;

    return match;

}

/* Expand hash tables when they get too many entries. *

 * The new size is 4 times the previous size.         */

/**/

static void

expandhashtable(HashTable ht)

{

    struct hashnode **onodes, **ha, *hn, *hp;

    int i, osize;

    osize = ht->hsize;

    onodes = ht->nodes;

    ht->hsize = osize * 4;

    ht->nodes = (HashNode *) zshcalloc(ht->hsize * sizeof(HashNode));

    ht->ct = 0;

    /* scan through the old list of nodes, and *

     * rehash them into the new list of nodes  */

    for (i = 0, ha = onodes; i < osize; i++, ha++) {

	for (hn = *ha; hn;) {

	    hp = hn->next;

	    ht->addnode(ht, hn->nam, hn);

	    hn = hp;

	}

    }

    zfree(onodes, osize * sizeof(HashNode));

}

/* Empty the hash table and resize it if necessary */

/**/

static void

resizehashtable(HashTable ht, int newsize)

{

    struct hashnode **ha, *hn, *hp;

    int i;

    /* free all the hash nodes */

    ha = ht->nodes;

    for (i = 0; i < ht->hsize; i++, ha++) {

	for (hn = *ha; hn;) {

	    hp = hn->next;

	    ht->freenode(hn);

	    hn = hp;

	}

    }

    /* If new size desired is different from current size, *

     * we free it and allocate a new nodes array.          */

    if (ht->hsize != newsize) {

	zfree(ht->nodes, ht->hsize * sizeof(HashNode));

	ht->nodes = (HashNode *) zshcalloc(newsize * sizeof(HashNode));

	ht->hsize = newsize;

    } else {

	/* else we just re-zero the current nodes array */

	memset(ht->nodes, 0, newsize * sizeof(HashNode));

    }

    ht->ct = 0;

}

/* Generic method to empty a hash table */

/**/

mod_export void

emptyhashtable(HashTable ht)

{

    resizehashtable(ht, ht->hsize);

}

/**/

#ifdef ZSH_HASH_DEBUG

/* Print info about hash table */