aboutsummaryrefslogtreecommitdiff
path: root/gnu/usr.bin/cvs/lib/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'gnu/usr.bin/cvs/lib/hash.c')
-rw-r--r--gnu/usr.bin/cvs/lib/hash.c400
1 files changed, 0 insertions, 400 deletions
diff --git a/gnu/usr.bin/cvs/lib/hash.c b/gnu/usr.bin/cvs/lib/hash.c
deleted file mode 100644
index 8ac93237c380..000000000000
--- a/gnu/usr.bin/cvs/lib/hash.c
+++ /dev/null
@@ -1,400 +0,0 @@
-/*
- * 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 1.4 kit.
- *
- * Polk's hash list manager. So cool.
- */
-
-#include "cvs.h"
-
-#ifndef lint
-static const char rcsid[] = "$CVSid: @(#)hash.c 1.19 94/09/23 $";
-USE(rcsid);
-#endif
-
-/* global caches */
-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;
-
- while (*key != 0)
- {
- h = (h << 4) + *key++;
- 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 */
- p->type = UNKNOWN;
- p->next = nodecache;
- nodecache = p;
- }
- }
-
- /* put it on the cache */
- (*listp)->next = listcache;
- listcache = *listp;
- *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 = 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 = (char *) 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 */
- p->type = UNKNOWN;
- p->next = nodecache;
- nodecache = p;
-}
-
-/*
- * 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;
-{
- int hashval;
- Node *q;
-
- if (p->key != NULL) /* hash it too? */
- {
- 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;
- }
-
- /* put it into the regular list */
- p->prev = list->list->prev;
- p->next = list->list;
- list->list->prev->next = p;
- list->list->prev = p;
-
- return (0);
-}
-
-/*
- * look up an entry in hash list table and return a pointer to the
- * node. Return NULL on error or not found.
- */
-Node *
-findnode (list, key)
- List *list;
- const char *key;
-{
- Node *head, *p;
-
- if (list == (List *) NULL)
- return ((Node *) NULL);
-
- head = list->hasharray[hashp (key)];
- if (head == (Node *) NULL)
- return ((Node *) NULL);
-
- for (p = head->hashnext; p != head; p = p->hashnext)
- if (strcmp (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);
-}
-
-/*
- * 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, *q;
-
- /* save the old first element of the list */
- head = list->list;
- remain = head->next;
-
- /* make the header node into a null list of it's own */
- head->next = head->prev = head;
-
- /* while there are nodes remaining, do insert sort */
- while (remain != head)
- {
- /* take one from the list */
- p = remain;
- remain = remain->next;
-
- /* traverse the sorted list looking for the place to insert it */
- for (q = head->next; q != head; q = q->next)
- {
- if (comp (p, q) < 0)
- {
- /* p comes before q */
- p->next = q;
- p->prev = q->prev;
- p->prev->next = p;
- q->prev = p;
- break;
- }
- }
- if (q == head)
- {
- /* it belongs at the end of the list */
- p->next = head;
- p->prev = head->prev;
- p->prev->next = p;
- head->prev = p;
- }
- }
-}
-
-/* Debugging functions. Quite useful to call from within gdb. */
-
-char *
-nodetypestring (type)
- Ntype type;
-{
- switch (type) {
- case 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");
- }
-
- 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 0x%p: type = %s, key = 0x%p = \"%s\", data = 0x%p, next = 0x%p, prev = 0x%p\n",
- node, nodetypestring(node->type), node->key, node->key, node->data, node->next, node->prev);
-
- return(0);
-}
-
-void
-printlist (list)
- List *list;
-{
- if (list == NULL)
- {
- (void) printf("NULL list.\n");
- return;
- }
-
- (void) printf("List at 0x%p: list = 0x%p, HASHSIZE = %d, next = 0x%p\n",
- list, list->list, HASHSIZE, list->next);
-
- (void) walklist(list, printnode, NULL);
-
- return;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-31 09:13:30 +0000