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