#include "cvs.h"
static List *listcache = NULL;
static Node *nodecache = NULL;
static void freenode_mem (Node * p);
static int
hashp (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 (void)
{
int i;
List *list;
Node *node;
if (listcache != NULL)
{
list = listcache;
listcache = listcache->next;
list->next = NULL;
for (i = 0; i < HASHSIZE; i++)
list->hasharray[i] = NULL;
}
else
{
list = xmalloc (sizeof (List));
memset (list, 0, sizeof (List));
node = getnode ();
list->list = node;
node->type = HEADER;
node->next = node->prev = node;
}
return list;
}
void
dellist (List **listp)
{
int i;
Node *p;
List *tmp;
if (*listp == NULL)
return;
tmp = *listp;
*listp = NULL;
p = tmp->list;
while (p->next != p)
delnode (p->next);
freenode_mem (p);
for (i = 0; i < HASHSIZE; i++)
{
if ((p = tmp->hasharray[i]) != NULL)
{
#ifndef NOCACHE
p->type = NT_UNKNOWN;
p->next = nodecache;
nodecache = p;
#else
free (p);
#endif
}
}
#ifndef NOCACHE
tmp->next = listcache;
listcache = tmp;
#else
free (tmp->list);
free (tmp);
#endif
}
void
removenode (Node *p)
{
if (!p) return;
p->next->prev = p->prev;
p->prev->next = p->next;
if (p->hashnext)
{
p->hashnext->hashprev = p->hashprev;
p->hashprev->hashnext = p->hashnext;
}
}
void
mergelists (List *dest, List **src)
{
Node *head, *p, *n;
head = (*src)->list;
for (p = head->next; p != head; p = n)
{
n = p->next;
removenode (p);
addnode (dest, p);
}
dellist (src);
}
Node *
getnode (void)
{
Node *p;
if (nodecache != NULL)
{
p = nodecache;
nodecache = p->next;
}
else
{
p = xmalloc (sizeof (Node));
}
memset (p, 0, sizeof (Node));
p->type = NT_UNKNOWN;
return p;
}
void
delnode (Node *p)
{
if (!p) return;
removenode (p);
freenode (p);
}
static void
freenode_mem (Node *p)
{
if (p->delproc != 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 = NULL;
}
void
freenode (Node *p)
{
freenode_mem (p);
#ifndef NOCACHE
p->type = NT_UNKNOWN;
p->next = nodecache;
nodecache = p;
#else
free (p);
#endif
}
int
insert_before (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 *list, Node *p)
{
return insert_before (list, list->list, p);
}
int
addnode_at_front (List *list, Node *p)
{
return insert_before (list, list->list->next, p);
}
Node *
findnode (List *list, const char *key)
{
Node *head, *p;
if ((list == NULL))
return NULL;
assert (key != NULL);
head = list->hasharray[hashp (key)];
if (head == NULL)
return NULL;
for (p = head->hashnext; p != head; p = p->hashnext)
if (strcmp (p->key, key) == 0)
return p;
return NULL;
}
Node *
findnode_fn (List *list, const char *key)
{
Node *head, *p;
if (list == NULL)
return NULL;
assert (key != NULL);
head = list->hasharray[hashp (key)];
if (head == NULL)
return NULL;
for (p = head->hashnext; p != head; p = p->hashnext)
if (fncmp (p->key, key) == 0)
return p;
return NULL;
}
int
walklist (List *list, int (*proc) (Node *, void *), void *closure)
{
Node *head, *p;
int err = 0;
#ifdef HAVE_PRINTF_PTR
TRACE (TRACE_FLOW, "walklist ( list=%p, proc=%p, closure=%p )",
(void *)list, (void *)proc, (void *)closure);
#else
TRACE (TRACE_FLOW, "walklist ( list=%lx, proc=%lx, closure=%lx )",
(unsigned long)list,(unsigned long) proc,
(unsigned long)closure);
#endif
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)
{
return list == NULL || list->list->next == list->list;
}
static int (*client_comp) (const Node *, const Node *);
static int
qsort_comp (const void *elem1, const void *elem2)
{
Node **node1 = (Node **) elem1;
Node **node2 = (Node **) elem2;
return client_comp (*node1, *node2);
}
void
sortlist (List *list, int (*comp) (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 = xnmalloc (n, sizeof (Node *));
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 (const Node *p, const Node *q)
{
return strcmp (p->key, q->key);
}
static char *
nodetypestring (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 (Node *node, void *closure)
{
if (node == NULL)
{
(void) printf("NULL node.\n");
return 0;
}
#ifdef HAVE_PRINTF_PTR
(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);
#else
(void) printf("Node at 0x%lx: type = %s, key = 0x%lx = \"%s\", data = 0x%lx, next = 0x%lx, prev = 0x%lx\n",
(unsigned long) node, nodetypestring(node->type),
(unsigned long) node->key, node->key, (unsigned long) node->data,
(unsigned long) node->next, (unsigned long) node->prev);
#endif
return 0;
}
void
printlist (List *list)
{
if (list == NULL)
{
(void) printf("NULL list.\n");
return;
}
#ifdef HAVE_PRINTF_PTR
(void) printf("List at %p: list = %p, HASHSIZE = %d, next = %p\n",
(void *) list, (void *) list->list, HASHSIZE, (void *) list->next);
#else
(void) printf("List at 0x%lx: list = 0x%lx, HASHSIZE = %d, next = 0x%lx\n",
(unsigned long) list, (unsigned long) list->list, HASHSIZE,
(unsigned long) list->next);
#endif
(void) walklist(list, printnode, NULL);
return;
}