+++ /dev/null
-/*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_*/