- fixed the slow memory leak problem.
KyoungSoo Park [Mon, 22 Oct 2007 17:14:06 +0000 (17:14 +0000)]
- added memory leak debugging code
- up the RPM version

Makefile
codemux.c
codemux.spec
codemuxlib.c
codemuxlib.h
debug.c [new file with mode: 0644]
debug.h
queue.h [new file with mode: 0644]

index 83cb0f3..2024ca4 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -8,7 +8,7 @@ all: ${TARGS}
 clean:
        rm -f ${TARGS} *.o *~
 
-SHARED_OBJ = codemuxlib.o
+SHARED_OBJ = codemuxlib.o debug.o
 
 CODEMUX_OBJ = codemux.o ${SHARED_OBJ}
 
index 34ffc30..5ba4b01 100644 (file)
--- a/codemux.c
+++ b/codemux.c
 #include <unistd.h>
 #include <string.h>
 #include "codemuxlib.h"
-
-#define DEBUG 0
+#include "debug.h"
 
 #ifdef DEBUG
-#define TRACE(fmt, msg...) fprintf(stderr, "[%s,%d] " fmt, __FUNCTION__, __LINE__, ##msg)
-#else
-#define TRACE(fmt, msg...) (void)0
+HANDLE hdebugLog;
+int defaultTraceSync;
 #endif
 
 #define CONF_FILE "/etc/codemux/codemux.conf"
@@ -174,14 +172,14 @@ GetSliceXids(void)
     int xid;
 
     if ((temp = strchr(line, ':')) == NULL)
-      continue;                        /* weird line */
+      goto next_line;                  /* weird line */
     *temp = '\0';              /* terminate slice name */
     temp++;
     if ((temp = strchr(temp+1, ':')) == NULL)
-      continue;                        /* weird line */
+      goto next_line;  /* weird line */
     if ((xid = atoi(temp+1)) < 1)
-      continue;                        /* weird xid */
-
+      goto next_line;  /* weird xid */
+    
     /* we've got a slice name and xid, let's try to match */
     for (i = 0; i < numSlices; i++) {
       if (slices[i].si_xid == 0 &&
@@ -190,6 +188,9 @@ GetSliceXids(void)
        break;
       }
     }
+  next_line:
+    if (line)
+      xfree(line);
   }
 
   /* assume service 0 is the root service, and don't check it since
@@ -246,11 +247,11 @@ WhichSlicePos(char *slice)
 
   if (numSlices >= numSlicesAlloc) {
     numSlicesAlloc = MAX(8, numSlicesAlloc * 2);
-    slices = realloc(slices, numSlicesAlloc * sizeof(SliceInfo));
+    slices = xrealloc(slices, numSlicesAlloc * sizeof(SliceInfo));
   }
 
   memset(&slices[numSlices], 0, sizeof(SliceInfo));
-  slices[numSlices].si_sliceName = strdup(slice);
+  slices[numSlices].si_sliceName = xstrdup(slice);
   numSlices++;
   return(numSlices-1);
 }
@@ -290,7 +291,7 @@ ReadConfFile(void)
     ServiceSig serv;
     int port;
     if (line != NULL)
-      free(line);
+      xfree(line);
     
     if ((line = GetNextLine(f)) == NULL)
       break;
@@ -317,7 +318,7 @@ ReadConfFile(void)
     }
     if (num >= numAlloc) {
       numAlloc = MAX(numAlloc * 2, 8);
-      servs = realloc(servs, numAlloc * sizeof(ServiceSig));
+      servs = xrealloc(servs, numAlloc * sizeof(ServiceSig));
     }
     serv.ss_slicePos = WhichSlicePos(serv.ss_slice);
     if (slices[serv.ss_slicePos].si_inUse == 0 &&
@@ -338,10 +339,10 @@ ReadConfFile(void)
   }
 
   for (i = 0; i < numServices; i++) {
-    free(serviceSig[i].ss_host);
-    free(serviceSig[i].ss_slice);
+    xfree(serviceSig[i].ss_host);
+    xfree(serviceSig[i].ss_slice);
   }
-  free(serviceSig);
+  xfree(serviceSig);
   serviceSig = servs;
   numServices = num;
   confFileReadTime = statBuf.st_mtime;
@@ -680,7 +681,7 @@ SocketReadyToRead(int fd)
   }
 
   if ((fb = si->si_readBuf) == NULL) {
-    fb = si->si_readBuf = calloc(1, sizeof(FlowBuf));
+    fb = si->si_readBuf = xcalloc(1, sizeof(FlowBuf));
     fb->fb_refs = 1;
     if (si->si_peerFd >= 0) {
       sockInfo[si->si_peerFd].si_writeBuf = fb;
@@ -689,7 +690,7 @@ SocketReadyToRead(int fd)
   }
 
   if (fb->fb_buf == NULL)
-    fb->fb_buf = malloc(FB_ALLOCSIZE);
+    fb->fb_buf = xmalloc(FB_ALLOCSIZE);
 
   /* determine read buffer size - if 0, then block reads and return */
   if ((spaceLeft = FB_SIZE - fb->fb_used) <= 0) {
index 5e9eb8f..7196e64 100644 (file)
@@ -1,6 +1,6 @@
 %define name codemux 
 %define version 0.1
-%define release 6%{?pldistro:.%{pldistro}}%{?date:.%{date}}
+%define release 7%{?pldistro:.%{pldistro}}%{?date:.%{date}}
 
 Summary: CoDemux - HTTP port DeMux
 Name: %{name} 
index 1f88633..206c08f 100644 (file)
@@ -10,8 +10,8 @@
 #include <time.h>
 #include <unistd.h>
 #include <errno.h>
-#include "debug.h"
 #include "codemuxlib.h"
+#include "debug.h"
 
 /*-----------------------------------------------------------------*/
 static char *
@@ -271,3 +271,255 @@ NiceExitBack(int val, char *reason, char *file, int line)
   fprintf(stderr, "%s", buf);
   exit(val);
 }
