#include "cvs.h"
#include <assert.h>
static List *listcache = NULL;
static Node *nodecache = NULL;
static void freenode_mem PROTO((Node * p));
static int
hashp (key)
const char *key;
{
unsigned int h = 0;
unsigned int g;
assert(key != NULL);
while (*key != 0)
{
unsigned int c = *key++;
h = (h << 4) + FOLD_FN_CHAR (c);
if ((g = h & 0xf0000000) != 0)
h = (h ^ (g >> 24)) ^ g;
}
return (h % HASHSIZE);
}
List *
getlist ()
{
int i;
List *list;
Node *node;
if (listcache != NULL)
{
list = listcache;
listcache = listcache->next;
list->next = (List *) NULL;
for (i = 0; i < HASHSIZE; i++)
list->hasharray[i] = (Node *) NULL;
}
else
{
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);
}
void
dellist (listp)
List **listp;
{
int i;
Node *p;
if (*listp == (List *) NULL)
return;
p = (*listp)->list;
while (p->next != p)
delnode (p->next);
freenode_mem (p);
for (i = 0; i < HASHSIZE; i++)
{
if ((p = (*listp)->hasharray[i]) != (Node *) NULL)
{
#ifndef NOCACHE
p->type = NT_UNKNOWN;
p->next = nodecache;
nodecache = p;
#else
free (p);
#endif
}
}
#ifndef NOCACHE
(*listp)->next = listcache;
listcache = *listp;
#else
free ((*listp)->list);
free (*listp);
#endif
*listp = (List *) NULL;
}
Node *
getnode ()
{
Node *p;
if (nodecache != (Node *) NULL)
{
p = nodecache;
nodecache = p->next;
}
else
{
p = (Node *) xmalloc (sizeof (Node));
}
memset ((char *) p, 0, sizeof (Node));
p->type = NT_UNKNOWN;
return (p);
}
void
delnode (p)
Node *p;
{
if (p == (Node *) NULL)
return;
p->next->prev = p->prev;
p->prev->next = p->next;
if (p->hashnext != (Node *) NULL)
{
p->hashnext->hashprev = p->hashprev;
p->hashprev->hashnext = p->hashnext;
}
freenode (p);
}
static void
freenode_mem (p)
Node *p;
{
if (p->delproc != (void (*) ()) NULL)
p->delproc (p);
else
{
if (p->data != NULL)
free (p->data);
}
if (p->key != NULL)
free (p->key);
p->key = p->data = NULL;
p->delproc = (void (*) ()) NULL;
}
void
freenode (p)
Node *p;
{
freenode_mem (p);
#ifndef NOCACHE
p->type = NT_UNKNOWN;
p->next = nodecache;
nodecache = p;
#else
free (p);
#endif
}
int
insert_before (list, marker, p)
List *list;
Node *marker;
Node *p;
{
if (p->key != NULL)
{
int hashval;
Node *q;
hashval = hashp (p->key);
if (list->hasharray[hashval] == NULL)
{
q = getnode ();
q->type = HEADER;
list->hasharray[hashval] = q->hashnext = q->hashprev = q;
}
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);
}
int
addnode (list, p)
List *list;
Node *p;
{
return insert_before (list, list->list, p);
}
int
addnode_at_front (list, p)
List *list;
Node *p;
{
return insert_before (list, list->list->next, p);
}
Node *
findnode (list, key)
List *list;
const char *key;
{
Node *head, *p;
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 (strcmp (p->key, key) == 0)
return (p);
return ((Node *) NULL);
}
Node *
findnode_fn (list, key)
List *list;
const char *key;
{
Node *head, *p;
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);
}
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);
}
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;
head = list->list;
remain = head->next;
n = 0;
for (p = remain; p != head; p = p->next)
n++;
array = (Node **) xmalloc (sizeof(Node *) * n);
i = 0;
for (p = remain; p != head; p = p->next)
array[i++] = p;
client_comp = comp;
qsort (array, n, sizeof(Node *), qsort_comp);
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;
}
free (array);
}
int
fsortcmp (p, q)
const Node *p;
const Node *q;
{
return (strcmp (p->key, q->key));
}
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);
}
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;
}