| /*M/////////////////////////////////////////////////////////////////////////////////////// |
| // |
| // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. |
| // |
| // By downloading, copying, installing or using the software you agree to this license. |
| // If you do not agree to this license, do not download, install, |
| // copy or use the software. |
| // |
| // |
| // Intel License Agreement |
| // For Open Source Computer Vision Library |
| // |
| // Copyright (C) 2000, Intel Corporation, all rights reserved. |
| // Third party copyrights are property of their respective owners. |
| // |
| // Redistribution and use in source and binary forms, with or without modification, |
| // are permitted provided that the following conditions are met: |
| // |
| // * Redistribution's of source code must retain the above copyright notice, |
| // this list of conditions and the following disclaimer. |
| // |
| // * Redistribution's 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. |
| // |
| // * The name of Intel Corporation may not be used to endorse or promote products |
| // derived from this software without specific prior written permission. |
| // |
| // This software is provided by the copyright holders 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 Intel Corporation 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. |
| // |
| //M*/ |
| |
| #ifndef _CV_LIST_H_ |
| #define _CV_LIST_H_ |
| |
| #include <stdlib.h> |
| #include <assert.h> |
| |
| #define CV_FORCE_INLINE CV_INLINE |
| |
| #if !defined(_LIST_INLINE) |
| #define _LIST_INLINE CV_FORCE_INLINE |
| #endif /*_LIST_INLINE*/ |
| |
| #if defined DECLARE_LIST |
| #if defined _MSC_VER && _MSC_VER >= 1200 |
| #pragma warning("DECLARE_LIST macro is already defined!") |
| #endif |
| #endif /*DECLARE_LIST*/ |
| |
| static const long default_size = 10; |
| static const long default_inc_size = 10; |
| |
| struct _pos |
| { |
| void* m_pos; |
| #ifdef _DEBUG |
| struct _list* m_list; |
| #endif /*_DEBUG*/ |
| }; |
| typedef struct _pos CVPOS; |
| struct _list |
| { |
| void* m_buffer; |
| void* m_first_buffer; |
| long m_buf_size; /* The size of the buffer */ |
| long m_size; /* The number of elements */ |
| CVPOS m_head; |
| CVPOS m_tail; |
| CVPOS m_head_free; |
| }; |
| |
| typedef struct _list _CVLIST; |
| |
| #define DECLARE_LIST(type, prefix)\ |
| /* Basic element of a list*/\ |
| struct prefix##element_##type\ |
| {\ |
| struct prefix##element_##type* m_prev;\ |
| struct prefix##element_##type* m_next;\ |
| type m_data;\ |
| };\ |
| typedef struct prefix##element_##type ELEMENT_##type;\ |
| /* Initialization and destruction*/\ |
| _LIST_INLINE _CVLIST* prefix##create_list_##type(long);\ |
| _LIST_INLINE void prefix##destroy_list_##type(_CVLIST*);\ |
| /* Access functions*/\ |
| _LIST_INLINE CVPOS prefix##get_head_pos_##type(_CVLIST*);\ |
| _LIST_INLINE CVPOS prefix##get_tail_pos_##type(_CVLIST*);\ |
| _LIST_INLINE type* prefix##get_next_##type(CVPOS*);\ |
| _LIST_INLINE type* prefix##get_prev_##type(CVPOS*);\ |
| /* Modification functions*/\ |
| _LIST_INLINE void prefix##clear_list_##type(_CVLIST*);\ |
| _LIST_INLINE CVPOS prefix##add_head_##type(_CVLIST*, type*);\ |
| _LIST_INLINE CVPOS prefix##add_tail_##type(_CVLIST*, type*);\ |
| _LIST_INLINE void prefix##remove_head_##type(_CVLIST*);\ |
| _LIST_INLINE void prefix##remove_tail_##type(_CVLIST*);\ |
| _LIST_INLINE CVPOS prefix##insert_before_##type(_CVLIST*, CVPOS, type*);\ |
| _LIST_INLINE CVPOS prefix##insert_after_##type(_CVLIST*, CVPOS, type*);\ |
| _LIST_INLINE void prefix##remove_at_##type(_CVLIST*, CVPOS);\ |
| _LIST_INLINE void prefix##set_##type(CVPOS, type*);\ |
| _LIST_INLINE type* prefix##get_##type(CVPOS);\ |
| /* Statistics functions*/\ |
| _LIST_INLINE int prefix##get_count_##type(_CVLIST*); |
| |
| /* This macro finds a space for a new element and puts in into 'element' pointer */ |
| #define INSERT_NEW(element_type, l, element)\ |
| l->m_size++;\ |
| if(l->m_head_free.m_pos != NULL)\ |
| {\ |
| element = (element_type*)(l->m_head_free.m_pos);\ |
| if(element->m_next != NULL)\ |
| {\ |
| element->m_next->m_prev = NULL;\ |
| l->m_head_free.m_pos = element->m_next;\ |
| }\ |
| else\ |
| {\ |
| l->m_head_free.m_pos = NULL;\ |
| }\ |
| }\ |
| else\ |
| {\ |
| if(l->m_buf_size < l->m_size && l->m_head_free.m_pos == NULL)\ |
| {\ |
| *(void**)l->m_buffer = cvAlloc(l->m_buf_size*sizeof(element_type) + sizeof(void*));\ |
| l->m_buffer = *(void**)l->m_buffer;\ |
| *(void**)l->m_buffer = NULL;\ |
| element = (element_type*)((char*)l->m_buffer + sizeof(void*));\ |
| }\ |
| else\ |
| {\ |
| element = (element_type*)((char*)l->m_buffer + sizeof(void*)) + l->m_size - 1;\ |
| }\ |
| } |
| |
| /* This macro adds 'element' to the list of free elements*/ |
| #define INSERT_FREE(element_type, l, element)\ |
| if(l->m_head_free.m_pos != NULL)\ |
| {\ |
| ((element_type*)l->m_head_free.m_pos)->m_prev = element;\ |
| }\ |
| element->m_next = ((element_type*)l->m_head_free.m_pos);\ |
| l->m_head_free.m_pos = element; |
| |
| |
| /*#define GET_FIRST_FREE(l) ((ELEMENT_##type*)(l->m_head_free.m_pos))*/ |
| |
| #define IMPLEMENT_LIST(type, prefix)\ |
| _CVLIST* prefix##create_list_##type(long size)\ |
| {\ |
| _CVLIST* pl = (_CVLIST*)cvAlloc(sizeof(_CVLIST));\ |
| pl->m_buf_size = size > 0 ? size : default_size;\ |
| pl->m_first_buffer = cvAlloc(pl->m_buf_size*sizeof(ELEMENT_##type) + sizeof(void*));\ |
| pl->m_buffer = pl->m_first_buffer;\ |
| *(void**)pl->m_buffer = NULL;\ |
| pl->m_size = 0;\ |
| pl->m_head.m_pos = NULL;\ |
| pl->m_tail.m_pos = NULL;\ |
| pl->m_head_free.m_pos = NULL;\ |
| return pl;\ |
| }\ |
| void prefix##destroy_list_##type(_CVLIST* l)\ |
| {\ |
| void* cur = l->m_first_buffer;\ |
| void* next;\ |
| while(cur)\ |
| {\ |
| next = *(void**)cur;\ |
| cvFree(&cur);\ |
| cur = next;\ |
| }\ |
| cvFree(&l);\ |
| }\ |
| CVPOS prefix##get_head_pos_##type(_CVLIST* l)\ |
| {\ |
| return l->m_head;\ |
| }\ |
| CVPOS prefix##get_tail_pos_##type(_CVLIST* l)\ |
| {\ |
| return l->m_tail;\ |
| }\ |
| type* prefix##get_next_##type(CVPOS* pos)\ |
| {\ |
| if(pos->m_pos)\ |
| {\ |
| ELEMENT_##type* element = (ELEMENT_##type*)(pos->m_pos);\ |
| pos->m_pos = element->m_next;\ |
| return &element->m_data;\ |
| }\ |
| else\ |
| {\ |
| return NULL;\ |
| }\ |
| }\ |
| type* prefix##get_prev_##type(CVPOS* pos)\ |
| {\ |
| if(pos->m_pos)\ |
| {\ |
| ELEMENT_##type* element = (ELEMENT_##type*)(pos->m_pos);\ |
| pos->m_pos = element->m_prev;\ |
| return &element->m_data;\ |
| }\ |
| else\ |
| {\ |
| return NULL;\ |
| }\ |
| }\ |
| int prefix##is_pos_##type(CVPOS pos)\ |
| {\ |
| return !!pos.m_pos;\ |
| }\ |
| void prefix##clear_list_##type(_CVLIST* l)\ |
| {\ |
| l->m_head.m_pos = NULL;\ |
| l->m_tail.m_pos = NULL;\ |
| l->m_size = 0;\ |
| l->m_head_free.m_pos = NULL;\ |
| }\ |
| CVPOS prefix##add_head_##type(_CVLIST* l, type* data)\ |
| {\ |
| ELEMENT_##type* element;\ |
| INSERT_NEW(ELEMENT_##type, l, element);\ |
| element->m_prev = NULL;\ |
| element->m_next = (ELEMENT_##type*)(l->m_head.m_pos);\ |
| memcpy(&(element->m_data), data, sizeof(*data));\ |
| if(element->m_next)\ |
| {\ |
| element->m_next->m_prev = element;\ |
| }\ |
| else\ |
| {\ |
| l->m_tail.m_pos = element;\ |
| }\ |
| l->m_head.m_pos = element;\ |
| return l->m_head;\ |
| }\ |
| CVPOS prefix##add_tail_##type(_CVLIST* l, type* data)\ |
| {\ |
| ELEMENT_##type* element;\ |
| INSERT_NEW(ELEMENT_##type, l, element);\ |
| element->m_next = NULL;\ |
| element->m_prev = (ELEMENT_##type*)(l->m_tail.m_pos);\ |
| memcpy(&(element->m_data), data, sizeof(*data));\ |
| if(element->m_prev)\ |
| {\ |
| element->m_prev->m_next = element;\ |
| }\ |
| else\ |
| {\ |
| l->m_head.m_pos = element;\ |
| }\ |
| l->m_tail.m_pos = element;\ |
| return l->m_tail;\ |
| }\ |
| void prefix##remove_head_##type(_CVLIST* l)\ |
| {\ |
| ELEMENT_##type* element = ((ELEMENT_##type*)(l->m_head.m_pos));\ |
| if(element->m_next != NULL)\ |
| {\ |
| element->m_next->m_prev = NULL;\ |
| }\ |
| l->m_head.m_pos = element->m_next;\ |
| INSERT_FREE(ELEMENT_##type, l, element);\ |
| l->m_size--;\ |
| }\ |
| void prefix##remove_tail_##type(_CVLIST* l)\ |
| {\ |
| ELEMENT_##type* element = ((ELEMENT_##type*)(l->m_tail.m_pos));\ |
| if(element->m_prev != NULL)\ |
| {\ |
| element->m_prev->m_next = NULL;\ |
| }\ |
| l->m_tail.m_pos = element->m_prev;\ |
| INSERT_FREE(ELEMENT_##type, l, element);\ |
| l->m_size--;\ |
| }\ |
| CVPOS prefix##insert_after_##type(_CVLIST* l, CVPOS pos, type* data)\ |
| {\ |
| ELEMENT_##type* element;\ |
| ELEMENT_##type* before;\ |
| CVPOS newpos;\ |
| INSERT_NEW(ELEMENT_##type, l, element);\ |
| memcpy(&(element->m_data), data, sizeof(*data));\ |
| before = (ELEMENT_##type*)pos.m_pos;\ |
| element->m_prev = before;\ |
| element->m_next = before->m_next;\ |
| before->m_next = element;\ |
| if(element->m_next != NULL)\ |
| element->m_next->m_prev = element;\ |
| else\ |
| l->m_tail.m_pos = element;\ |
| newpos.m_pos = element;\ |
| return newpos;\ |
| }\ |
| CVPOS prefix##insert_before_##type(_CVLIST* l, CVPOS pos, type* data)\ |
| {\ |
| ELEMENT_##type* element;\ |
| ELEMENT_##type* after;\ |
| CVPOS newpos;\ |
| INSERT_NEW(ELEMENT_##type, l, element);\ |
| memcpy(&(element->m_data), data, sizeof(*data));\ |
| after = (ELEMENT_##type*)pos.m_pos;\ |
| element->m_prev = after->m_prev;\ |
| element->m_next = after;\ |
| after->m_prev = element;\ |
| if(element->m_prev != NULL)\ |
| element->m_prev->m_next = element;\ |
| else\ |
| l->m_head.m_pos = element;\ |
| newpos.m_pos = element;\ |
| return newpos;\ |
| }\ |
| void prefix##remove_at_##type(_CVLIST* l, CVPOS pos)\ |
| {\ |
| ELEMENT_##type* element = ((ELEMENT_##type*)pos.m_pos);\ |
| if(element->m_prev != NULL)\ |
| {\ |
| element->m_prev->m_next = element->m_next;\ |
| }\ |
| else\ |
| {\ |
| l->m_head.m_pos = element->m_next;\ |
| }\ |
| if(element->m_next != NULL)\ |
| {\ |
| element->m_next->m_prev = element->m_prev;\ |
| }\ |
| else\ |
| {\ |
| l->m_tail.m_pos = element->m_prev;\ |
| }\ |
| INSERT_FREE(ELEMENT_##type, l, element);\ |
| l->m_size--;\ |
| }\ |
| void prefix##set_##type(CVPOS pos, type* data)\ |
| {\ |
| ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\ |
| memcpy(&(element->m_data), data, sizeof(data));\ |
| }\ |
| type* prefix##get_##type(CVPOS pos)\ |
| {\ |
| ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\ |
| return &(element->m_data);\ |
| }\ |
| int prefix##get_count_##type(_CVLIST* list)\ |
| {\ |
| return list->m_size;\ |
| } |
| |
| #define DECLARE_AND_IMPLEMENT_LIST(type, prefix)\ |
| DECLARE_LIST(type, prefix)\ |
| IMPLEMENT_LIST(type, prefix) |
| |
| typedef struct __index |
| { |
| int value; |
| float rho, theta; |
| } |
| _index; |
| |
| DECLARE_LIST( _index, h_ ) |
| |
| #endif/*_CV_LIST_H_*/ |