+/*-----------------------------------------------------------------*/
+/* Logging & Trace support */
+
+/* buffer threshold : when the size hits this value, it flushes its content
+   to the file  */
+#define LOG_BYTES_THRESHOLD (32*1024)
+
+/* this flag indicates that it preserves the base file name for the current
+   one, and changes its name when it actually closes it off */
+#define CHANGE_FILE_NAME_ON_SAVE 0x01 
+
+/* size of the actual log buffer */
+#define LOG_BYTES_MAX       (2*LOG_BYTES_THRESHOLD)
+
+/* log/trace book keeping information */
+typedef struct ExtendedLog {
+  char buffer[LOG_BYTES_MAX]; /* 64 KB */
+  int  bytes;           /* number of bytes written */
+  int  filesize;        /* number of bytes written into this file so far */
+  int  fd;              /* file descriptor */
+  char* sig;            /* base file name */
+  int flags;            /* flags */
+  time_t nextday;
+} ExtendedLog, *PExtendedLog;
+
+/* maximum single file size */
+int maxSingleLogSize = 100 * (1024*1024);
+
+static time_t
+GetNextLogFileName(char* file, int size, const char* sig)
+{
+#define COMPRESS_EXT1 ".bz2"
+#define COMPRESS_EXT2 ".gz"
+
+  struct tm cur_tm;
+  time_t cur_t;
+  int idx = 0;
+
+  cur_t = time(NULL);
+  cur_tm = *gmtime(&cur_t);
+
+  for (;;) {
+    /* check if .bz2 exists */
+    snprintf(file, size, "%s.%04d%02d%02d_%03d%s", 
+            sig, cur_tm.tm_year+1900, cur_tm.tm_mon+1, cur_tm.tm_mday, 
+            idx, COMPRESS_EXT1);
+
+    if (access(file, F_OK) == 0) {
+      idx++;
+      continue;
+    }
+
+    /* check if .gz exists */
+    snprintf(file, size, "%s.%04d%02d%02d_%03d%s", 
+            sig, cur_tm.tm_year+1900, cur_tm.tm_mon+1, cur_tm.tm_mday, 
+            idx++, COMPRESS_EXT2);
+
+    if (access(file, F_OK) == 0) 
+      continue;
+
+    /* strip the extension and see if the (uncompressed) file exists */
+    file[strlen(file) - sizeof(COMPRESS_EXT2) + 1] = 0;
+    if (access(file, F_OK) != 0)
+      break;
+  }
+  
+  /* calculate & return the next day */
+  cur_t -= (3600*cur_tm.tm_hour + 60*cur_tm.tm_min + cur_tm.tm_sec);
+  return cur_t + 60*60*24;
+
+#undef COMPRESS_EXT1
+#undef COMPRESS_EXT2
+}
+/*-----------------------------------------------------------------*/
+static void
+FlushBuffer(HANDLE file) 
+{
+  /* write data into the file */
+  ExtendedLog* pel = (ExtendedLog *)file;
+  int written;
+
+  if (pel == NULL || pel->fd < 0)
+    return;
+  
+  if ((written = write(pel->fd, pel->buffer, pel->bytes)) > 0) {
+    pel->bytes -= written;
+
+    /* if it hasn't written all data, then we need to move memory */
+    if (pel->bytes > 0) 
+      memmove(pel->buffer, pel->buffer + written, pel->bytes);
+    pel->buffer[pel->bytes] = 0;
+    pel->filesize += written;
+  }
+  
+  /* if the filesize is bigger than maxSignleLogSize, then close it off */
+  if (pel->filesize >= maxSingleLogSize) 
+    OpenLogF(file);
+}
+
+/*-----------------------------------------------------------------*/
+HANDLE
+CreateLogFHandle(const char* signature, int change_file_name_on_save)
+{
+  ExtendedLog* pel;
+  char *temp;
+
+  /* check if the file can be created */
+  if ((temp = strrchr(signature, '/')) != NULL) {
+    int dirlen = temp - signature + 1;
+    char pardir[dirlen+1];
+
+    memcpy(pardir, signature, dirlen);
+    pardir[dirlen] = 0;
+    if (access(pardir, W_OK) != 0) 
+      return NULL;
+  } else {
+    /* assume it's the current directory */
+    if (access("./", W_OK) != 0) 
+      return NULL;
+  }
+
+  if ((pel = (ExtendedLog *)xcalloc(1, sizeof(ExtendedLog))) == NULL)
+    NiceExit(-1, "failed");
+
+  pel->fd = -1;
+  pel->sig = xstrdup(signature);
+  if (pel->sig == NULL)
+    NiceExit(-1, "signature copying failed");
+  if (change_file_name_on_save)
+    pel->flags |= CHANGE_FILE_NAME_ON_SAVE;
+
+  return pel;
+}
+
+
+/*-----------------------------------------------------------------*/
+int
+OpenLogF(HANDLE file)
+{
+  char filename[1024];
+  ExtendedLog* pel = (ExtendedLog *)file;
+
+  if (pel == NULL)
+    return -1;
+
+  if (pel->fd != -1) 
+    close(pel->fd);
+
+  pel->nextday = GetNextLogFileName(filename, sizeof(filename), pel->sig);
+
+  /* change the file name only at saving time 
+     use pel->sig as current file name         */
+  if (pel->flags & CHANGE_FILE_NAME_ON_SAVE) {
+    if (access(pel->sig, F_OK) == 0) 
+      rename(pel->sig, filename);
+    strcpy(filename, pel->sig);
+  }
+
+  /* file opening */
+  if ((pel->fd = open(filename, O_RDWR | O_CREAT | O_APPEND, 
+                     S_IRUSR | S_IWUSR)) == -1) {
+    char errMessage[2048];
+    sprintf(errMessage, "couldn't open the extended log file %s\n", filename);
+    NiceExit(-1, errMessage);
+  }
+
+  /* reset the file size */
+  pel->filesize = 0;
+  return 0;
+}
+
+/*-----------------------------------------------------------------*/
+int 
+WriteLog(HANDLE file, const char* data, int size, int forceFlush)
+{
+  ExtendedLog* pel = (ExtendedLog *)file;
+
+  /* if an error might occur, then stop here */
+  if (pel == NULL || pel->fd < 0 || size > LOG_BYTES_MAX)
+    return -1;
+
+  if (data != NULL) {
+    /* flush the previous data, if this data would overfill the buffer */
+    if (pel->bytes + size >= LOG_BYTES_MAX) 
+      FlushBuffer(file);
+
+    /* write into the buffer */
+    memcpy(pel->buffer + pel->bytes, data, size);
+    pel->bytes += size;
+  }
+
+  /* need to flush ? */
+  if ((forceFlush && (pel->bytes > 0)) || (pel->bytes >= LOG_BYTES_THRESHOLD))
+    FlushBuffer(file);
+
+  return 0;
+}
+/*-----------------------------------------------------------------*/
+void
+DailyReopenLogF(HANDLE file) 
+{
+  /* check if current file is a day long,
+     opens another for today's file         */
+  ExtendedLog* pel = (ExtendedLog *)file;
+
+  if (pel && (time(NULL) >= pel->nextday)) {
+    FlushLogF(file);               /* flush */
+    OpenLogF(file);                /* close previous one & reopen today's */
+  }
+}
+/*-----------------------------------------------------------------*/
+int 
+HandleToFileNo(HANDLE file)
+{
+  ExtendedLog* pel = (ExtendedLog *)file;
+
+  return (pel != NULL) ? pel->fd : -1;
+}
+/*-----------------------------------------------------------------*/
+unsigned int 
+HashString(const char *name, unsigned int hash, int endOnQuery, 
+          int skipLastIfDot)
+{
+  /* if endOnQuery, we stop the hashing when we hit the question mark.
+     if skipLastIfDot, we check the last component of the path to see
+     if it includes a dot, and it so, we skip it. if both are specified,
+     we first try the query, and if that exists, we don't trim the path */
+
+  int i;
+  int len;
+  char *temp;
+
+  if (name == NULL)
+    return 0;
+
+  len = strlen(name);
+  if (endOnQuery && (temp = strchr(name, '?')) != NULL)
+    len = temp - name;
+  else if (skipLastIfDot) {
+    /* first, find last component by searching backward */
+    if ((temp = strrchr(name, '/')) != NULL) {
+      /* now search forward for the dot */
+      if (strchr(temp, '.') != NULL)
+       len = temp - name;
+    }
+  }
+
+  for (i = 0; i < len; i ++)
+    hash += (_rotl(hash, 19) + name[i]);
+
+  return hash;
+}
index b954e31..5911620 100644 (file)
 
 #include "appdef.h"
 
