Ring containers source code: ring.c

Hosted by the courtesy of
GitHub

The stars ASAP

Durée du voyage intersidéral

Résolutions de l'ONU en HTML

Bussard Ramjet

DWARF : dwarf2xml

ELF : libelf examples

Code presentation : ctoohtml

file: ring.c

1 /* 2 * Copyright (C) 2008-2009 by Emmanuel Azencot under the GNU LGPL 3 * license version 2.0 or 2.1. You should have received a copy of the 4 * LGPL license along with this library if you did not you can find it 5 * at http://www.gnu.org/. 6 */ 7 /* 8 * Azencot : Wed Nov 12 21:45:57 CET 2008 9 * Creation 10 * Azencot : Tue Nov 18 21:31:30 CET 2008 11 * Add doc++ comments 12 * Azencot : Sat Dec 13 00:20:02 CET 2008 13 * f_ring_off_xxx -> f_ring_xxx 14 */ 15 #define /*X*/ _GNU_SOURCE 16 #include <errno.h> 17 #include <string.h> 18 19 #include "config.h" 20 #include "exception.h" 21 #include "ring.h" 22 23 /** @memo Hold check option. */ 24 static int /*X*/ check_opt; 25 /** @memo Set or get check option. 26 * @doc 27 * The check option provides integrity check on the ring on each call to 28 * API funtions. 29 * @param level (IN) 0 set to disable, 1 enable, -1 read curent value. 30 * @return curent value. 31 */ 32 int /*X*/ f_ring_check_opt(int level) { if ( level != -1 ) check_opt = level; return check_opt; } 33 34 /** @name Ring 35 */ 36 //@{ 37 /** @memo Ring self integrity test 38 * @doc 39 * Walk around the ring to check link ptrs. 40 * In most of the errors situation the functions will not give or even 41 * cleanly return. 42 * @param ring (IN) Ring to be checked 43 * @param offset (IN) offset of structure s_ring 44 * @return 1 if OK, 0 and errno if faulty. 45 * @exception EMLINK null pointer found in ring link. 46 */ 47 bool /*X*/ f_ring_selftest(struct s_ring *ring, size_t offset) { 48 typeof(ring) r; 49 if ( ring == (typeof(ring))offset ) return 1; 50 for ( r = ring; r; r = r->next ) { 51 if ( r == ring ) return 1; 52 } 53 excp_raise (return 0, EMLINK, "nul node found in ring"); 54 } 55 /** @memo Test if an element is in a ring 56 * @doc 57 * Return true if element is in. 58 * @param is (IN) Element to search 59 * @param in (IN) Ring 60 * @param offset (IN) offset of structure s_ring 61 * @return 1 if OK, 0 and errno if faulty. 62 * @exception EFAULT is is nil. 63 * @exception EMLINK null pointer found in ring link. 64 */ 65 bool /*X*/ f_ring_is_in(struct s_ring *is, struct s_ring *in, size_t offset) { 66 typeof(in) r; 67 if ( is == (typeof(in))offset ) excp_raise(return 0, EFAULT, "is, is nil, indeed"); 68 if ( in == (typeof(in))offset ) return 0; 69 if ( check_opt > 0 && !f_ring_selftest(in, offset) ) excp_relay (return 0, " ") ; 70 r = in; 71 do { 72 if ( r == is ) return 1; 73 } while ( r = r->next, r != in ); 74 return 0; 75 } 76 /** @memo Add a new element in the ring. 77 * @doc 78 * Insert a new pearl in a ring. 79 * Return is always valid, even if ring is nil. 80 * Be carefull if new can be nil, as you can lose the ring handle. 81 * @param ring (IN) a pointer to ring part of a ring's node 82 * @param new (IN) a pointer to the ring part of the node 83 * @param offset (IN) the offset of the ring part in the node. 84 * @return 0 the ring is empty, or the next node in the ring. 85 * @exception EEXIST, new is already in ring. 86 * @exception EFAULT new is nil. 87 * @exception EMLINK null pointer found in ring link. 88 */ 89 void * /*X*/ f_ring_link(struct s_ring *ring, struct s_ring *new, size_t offset) { 90 if ( check_opt > 0 && !f_ring_selftest(ring, offset) == 0 ) excp_relay (return 0, "Memory jam"); 91 92 if ( new == (typeof(ring))offset ) excp_raise (return 0, EFAULT, "new node is nil"); 93 if ( check_opt > 0 && f_ring_is_in(new, ring, offset) ) 94 excp_raise (return 0, EEXIST, "node is already in ring"); 95 96 if ( ring == (typeof(ring))offset ) ring = new; 97 98 new->next = ring->next; 99 ring->next = new; 100 101 return new?((char *)new - offset):0; 102 } 103 /** @memo Remove an element from a ring 104 * @doc 105 * The ring is relinked to exclude the element. 106 * Return ptr is 0 if ring becomes empty. 107 * @param node (IN) a pointer to ring part of the node 108 * @param offset (IN) the offset of the ring part in the node. 109 * @return 0 the ring is empty, or the next node in the ring. 110 * @exception EMLINK null pointer found in ring link. 111 */ 112 void * /*X*/ f_ring_unlink(struct s_ring *node, size_t offset) { 113 typeof(node) r; 114 115 if ( check_opt > 0 && !f_ring_selftest(node, offset) == 0) excp_relay (return 0, "Memory jam"); 116 if ( node == (typeof(node))offset ) return 0; 117 if ( node == node->next ) return 0; 118 119 for ( r = node; r->next != node; r = r->next ); 120 r->next = node->next; 121 node->next = 0; 122 123 return r?((char *)r - offset):0; 124 } 125 //@} 126 /** @name Named ring 127 */ 128 //@{ 129 /** @memo Name ring integrity test 130 * @doc 131 * Walk around the ring to check link ptrs. 132 * In most of the errors situation the functions will not give or even 133 * cleanly return. 134 * @param ring (IN) Ring to be checked 135 * @param offset (IN) offset of structure s_ring 136 * @return 1 if OK, 0 and errno if faulty. 137 * @exception EMLINK null pointer found in ring link. 138 */ 139 bool /*X*/ f_nring_selftest(struct s_nring *ring, size_t offset) { 140 typeof(ring) r; 141 if ( ring == (typeof(ring))offset ) return 1; 142 for ( r = ring; r; r = r->next ) { 143 if ( r == ring ) return 1; 144 } 145 excp_raise (return 0, EMLINK, "nul node found in ring"); 146 } 147 /** @memo Test if an element is in a ring 148 * @doc 149 * Return true if element is in. 150 * @param is (IN) Element to search 151 * @param in (IN) Ring 152 * @param offset (IN) offset of structure s_ring 153 * @return 1 if OK, 0 and errno if faulty. 154 * @exception EFAULT is is nil. 155 * @exception EMLINK null pointer found in ring link. 156 */ 157 bool /*X*/ f_nring_is_in(struct s_nring *is, struct s_nring *in, size_t offset) { 158 typeof(in) r; 159 if ( is == (typeof(in))offset ) excp_raise(return 0, EFAULT, "is, is nil, indeed"); 160 if ( in == (typeof(in))offset ) return 0; 161 if ( check_opt > 0 && !f_nring_selftest(in, offset) ) excp_relay (return 0, " ") ; 162 r = in; 163 do { 164 if ( r == is ) return 1; 165 } while ( r = r->next, r != in ); 166 return 0; 167 } 168 /** @memo Find a node in a named ring by its name. 169 * @doc 170 * Names are limited to 1000 bytes. 171 * @param ring (IN) a pointer to ring part of a ring's node 172 * @param name (IN) name to look for 173 * @param offset (IN) the offset of the ring part in the node. 174 * @return 0 the ring is not found, or a node. 175 * @exception EMLINK null pointer found in ring link. 176 */ 177 void * /*X*/ f_nring_find(struct s_nring *ring, const char *name, size_t offset) { 178 typeof(ring) r; 179 if ( check_opt > 0 && !f_nring_selftest(ring, offset) == 0) excp_relay (return 0, " "); 180 if ( ring == (typeof(ring))offset ) return 0; 181 182 for ( r = ring->next; r && strncmp(r->name, name, 1000); r = r->next ) { 183 if ( r == ring ) return 0; 184 } 185 return (r)?((char *)r - offset):0; 186 } 187 /** @memo Add a new element in the ring. 188 * @doc 189 * Insert a new pearl in a ring. 190 * Return is always valid, even if ring is nil. 191 * Be carefull if new can be nil, as you can lose the ring handle. 192 * @param ring (IN) a pointer to ring part of a ring's node 193 * @param new (IN) a pointer to the ring part of the node 194 * @param offset (IN) the offset of the ring part in the node. 195 * @return 0 the ring is empty, or the next node in the ring. 196 * @exception ENOTNAM, Name is nil. 197 * @exception ENAMETOOLONG, Name is too long. 198 * @exception EEXIST, new is already in ring. 199 * @exception EFAULT new is nil. 200 * @exception EMLINK null pointer found in ring link. 201 */ 202 void * /*X*/ f_nring_link(struct s_nring *ring, struct s_nring *new, size_t offset) { 203 if ( check_opt > 0 && !f_nring_selftest(ring, offset) == 0 ) excp_relay (return 0, "Memory jam"); 204 205 if ( new == (typeof(ring))offset ) excp_raise (return 0, EFAULT, "new node is nil"); 206 if ( !new->name ) excp_raise (return 0, ENOTNAM, "new node name is nil"); 207 if ( strnlen(new->name, 1000) == 1000 ) excp_raise (return 0, ENAMETOOLONG, "new node name is too long"); 208 if ( check_opt > 0 && f_nring_is_in(new, ring, offset) ) 209 excp_raise (return 0, EEXIST, "node is already in ring"); 210 if ( f_nring_find(ring, new->name, offset) ) 211 excp_raise(return 0, ENOTUNIQ, "A node named \"%s\" already exists",new->name); 212 213 if ( ring == (typeof(ring))offset ) ring = new; 214 215 new->next = ring->next; 216 ring->next = new; 217 218 return new?((char *)new - offset):0; 219 } 220 /** @memo Remove an element from a ring 221 * @doc 222 * The ring is relinked to exclude the element. 223 * Return ptr is 0 if ring becomes empty. 224 * @param node (IN) a pointer to ring part of the node 225 * @param offset (IN) the offset of the ring part in the node. 226 * @return 0 the ring is empty, or the next node in the ring. 227 * @exception EMLINK null pointer found in ring link. 228 */ 229 void * /*X*/ f_nring_unlink(struct s_nring *node, size_t offset) { 230 typeof(node) r; 231 232 if ( check_opt > 0 && !f_nring_selftest(node, offset) == 0) excp_relay (return 0, "Memory jam"); 233 if ( node == (typeof(node))offset ) return 0; 234 if ( node == node->next ) return 0; 235 236 for ( r = node; r->next != node; r = r->next ); 237 r->next = node->next; 238 239 return r?((char *)r - offset):0; 240 } 241 //@} 242 243 /** @name Double linked ring 244 */ 245 //@{ 246 /** @memo Ring integrity test 247 * @doc 248 * Walk around the ring to check link ptrs. 249 * In most of the errors situation the functions will not give or even 250 * cleanly return. 251 * @param ring (IN) Ring to be checked 252 * @param offset (IN) offset of structure s_ring 253 * @return 1 if OK, 0 and errno if faulty. 254 * @exception EMLINK null pointer found in ring link. 255 */ 256 bool /*X*/ f_dring_selftest(struct s_dring *ring, size_t offset) { 257 typeof(ring) r; 258 259 if ( ring == (typeof(ring))offset ) return 1; 260 261 for ( r = ring; r; r = r->next ) { 262 if ( !r->next ) break; 263 if ( !r->prev ) break; 264 if ( r->next->prev != r || r->prev->next != r) 265 excp_raise (return 0, EMLINK, "Broken link for node %p", r); 266 if ( r == ring ) return 1; 267 } 268 excp_raise (return 0, EMLINK, "Nul link found in node %p", r); 269 } 270 /** @memo Test if an element is in a ring 271 * @doc 272 * Return true if element is in. 273 * @param is (IN) Element to search 274 * @param in (IN) Ring 275 * @param offset (IN) offset of structure s_ring 276 * @return 1 if OK, 0 and errno if faulty. 277 * @exception EFAULT is is nil. 278 * @exception EMLINK null pointer found in ring link. 279 */ 280 bool /*X*/ f_dring_is_in(struct s_dring *is, struct s_dring *in, size_t offset) { 281 typeof(in) r; 282 if ( is == (typeof(in))offset ) excp_raise(return 0, EFAULT, "is, is nil, indeed"); 283 if ( in == (typeof(in))offset ) return 0; 284 if ( check_opt > 0 && !f_dring_selftest(in, offset) ) excp_relay (return 0, " ") ; 285 r = in; 286 do { 287 if ( r == is ) return 1; 288 } while ( r = r->next, r != in ); 289 return 0; 290 } 291 /** @memo Return +/- nth node frome curent 292 * @doc 293 * Provide a abitrary position displacement in a ring. It is probably 294 * usefull only for small values of hop counts (1 or -1), as ring order 295 * does not matter. 296 * @param ring (IN) a pointer to ring part of a ring's node 297 * @param hops (IN) number of hops to move 298 * @param check (IN) Check circular overshoot 299 * @param offset (IN) the offset of the ring part in the node. 300 * @return 0 the ring is empty or check error, node at pos + hops in the ring. 301 * @exception ELOOP Move made a complete loop 302 * @exception EMLINK null pointer found in ring link. 303 */ 304 void * /*X*/ f_dring_move(struct s_dring *ring, int hops, bool check, size_t offset) { 305 typeof(ring) r = ring; 306 307 if ( ring == (typeof(ring))offset || !hops ) return (char *)ring -offset; 308 if ( check_opt > 0 && !f_dring_selftest(ring, offset) ) excp_relay (return 0, " ") ; 309 if ( hops > 0 ) { 310 for ( r = ring->next, --hops; hops; --hops, r = r->next ) { 311 if ( check && r->next == ring ) excp_raise( return (void *) -offset, ELOOP, "Move made a complete loop"); 312 } 313 return (char *)r - offset; 314 } 315 for ( r = ring->prev, ++hops; hops; ++hops, r = r->prev ) { 316 if ( check && r->prev == ring ) excp_raise( return (void *) -offset, ELOOP, "Move made a complete loop"); 317 } 318 return (char *)r - offset; 319 } 320 /** @memo Add a new element in the ring. 321 * @doc 322 * Insert a new pearl in a ring. 323 * Return is always valid, even if ring is nil. 324 * Be carefull if new can be nil, as you can lose the ring handle. 325 * @param ring (IN) a pointer to ring part of a ring's node 326 * @param new (IN) a pointer to the ring part of the node 327 * @param offset (IN) the offset of the ring part in the node. 328 * @return 0 the ring is empty, or the next node in the ring. 329 * @exception EEXIST, new is already in ring. 330 * @exception EFAULT new is nil. 331 * @exception EMLINK null pointer found in ring link. 332 */ 333 void * /*X*/ f_dring_link(struct s_dring *ring, struct s_dring *new, size_t offset) { 334 if ( check_opt > 0 && !f_dring_selftest(ring, offset) == 0 ) excp_relay (return 0, " "); 335 if ( new == (typeof(ring))offset ) excp_raise (return 0, EFAULT, "new node is nil"); 336 if ( check_opt > 0 && f_dring_is_in(new, ring, offset) ) 337 excp_raise (return 0, EEXIST, "node is already in ring"); 338 if ( ring == (typeof(ring))offset ) ring = new; 339 340 new->next = ring->next; 341 new->prev = ring; 342 ring->next = new; 343 new->next->prev = new; 344 345 return new?((char *)new - offset):0; 346 } 347 /** @memo Remove an element from a ring 348 * @doc 349 * The ring is relinked to exclude the element. 350 * Return ptr is 0 if ring becomes empty. 351 * @param node (IN) a pointer to ring part of the node 352 * @param offset (IN) the offset of the ring part in the node. 353 * @return 0 the ring is empty, or the next node in the ring. 354 * @exception EMLINK null pointer found in ring link. 355 */ 356 void * /*X*/ f_dring_unlink(struct s_dring *node, size_t offset) { 357 if ( node == (typeof(node))offset ) return 0; /* node = 0 */ 358 359 /* AZT sam, 09 mai 2009 13:00:46 +0200 360 if ( node == (typeof(node))offset ) return 0; */ 361 if ( check_opt > 0 && !f_dring_selftest(node, offset) == 0) excp_relay (return 0, " "); 362 if ( node == node->next ) return 0; 363 364 node->prev->next = node->next; 365 node->next->prev = node->prev; 366 367 return node?((char *)node->prev - offset):0; 368 } 369 //@} 370 371 /** @name Double linked named ring 372 */ 373 //@{ 374 /** @memo Ring integrity test 375 * @doc 376 * Walk around the ring to check link ptrs. 377 * In most of the errors situation the functions will not give or even 378 * cleanly return. 379 * @param ring (IN) Ring to be checked 380 * @param offset (IN) offset of structure s_ring 381 * @return 1 if OK, 0 and errno if faulty. 382 * @exception EMLINK null pointer found in ring link. 383 */ 384 bool /*X*/ f_ndring_selftest(struct s_ndring *ring, size_t offset) { 385 typeof(ring) r; 386 387 if ( ring == (typeof(ring))offset ) return 1; 388 389 for ( r = ring; r; r = r->next ) { 390 if ( !r->next ) break; 391 if ( !r->prev ) break; 392 if ( r->next->prev != r || r->prev->next != r) 393 excp_raise (return 0, EMLINK, "Broken link for node %p", r); 394 if ( r == ring ) return 1; 395 } 396 excp_raise (return 0, EMLINK, "Nul link found in node %p", r); 397 } 398 /** @memo Test if an element is in a ring 399 * @doc 400 * Return true if element is in. 401 * @param is (IN) Element to search 402 * @param in (IN) Ring 403 * @param offset (IN) offset of structure s_ring 404 * @return 1 if OK, 0 and errno if faulty. 405 * @exception EFAULT is is nil. 406 * @exception EMLINK null pointer found in ring link. 407 */ 408 bool /*X*/ f_ndring_is_in(struct s_ndring *is, struct s_ndring *in, size_t offset) { 409 typeof(in) r; 410 if ( is == (typeof(in))offset ) excp_raise(return 0, EFAULT, "is, is nil, indeed"); 411 if ( in == (typeof(in))offset ) return 0; 412 if ( check_opt > 0 && !f_ndring_selftest(in, offset) ) excp_relay (return 0, " ") ; 413 r = in; 414 do { 415 if ( r == is ) return 1; 416 } while ( r = r->next, r != in ); 417 return 0; 418 } 419 420 /** @memo Return +/- nth node frome curent 421 * @doc 422 * Provide a abritrary position displacement in a ring. It is probably 423 * usefull only for small values of hop counsts (1 or -1), as ring order 424 * does not matter. 425 * @param ring (IN) a pointer to ring part of a ring's node 426 * @param hops (IN) number of hops to move 427 * @param check (IN) Check circular overshoot 428 * @param offset (IN) the offset of the ring part in the node. 429 * @return 0 the ring is empty or check error, node at pos + hops in the ring. 430 * @exception ELOOP Move made a complete loop 431 * @exception EMLINK null pointer found in ring link. 432 */ 433 void * /*X*/ f_ndring_move(struct s_ndring *ring, int hops, bool check, size_t offset) { 434 typeof(ring) r = ring; 435 436 if ( ring == (typeof(ring))offset || !hops ) return (char *)ring -offset; 437 if ( check_opt > 0 && !f_ndring_selftest(ring, offset) ) excp_relay (return 0, " ") ; 438 if ( hops > 0 ) { 439 for ( r = ring->next, --hops; hops; --hops, r = r->next ) { 440 if ( check && r->next == ring ) excp_raise( return (void *) -offset, ELOOP, "Move made a complete loop"); 441 } 442 return (char *)r - offset; 443 } 444 for ( r = ring->prev, ++hops; hops; ++hops, r = r->prev ) { 445 if ( check && r->prev == ring ) excp_raise( return (void *) -offset, ELOOP, "Move made a complete loop"); 446 } 447 return (char *)r - offset; 448 } 449 /** @memo Find a node in a named ring by its name. 450 * @doc 451 * Names are limited to 1000 bytes. 452 * @param ring (IN) a pointer to ring part of a ring's node 453 * @param name (IN) name to look for 454 * @param offset (IN) the offset of the ring part in the node. 455 * @return 0 the ring is not found, or a node. 456 * @exception EMLINK null pointer found in ring link. 457 */ 458 void * /*X*/ f_ndring_find(struct s_ndring *ring, const char *name, size_t offset) { 459 typeof(ring) r; 460 if ( check_opt > 0 && !f_ndring_selftest(ring, offset) == 0) excp_relay (return 0, " "); 461 if ( ring == (typeof(ring))offset ) return 0; 462 463 for ( r = ring->next; r && strncmp(r->name, name, 1000); r = r->next ) { 464 if ( r == ring ) return 0; 465 } 466 return (r)?((char *)r - offset):0; 467 } 468 /** @memo Add a new element in the ring. 469 * @doc 470 * Insert a new pearl in a ring. 471 * Return is always valid, even if ring is nil. 472 * Be carefull if new can be nil, as you can lose the ring handle. 473 * @param ring (IN) a pointer to ring part of a ring's node 474 * @param new (IN) a pointer to the ring part of the node 475 * @param offset (IN) the offset of the ring part in the node. 476 * @return 0 the ring is empty, or the next node in the ring. 477 * @exception ENOTNAM, Name is nil. 478 * @exception ENAMETOOLONG, Name is too long. 479 * @exception EEXIST, new is already in ring. 480 * @exception EFAULT new is nil. 481 * @exception EMLINK null pointer found in ring link. 482 */ 483 void * /*X*/ f_ndring_link(struct s_ndring *ring, struct s_ndring *new, size_t offset) { 484 if ( check_opt > 0 && !f_ndring_selftest(ring, offset) == 0 ) excp_relay (return 0, " "); 485 if ( new == (typeof(ring))offset ) excp_raise (return 0, EFAULT, "new node is nil"); 486 if ( !new->name ) excp_raise (return 0, ENOTNAM, "new node name is nil"); 487 if ( strnlen(new->name, 1000) == 1000 ) excp_raise (return 0, ENAMETOOLONG, "new node name is too long"); 488 if ( check_opt > 0 && f_ndring_is_in(new, ring, offset) ) 489 excp_raise (return 0, EEXIST, "node is already in ring"); 490 if ( f_ndring_find(ring, new->name, offset) ) 491 excp_raise(return 0, ENOTUNIQ, "A node named \"%s\" already exists",new->name); 492 493 if ( ring == (typeof(ring))offset ) ring = new; 494 495 new->next = ring->next; 496 new->prev = ring; 497 ring->next = new; 498 new->next->prev = new; 499 500 return new?((char *)new - offset):0; 501 } 502 /** @memo Remove an element from a ring 503 * @doc 504 * The ring is relinked to exclude the element. 505 * Return ptr is 0 if ring becomes empty. 506 * @param node (IN) a pointer to ring part of the node 507 * @param offset (IN) the offset of the ring part in the node. 508 * @return 0 the ring is empty, or the next node in the ring. 509 * @exception EMLINK null pointer found in ring link. 510 */ 511 void * /*X*/ f_ndring_unlink(struct s_ndring *node, size_t offset) { 512 if ( node == (typeof(node))offset ) node = 0; 513 514 if ( node == (typeof(node))offset ) return 0; 515 if ( check_opt > 0 && !f_ndring_selftest(node, offset) == 0) excp_relay (return 0, " "); 516 if ( node == node->next ) return 0; 517 518 node->prev->next = node->next; 519 node->next->prev = node->prev; 520 521 return node?((char *)node->prev - offset):0; 522 } 523 524 //@} 525