1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
48 #define CV_FORCE_INLINE CV_INLINE
50 #if !defined(_LIST_INLINE)
51 #define _LIST_INLINE CV_FORCE_INLINE
52 #endif /*_LIST_INLINE*/
54 #if defined DECLARE_LIST
55 #if defined _MSC_VER && _MSC_VER >= 1200
56 #pragma warning("DECLARE_LIST macro is already defined!")
58 #endif /*DECLARE_LIST*/
60 static const long default_size = 10;
61 static const long default_inc_size = 10;
70 typedef struct _pos CVPOS;
75 long m_buf_size; /* The size of the buffer */
76 long m_size; /* The number of elements */
82 typedef struct _list _CVLIST;
84 #define DECLARE_LIST(type, prefix)\
85 /* Basic element of a list*/\
86 struct prefix##element_##type\
88 struct prefix##element_##type* m_prev;\
89 struct prefix##element_##type* m_next;\
92 typedef struct prefix##element_##type ELEMENT_##type;\
93 /* Initialization and destruction*/\
94 _LIST_INLINE _CVLIST* prefix##create_list_##type(long);\
95 _LIST_INLINE void prefix##destroy_list_##type(_CVLIST*);\
96 /* Access functions*/\
97 _LIST_INLINE CVPOS prefix##get_head_pos_##type(_CVLIST*);\
98 _LIST_INLINE CVPOS prefix##get_tail_pos_##type(_CVLIST*);\
99 _LIST_INLINE type* prefix##get_next_##type(CVPOS*);\
100 _LIST_INLINE type* prefix##get_prev_##type(CVPOS*);\
101 /* Modification functions*/\
102 _LIST_INLINE void prefix##clear_list_##type(_CVLIST*);\
103 _LIST_INLINE CVPOS prefix##add_head_##type(_CVLIST*, type*);\
104 _LIST_INLINE CVPOS prefix##add_tail_##type(_CVLIST*, type*);\
105 _LIST_INLINE void prefix##remove_head_##type(_CVLIST*);\
106 _LIST_INLINE void prefix##remove_tail_##type(_CVLIST*);\
107 _LIST_INLINE CVPOS prefix##insert_before_##type(_CVLIST*, CVPOS, type*);\
108 _LIST_INLINE CVPOS prefix##insert_after_##type(_CVLIST*, CVPOS, type*);\
109 _LIST_INLINE void prefix##remove_at_##type(_CVLIST*, CVPOS);\
110 _LIST_INLINE void prefix##set_##type(CVPOS, type*);\
111 _LIST_INLINE type* prefix##get_##type(CVPOS);\
112 /* Statistics functions*/\
113 _LIST_INLINE int prefix##get_count_##type(_CVLIST*);
115 /* This macro finds a space for a new element and puts in into 'element' pointer */
116 #define INSERT_NEW(element_type, l, element)\
118 if(l->m_head_free.m_pos != NULL)\
120 element = (element_type*)(l->m_head_free.m_pos);\
121 if(element->m_next != NULL)\
123 element->m_next->m_prev = NULL;\
124 l->m_head_free.m_pos = element->m_next;\
128 l->m_head_free.m_pos = NULL;\
133 if(l->m_buf_size < l->m_size && l->m_head_free.m_pos == NULL)\
135 *(void**)l->m_buffer = cvAlloc(l->m_buf_size*sizeof(element_type) + sizeof(void*));\
136 l->m_buffer = *(void**)l->m_buffer;\
137 *(void**)l->m_buffer = NULL;\
138 element = (element_type*)((char*)l->m_buffer + sizeof(void*));\
142 element = (element_type*)((char*)l->m_buffer + sizeof(void*)) + l->m_size - 1;\
146 /* This macro adds 'element' to the list of free elements*/
147 #define INSERT_FREE(element_type, l, element)\
148 if(l->m_head_free.m_pos != NULL)\
150 ((element_type*)l->m_head_free.m_pos)->m_prev = element;\
152 element->m_next = ((element_type*)l->m_head_free.m_pos);\
153 l->m_head_free.m_pos = element;
156 /*#define GET_FIRST_FREE(l) ((ELEMENT_##type*)(l->m_head_free.m_pos))*/
158 #define IMPLEMENT_LIST(type, prefix)\
159 _CVLIST* prefix##create_list_##type(long size)\
161 _CVLIST* pl = (_CVLIST*)cvAlloc(sizeof(_CVLIST));\
162 pl->m_buf_size = size > 0 ? size : default_size;\
163 pl->m_first_buffer = cvAlloc(pl->m_buf_size*sizeof(ELEMENT_##type) + sizeof(void*));\
164 pl->m_buffer = pl->m_first_buffer;\
165 *(void**)pl->m_buffer = NULL;\
167 pl->m_head.m_pos = NULL;\
168 pl->m_tail.m_pos = NULL;\
169 pl->m_head_free.m_pos = NULL;\
172 void prefix##destroy_list_##type(_CVLIST* l)\
174 void* cur = l->m_first_buffer;\
178 next = *(void**)cur;\
184 CVPOS prefix##get_head_pos_##type(_CVLIST* l)\
188 CVPOS prefix##get_tail_pos_##type(_CVLIST* l)\
192 type* prefix##get_next_##type(CVPOS* pos)\
196 ELEMENT_##type* element = (ELEMENT_##type*)(pos->m_pos);\
197 pos->m_pos = element->m_next;\
198 return &element->m_data;\
205 type* prefix##get_prev_##type(CVPOS* pos)\
209 ELEMENT_##type* element = (ELEMENT_##type*)(pos->m_pos);\
210 pos->m_pos = element->m_prev;\
211 return &element->m_data;\
218 int prefix##is_pos_##type(CVPOS pos)\
222 void prefix##clear_list_##type(_CVLIST* l)\
224 l->m_head.m_pos = NULL;\
225 l->m_tail.m_pos = NULL;\
227 l->m_head_free.m_pos = NULL;\
229 CVPOS prefix##add_head_##type(_CVLIST* l, type* data)\
231 ELEMENT_##type* element;\
232 INSERT_NEW(ELEMENT_##type, l, element);\
233 element->m_prev = NULL;\
234 element->m_next = (ELEMENT_##type*)(l->m_head.m_pos);\
235 memcpy(&(element->m_data), data, sizeof(*data));\
238 element->m_next->m_prev = element;\
242 l->m_tail.m_pos = element;\
244 l->m_head.m_pos = element;\
247 CVPOS prefix##add_tail_##type(_CVLIST* l, type* data)\
249 ELEMENT_##type* element;\
250 INSERT_NEW(ELEMENT_##type, l, element);\
251 element->m_next = NULL;\
252 element->m_prev = (ELEMENT_##type*)(l->m_tail.m_pos);\
253 memcpy(&(element->m_data), data, sizeof(*data));\
256 element->m_prev->m_next = element;\
260 l->m_head.m_pos = element;\
262 l->m_tail.m_pos = element;\
265 void prefix##remove_head_##type(_CVLIST* l)\
267 ELEMENT_##type* element = ((ELEMENT_##type*)(l->m_head.m_pos));\
268 if(element->m_next != NULL)\
270 element->m_next->m_prev = NULL;\
272 l->m_head.m_pos = element->m_next;\
273 INSERT_FREE(ELEMENT_##type, l, element);\
276 void prefix##remove_tail_##type(_CVLIST* l)\
278 ELEMENT_##type* element = ((ELEMENT_##type*)(l->m_tail.m_pos));\
279 if(element->m_prev != NULL)\
281 element->m_prev->m_next = NULL;\
283 l->m_tail.m_pos = element->m_prev;\
284 INSERT_FREE(ELEMENT_##type, l, element);\
287 CVPOS prefix##insert_after_##type(_CVLIST* l, CVPOS pos, type* data)\
289 ELEMENT_##type* element;\
290 ELEMENT_##type* before;\
292 INSERT_NEW(ELEMENT_##type, l, element);\
293 memcpy(&(element->m_data), data, sizeof(*data));\
294 before = (ELEMENT_##type*)pos.m_pos;\
295 element->m_prev = before;\
296 element->m_next = before->m_next;\
297 before->m_next = element;\
298 if(element->m_next != NULL)\
299 element->m_next->m_prev = element;\
301 l->m_tail.m_pos = element;\
302 newpos.m_pos = element;\
305 CVPOS prefix##insert_before_##type(_CVLIST* l, CVPOS pos, type* data)\
307 ELEMENT_##type* element;\
308 ELEMENT_##type* after;\
310 INSERT_NEW(ELEMENT_##type, l, element);\
311 memcpy(&(element->m_data), data, sizeof(*data));\
312 after = (ELEMENT_##type*)pos.m_pos;\
313 element->m_prev = after->m_prev;\
314 element->m_next = after;\
315 after->m_prev = element;\
316 if(element->m_prev != NULL)\
317 element->m_prev->m_next = element;\
319 l->m_head.m_pos = element;\
320 newpos.m_pos = element;\
323 void prefix##remove_at_##type(_CVLIST* l, CVPOS pos)\
325 ELEMENT_##type* element = ((ELEMENT_##type*)pos.m_pos);\
326 if(element->m_prev != NULL)\
328 element->m_prev->m_next = element->m_next;\
332 l->m_head.m_pos = element->m_next;\
334 if(element->m_next != NULL)\
336 element->m_next->m_prev = element->m_prev;\
340 l->m_tail.m_pos = element->m_prev;\
342 INSERT_FREE(ELEMENT_##type, l, element);\
345 void prefix##set_##type(CVPOS pos, type* data)\
347 ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\
348 memcpy(&(element->m_data), data, sizeof(data));\
350 type* prefix##get_##type(CVPOS pos)\
352 ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\
353 return &(element->m_data);\
355 int prefix##get_count_##type(_CVLIST* list)\
357 return list->m_size;\
360 #define DECLARE_AND_IMPLEMENT_LIST(type, prefix)\
361 DECLARE_LIST(type, prefix)\
362 IMPLEMENT_LIST(type, prefix)
364 typedef struct __index
371 DECLARE_LIST( _index, h_ )
373 #endif/*_CV_LIST_H_*/