+typedef void* HANDLE;
+
 /* stripped version of applib.c for codemux */
 
-char *GetNextLine(FILE *file);
-int   WordCount(char *buf);
-char *GetField(const char *start, int whichField);
-char *GetWord(const char *start, int whichWord);
-int   DoesDotlessSuffixMatch(char *start, int len, char *suffix);
-int   CreatePrivateAcceptSocket(int portNum, int nonBlocking);
-char *StrdupLower(const char *orig);
-void  StrcpyLower(char *dest, const char *src);
+extern char *GetNextLine(FILE *file);
+extern int   WordCount(char *buf);
+extern char *GetField(const char *start, int whichField);
+extern char *GetWord(const char *start, int whichWord);
+extern int   DoesDotlessSuffixMatch(char *start, int len, char *suffix);
+extern int   CreatePrivateAcceptSocket(int portNum, int nonBlocking);
+extern char *StrdupLower(const char *orig);
+extern void  StrcpyLower(char *dest, const char *src);
+
+extern int OpenLogF(HANDLE file);
+extern int WriteLog(HANDLE file, const char* data, int size, int forceFlush);
+extern void DailyReopenLogF(HANDLE file);
+extern unsigned int HashString(const char *name, unsigned int hash, 
+                              int endOnQuery, int skipLastIfDot);
+
+#define FlushLogF(h)  WriteLog(h, NULL, 0, TRUE)
+
+#define MASK 0xFFFFFFFF
+#define _rotl(Val, Bits) ((((Val)<<(Bits)) | (((Val) & MASK)>>(32 - (Bits)))) & MASK)
 
 /* nice exit support */
-void  NiceExitBack(int val, char *reason, char *file, int line);
+extern void  NiceExitBack(int val, char *reason, char *file, int line);
 #define NiceExit(val, reason) NiceExitBack(val, reason, __FILE__, __LINE__)
 
 
