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 60 static const long default_size = 10; 61 static const long default_inc_size = 10; 62 63 struct _pos 64 { 65 void* m_pos; 66 #ifdef _DEBUG 67 struct _list* m_list; 68 #endif /*_DEBUG*/ 69 }; 70 typedef struct _pos CVPOS; 71 struct _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 82 typedef 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 }\ 172 void 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 }\ 184 CVPOS prefix##get_head_pos_##type(_CVLIST* l)\ 185 {\ 186 return l->m_head;\ 187 }\ 188 CVPOS prefix##get_tail_pos_##type(_CVLIST* l)\ 189 {\ 190 return l->m_tail;\ 191 }\ 192 type* 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 }\ 205 type* 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 }\ 218 int prefix##is_pos_##type(CVPOS pos)\ 219 {\ 220 return !!pos.m_pos;\ 221 }\ 222 void 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 }\ 229 CVPOS 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 }\ 247 CVPOS 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 }\ 265 void 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 }\ 276 void 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 }\ 287 CVPOS 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 }\ 305 CVPOS 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 }\ 323 void 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 }\ 345 void 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 }\ 350 type* prefix##get_##type(CVPOS pos)\ 351 {\ 352 ELEMENT_##type* element = ((ELEMENT_##type*)(pos.m_pos));\ 353 return &(element->m_data);\ 354 }\ 355 int 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 364 typedef struct __index 365 { 366 int value; 367 float rho, theta; 368 } 369 _index; 370 371 DECLARE_LIST( _index, h_ ) 372 373 #endif/*_CV_LIST_H_*/ 374
