Loading...
Searching...
No Matches
omList.c
Go to the documentation of this file.
/*******************************************************************
* File: omList.c
* Purpose: implementation of routines for operations on linked lists
* Author: obachman (Olaf Bachmann)
* Created: 11/99
*******************************************************************/
#include "omConfig.h"
#ifdef HAVE_OMALLOC
#ifndef NULL
#define NULL ((void*) 0)
#endif
#define _VALUE(list, offset) *((void**) ((char *)list + offset))
#define VALUE(list, offset) (unsigned long) _VALUE(list, offset)
#define NEXT(list) _VALUE(list, next)
#define ITER(list) list = NEXT(list)
int _omListLength(void* list, int next)
{
int l = 0;
while (list != NULL)
{
l++;
ITER(list);
}
return l;
}
void* _omListLast(void* list, int next)
{
if (list == NULL) return NULL;
while (NEXT(list) != NULL) ITER(list);
return list;
}
void* _omListHasCycle(void* list, int next)
{
void* l1 = list;
void* l2;
int l = 0, i;
while (l1 != NULL)
{
i = 0;
l2 = list;
while (l1 != l2)
{
i++;
ITER(l2);
}
if (i != l) return l1;
ITER(l1);
l++;
}
return NULL;
}
void* _omIsOnList(void* list, int next, void* addr)
{
if (addr == NULL)
return (NULL);
while (list != NULL)
{
if (addr == list) return addr;
ITER(list);
}
return 0;
}
void* _omRemoveFromList(void* list, int next, void* addr)
{
void* nlist;
void* olist;
if (list == NULL) return NULL;
nlist = NEXT(list);
if (list == addr) return nlist;
olist = list;
while (nlist != NULL && nlist != addr)
{
list = nlist;
ITER(nlist);
}
if (nlist != NULL) NEXT(list) = NEXT(nlist);
return olist;
}
void* _omFindInList(void* list, int next, int long_field, unsigned long what)
{
while (list != NULL)
{
if (VALUE(list, long_field) == what) return list;
ITER(list);
}
return NULL;
}
void* _omFindInSortedList(void* list, int next, int long_field,
unsigned long what)
{
while (list != NULL)
{
if (VALUE(list, long_field) >= what)
{
if (VALUE(list, long_field) == what) return list;
return NULL;
}
ITER(list);
}
return NULL;
}
void* _omRemoveFromSortedList(void* list, int next, int long_field, void* addr)
{
void* nlist;
void* olist;
unsigned long what = VALUE(addr, long_field);
if (list == NULL) return NULL;
nlist = NEXT(list);
if (list == addr) return nlist;
if (VALUE(list, long_field) > what) return list;
olist = list;
while (nlist != NULL && nlist != addr)
{
if (VALUE(list, long_field) > what) return olist;
list = nlist;
ITER(nlist);
}
if (nlist != NULL) NEXT(list) = NEXT(nlist);
return olist;
}
void* _omInsertInSortedList(void* list, int next, int long_field, void* addr)
{
unsigned long what = VALUE(addr, long_field);
if (list == NULL || what <= VALUE(list, long_field))
{
NEXT(addr) = list;
return addr;
}
else
{
void* prev = list;
void* curr = NEXT(list);
while (curr != NULL && VALUE(curr, long_field) < what)
{
prev = curr;
ITER(curr);
}
NEXT(prev) = addr;
NEXT(addr) = curr;
return list;
}
}
#ifndef OM_NDEBUG
#include "omalloc.h"
#include "omDebug.h"
omError_t _omCheckList(void* list, int next, int level, omError_t report, OM_FLR_DECL)
{
if (level < 1) return omError_NoError;
if (level == 1)
{
while (list != NULL)
{
omCheckReturn(omCheckPtr(list, report, OM_FLR_VAL));
ITER(list);
}
}
else
{
void* l1 = list;
void* l2;
int l = 0, i;
l1 = list;
while (l1 != NULL)
{
omCheckReturn(omCheckPtr(l1, report, OM_FLR_VAL));
i = 0;
l2 = list;
while (l1 != l2)
{
i++;
ITER(l2);
}
if (i != l)
return omReportError(omError_ListCycleError, report, OM_FLR_VAL, "");
ITER(l1);
l++;
}
}
return omError_NoError;
}
omError_t _omCheckSortedList(void* list, int next, int long_field, int level, omError_t report, OM_FLR_DECL)
{
void* prev = NULL;
if (level <= 1) return omError_NoError;
if (level == 1)
{
while (list != NULL)
{
omCheckReturn(omCheckPtr(list, report, OM_FLR_VAL));
if (prev != NULL && VALUE(prev, long_field) > VALUE(list, long_field))
return omReportError(omError_SortedListError, report, OM_FLR_VAL,
"%d > %d", VALUE(prev, long_field), VALUE(list, long_field));
prev = list;
ITER(list);
}
}
else
{
void* l1 = list;
void* l2;
int l = 0, i;
while (l1 != NULL)
{
omCheckReturn(omCheckPtr(l1, report, OM_FLR_VAL));
if (prev != NULL && VALUE(prev, long_field) > VALUE(l1, long_field))
return omReportError(omError_SortedListError, report, OM_FLR_VAL,
"%d > %d", VALUE(prev, long_field), VALUE(l1, long_field));
i = 0;
l2 = list;
while (l1 != l2)
{
i++;
ITER(l2);
}
omCheckReturnError(i != l, omError_ListCycleError);
prev = l1;
ITER(l1);
l++;
}
}
return omError_NoError;
}
#endif
#endif
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132
next
ListNode * next
Definition janet.h:31
omDebug.h
omCheckPtr
omError_t omCheckPtr(const void *ptr, omError_t report, OM_FLR_DECL)
Definition omDebugCheck.c:136
omCheckReturnError
#define omCheckReturnError(cond, error)
Definition omDebug.h:172
omCheckReturn
#define omCheckReturn(cond)
Definition omDebug.h:170
omReportError
omError_t omReportError(omError_t error, omError_t report_error, OM_FLR_DECL, const char *fmt,...)
Definition omError.c:80
omError_ListCycleError
@ omError_ListCycleError
Definition omError.h:34
omError_SortedListError
@ omError_SortedListError
Definition omError.h:35
omError_NoError
@ omError_NoError
Definition omError.h:18
omError_t
enum omError_e omError_t
Definition omError.h:44
_omIsOnList
void * _omIsOnList(void *list, int next, void *addr)
Definition omList.c:66
NULL
#define NULL
Definition omList.c:12
_omRemoveFromList
void * _omRemoveFromList(void *list, int next, void *addr)
Definition omList.c:79
_omListLast
void * _omListLast(void *list, int next)
Definition omList.c:32
NEXT
#define NEXT(list)
Definition omList.c:17
_omInsertInSortedList
void * _omInsertInSortedList(void *list, int next, int long_field, void *addr)
Definition omList.c:148
ITER
#define ITER(list)
Definition omList.c:18
_omListHasCycle
void * _omListHasCycle(void *list, int next)
Definition omList.c:42
VALUE
#define VALUE(list, offset)
Definition omList.c:16
_omCheckSortedList
omError_t _omCheckSortedList(void *list, int next, int long_field, int level, omError_t report, OM_FLR_DECL)
Definition omList.c:216
_omFindInSortedList
void * _omFindInSortedList(void *list, int next, int long_field, unsigned long what)
Definition omList.c:110
_omFindInList
void * _omFindInList(void *list, int next, int long_field, unsigned long what)
Definition omList.c:100
_omListLength
int _omListLength(void *list, int next)
Definition omList.c:20
_omCheckList
omError_t _omCheckList(void *list, int next, int level, omError_t report, OM_FLR_DECL)
Definition omList.c:178
_omRemoveFromSortedList
void * _omRemoveFromSortedList(void *list, int next, int long_field, void *addr)
Definition omList.c:125
omalloc.h