diff --git a/debug.c b/debug.c
new file mode 100644 (file)
index 0000000..6878994
--- /dev/null
+++ b/debug.c
@@ -0,0 +1,177 @@
+#include <stdlib.h>
+#include "codemuxlib.h"
+#include "debug.h"
+#include "queue.h"
+
+#ifdef DEBUG_MEMORY_LEAK
+
+/* Maximum length of the location string containing function, file and
+   the line number of the memory allocation part in the original
+   source code. The location info is added in front of the pointer
+   when allocating memory and return p + MAX_LOCATION_STRLEN to the
+   user */
+#define MAX_LOCATION_STRLEN 512 
+
+typedef struct MemoryAllocInfo {
+  char *mi_locstr;             /* location string "__FUNCTION__:__LINE__" */
+  int  mi_count;               /* allocated memory counts */
+  LIST_ENTRY(MemoryAllocInfo) mi_hash;
+  LIST_ENTRY(MemoryAllocInfo) mi_all;                   
+} MemoryAllocInfo;
+
+#define MAX_BINS 257 /* a prime number near 256 */
+static LIST_HEAD(, MemoryAllocInfo) miBins[MAX_BINS];
+static LIST_HEAD(, MemoryAllocInfo) miHead = LIST_HEAD_INITIALIZER(miHead);
+
+/*-------------------------------------------------------------------------*/
+void 
+dbg_print_memtrace(void)
+{
+  MemoryAllocInfo *walk;
+
+  TRACE("memory alloc counts dump begins\n");
+  LIST_FOREACH(walk, &miHead, mi_all) {
+    TRACE("%-50s: %d\n", walk->mi_locstr, walk->mi_count);
+  }
+  TRACE("memory alloc counts dump ends\n");
+}
+/*-------------------------------------------------------------------------*/
+static void 
+increase_alloc_count(char* p, const char* func, 
+                    const char* file, const int line)
+{
+  int bin;
+  MemoryAllocInfo* walk;
+
+#define MAX_LINE_DIGIT 7 /* million lines of code per file is way too much */
+#define LOCSTR_LENGH  (strlen(func) + strlen(file) + MAX_LINE_DIGIT + 3)
+
+  if (LOCSTR_LENGH >= MAX_LOCATION_STRLEN) {
+    TRACE("over the length limit %s:%d\n", func, line);
+    FlushLogF(hdebugLog);
+    exit(-1);
+  }
+  snprintf(p, MAX_LOCATION_STRLEN, "%s:%s:%d", func, file, line);
+
+  bin = (int)(HashString(p, 0, FALSE, FALSE) % MAX_BINS);
+  LIST_FOREACH(walk, &miBins[bin], mi_hash) {
+    if (strcmp(walk->mi_locstr, p) == 0) { /* match */
+      walk->mi_count++;
+      return;
+    }
+  }
+  
+  /* allocate it if not found */
+  if ((walk = (MemoryAllocInfo *)calloc(1, sizeof(MemoryAllocInfo))) == NULL) {
+    TRACE("calloc failed\n");
+    FlushLogF(hdebugLog);
+    exit(-1);
+  }
+  if ((walk->mi_locstr = strdup(p)) == NULL) {
+    TRACE("calloc failed\n");
+    FlushLogF(hdebugLog);
+    exit(-1);
+  }
+  walk->mi_count++;
+  LIST_INSERT_HEAD(&miBins[bin], walk, mi_hash);
+  LIST_INSERT_HEAD(&miHead, walk, mi_all);
+}
+/*-------------------------------------------------------------------------*/
+static void
+decrease_alloc_count(char *p, const char* func, 
+                    const char* file, const int line)
+{ 
+  int bin = (int)(HashString(p, 0, FALSE, FALSE) % MAX_BINS);
+  MemoryAllocInfo* walk;
+
+  LIST_FOREACH(walk, &miBins[bin], mi_hash) {
+    if (strcmp(walk->mi_locstr, p) == 0) { /* match */
+      walk->mi_count--;
+      if (walk->mi_count == 0) {
+       LIST_REMOVE(walk, mi_hash);
+       LIST_REMOVE(walk, mi_all);
+       free(walk->mi_locstr);
+       free(walk);
+      }
+      return;
+    }
+  }
+
+  TRACE("decrease failed %s:%s:%d\n", func, file, line);
+  FlushLogF(hdebugLog);
+  exit(-1);
+}
+/*-------------------------------------------------------------------------*/
+void *
+dbgcalloc(size_t nmemb, size_t size, 
+         const char* func,  const char* file, const int line)
+{
+  int msize = nmemb * size + MAX_LOCATION_STRLEN;
+  char *p;
+
+  if ((p = (char *)calloc(1, msize)) != NULL) {
+    increase_alloc_count(p, func, file, line);
+    return (void *)(p + MAX_LOCATION_STRLEN);
+  }
+  return NULL;
+}
+/*-------------------------------------------------------------------------*/
+void *
+dbgmalloc(size_t size, const char* func, const char* file, const int line)
+{
+  int msize = size + MAX_LOCATION_STRLEN;
+  char *p;
+
+  if ((p = (char *)malloc(msize)) != NULL) {
+    increase_alloc_count(p, func, file, line);
+    return (void *)(p + MAX_LOCATION_STRLEN);
+  }
+  return NULL;
+}
+/*-------------------------------------------------------------------------*/
+void *
+dbgrealloc(void *ptr, size_t size, 
+          const char* func, const char* file, const int line)
+{
+  int msize = size + MAX_LOCATION_STRLEN;
+  char *p;
+
+  if (ptr != NULL) {
+    ptr -= MAX_LOCATION_STRLEN;
+    decrease_alloc_count(ptr, func, file, line);
+  }
+
+  if ((p = (char *)realloc(ptr, msize)) != NULL) {
+    increase_alloc_count(p, func, file, line);
+    return (void *)(p + MAX_LOCATION_STRLEN);
+  }
+  return NULL;
+}
+/*-------------------------------------------------------------------------*/
+char *
+dbgstrdup(const char *s, const char* func, const char* file, const int line)
+{
+  int msize = strlen(s) + 1 + MAX_LOCATION_STRLEN;
+  char *p;
+
+  if ((p = (char *)malloc(msize))) {
+    increase_alloc_count(p, func, file, line);
+    p += MAX_LOCATION_STRLEN;
+    strcpy(p, s);
+    return p;
+  }
+  return NULL;
+}
+/*-------------------------------------------------------------------------*/
+void 
+dbgfree(void *ptr, const char* func, const char* file, const int line)
+{
+  /* should free the original pointer */
+  char* chptr = (char *)ptr;
+
+  chptr -= MAX_LOCATION_STRLEN;
+  decrease_alloc_count(chptr, func, file, line);
+  free(chptr);
+}
+#endif
+
diff --git a/debug.h b/debug.h
index 566885c..bb46c12 100644 (file)
--- a/debug.h
+++ b/debug.h
   TRACE1 : print "buf" whose size is "size"
 */
 
