source: git/omalloc/omList.c @ 599326

spielwiese
Last change on this file since 599326 was 599326, checked in by Kai Krüger <krueger@…>, 14 years ago
Anne, Kai, Frank: - changes to #include "..." statements to allow cleaner build structure - affected directories: omalloc, kernel, Singular - not yet done: IntergerProgramming git-svn-id: file:///usr/local/Singular/svn/trunk@13032 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 5.0 KB
Line 
1/*******************************************************************
2 *  File:    omList.c
3 *  Purpose: implementation of routines for operations on linked lists
4 *  Author:  obachman (Olaf Bachmann)
5 *  Created: 11/99
6 *  Version: $Id$
7 *******************************************************************/
8#include <omalloc/omConfig.h>
9
10#ifndef NULL
11#define NULL ((void*) 0)
12#endif
13
14#define _VALUE(list, offset) *((void**) ((char *)list + offset))
15#define VALUE(list, offset) (unsigned long) _VALUE(list, offset)
16#define NEXT(list) _VALUE(list, next)
17#define ITER(list) list = NEXT(list)
18
19int _omListLength(void* list, int next)
20{
21  int l = 0;
22  while (list != NULL)
23  {
24    l++;
25    ITER(list);
26  }
27  return l;
28}
29
30
31void* _omListLast(void* list, int next)
32{
33  if (list == NULL) return NULL;
34
35  while (NEXT(list) != NULL) ITER(list);
36
37  return list;
38}
39
40
41void* _omListHasCycle(void* list, int next)
42{
43  void* l1 = list;
44  void* l2;
45
46  int l = 0, i;
47
48  while (l1 != NULL)
49  {
50    i = 0;
51    l2 = list;
52    while (l1 != l2)
53    {
54      i++;
55      ITER(l2);
56    }
57    if (i != l) return l1;
58    ITER(l1);
59    l++;
60  }
61  return NULL;
62}
63
64
65void* _omIsOnList(void* list, int next, void* addr)
66{
67  if (addr == NULL)
68    return (NULL);
69
70  while (list != NULL)
71  {
72    if (addr == list) return addr;
73    ITER(list);
74  }
75  return 0;
76}
77
78void* _omRemoveFromList(void* list, int next, void* addr)
79{
80  void* nlist;
81  void* olist;
82
83  if (list == NULL) return NULL;
84
85  nlist = NEXT(list);
86  if (list == addr) return nlist;
87
88  olist = list;
89  while (nlist != NULL && nlist != addr)
90  {
91    list = nlist;
92    ITER(nlist);
93  }
94
95  if (nlist != NULL) NEXT(list) = NEXT(nlist);
96  return olist;
97}
98
99void* _omFindInList(void* list, int next, int long_field, unsigned long what)
100{
101  while (list != NULL)
102  {
103    if (VALUE(list, long_field) == what) return list;
104    ITER(list);
105  }
106  return NULL;
107}
108
109void* _omFindInSortedList(void* list, int next, int long_field,
110                          unsigned long what)
111{
112  while (list != NULL)
113  {
114    if (VALUE(list, long_field) >= what)
115    {
116      if (VALUE(list, long_field) == what) return list;
117      return NULL;
118    }
119    ITER(list);
120  }
121  return NULL;
122}
123
124void* _omRemoveFromSortedList(void* list, int next, int long_field, void* addr)
125{
126  void* nlist;
127  void* olist;
128  unsigned long what = VALUE(addr, long_field);
129
130  if (list == NULL) return NULL;
131  nlist = NEXT(list);
132  if (list == addr) return nlist;
133  if (VALUE(list, long_field) > what) return list;
134
135  olist = list;
136  while (nlist != NULL && nlist != addr)
137  {
138    if (VALUE(list, long_field) > what) return olist;
139    list = nlist;
140    ITER(nlist);
141  }
142
143  if (nlist != NULL) NEXT(list) = NEXT(nlist);
144  return olist;
145}
146
147void* _omInsertInSortedList(void* list, int next, int long_field, void* addr)
148{
149  unsigned long what = VALUE(addr, long_field);
150
151  if (list == NULL || what <= VALUE(list, long_field))
152  {
153    NEXT(addr) = list;
154    return addr;
155  }
156  else
157  {
158    void* prev = list;
159    void* curr = NEXT(list);
160
161    while (curr != NULL && VALUE(curr, long_field) < what)
162    {
163      prev = curr;
164      ITER(curr);
165    }
166    NEXT(prev) = addr;
167    NEXT(addr) = curr;
168    return list;
169  }
170}
171
172
173#ifndef OM_NDEBUG
174#include <omalloc/om_Alloc.h>
175#include <omalloc/omDebug.h>
176
177omError_t _omCheckList(void* list, int next, int level, omError_t report, OM_FLR_DECL)
178{
179  if (level < 1) return omError_NoError;
180
181  if (level == 1)
182  {
183    while (list != NULL)
184    {
185      omCheckReturn(omCheckPtr(list, report, OM_FLR_VAL));
186      ITER(list);
187    }
188  }
189  else
190  {
191    void* l1 = list;
192    void* l2;
193    int l = 0, i;
194
195    l1 = list;
196    while (l1 != NULL)
197    {
198      omCheckReturn(omCheckPtr(l1, report, OM_FLR_VAL));
199      i = 0;
200      l2 = list;
201      while (l1 != l2)
202      {
203        i++;
204        ITER(l2);
205      }
206      if (i != l)
207        return omReportError(omError_ListCycleError, report, OM_FLR_VAL, "");
208      ITER(l1);
209      l++;
210    }
211  }
212  return omError_NoError;
213}
214
215omError_t _omCheckSortedList(void* list, int next, int long_field, int level, omError_t report, OM_FLR_DECL)
216{
217  void* prev = NULL;
218
219  if (level <= 1) return omError_NoError;
220
221  if (level == 1)
222  {
223    while (list != NULL)
224    {
225      omCheckReturn(omCheckPtr(list, report, OM_FLR_VAL));
226      if (prev != NULL && VALUE(prev, long_field) > VALUE(list, long_field))
227        return omReportError(omError_SortedListError, report, OM_FLR_VAL,
228                             "%d > %d", VALUE(prev, long_field), VALUE(list, long_field));
229      prev = list;
230      ITER(list);
231    }
232  }
233  else
234  {
235    void* l1 = list;
236    void* l2;
237    int l = 0, i;
238
239    while (l1 != NULL)
240    {
241      omCheckReturn(omCheckPtr(l1, report, OM_FLR_VAL));
242      if (prev != NULL && VALUE(prev, long_field) > VALUE(l1, long_field))
243        return omReportError(omError_SortedListError, report, OM_FLR_VAL,
244                             "%d > %d", VALUE(prev, long_field), VALUE(l1, long_field));
245      i = 0;
246      l2 = list;
247      while (l1 != l2)
248      {
249        i++;
250        ITER(l2);
251      }
252      omCheckReturnError(i != l, omError_ListCycleError);
253      prev = l1;
254      ITER(l1);
255      l++;
256    }
257  }
258  return omError_NoError;
259}
260#endif
Note: See TracBrowser for help on using the repository browser.