diff options
Diffstat (limited to 'ext/hyperwave/dlist.c')
| -rw-r--r-- | ext/hyperwave/dlist.c | 410 |
1 files changed, 410 insertions, 0 deletions
diff --git a/ext/hyperwave/dlist.c b/ext/hyperwave/dlist.c new file mode 100644 index 0000000000..27c1305664 --- /dev/null +++ b/ext/hyperwave/dlist.c @@ -0,0 +1,410 @@ +/**************************************************************************** +* +* Copyright (C) 1991 Kendall Bennett. +* All rights reserved. +* +* Filename: $RCSfile$ +* Version: $Revision$ +* +* Language: ANSI C +* Environment: any +* +* Description: Module to implement doubly linked lists. Includes a routine +* to peform a mergesort on the doubly linked list. +* +* $Id$ +* +* Revision History: +* ----------------- +* +* $Log$ +* Revision 1.1.1.1 1999/04/07 21:03:31 zeev +* PHP 4.0 +* +* Revision 1.1.1.1 1999/03/17 04:29:11 andi +* PHP4 +* +* Revision 1.1.1.1 1998/12/21 07:56:22 andi +* Trying to start the zend CVS tree +* +* Revision 1.1 1998/08/12 09:29:16 steinm +* First version of Hyperwave module. +* +* Revision 1.5 91/12/31 19:39:49 kjb +* Modified include file directories. +* +* Revision 1.4 91/10/28 03:16:39 kjb +* Ported to the Iris. +* +* Revision 1.3 91/09/27 03:09:18 kjb +* Cosmetic change. +* +* Revision 1.2 91/09/03 18:27:42 ROOT_DOS +* Ported to UNIX. +* +* Revision 1.1 91/09/01 18:35:23 ROOT_DOS +* Initial revision +* +****************************************************************************/ + +#ifndef MSVC5 +#include "config.h" +#endif + +#if HYPERWAVE + +#include <stdio.h> +#include <malloc.h> +#include <signal.h> +#include "debug.h" +#include "DList.h" + +PUBLIC void *dlst_newnode(int size) +/**************************************************************************** +* +* Function: dlst_newnode +* Parameters: size - Amount of memory to allocate for node +* Returns: Pointer to the allocated node's user space. +* +* Description: Allocates the memory required for a node, adding a small +* header at the start of the node. We return a reference to +* the user space of the node, as if it had been allocated via +* malloc(). +* +****************************************************************************/ +{ + DLST_BUCKET *node; + + if ( !(node = (DLST_BUCKET*)malloc(size + sizeof(DLST_BUCKET))) ) { + fprintf(stderr,"Not enough memory to allocate list node.\n"); +/* raise(SIGABRT);*/ + return NULL; + } + + return DLST_USERSPACE(node); /* Return pointer to user space */ +} + +PUBLIC void dlst_freenode(void *node) +/**************************************************************************** +* +* Function: dlst_freenode +* Parameters: node - Node to free. +* +* Description: Frees a node previously allocated with lst_newnode(). +* +****************************************************************************/ +{ + free(DLST_HEADER(node)); +} + +PUBLIC DLIST *dlst_init(void) +/**************************************************************************** +* +* Function: dlst_init +* Returns: Pointer to a newly created list. +* +* Description: Initialises a list and returns a pointer to it. +* +****************************************************************************/ +{ + DLIST *l; + + if ((l = (DLIST*)malloc(sizeof(DLIST))) != NULL) { + l->count = 0; + l->head = &(l->hz[0]); + l->z = &(l->hz[1]); + l->head->next = l->z->next = l->z; + l->z->prev = l->head->prev = l->head; + } + else { + fprintf(stderr,"Insufficient memory to allocate list\n"); + /*raise(SIGABRT);*/ + return NULL; + } + + return l; +} + +PUBLIC void dlst_kill(DLIST *l,void (*freeNode)(void *node)) +/**************************************************************************** +* +* Function: dlst_kill +* Parameters: l - List to kill +* freeNode - Pointer to user routine to free a node +* +* Description: Kills the list l, by deleting all of the elements contained +* within the list one by one and then deleting the list +* itself. Note that we call the user supplied routine +* (*freeNode)() to free each list node. This allows the user +* program to perform any extra processing needed to kill each +* node (if each node contains pointers to other items on the +* heap for example). If no extra processing is required, just +* pass the address of dlst_freenode(), ie: +* +* dlst_kill(myList,dlst_freenode); +* +****************************************************************************/ +{ + DLST_BUCKET *n,*p; + + n = l->head->next; + while (n != l->z) { /* Free all nodes in list */ + p = n; + n = n->next; + (*freeNode)(DLST_USERSPACE(p)); + } + free(l); /* Free the list itself */ +} + +PUBLIC void dlst_insertafter(DLIST *l,void *node,void *after) +/**************************************************************************** +* +* Function: lst_insertafter +* Parameters: l - List to insert node into +* node - Pointer to user space of node to insert +* after - Pointer to user space of node to insert node after +* +* Description: Inserts a new node into the list after the node 'after'. To +* insert a new node at the beginning of the list, user the +* macro DLST_HEAD in place of 'after'. ie: +* +* dlst_insertafter(mylist,node,DLST_HEAD(mylist)); +* +****************************************************************************/ +{ + DLST_BUCKET *n = DLST_HEADER(node),*a = DLST_HEADER(after); + + n->next = a->next; + a->next = n; + n->prev = a; + n->next->prev = n; + l->count++; +} + +PUBLIC void *dlst_deletenext(DLIST *l,void *node) +/**************************************************************************** +* +* Function: lst_deletenext +* Parameters: l - List to delete node from. +* node - Node to delete the next node from +* Returns: Pointer to the deleted node's userspace. +* +* Description: Removes the node AFTER 'node' from the list l. +* +****************************************************************************/ +{ + DLST_BUCKET *n = DLST_HEADER(node); + + node = DLST_USERSPACE(n->next); + n->next->next->prev = n; + n->next = n->next->next; + l->count--; + return node; +} + +PUBLIC void *dlst_first(DLIST *l) +/**************************************************************************** +* +* Function: dlst_first +* Parameters: l - List to obtain first node from +* Returns: Pointer to first node in list, NULL if list is empty. +* +* Description: Returns a pointer to the user space of the first node in +* the list. If the list is empty, we return NULL. +* +****************************************************************************/ +{ + DLST_BUCKET *n; + + n = l->head->next; + return (n == l->z ? NULL : DLST_USERSPACE(n)); +} + +PUBLIC void *dlst_last(DLIST *l) +/**************************************************************************** +* +* Function: dlst_last +* Parameters: l - List to obtain last node from +* Returns: Pointer to last node in list, NULL if list is empty. +* +* Description: Returns a pointer to the user space of the last node in +* the list. If the list is empty, we return NULL. +* +****************************************************************************/ +{ + DLST_BUCKET *n; + + n = l->z->prev; + return (n == l->head ? NULL : DLST_USERSPACE(n)); +} + +PUBLIC void *dlst_next(void *prev) +/**************************************************************************** +* +* Function: dlst_next +* Parameters: prev - Previous node in list to obtain next node from +* Returns: Pointer to the next node in the list, NULL at end of list. +* +* Description: Returns a pointer to the user space of the next node in the +* list given a pointer to the user space of the previous node. +* If we have reached the end of the list, we return NULL. The +* end of the list is detected when the next pointer of a node +* points back to itself, as does the dummy last node's next +* pointer. This enables us to detect the end of the list +* without needed access to the list data structure itself. +* +* NOTE: We do no checking to ensure that 'prev' is NOT a +* NULL pointer. +* +****************************************************************************/ +{ + DLST_BUCKET *n = DLST_HEADER(prev); + + n = n->next; + return (n == n->next ? NULL : DLST_USERSPACE(n)); +} + +PUBLIC void *dlst_prev(void *next) +/**************************************************************************** +* +* Function: dlst_prev +* Parameters: next - Next node in list to obtain previous node from +* Returns: Pointer to the previous node in the list, NULL at start list. +* +* Description: Returns a pointer to the user space of the prev node in the +* list given a pointer to the user space of the next node. +* If we have reached the start of the list, we return NULL. The +* start of the list is detected when the prev pointer of a node +* points back to itself, as does the dummy head node's prev +* pointer. This enables us to detect the start of the list +* without needed access to the list data structure itself. +* +* NOTE: We do no checking to ensure that 'next' is NOT a +* NULL pointer. +* +****************************************************************************/ +{ + DLST_BUCKET *n = DLST_HEADER(next); + + n = n->prev; + return (n == n->prev ? NULL : DLST_USERSPACE(n)); +} + +/* Static globals required by merge() */ + +static DLST_BUCKET *z; +static int (*cmp)(void*,void*); + +PRIVATE DLST_BUCKET *merge(DLST_BUCKET *a,DLST_BUCKET *b,DLST_BUCKET **end) +/**************************************************************************** +* +* Function: merge +* Parameters: a,b - Sublist's to merge +* Returns: Pointer to the merged sublists. +* +* Description: Merges two sorted lists of nodes together into a single +* sorted list. +* +****************************************************************************/ +{ + DLST_BUCKET *c; + + /* Go through the lists, merging them together in sorted order */ + + c = z; + while (a != z && b != z) { + if ((*cmp)(DLST_USERSPACE(a),DLST_USERSPACE(b)) <= 0) { + c->next = a; c = a; a = a->next; + } + else { + c->next = b; c = b; b = b->next; + } + }; + + /* If one of the lists is not exhausted, then re-attach it to the end + * of the newly merged list + */ + + if (a != z) c->next = a; + if (b != z) c->next = b; + + /* Set *end to point to the end of the newly merged list */ + + while (c->next != z) c = c->next; + *end = c; + + /* Determine the start of the merged lists, and reset z to point to + * itself + */ + + c = z->next; z->next = z; + return c; +} + +PUBLIC void dlst_mergesort(DLIST *l,int (*cmp_func)(void*,void*)) +/**************************************************************************** +* +* Function: dlst_mergesort +* Parameters: l - List to merge sort +* cmp_func - Function to compare two user spaces +* +* Description: Mergesort's all the nodes in the list. 'cmp' must point to +* a comparison function that can compare the user spaces of +* two different nodes. 'cmp' should work the same as +* strcmp(), in terms of the values it returns. Rather than +* waste processing time keeping the previous pointers up to +* date while performing the mergesort, we simply run through +* the list at the end of the sort to fix the previous pointers. +* +****************************************************************************/ +{ + int i,N; + DLST_BUCKET *a,*b; /* Pointers to sublists to merge */ + DLST_BUCKET *c; /* Pointer to end of sorted sublists */ + DLST_BUCKET *head; /* Pointer to dummy head node for list */ + DLST_BUCKET *todo; /* Pointer to sublists yet to be sorted */ + DLST_BUCKET *t; /* Temporary */ + + /* Set up globals required by merge() and pointer to head */ + + z = l->z; cmp = cmp_func; head = l->head; + + for (N = 1,a = z; a != head->next; N = N + N) { + todo = head->next; c = head; + while (todo != z) { + + /* Build first sublist to be merged, and splice from main list + */ + + a = t = todo; + for (i = 1; i < N; i++) t = t->next; + b = t->next; t->next = z; t = b; + + /* Build second sublist to be merged and splice from main list + */ + + for (i = 1; i < N; i++) t = t->next; + todo = t->next; t->next = z; + + /* Merge the two sublists created, and set 'c' to point to the + * end of the newly merged sublists. + */ + + c->next = merge(a,b,&t); c = t; + } + } + + /* Fix the previous pointers for the list */ + + a = b = l->head; + b = b->next; + while (1) { + b->prev = a; + if (b == z) + break; + a = a->next; + b = b->next; + } +} + +#endif |