-#define DEBUG
-
-// extern HANDLE hdebugLog;
-// extern int defaultTraceSync;
-#define TRACE0(fmt, msg...) {                                             \
-       char __buf[2048];                                                  \
-       if (hdebugLog) {                                                   \
-          snprintf(__buf, sizeof(__buf), fmt, ##msg);                     \
-          WriteLog(hdebugLog, __buf, strlen(__buf), defaultTraceSync);    \
-       }                                                                  \
+//#define DEBUG
+#ifdef DEBUG
+extern HANDLE hdebugLog;
+extern int defaultTraceSync;
+#define TRACE0(fmt, msg...) {                                              \
+       char __buf[2048];                                                   \
+       if (hdebugLog) {                                                    \
+          snprintf(__buf, sizeof(__buf), fmt, ##msg);                      \
+          WriteLog(hdebugLog, __buf, strlen(__buf), defaultTraceSync);     \
+       }                                                                   \
 }          
-#define TRACE1(buf, size) {                                 \
-       WriteLog(hdebugLog, buf, size, defaultTraceSync);    \
+#define TRACE1(buf, size) {                                                \
+       WriteLog(hdebugLog, buf, size, defaultTraceSync);                   \
 }
 #define TRACE(fmt, msg...) {                                               \
        char __buf[2048];                                                   \
          WriteLog(hdebugLog, __buf, strlen(__buf), defaultTraceSync);      \
        }                                                                  \
 }                                                                  
