summaryrefslogtreecommitdiffstats
path: root/contrib/cvs/src/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/cvs/src/hash.c')
-rw-r--r--contrib/cvs/src/hash.c528
1 files changed, 0 insertions, 528 deletions
diff --git a/contrib/cvs/src/hash.c b/contrib/cvs/src/hash.c
deleted file mode 100644
index d9bc12c..0000000
--- a/contrib/cvs/src/hash.c
+++ /dev/null
@@ -1,528 +0,0 @@
-/*
- * Copyright (C) 1986-2005 The Free Software Foundation, Inc.
- *
- * Portions Copyright (C) 1998-2005 Derek Price, Ximbiot <http://ximbiot.com>,
- * and others.
- *
- * Portions Copyright (C) 1992, Brian Berliner and Jeff Polk
- *
- * You may distribute under the terms of the GNU General Public License as
- * specified in the README file that comes with the CVS source distribution.
- *
- * Polk's hash list manager. So cool.
- */
-
-#include "cvs.h"
-#include <assert.h>
-
-/* Global caches. The idea is that we maintain a linked list of "free"d
- nodes or lists, and get new items from there. It has been suggested
- to use an obstack instead, but off the top of my head, I'm not sure
- that would gain enough to be worth worrying about. */
-static List *listcache = NULL;
-static Node *nodecache = NULL;
-
-static void freenode_mem PROTO((Node * p));
-
-/* hash function */
-static int
-hashp (key)
- const char *key;
-{
- unsigned int h = 0;
- unsigned int g;
-
- assert(key != NULL);
-
- while (*key != 0)
- {
- unsigned int c = *key++;
- /* The FOLD_FN_CHAR is so that findnode_fn works. */
- h = (h << 4) + FOLD_FN_CHAR (c);
- if ((g = h & 0xf0000000) != 0)
- h = (h ^ (g >> 24)) ^ g;
- }
-
- return (h % HASHSIZE);
-}
-
-/*
- * create a new list (or get an old one from the cache)
- */
-List *
-getlist ()
-{
- int i;
- List *list;
- Node *node;
-
- if (listcache != NULL)
- {
- /* get a list from the cache and clear it */
- list = listcache;
- listcache = listcache->next;
- list->next = (List *) NULL;
- for (i = 0; i < HASHSIZE; i++)
- list->hasharray[i] = (Node *) NULL;
- }
- else
- {
- /* make a new list from scratch */
- list = (List *) xmalloc (sizeof (List));
- memset ((char *) list, 0, sizeof (List));
- node = getnode ();
- list->list = node;
- node->type = HEADER;
- node->next = node->prev = node;
- }
- return (list);
-}
-
-/*
- * free up a list
- */
-void
-dellist (listp)
- List **listp;
-{
- int i;
- Node *p;
-
- if (*listp == (List *) NULL)
- return;
-
- p = (*listp)->list;
-
- /* free each node in the list (except header) */
- while (p->next != p)
- delnode (p->next);
-
- /* free any list-private data, without freeing the actual header */
- freenode_mem (p);
-
- /* free up the header nodes for hash lists (if any) */
- for (i = 0; i < HASHSIZE; i++)
- {
- if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
- {
- /* put the nodes into the cache */
-#ifndef NOCACHE
- p->type = NT_UNKNOWN;
- p->next = nodecache;
- nodecache = p;
-#else
- /* If NOCACHE is defined we turn off the cache. This can make
- it easier to tools to determine where items were allocated
- and freed, for tracking down memory leaks and the like. */
- free (p);
-#endif
- }
- }
-
- /* put it on the cache */
-#ifndef NOCACHE
- (*listp)->next = listcache;
- listcache = *listp;
-#else
- free ((*listp)->list);
- free (*listp);
-#endif
- *listp = (List *) NULL;
-}
-
-/*
- * get a new list node
- */
-Node *
-getnode ()
-{
- Node *p;
-
- if (nodecache != (Node *) NULL)
- {
- /* get one from the cache */
- p = nodecache;
- nodecache = p->next;
- }
- else
- {
- /* make a new one */
- p = (Node *) xmalloc (sizeof (Node));
- }
-
- /* always make it clean */
- memset ((char *) p, 0, sizeof (Node));
- p->type = NT_UNKNOWN;
-
- return (p);
-}
-
-/*
- * remove a node from it's list (maybe hash list too) and free it
- */
-void
-delnode (p)
- Node *p;
-{
- if (p == (Node *) NULL)
- return;
-
- /* take it out of the list */
- p->next->prev = p->prev;
- p->prev->next = p->next;
-
- /* if it was hashed, remove it from there too */
- if (p->hashnext != (Node *) NULL)
- {
- p->hashnext->hashprev = p->hashprev;
- p->hashprev->hashnext = p->hashnext;
- }
-
- /* free up the storage */
- freenode (p);
-}
-
-/*
- * free up the storage associated with a node
- */
-static void
-freenode_mem (p)
- Node *p;
-{
- if (p->delproc != (void (*) ()) NULL)
- p->delproc (p); /* call the specified delproc */
- else
- {
- if (p->data != NULL) /* otherwise free() it if necessary */
- free (p->data);
- }
- if (p->key != NULL) /* free the key if necessary */
- free (p->key);
-
- /* to be safe, re-initialize these */
- p->key = p->data = NULL;
- p->delproc = (void (*) ()) NULL;
-}
-
-/*
- * free up the storage associated with a node and recycle it
- */
-void
-freenode (p)
- Node *p;
-{
- /* first free the memory */
- freenode_mem (p);
-
- /* then put it in the cache */
-#ifndef NOCACHE
- p->type = NT_UNKNOWN;
- p->next = nodecache;
- nodecache = p;
-#else
- free (p);
-#endif
-}
-
-/*
- * Link item P into list LIST before item MARKER. If P->KEY is non-NULL and
- * that key is already in the hash table, return -1 without modifying any
- * parameter.
- *
- * return 0 on success
- */
-int
-insert_before (list, marker, p)
- List *list;
- Node *marker;
- Node *p;
-{
- if (p->key != NULL) /* hash it too? */
- {
- int hashval;
- Node *q;
-
- hashval = hashp (p->key);
- if (list->hasharray[hashval] == NULL) /* make a header for list? */
- {
- q = getnode ();
- q->type = HEADER;
- list->hasharray[hashval] = q->hashnext = q->hashprev = q;
- }
-
- /* put it into the hash list if it's not already there */
- for (q = list->hasharray[hashval]->hashnext;
- q != list->hasharray[hashval]; q = q->hashnext)
- {
- if (strcmp (p->key, q->key) == 0)
- return (-1);
- }
- q = list->hasharray[hashval];
- p->hashprev = q->hashprev;
- p->hashnext = q;
- p->hashprev->hashnext = p;
- q->hashprev = p;
- }
-
- p->next = marker;
- p->prev = marker->prev;
- marker->prev->next = p;
- marker->prev = p;
-
- return (0);
-}
-
-/*
- * insert item p at end of list "list" (maybe hash it too) if hashing and it
- * already exists, return -1 and don't actually put it in the list
- *
- * return 0 on success
- */
-int
-addnode (list, p)
- List *list;
- Node *p;
-{
- return insert_before (list, list->list, p);
-}
-
-/*
- * Like addnode, but insert p at the front of `list'. This bogosity is
- * necessary to preserve last-to-first output order for some RCS functions.
- */
-int
-addnode_at_front (list, p)
- List *list;
- Node *p;
-{
- return insert_before (list, list->list->next, p);
-}
-
-/* Look up an entry in hash list table and return a pointer to the
- node. Return NULL if not found. Abort with a fatal error for
- errors. */
-Node *
-findnode (list, key)
- List *list;
- const char *key;
-{
- Node *head, *p;
-
- /* This probably should be "assert (list != NULL)" (or if not we
- should document the current behavior), but only if we check all
- the callers to see if any are relying on this behavior. */
- if ((list == (List *) NULL))
- return ((Node *) NULL);
-
- assert (key != NULL);
-
- head = list->hasharray[hashp (key)];
- if (head == (Node *) NULL)
- /* Not found. */
- return ((Node *) NULL);
-
- for (p = head->hashnext; p != head; p = p->hashnext)
- if (strcmp (p->key, key) == 0)
- return (p);
- return ((Node *) NULL);
-}
-
-/*
- * Like findnode, but for a filename.
- */
-Node *
-findnode_fn (list, key)
- List *list;
- const char *key;
-{
- Node *head, *p;
-
- /* This probably should be "assert (list != NULL)" (or if not we
- should document the current behavior), but only if we check all
- the callers to see if any are relying on this behavior. */
- if (list == (List *) NULL)
- return ((Node *) NULL);
-
- assert (key != NULL);
-
- head = list->hasharray[hashp (key)];
- if (head == (Node *) NULL)
- return ((Node *) NULL);
-
- for (p = head->hashnext; p != head; p = p->hashnext)
- if (fncmp (p->key, key) == 0)
- return (p);
- return ((Node *) NULL);
-}
-
-/*
- * walk a list with a specific proc
- */
-int
-walklist (list, proc, closure)
- List *list;
- int (*proc) PROTO ((Node *, void *));
- void *closure;
-{
- Node *head, *p;
- int err = 0;
-
- if (list == NULL)
- return (0);
-
- head = list->list;
- for (p = head->next; p != head; p = p->next)
- err += proc (p, closure);
- return (err);
-}
-
-int
-list_isempty (list)
- List *list;
-{
- return list == NULL || list->list->next == list->list;
-}
-
-static int (*client_comp) PROTO ((const Node *, const Node *));
-static int qsort_comp PROTO ((const void *, const void *));
-
-static int
-qsort_comp (elem1, elem2)
- const void *elem1;
- const void *elem2;
-{
- Node **node1 = (Node **) elem1;
- Node **node2 = (Node **) elem2;
- return client_comp (*node1, *node2);
-}
-
-/*
- * sort the elements of a list (in place)
- */
-void
-sortlist (list, comp)
- List *list;
- int (*comp) PROTO ((const Node *, const Node *));
-{
- Node *head, *remain, *p, **array;
- int i, n;
-
- if (list == NULL)
- return;
-
- /* save the old first element of the list */
- head = list->list;
- remain = head->next;
-
- /* count the number of nodes in the list */
- n = 0;
- for (p = remain; p != head; p = p->next)
- n++;
-
- /* allocate an array of nodes and populate it */
- array = (Node **) xmalloc (sizeof(Node *) * n);
- i = 0;
- for (p = remain; p != head; p = p->next)
- array[i++] = p;
-
- /* sort the array of nodes */
- client_comp = comp;
- qsort (array, n, sizeof(Node *), qsort_comp);
-
- /* rebuild the list from beginning to end */
- head->next = head->prev = head;
- for (i = 0; i < n; i++)
- {
- p = array[i];
- p->next = head;
- p->prev = head->prev;
- p->prev->next = p;
- head->prev = p;
- }
-
- /* release the array of nodes */
- free (array);
-}
-
-/*
- * compare two files list node (for sort)
- */
-int
-fsortcmp (p, q)
- const Node *p;
- const Node *q;
-{
- return (strcmp (p->key, q->key));
-}
-
-/* Debugging functions. Quite useful to call from within gdb. */
-
-static char *nodetypestring PROTO ((Ntype));
-
-static char *
-nodetypestring (type)
- Ntype type;
-{
- switch (type) {
- case NT_UNKNOWN: return("UNKNOWN");
- case HEADER: return("HEADER");
- case ENTRIES: return("ENTRIES");
- case FILES: return("FILES");
- case LIST: return("LIST");
- case RCSNODE: return("RCSNODE");
- case RCSVERS: return("RCSVERS");
- case DIRS: return("DIRS");
- case UPDATE: return("UPDATE");
- case LOCK: return("LOCK");
- case NDBMNODE: return("NDBMNODE");
- case FILEATTR: return("FILEATTR");
- case VARIABLE: return("VARIABLE");
- case RCSFIELD: return("RCSFIELD");
- case RCSCMPFLD: return("RCSCMPFLD");
- }
-
- return("<trash>");
-}
-
-static int printnode PROTO ((Node *, void *));
-static int
-printnode (node, closure)
- Node *node;
- void *closure;
-{
- if (node == NULL)
- {
- (void) printf("NULL node.\n");
- return(0);
- }
-
- (void) printf("Node at %p: type = %s, key = %p = \"%s\", data = %p, next = %p, prev = %p\n",
- (void *)node, nodetypestring(node->type),
- (void *)node->key, node->key, node->data,
- (void *)node->next, (void *)node->prev);
-
- return(0);
-}
-
-/* This is global, not static, so that its name is unique and to avoid
- compiler warnings about it not being used. But it is not used by CVS;
- it exists so one can call it from a debugger. */
-void printlist PROTO ((List *));
-
-void
-printlist (list)
- List *list;
-{
- if (list == NULL)
- {
- (void) printf("NULL list.\n");
- return;
- }
-
- (void) printf("List at %p: list = %p, HASHSIZE = %d, next = %p\n",
- (void *)list, (void *)list->list, HASHSIZE, (void *)list->next);
-
- (void) walklist(list, printnode, NULL);
-
- return;
-}
OpenPOWER on IntegriCloud