git.maemo.org Git - opencv/blob - cv/src/_cvlist.h

   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_*/