1/*M///////////////////////////////////////////////////////////////////////////////////////
2//
3//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4//
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.
8//
9//
10//                        Intel License Agreement
11//                For Open Source Computer Vision Library
12//
13// Copyright (C) 2000, Intel Corporation, all rights reserved.
14// Third party copyrights are property of their respective owners.
15//
16// Redistribution and use in source and binary forms, with or without modification,
17// are permitted provided that the following conditions are met:
18//
19//   * Redistribution's of source code must retain the above copyright notice,
20//     this list of conditions and the following disclaimer.
21//
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.
25//
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.
28//
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.
39//
40//M*/
41
42#ifndef _CV_LIST_H_
43#define _CV_LIST_H_
44
45#include <stdlib.h>
46#include <assert.h>
47
48#define CV_FORCE_INLINE CV_INLINE
49
50#if !defined(_LIST_INLINE)
51#define _LIST_INLINE CV_FORCE_INLINE
52#endif /*_LIST_INLINE*/
53
54#if defined DECLARE_LIST
55#if defined _MSC_VER && _MSC_VER >= 1200
56    #pragma warning("DECLARE_LIST macro is already defined!")
57#endif
58#endif /*DECLARE_LIST*/
59
60static const long default_size = 10;
61static const long default_inc_size = 10;
62
63struct _pos
64{
65    void* m_pos;
66#ifdef _DEBUG
67    struct _list* m_list;
68#endif /*_DEBUG*/
69};
70typedef struct _pos CVPOS;
71struct _list
72{
73    void* m_buffer;
74    void* m_first_buffer;
75    long m_buf_size; /* The size of the buffer */
76    long m_size; /* The number of elements */
77    CVPOS m_head;
78    CVPOS m_tail;
79    CVPOS m_head_free;
80};
81
82typedef struct _list _CVLIST;
83
84#define DECLARE_LIST(type, prefix)\
85    /* Basic element of a list*/\
86    struct prefix##element_##type\
87    {\
88        struct prefix##element_##type* m_prev;\
89        struct prefix##element_##type* m_next;\
90        type m_data;\
91    };\
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*);
114
115/* This macro finds a space for a new element and puts in into 'element' pointer */
116#define INSERT_NEW(element_type, l, element)\
117    l->m_size++;\
118    if(l->m_head_free.m_pos != NULL)\
119    {\
120        element = (element_type*)(l->m_head_free.m_pos);\
121        if(element->m_next != NULL)\
122        {\
123            element->m_next->m_prev = NULL;\
124            l->m_head_free.m_pos = element->m_next;\
125        }\
126        else\
127        {\
128            l->m_head_free.m_pos = NULL;\
129        }\
130    }\
131    else\
132    {\
133        if(l->m_buf_size < l->m_size && l->m_head_free.m_pos == NULL)\
134        {\
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*));\
139        }\
140        else\
141        {\
142            element = (element_type*)((char*)l->m_buffer + sizeof(void*)) + l->m_size - 1;\
143        }\
144    }
145
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)\
149    {\
150        ((element_type*)l->m_head_free.m_pos)->m_prev = element;\
151    }\
152    element->m_next = ((element_type*)l->m_head_free.m_pos);\
153    l->m_head_free.m_pos = element;
154
155
156/*#define GET_FIRST_FREE(l) ((ELEMENT_##type*)(l->m_head_free.m_pos))*/
157
158#define IMPLEMENT_LIST(type, prefix)\
159_CVLIST* prefix##create_list_##type(long size)\
160{\
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;\
166    pl->m_size = 0;\
167    pl->m_head.m_pos = NULL;\
168    pl->m_tail.m_pos = NULL;\
169    pl->m_head_free.m_pos = NULL;\
170    return pl;\
171}\
172void prefix##destroy_list_##type(_CVLIST* l)\
173{\
174    void* cur = l->m_first_buffer;\
175    void* next;\
176    while(cur)\
177    {\
178        next = *(void**)cur;\
179        cvFree(&cur);\
180        cur = next;\
181    }\
182    cvFree(&l);\
183}\
184CVPOS prefix##get_head_pos_##type(_CVLIST* l)\
185{\
186    return l->m_head;\
187}\
188CVPOS prefix##get_tail_pos_##type(_CVLIST* l)\
189{\
190    return l->m_tail;\
191}\
192type* prefix##get_next_##type(CVPOS* pos)\
193{\
194    if(pos->m_pos)\
195    {\
196        ELEMENT_##type* element = (ELEMENT_##type*)(pos->m_pos);\
197        pos->m_pos = element->m_next;\
198        return &element->m_data;\
199    }\
200    else\
201    {\
202        return NULL;\
203    }\
204}\
205type* prefix##get_prev_##type(CVPOS* pos)\
206{\
207    if(pos->m_pos)\
208    {\
209        ELEMENT_##type* element = (ELEMENT_##type*)(pos->m_pos);\
210        pos->m_pos = element->m_prev;\
211        return &element->m_data;\
212    }\
213    else\
214    {\
215        return NULL;\
216    }\
217}\
218int prefix##is_pos_##type(CVPOS pos)\
219{\
220    return !!pos.m_pos;\
221}\
222void prefix##clear_list_##type(_CVLIST* l)\
223{\
224    l->m_head.m_pos = NULL;\
225    l->m_tail.m_pos = NULL;\
226    l->m_size = 0;\
227    l->m_head_free.m_pos = NULL;\
228}\
229CVPOS prefix##add_head_##type(_CVLIST* l, type* data)\
230{\
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));\
236    if(element->m_next)\
237    {\
238        element->m_next->m_prev = element;\
239    }\
240    else\
241    {\
242        l->m_tail.m_pos = element;\
243    }\
244    l->m_head.m_pos = element;\
245    return l->m_head;\
246}\
247CVPOS prefix##add_tail_##type(_CVLIST* l, type* data)\
248{\
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));\
254    if(element->m_prev)\
255    {\
256        element->m_prev->m_next = element;\
257    }\
258    else\
259    {\
260        l->m_head.m_pos = element;\
261    }\
262    l->m_tail.m_pos = element;\
263    return l->m_tail;\
264}\
265void prefix##remove_head_##type(_CVLIST* l)\
266{\
267    ELEMENT_##type* element = ((ELEMENT_##type*)(l->m_head.m_pos));\
268    if(element->m_next != NULL)\
269    {\
270        element->m_next->m_prev = NULL;\
271    }\
272    l->m_head.m_pos = element->m_next;\
273    INSERT_FREE(ELEMENT_##type, l, element);\
274    l->m_size--;\
275}\
276void prefix##remove_tail_##type(_CVLIST* l)\
277{\
278    ELEMENT_##type* element = ((ELEMENT_##type*)(l->m_tail.m_pos));\
279    if(element->m_prev != NULL)\
280    {\
281        element->m_prev->m_next = NULL;\
282    }\
283    l->m_tail.m_pos = element->m_prev;\
284    INSERT_FREE(ELEMENT_##type, l, element);\
285    l->m_size--;\
286}\
287CVPOS prefix##insert_after_##type(_CVLIST* l, CVPOS pos, type* data)\
288{\
289    ELEMENT_##type* element;\
290    ELEMENT_##type* before;\
291    CVPOS newpos;\
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;\
300    else\
301        l->m_tail.m_pos = element;\
302    newpos.m_pos = element;\
303    return newpos;\
304}\
305CVPOS prefix##insert_before_##type(_CVLIST* l, CVPOS pos, type* data)\
306{\
307    ELEMENT_##type* element;\
308    ELEMENT_##type* after;\
309    CVPOS newpos;\
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;\
318    else\
319        l->m_head.m_pos = element;\
320    newpos.m_pos = element;\
321    return newpos;\
322}\
323void prefix##remove_at_##type(_CVLIST* l, CVPOS pos)\
324{\
325    ELEMENT_##type* element = ((ELEMENT_##type*)pos.m_pos);\
326    if(element->m_prev != NULL)\
327    {\
328        element->m_prev->m_next = element->m_next;\
329    }\
330    else\
331    {\
332        l->m_head.m_pos = element->m_next;\
333    }\
334    if(element->m_next != NULL)\
335    {\
336        element->m_next->m_prev = element->m_prev;\
337    }\
338    else\
339    {\
340        l->m_tail.m_pos = element->m_prev;\
341    }\
342    INSERT_FREE(ELEMENT_##type, l, element);\
343    l->m_size--;\
344}\
345void prefix##set_##type(CVPOS pos, type* data)\
346{\
347    ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\
348    memcpy(&(element->m_data), data, sizeof(data));\
349}\
350type* prefix##get_##type(CVPOS pos)\
351{\
352    ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\
353    return &(element->m_data);\
354}\
355int prefix##get_count_##type(_CVLIST* list)\
356{\
357    return list->m_size;\
358}
359
360#define DECLARE_AND_IMPLEMENT_LIST(type, prefix)\
361    DECLARE_LIST(type, prefix)\
362    IMPLEMENT_LIST(type, prefix)
363
364typedef struct __index
365{
366    int value;
367    float rho, theta;
368}
369_index;
370
371DECLARE_LIST( _index, h_ )
372
373#endif/*_CV_LIST_H_*/
374