Parent Directory
| 
Revision Log
| 
Revision Graph
* g2.c 67% done. * ext_rnode merged in rnode_list of 2radar.c * gnode2ip redesigned * (de)allocation functions for gmaps and ext-maps * fixed array_grow()
1 /* This file is part of Netsukuku 2 * (c) Copyright 2005 Andrea Lo Pumo aka AlpT <alpt@freaknet.org> 3 * 4 * This source code is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License as published 6 * by the Free Software Foundation; either version 2 of the License, 7 * or (at your option) any later version. 8 * 9 * This source code is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 12 * Please refer to the GNU Public License for more details. 13 * 14 * You should have received a copy of the GNU Public License along with 15 * this source code; if not, write to: 16 * Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 17 * 18 * -- 19 * buffer.c 20 * 21 * Various functions to manipulate buffers and arrays (see {-bufarr_t-}). 22 */ 23 24 #ifndef BUFFER_H 25 #define BUFFER_H 26 27 /* 28 * In bzero(3): 29 * <<4.3BSD. This function [bzero] is deprecated -- use memset in new 30 * programs.>> 31 */ 32 #define setzero(_p, _sz) memset((_p), 0, (_sz)) 33 34 /*\ 35 * 36 * Buffer macros 37 * ============= 38 * 39 * The following macros are used to put/get data in a buffer. 40 * 41 \*/ 42 43 44 /* 45 * memput 46 * 47 * It copies `__sz' bytes from `__src' to `__dst' and then increments the `__dst' 48 * pointer of `__sz' bytes. 49 * 50 * The incremented `__dst' pointer is returned. 51 * 52 * Note: you can also use side expression, f.e. 53 * memput(buf++, src, (size+=sizeof(src)); 54 */ 55 #define memput(__dst, __src, __sz) \ 56 ({ \ 57 void **_mp_pdst=(void **)&(__dst); \ 58 void *_mp_dst=*_mp_pdst, *_mp_src=(__src); \ 59 size_t _mp_sz=(size_t)(__sz); \ 60 \ 61 memcpy(_mp_dst, _mp_src, _mp_sz); \ 62 (*_mp_pdst)+=(_mp_sz); \ 63 _mp_dst; \ 64 }) 65 66 /* 67 * memget 68 * 69 * the same of memput(), but it increments `__src' instead. 70 * 71 * The incremented `__src' pointer is returned. 72 */ 73 #define memget(__dst, __src, __sz) \ 74 ({ \ 75 void **_mp_psrc=(void **)&(__src); \ 76 void *_mp_dst=(__dst), *_mp_src=*_mp_psrc; \ 77 size_t _mp_sz=(size_t)(__sz); \ 78 \ 79 memcpy(_mp_dst, _mp_src, _mp_sz); \ 80 (*_mp_psrc)+=(_mp_sz); \ 81 _mp_src; \ 82 }) 83 84 /* use of hardcoded `_src' and `_dst' variable names */ 85 #define bufput(_src, _sz) (memput(buf, (_src), (_sz))) 86 #define bufget(_dst, _sz) (memget((_dst), buf, (_sz))) 87 88 89 90 /*\ 91 * 92 * Buffer Array |{bufarr_t}| 93 * ============ 94 * 95 * A buffer array is defined by these three elements: 96 * 97 * atype *buf, int nmemb, int nalloc 98 * 99 * `atype' is the type the elements of the array, f.e. it can be "int", 100 * "double" or whatever. 101 * 102 * `buf' is the pointer to the start of the array, i.e. the first element. 103 * 104 * `nmemb' is the number of elements stored in the array. buf[*nmemb-1] is the 105 * last one. 106 * 107 * `nalloc' is the number of allocated elements of the array. It can be 108 * greater than `nmemb'. 109 * 110 * 111 * The macros defined below are used to manipulate a buffer array. Their 112 * generic prototype is: 113 * 114 * atype **_buf, int *_nmemb, int *_nalloc 115 * 116 * Where `_buf' is a pointer to a `buf' pointer described above. 117 * `_nmemb' is a pointer to a `nmemb' variable, 118 * `_nalloc' is a pointer to a `nalloc' variable. 119 * Note that a macro may modify `*_buf', `*_nmemb' or `*_nalloc'. 120 * 121 * 122 * WARNING: do not use expression as arguments to these macros. For example, 123 * DO NOT use array_replace(.., pos++, ...), but instead 124 * array_replace(.., pos, ...); pos++; 125 * 126 * Optional arguments 127 * ------------------ 128 * 129 * `_nmemb' and `_nalloc' must to two different variables. 130 * If you don't want to specify `_nalloc', set it to 0. 131 * If the `nalloc' argument passed to a macro is set to 0, then 132 * the macro will assume that *nmemb == *nalloc and it will only 133 * modify `*nmemb'. 134 * 135 * Notes on loops and buffer deletion 136 * ---------------------------------- 137 * 138 * Consider the following loop: 139 * 140 * for(i=0; i<nmembs; i++) 141 * * Remove buffer[i] 142 * array_del(&buffer, &nmembs, i); 143 * 144 * What will happen? 145 * The loop will skip over some elements. That's why: 146 * 147 * the loop starts; 148 * i=0; 149 * buffer[0] is removed: 150 * 151 * the array is shifted to the left by one: 152 * buffer[1] replaces buffer[0], 153 * buffer[2] replaces buffer[1], 154 * and so on... until 155 * buffer[nmembs-1] replaces buffer[nmembs-2] 156 * 157 * nmembs is decremented by one 158 * 159 * the loop continues; 160 * i=1; 161 * [!] buffer[1] is removed, however buffer[1] was substituted with 162 * buffer[2]! Thus, the original buffer[1] is not removed. 163 * 164 * ... 165 * 166 * The correct loop is: 167 * 168 * 169 * for(i=0; i<nmembs; i++) { 170 * * Remove buffer[i] 171 * array_del(&buffer, &nmembs, i); 172 * * Adjust the index 173 * i--; 174 * } 175 * 176 * Note also that `nmembs' is modified during the call to `array_del'. 177 * 178 * If you want to simply destroy the array, use {-array_destroy-} 179 \*/ 180 181 /* 182 * array_replace 183 * ------------- 184 * 185 * Copies the data pointed by _new to (*_buf)[_pos] and returns &(*_buf)[pos] 186 * Note: `_pos' must be < `*nalloc', otherwise an overflow will occur. 187 * 188 * Usage: 189 * array_replace(&buf_array_ptr, pos, new_element_ptr); 190 */ 191 #define array_replace(_buf, _pos, _new) \ 192 ({ \ 193 void *_ar_ptr=(*(_buf))[(_pos)]; \ 194 memcpy(_ar_ptr, (_new), sizeof(typeof(*(_new)))); \ 195 (typeof(*(_buf)) _ar_ptr; \ 196 }) 197 198 /* 199 * array_insert 200 * ------------ 201 * 202 * The same of {-array_replace-}, but with an additional check. 203 * :fatal(): is called if _pos is greater than *_nalloc 204 * 205 * Usage: 206 * array_insert(&buf_array_ptr, &nalloc_var, new_elem_ptr); 207 */ 208 #define array_insert(_buf, _nalloc, _pos, _new) \ 209 ({ \ 210 if(_pos >= *(_nalloc) || _pos < 0) \ 211 fatal(ERROR_MSG"Array overflow: _nalloc %d, _pos %d", \ 212 ERROR_POS, _nalloc, _pos); \ 213 \ 214 array_replace(_buf, _pos, _new); \ 215 }) 216 217 218 /* 219 * array_grow 220 * ---------- 221 * 222 * It enlarges the array by allocating `_count' elements and appending them at 223 * its end. 224 * `*_nalloc' is incremented and `*_buf' is set to point to the new start of the 225 * array (since :xrealloc(): is used). 226 * 227 * If `_count' is zero, then the array will be shrinked/enlarged to exactly 228 * `*_nalloc' elements. 229 * 230 * Note: if `_count' is a negative value and _nalloc-_count >= 0, then 231 * the array is shrinked (see {-array_shrink-}). 232 * 233 * Usage: 234 * array_grow(&buf_array_ptr, &nalloc_var, count); 235 * or 236 * array_grow(&buf_array_ptr, &nalloc_var, 0); 237 */ 238 #define array_grow(_buf, _nalloc, _count) \ 239 do { \ 240 (*_nalloc)+=(_count); \ 241 if((*_nalloc) < 0) \ 242 fatal(ERROR_MSG"Array underflow: _count %d", \ 243 ERROR_POS, _count); \ 244 *(_buf)=xrealloc(*(_buf), sizeof(typeof(**(_buf)))*(*_nalloc)); \ 245 } while(0) 246 247 /* 248 * array_shrink 249 * ------------ 250 * 251 * Deallocates and destroys the last `_count' elements of the array. 252 * `*_buf' is set to point to the new start of the array (since :xrealloc(): 253 * is used). 254 * 255 * Usage: 256 * array_shrink(&buf_array_ptr, &nmemb_var, &nalloc_var, count); 257 */ 258 #define array_shrink(_buf, _nalloc, _count) \ 259 array_grow(_buf, _nalloc, -abs(_count)) 260 261 262 /* 263 * Trick to handle NULL pointers. 264 * If you want to understand it, see where it is 265 * used: {-__array_fake_nalloc:"r-} 266 */ 267 #define __array_fake_nalloc(__nmemb, __nalloc) \ 268 typeof(__nmemb) _ag_na = (__nalloc); \ 269 typeof(*(__nmemb)) _ag_fake_na; \ 270 if(!_ag_na) { \ 271 _ag_fake_na = *(__nmemb); \ 272 _ag_na = &_ag_fake_na; \ 273 } 274 275 /* 276 * Private macro. See {-array_add-} and {-array_add_more-} below. 277 */ 278 #define array_add_grow(_buf, _nmemb, _nalloc, _new, _newalloc) \ 279 ({ \ 280 __array_fake_nalloc(_nmemb, _nalloc); \ 281 \ 282 (*(_nmemb))++; \ 283 \ 284 if(*(_nmemb) > *(_ag_na)) \ 285 array_grow(_buf, _ag_na, _newalloc); \ 286 \ 287 array_replace(_buf, (*(_nmemb))-1, _new); \ 288 )} 289 290 291 /* 292 * array_add 293 * --------- 294 * 295 * Adds a new element at the end of the array and copies in it 296 * the data pointed by `_new'. 297 * 298 * `*_nmemb' is always incremented by one. If necessary, a new 299 * element is allocated at the end of the array and `*_nalloc' is incremented 300 * by one. 301 * 302 * The pointer to the new inserted element is returned. 303 * 304 * Exception: 305 * if the `_nalloc' argument is set to 0, then this macro will assume that 306 * `*_nmemb' == `*_nalloc', and only `*_nmemb' will be incremented. 307 * 308 * Usage: 309 * array_add(&buf_array_ptr, &nmemb_var, &nalloc_var, new_elem_ptr); 310 * or 311 * array_add(&buf_array_ptr, &nmemb_var, 0, new_element_ptr); 312 */ 313 #define array_add(_buf, _nmemb, _nalloc, _new) \ 314 array_add_grow(_buf, _nmemb, _nalloc, _new, 1) 315 316 /* 317 * array_add_more 318 * -------------- 319 * 320 * The same of {-array_add-}, but instead of allocating just one new element, it 321 * allocates _nmemb/2+1 elements. 322 * This is useful if array_add_more() is called many times. 323 */ 324 #define array_add_more(_buf, _nmemb, _nalloc, _new) \ 325 array_add_grow(_buf, _nmemb, _nalloc, _new, (_nmemb)/2+1) 326 327 328 /* 329 * array_del 330 * --------- 331 * 332 * Deletes the element at position `_pos'. 333 * The element is deleted by copying the last element of the array over it, 334 * i.e. we copy (*_buf)[*_nmemb-1] over (*_buf)[_pos]. In this way, the last 335 * element of the array is reusable. 336 * `*_nmemb' is decremented by one. 337 * 338 * Note that this macro doesn't deallocate anything, see {-array_del_free-} for 339 * that. 340 * 341 * If `_pos' isn't a valid value, an array overflow occurs and :fatal(): is 342 * called. 343 */ 344 #define array_del(_buf, _nmemb, _pos) \ 345 do { \ 346 if(_pos >= *(_nmemb) || _pos < 0) \ 347 fatal(ERROR_MSG "Array overflow: _nmemb %d, _pos %d", \ 348 ERROR_POS, *(_nmemb), *(_pos)); \ 349 (*(_nmemb))--; \ 350 if(_pos < *(_nmemb)) \ 351 memcpy( (*(_buf))[(_pos)], (*(_buf))[*(_nmemb)], \ 352 sizeof(typeof(**(_buf))) ); \ 353 } while(0) 354 355 356 /* 357 * array_del_free 358 * -------------- 359 * 360 * The same of {-array_del-}, but deallocates one element from the array. 361 * `*_buf' is set to point to the new start of the array (since :xrealloc(): 362 * is used). 363 * 364 * Exception: 365 * if the `_nalloc' argument is set to 0, then this macro will assume that 366 * `*_nmemb' == `*_nalloc', and only `*_nmemb' will be decremented. 367 * 368 * Usage: 369 * array_del_free(&buf_array_ptr, &nmemb_var, &nalloc_var, pos); 370 * or 371 * array_del_free(&buf_array_ptr, &nmemb_var, 0, pos); 372 */ 373 #define array_del_free(_buf, _nmemb, _nalloc, _pos) \ 374 do { \ 375 __array_fake_nalloc(_nmemb, _nalloc); \ 376 \ 377 array_del(_buf, _nmemb, _pos); \ 378 array_shrink(_buf, _ag_na, 1); \ 379 } while(0) 380 381 /* 382 * array_rem 383 * --------- 384 * 385 * Deletes the element at position `_pos'. 386 * The element is deleted by shifting to the left all its successive elements. 387 * In this way, the order of the array is preserved. 388 * This is useful if the array has been ordered with qsort(3), however this is 389 * less efficient than {-array_del-}. 390 * 391 * Note that this macro doesn't deallocate anything, see {-array_rem_free-} for 392 * that. Moreover, once the array is shifted, the data stored in 393 * (*_buf)[*_nmemb] is not touched. You may want to zero it. Example: 394 * 395 * array_rem(&buf_array_ptr, &nmemb_var, pos); 396 * setzero( buf_array_ptr[nmemb_var], sizeof(typeof(*buf_array_ptr)) ); 397 * 398 * If `_pos' isn't a valid value, an array overflow occurs and :fatal(): is 399 * called. 400 */ 401 #define array_rem(_buf, _nmemb, _pos) \ 402 do { \ 403 if(_pos >= *(_nmemb) || _pos < 0) \ 404 fatal(ERROR_MSG"Array overflow: _nmemb %d, _pos %d", \ 405 ERROR_POS, *(_nmemb), _pos); \ 406 /* Shift the array */ \ 407 if(_pos < (*(_nmemb))-1) \ 408 memmove( &(*(_buf))[_pos], &(*(_buf))[_pos+1], \ 409 sizeof(typeof(**(_buf))) * ((*(_nmemb))-_pos-1)); \ 410 (*(_nmemb))--; \ 411 } while(0) 412 413 /* 414 * array_rem_free 415 * -------------- 416 * 417 * The same of {-array_rem-}, but deallocates one element from the array. 418 * `*_buf' is set to point to the new start of the array (since :xrealloc(): 419 * is used). 420 */ 421 #define array_rem_free(_buf, _nmemb, _nalloc, _pos) \ 422 do { \ 423 __array_fake_nalloc(_nmemb, _nalloc); \ 424 array_rem(_buf, _nmemb, _pos); \ 425 array_shrink(_buf, _ag_na, 1); \ 426 } while(0) 427 428 /* 429 * array_destroy 430 * ------------- 431 * 432 * Deallocates the whole array and sets `*_nmemb', `*_nalloc' to zero. 433 * 434 * `_nmemb' or `_nalloc' can be 0. 435 * 436 * Usage: 437 * array_destroy(&buf_array_ptr, &nmemb_var, &nalloc_var); 438 * or 439 * array_destroy(&buf_array_ptr, 0, 0); 440 */ 441 #define array_destroy(_buf, _nmemb, _nalloc) \ 442 do { \ 443 if( *(_buf) && (!(_nmemb) || *(_nmemb) > 0) ) \ 444 xfree(*(_buf)); \ 445 _nmemb && *(_nmemb)=0; \ 446 _nalloc && *(_nalloc)=0; \ 447 } while(0) 448 449 /* 450 * array_bzero 451 * ----------- 452 * 453 * Sets `_count' elements of the array to 0. 454 * If `_count' == -1, then the whole array is zeroed. 455 * If `_count' > `*_nalloc', :fatal(): is called. 456 * 457 * Usage: 458 * array_bzero(&buf_array_ptr, &nalloc_var, count); 459 * or 460 * array_bzero(&buf_array_ptr, &nalloc_var, -1); 461 */ 462 #define array_bzero(_buf, _nalloc, _count) \ 463 do { \ 464 if((_count) > *(_nalloc)) \ 465 fatal(ERROR_MSG "Array overflow: _count %d", \ 466 ERROR_POS, (_count)); \ 467 \ 468 setzero(*(_buf), sizeof(typeof(**(_buf))) * \ 469 (_count == -1 ? *(_nalloc) : _count) ); \ 470 } while(0) 471 472 473 /*\ 474 * * * * Functions declaration * * * 475 \*/ 476 int is_bufzero(const void *a, int sz); 477 478 #endif /*BUFFER_H*/
| alpt (at) freaknet (dot) org | ViewVC Help |
| Powered by ViewVC 1.1-dev |