-
-#ifndef HERE
-#define HERE TRACE("file %s, line %d, func %s\n", __FILE__, __LINE__, __FUNCTION__)
-#endif
-
-#ifdef DEBUG
-#define ASSERT(exp) {                                         \
-  if (!(exp)) {                                               \
-    TRACE("ASSERTION (%s) FAILED in %s (%s:%d)\n",            \
-        (#exp), __FUNCTION__, __FILE__, __LINE__);           \
-  }                                                           \
-}
 #else
-#define ASSERT(exp)         1 ? (void)0 : (exp)
+#define TRACE0(fmt, msg...) (void)0
+#define TRACE1(fmt, msg...) (void)0
+#define TRACE(fmt, msg...)  (void)0
+#define TRACEX(fmt)         (void)0
 #endif // DEBUG
 
 /*--------------------------------------------------------------
 
 #else
 
+#ifndef DEBUG
+#error "define DEBUG first to make DEBUG_MEMORY_LEAK work"
+#endif
+
 #define xcalloc(nmemb, size) dbgcalloc(nmemb, size, __FUNCTION__, \
                                       __FILE__, __LINE__)
-#define xmalloc(size)        dbgmalloc(size, __FUNCTION__,\
+#define xmalloc(size)        dbgmalloc(size, __FUNCTION__,        \
                                        __FILE__, __LINE__)
-#define xrealloc(ptr, size)  dbgrealloc(ptr, size, __FUNCTION__,\
+#define xrealloc(ptr, size)  dbgrealloc(ptr, size, __FUNCTION__,  \
                                         __FILE__, __LINE__)
 #define xstrdup(s)           dbgstrdup(s, __FUNCTION__, __FILE__, __LINE__)
 #define xfree(ptr)           dbgfree(ptr, __FUNCTION__, __FILE__, __LINE__)
diff --git a/queue.h b/queue.h
new file mode 100644 (file)
index 0000000..98a61f2
--- /dev/null
+++ b/queue.h
@@ -0,0 +1,562 @@
+/*
+ * Copyright (c) 1991, 1993
+ *     The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *     This product includes software developed by the University of
+ *     California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *     @(#)queue.h     8.5 (Berkeley) 8/20/94
+ * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.7 2002/04/17 14:21:02 des Exp $
+ */
+
+#ifndef _SYS_QUEUE_H_
+#define        _SYS_QUEUE_H_
+
+#if 0
+we do not seem to have this on linux
+#include <machine/ansi.h>      /* for __offsetof */
+#endif
+
+/*
+ * This file defines five types of data structures: singly-linked lists,
+ * singly-linked tail queues, lists, tail queues, and circular queues.
+ *
+ * A singly-linked list is headed by a single forward pointer. The elements
+ * are singly linked for minimum space and pointer manipulation overhead at
+ * the expense of O(n) removal for arbitrary elements. New elements can be
+ * added to the list after an existing element or at the head of the list.
+ * Elements being removed from the head of the list should use the explicit
+ * macro for this purpose for optimum efficiency. A singly-linked list may
+ * only be traversed in the forward direction.  Singly-linked lists are ideal
+ * for applications with large datasets and few or no removals or for
+ * implementing a LIFO queue.
+ *
+ * A singly-linked tail queue is headed by a pair of pointers, one to the
+ * head of the list and the other to the tail of the list. The elements are
+ * singly linked for minimum space and pointer manipulation overhead at the
+ * expense of O(n) removal for arbitrary elements. New elements can be added
+ * to the list after an existing element, at the head of the list, or at the
+ * end of the list. Elements being removed from the head of the tail queue
+ * should use the explicit macro for this purpose for optimum efficiency.
+ * A singly-linked tail queue may only be traversed in the forward direction.
+ * Singly-linked tail queues are ideal for applications with large datasets
+ * and few or no removals or for implementing a FIFO queue.
+ *
+ * A list is headed by a single forward pointer (or an array of forward
+ * pointers for a hash table header). The elements are doubly linked
+ * so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before
+ * or after an existing element or at the head of the list. A list
+ * may only be traversed in the forward direction.
+ *
+ * A tail queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or
+ * after an existing element, at the head of the list, or at the end of
+ * the list. A tail queue may be traversed in either direction.
+ *
+ * A circle queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the list.
+ * A circle queue may be traversed in either direction, but has a more
+ * complex end of list detection.
+ *
+ * For details on the use of these macros, see the queue(3) manual page.
+ *
+ *
+ *                     SLIST   LIST    STAILQ  TAILQ   CIRCLEQ
+ * _HEAD               +       +       +       +       +
+ * _HEAD_INITIALIZER   +       +       +       +       +
+ * _ENTRY              +       +       +       +       +
+ * _INIT               +       +       +       +       +
+ * _EMPTY              +       +       +       +       +
+ * _FIRST              +       +       +       +       +
+ * _NEXT               +       +       +       +       +
+ * _PREV               -       -       -       +       +
+ * _LAST               -       -       +       +       +
+ * _FOREACH            +       +       +       +       +
+ * _FOREACH_REVERSE    -       -       -       +       +
+ * _INSERT_HEAD                +       +       +       +       +
+ * _INSERT_BEFORE      -       +       -       +       +
+ * _INSERT_AFTER       +       +       +       +       +
+ * _INSERT_TAIL                -       -       +       +       +
+ * _REMOVE_HEAD                +       -       +       -       -
+ * _REMOVE             +       +       +       +       +
+ *
+ */
+
+/*
+ * Singly-linked List declarations.
+ */
+#define        SLIST_HEAD(name, type)                                          \
+struct name {                                                          \
+       struct type *slh_first; /* first element */                     \
+}
+
+#define        SLIST_HEAD_INITIALIZER(head)                                    \
+       { NULL }
+#define        SLIST_ENTRY(type)                                               \
+struct {                                                               \
+       struct type *sle_next;  /* next element */                      \
+}
+/*
+ * Singly-linked List functions.
+ */
+#define        SLIST_EMPTY(head)       ((head)->slh_first == NULL)
+
+#define        SLIST_FIRST(head)       ((head)->slh_first)
+
+#define        SLIST_FOREACH(var, head, field)                                 \
+       for ((var) = SLIST_FIRST((head));                               \
+           (var);                                                      \
+           (var) = SLIST_NEXT((var), field))
+
+#define        SLIST_INIT(head) do {                                           \
+       SLIST_FIRST((head)) = NULL;                                     \
+} while (0)
+
+#define        SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
+       SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);       \
+       SLIST_NEXT((slistelm), field) = (elm);                          \
+} while (0)
+
+#define        SLIST_INSERT_HEAD(head, elm, field) do {                        \
+       SLIST_NEXT((elm), field) = SLIST_FIRST((head));                 \
+       SLIST_FIRST((head)) = (elm);                                    \
+} while (0)
+
+#define        SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
+
+#define        SLIST_REMOVE(head, elm, type, field) do {                       \
+       if (SLIST_FIRST((head)) == (elm)) {                             \
+               SLIST_REMOVE_HEAD((head), field);                       \
+       }                                                               \
+       else {                                                          \
+               struct type *curelm = SLIST_FIRST((head));              \
+               while (SLIST_NEXT(curelm, field) != (elm))              \
+                       curelm = SLIST_NEXT(curelm, field);             \
+               SLIST_NEXT(curelm, field) =                             \
+                   SLIST_NEXT(SLIST_NEXT(curelm, field), field);       \
+       }                                                               \
+} while (0)
+
+#define        SLIST_REMOVE_HEAD(head, field) do {                             \
+       SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);   \
+} while (0)
+
+/*
+ * Singly-linked Tail queue declarations.
+ */
+#define        STAILQ_HEAD(name, type)                                         \
+struct name {                                                          \
+       struct type *stqh_first;/* first element */                     \
+       struct type **stqh_last;/* addr of last next element */         \
+}
+
+#define        STAILQ_HEAD_INITIALIZER(head)                                   \
+       { NULL, &(head).stqh_first }
+
+#define        STAILQ_ENTRY(type)                                              \
+struct {                                                               \
+       struct type *stqe_next; /* next element */                      \
+}
+
+/*
+ * Singly-linked Tail queue functions.
+ */
+#define        STAILQ_EMPTY(head)      ((head)->stqh_first == NULL)
+
+#define        STAILQ_FIRST(head)      ((head)->stqh_first)
+
+#define        STAILQ_FOREACH(var, head, field)                                \
+       for((var) = STAILQ_FIRST((head));                               \
+          (var);                                                       \
+          (var) = STAILQ_NEXT((var), field))
+
+#define        STAILQ_INIT(head) do {                                          \
+       STAILQ_FIRST((head)) = NULL;                                    \
+       (head)->stqh_last = &STAILQ_FIRST((head));                      \
+} while (0)
+
+#define        STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {               \
+       if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
+               (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
+       STAILQ_NEXT((tqelm), field) = (elm);                            \
+} while (0)
+
+#define        STAILQ_INSERT_HEAD(head, elm, field) do {                       \
+       if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
+               (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
+       STAILQ_FIRST((head)) = (elm);                                   \
+} while (0)
+
+#define        STAILQ_INSERT_TAIL(head, elm, field) do {                       \
+       STAILQ_NEXT((elm), field) = NULL;                               \
+       *(head)->stqh_last = (elm);                                     \
+       (head)->stqh_last = &STAILQ_NEXT((elm), field);                 \
+} while (0)
+
+#define        STAILQ_LAST(head, type, field)                                  \
+       (STAILQ_EMPTY(head) ?                                           \
+               NULL :                                                  \
+               ((struct type *)                                        \
+               ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
+
+#define        STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
+
+#define        STAILQ_REMOVE(head, elm, type, field) do {                      \
+       if (STAILQ_FIRST((head)) == (elm)) {                            \
+               STAILQ_REMOVE_HEAD(head, field);                        \
+       }                                                               \
+       else {                                                          \
+               struct type *curelm = STAILQ_FIRST((head));             \
+               while (STAILQ_NEXT(curelm, field) != (elm))             \
+                       curelm = STAILQ_NEXT(curelm, field);            \
+               if ((STAILQ_NEXT(curelm, field) =                       \
+                    STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
+                       (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
+       }                                                               \
+} while (0)
+
+#define        STAILQ_REMOVE_HEAD(head, field) do {                            \
+       if ((STAILQ_FIRST((head)) =                                     \
+            STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)         \
+               (head)->stqh_last = &STAILQ_FIRST((head));              \
+} while (0)
+
+#define        STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {                 \
+       if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
+               (head)->stqh_last = &STAILQ_FIRST((head));              \
+} while (0)
+
+/*
+ * List declarations.
+ */
+#define        LIST_HEAD(name, type)                                           \
+struct name {                                                          \
+       struct type *lh_first;  /* first element */                     \
+}
+
+#define        LIST_HEAD_INITIALIZER(head)                                     \
+       { NULL }
+
+#define        LIST_ENTRY(type)                                                \
+struct {                                                               \
+       struct type *le_next;   /* next element */                      \
+       struct type **le_prev;  /* address of previous next element */  \
+}
+
+/*
+ * List functions.
+ */
+
+#define        LIST_EMPTY(head)        ((head)->lh_first == NULL)
+
+#define        LIST_FIRST(head)        ((head)->lh_first)
+
+#define        LIST_FOREACH(var, head, field)                                  \
+       for ((var) = LIST_FIRST((head));                                \
+           (var);                                                      \
+           (var) = LIST_NEXT((var), field))
+
+#define        LIST_INIT(head) do {                                            \
+       LIST_FIRST((head)) = NULL;                                      \
+} while (0)
+
+#define        LIST_INSERT_AFTER(listelm, elm, field) do {                     \
+       if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
+               LIST_NEXT((listelm), field)->field.le_prev =            \
+                   &LIST_NEXT((elm), field);                           \
+       LIST_NEXT((listelm), field) = (elm);                            \
+       (elm)->field.le_prev = &LIST_NEXT((listelm), field);            \
+} while (0)
+
+#define        LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
+       (elm)->field.le_prev = (listelm)->field.le_prev;                \
+       LIST_NEXT((elm), field) = (listelm);                            \
+       *(listelm)->field.le_prev = (elm);                              \
+       (listelm)->field.le_prev = &LIST_NEXT((elm), field);            \
+} while (0)
+
+#define        LIST_INSERT_HEAD(head, elm, field) do {                         \
+       if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
+               LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
+       LIST_FIRST((head)) = (elm);                                     \
+       (elm)->field.le_prev = &LIST_FIRST((head));                     \
+} while (0)
+
+#define        LIST_NEXT(elm, field)   ((elm)->field.le_next)
+
+#define        LIST_REMOVE(elm, field) do {                                    \
+       if (LIST_NEXT((elm), field) != NULL)                            \
+               LIST_NEXT((elm), field)->field.le_prev =                \
+                   (elm)->field.le_prev;                               \
+       *(elm)->field.le_prev = LIST_NEXT((elm), field);                \
+} while (0)
+
+/*
+ * Tail queue declarations.
+ */
+#define        TAILQ_HEAD(name, type)                                          \
+struct name {                                                          \
+       struct type *tqh_first; /* first element */                     \
+       struct type **tqh_last; /* addr of last next element */         \
+}
+
+#define        TAILQ_HEAD_INITIALIZER(head)                                    \
+       { NULL, &(head).tqh_first }
+
+#define        TAILQ_ENTRY(type)                                               \
+struct {                                                               \
+       struct type *tqe_next;  /* next element */                      \
+       struct type **tqe_prev; /* address of previous next element */  \
+}
+
+/*
+ * Tail queue functions.
+ */
+#define        TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
+
+#define        TAILQ_FIRST(head)       ((head)->tqh_first)
+
+#define        TAILQ_FOREACH(var, head, field)                                 \
+       for ((var) = TAILQ_FIRST((head));                               \
+           (var);                                                      \
+           (var) = TAILQ_NEXT((var), field))
+
+#define        TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
+       for ((var) = TAILQ_LAST((head), headname);                      \
+           (var);                                                      \
+           (var) = TAILQ_PREV((var), headname, field))
+
+#define        TAILQ_INIT(head) do {                                           \
+       TAILQ_FIRST((head)) = NULL;                                     \
+       (head)->tqh_last = &TAILQ_FIRST((head));                        \
+} while (0)
+
+#define        TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
+       if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
+               TAILQ_NEXT((elm), field)->field.tqe_prev =              \
+                   &TAILQ_NEXT((elm), field);                          \
+       else                                                            \
+               (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
+       TAILQ_NEXT((listelm), field) = (elm);                           \
+       (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);          \
+} while (0)
+
+#define        TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
+       (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
+       TAILQ_NEXT((elm), field) = (listelm);                           \
+       *(listelm)->field.tqe_prev = (elm);                             \
+       (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);          \
+} while (0)
+
+#define        TAILQ_INSERT_HEAD(head, elm, field) do {                        \
+       if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   \
+               TAILQ_FIRST((head))->field.tqe_prev =                   \
+                   &TAILQ_NEXT((elm), field);                          \
+       else                                                            \
+               (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
+       TAILQ_FIRST((head)) = (elm);                                    \
+       (elm)->field.tqe_prev = &TAILQ_FIRST((head));                   \
+} while (0)
+
+#define        TAILQ_INSERT_TAIL(head, elm, field) do {                        \
+       TAILQ_NEXT((elm), field) = NULL;                                \
+       (elm)->field.tqe_prev = (head)->tqh_last;                       \
+       *(head)->tqh_last = (elm);                                      \
+       (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
+} while (0)
+
+#define        TAILQ_LAST(head, headname)                                      \
+       (*(((struct headname *)((head)->tqh_last))->tqh_last))
+
+#define        TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
+
+#define        TAILQ_PREV(elm, headname, field)                                \
+       (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+
+#define        TAILQ_REMOVE(head, elm, field) do {                             \
+       if ((TAILQ_NEXT((elm), field)) != NULL)                         \
+               TAILQ_NEXT((elm), field)->field.tqe_prev =              \
+                   (elm)->field.tqe_prev;                              \
+       else                                                            \
+               (head)->tqh_last = (elm)->field.tqe_prev;               \
+       *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
+} while (0)
+
+/*
+ * Circular queue declarations.
+ */
+#define        CIRCLEQ_HEAD(name, type)                                        \
+struct name {                                                          \
+       struct type *cqh_first;         /* first element */             \
+       struct type *cqh_last;          /* last element */              \
+}
+
+#define        CIRCLEQ_HEAD_INITIALIZER(head)                                  \
+       { (void *)&(head), (void *)&(head) }
+
+#define        CIRCLEQ_ENTRY(type)                                             \
+struct {                                                               \
+       struct type *cqe_next;          /* next element */              \
+       struct type *cqe_prev;          /* previous element */          \
+}
+
+/*
+ * Circular queue functions.
+ */
+#define        CIRCLEQ_EMPTY(head)     ((head)->cqh_first == (void *)(head))
+
+#define        CIRCLEQ_FIRST(head)     ((head)->cqh_first)
+
+#define        CIRCLEQ_FOREACH(var, head, field)                               \
+       for ((var) = CIRCLEQ_FIRST((head));                             \
+           (var) != (void *)(head) || ((var) = NULL);                  \
+           (var) = CIRCLEQ_NEXT((var), field))
+
+#define        CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
+       for ((var) = CIRCLEQ_LAST((head));                              \
+           (var) != (void *)(head) || ((var) = NULL);                  \
+           (var) = CIRCLEQ_PREV((var), field))
+
+#define        CIRCLEQ_INIT(head) do {                                         \
+       CIRCLEQ_FIRST((head)) = (void *)(head);                         \
+       CIRCLEQ_LAST((head)) = (void *)(head);                          \
+} while (0)
+
+#define        CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
+       CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field);    \
+       CIRCLEQ_PREV((elm), field) = (listelm);                         \
+       if (CIRCLEQ_NEXT((listelm), field) == (void *)(head))           \
+               CIRCLEQ_LAST((head)) = (elm);                           \
+       else                                                            \
+               CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\
+       CIRCLEQ_NEXT((listelm), field) = (elm);                         \
+} while (0)
+
+#define        CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
+       CIRCLEQ_NEXT((elm), field) = (listelm);                         \
+       CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field);    \
+       if (CIRCLEQ_PREV((listelm), field) == (void *)(head))           \
+               CIRCLEQ_FIRST((head)) = (elm);                          \
+       else                                                            \
+               CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\
+       CIRCLEQ_PREV((listelm), field) = (elm);                         \
+} while (0)
+
+#define        CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
+       CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head));             \
+       CIRCLEQ_PREV((elm), field) = (void *)(head);                    \
+       if (CIRCLEQ_LAST((head)) == (void *)(head))                     \
+               CIRCLEQ_LAST((head)) = (elm);                           \
+       else                                                            \
+               CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm);     \
+       CIRCLEQ_FIRST((head)) = (elm);                                  \
+} while (0)
+
+#define        CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
+       CIRCLEQ_NEXT((elm), field) = (void *)(head);                    \
+       CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head));              \
+       if (CIRCLEQ_FIRST((head)) == (void *)(head))                    \
+               CIRCLEQ_FIRST((head)) = (elm);                          \
+       else                                                            \
+               CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm);      \
+       CIRCLEQ_LAST((head)) = (elm);                                   \
+} while (0)
+
+#define        CIRCLEQ_LAST(head)      ((head)->cqh_last)
+
+#define        CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
+
+#define        CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
+
+#define        CIRCLEQ_REMOVE(head, elm, field) do {                           \
+       if (CIRCLEQ_NEXT((elm), field) == (void *)(head))               \
+               CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field);      \
+       else                                                            \
+               CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) =       \
+                   CIRCLEQ_PREV((elm), field);                         \
+       if (CIRCLEQ_PREV((elm), field) == (void *)(head))               \
+               CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field);     \
+       else                                                            \
+               CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) =       \
+                   CIRCLEQ_NEXT((elm), field);                         \
+} while (0)
+
+#ifdef _KERNEL
+
+/*
+ * XXX insque() and remque() are an old way of handling certain queues.
+ * They bogusly assumes that all queue heads look alike.
+ */
+
+struct quehead {
+       struct quehead *qh_link;
+       struct quehead *qh_rlink;
+};
+
+#ifdef __GNUC__
+
+static __inline void
+insque(void *a, void *b)
+{
+       struct quehead *element = (struct quehead *)a,
+                *head = (struct quehead *)b;
+
+       element->qh_link = head->qh_link;
+       element->qh_rlink = head;
+       head->qh_link = element;
+       element->qh_link->qh_rlink = element;
+}
+
+static __inline void
+remque(void *a)
+{
+       struct quehead *element = (struct quehead *)a;
+
+       element->qh_link->qh_rlink = element->qh_rlink;
+       element->qh_rlink->qh_link = element->qh_link;
+       element->qh_rlink = 0;
+}
+
+#else /* !__GNUC__ */
+
+void   insque __P((void *a, void *b));
+void   remque __P((void *a));
+
+#endif /* __GNUC__ */
+
+#endif /* _KERNEL */
+
+#endif /* !_SYS_QUEUE_H_ */