410 ptrdiff_t loc_next |
410 ptrdiff_t loc_next |
411 ); |
411 ); |
412 |
412 |
413 /** |
413 /** |
414 * Describes a function that creates a tree node from the specified data. |
414 * Describes a function that creates a tree node from the specified data. |
415 */ |
415 * The first argument points to the data the node shall contain and |
416 typedef void (*cx_tree_node_create_fun)(void const*); |
416 * the second, optional, argument points to an existing node that already |
417 |
417 * contains the data. |
418 __attribute__((__nonnull__)) |
418 * The third argument may be used for additional data (e.g. an allocator). |
|
419 * Functions of this type shall either return a new pointer to a newly |
|
420 * created node, a pointer to the existing node, or \c NULL when allocation |
|
421 * fails. |
|
422 * Returning a pointer to the existing node means, that the function decides |
|
423 * not to create a new node for the data and that the caller shall continue to |
|
424 * use the existing node. |
|
425 */ |
|
426 typedef void (*cx_tree_node_create_func)(void const *, void const *, void *); |
|
427 |
|
428 /** |
|
429 * The local search depth for a new subtree when adding multiple elements. |
|
430 * The default value is 3. |
|
431 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to |
|
432 * implement optimized insertion of multiple elements into a tree. |
|
433 */ |
|
434 extern unsigned int cx_tree_add_look_around_depth; |
|
435 |
|
436 /** |
|
437 * Adds multiple elements efficiently to a tree. |
|
438 * |
|
439 * This function returns the number of elements successfully obtained from the |
|
440 * iterator, which is not necessarily the number of new nodes created (depending |
|
441 * on the implementation of \p cfunc). |
|
442 * |
|
443 * Once an element cannot be added to the tree, this function returns, leaving |
|
444 * the iterator in a valid state pointing to the element that could not be |
|
445 * added. |
|
446 * |
|
447 * The advantage of this function compared to multiple invocations of |
|
448 * #cx_tree_add() is that the search for the insert locations is not always |
|
449 * started from the root node. |
|
450 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes |
|
451 * of the current insert location before starting from the root node again. |
|
452 * When the variable is set to zero, only the last found location is checked |
|
453 * again. |
|
454 * |
|
455 * Refer to the documentation of #cx_tree_add() for more details. |
|
456 * |
|
457 * @param iter a pointer to an arbitrary iterator |
|
458 * @param sfunc a search function |
|
459 * @param cfunc a node creation function |
|
460 * @param cdata optional additional data |
|
461 * @param root the location where a pointer to the root node is stored |
|
462 * @param loc_parent offset in the node struct for the parent pointer |
|
463 * @param loc_children offset in the node struct for the children linked list |
|
464 * @param loc_last_child optional offset in the node struct for the pointer to |
|
465 * the last child in the linked list (negative if there is no such pointer) |
|
466 * @param loc_prev offset in the node struct for the prev pointer |
|
467 * @param loc_next offset in the node struct for the next pointer |
|
468 * @return the number of elements obtained from the iterator |
|
469 * @see cx_tree_add() |
|
470 */ |
|
471 __attribute__((__nonnull__(1, 2, 3, 5))) |
419 size_t cx_tree_add_iter( |
472 size_t cx_tree_add_iter( |
420 struct cx_iterator_base_s *iter, |
473 struct cx_iterator_base_s *iter, |
421 cx_tree_search_func sfunc, |
474 cx_tree_search_func sfunc, |
422 cx_tree_node_create_fun cfunc, |
475 cx_tree_node_create_func cfunc, |
|
476 void *cdata, |
423 void **root, |
477 void **root, |
424 ptrdiff_t loc_parent, |
478 ptrdiff_t loc_parent, |
425 ptrdiff_t loc_children, |
479 ptrdiff_t loc_children, |
|
480 ptrdiff_t loc_last_child, |
426 ptrdiff_t loc_prev, |
481 ptrdiff_t loc_prev, |
427 ptrdiff_t loc_next |
482 ptrdiff_t loc_next |
428 ); |
483 ); |
429 |
484 |
430 __attribute__((__nonnull__)) |
485 /** |
|
486 * Adds multiple elements efficiently to a tree. |
|
487 * |
|
488 * This function returns the number of elements successfully processed which |
|
489 * is not necessarily the number of new nodes created (depending on the |
|
490 * implementation of \p cfunc). |
|
491 * |
|
492 * Once an element cannot be added to the tree, this function returns. |
|
493 * That means, the integer \c n returned by this function means, that the first |
|
494 * \c n elements of \p src will be definitely in the tree. |
|
495 * |
|
496 * The advantage of this function compared to multiple invocations of |
|
497 * #cx_tree_add() is that the search for the insert locations is not always |
|
498 * started from the root node. |
|
499 * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes |
|
500 * of the current insert location before starting from the root node again. |
|
501 * When the variable is set to zero, only the last found location is checked |
|
502 * again. |
|
503 * |
|
504 * Refer to the documentation of #cx_tree_add() for more details. |
|
505 * |
|
506 * @param src a pointer to the source data array |
|
507 * @param num the number of elements in the \p src array |
|
508 * @param elem_size the size of each element in the \p src array |
|
509 * @param sfunc a search function |
|
510 * @param cfunc a node creation function |
|
511 * @param cdata optional additional data |
|
512 * @param root the location where a pointer to the root node is stored |
|
513 * @param loc_parent offset in the node struct for the parent pointer |
|
514 * @param loc_children offset in the node struct for the children linked list |
|
515 * @param loc_last_child optional offset in the node struct for the pointer to |
|
516 * the last child in the linked list (negative if there is no such pointer) |
|
517 * @param loc_prev offset in the node struct for the prev pointer |
|
518 * @param loc_next offset in the node struct for the next pointer |
|
519 * @return the number of array elements successfully processed |
|
520 * @see cx_tree_add() |
|
521 */ |
|
522 __attribute__((__nonnull__(1, 4, 5, 7))) |
431 size_t cx_tree_add_array( |
523 size_t cx_tree_add_array( |
432 void const *src, |
524 void const *src, |
433 size_t num, |
525 size_t num, |
434 size_t elem_size, |
526 size_t elem_size, |
435 cx_tree_search_func sfunc, |
527 cx_tree_search_func sfunc, |
436 cx_tree_node_create_fun cfunc, |
528 cx_tree_node_create_func cfunc, |
|
529 void *cdata, |
437 void **root, |
530 void **root, |
438 ptrdiff_t loc_parent, |
531 ptrdiff_t loc_parent, |
439 ptrdiff_t loc_children, |
532 ptrdiff_t loc_children, |
|
533 ptrdiff_t loc_last_child, |
440 ptrdiff_t loc_prev, |
534 ptrdiff_t loc_prev, |
441 ptrdiff_t loc_next |
535 ptrdiff_t loc_next |
442 ); |
536 ); |
443 |
537 |
444 __attribute__((__nonnull__)) |
538 /** |
|
539 * Adds data to a tree. |
|
540 * |
|
541 * An adequate location where to add the new tree node is searched with the |
|
542 * specified \p sfunc. |
|
543 * |
|
544 * When a location is found, the \p cfunc will be invoked with \p cdata and, |
|
545 * in case \p sfunc returned a direct match, the already found node. |
|
546 * |
|
547 * If \p cfunc returns a new node pointer, it will be linked into the tree. |
|
548 * Otherwise, this function just returns the found node. |
|
549 * |
|
550 * This function may return \c NULL when \p cfunc tries to allocate a new node |
|
551 * but fails to do so. |
|
552 * |
|
553 * The \p root argument shall point to a location where the pointer to the root |
|
554 * node is stored. The pointer to the root node may be \c NULL in which case |
|
555 * this function will instantly create a new node and write the location to |
|
556 * \p root. On the other hand, if \p sfunc returns a negative integer for |
|
557 * \c *root, the newly created node will be the new root node. |
|
558 * |
|
559 * Multiple elements can be added more efficiently with |
|
560 * #cx_tree_add_array() or #cx_tree_add_iter(). |
|
561 * |
|
562 * @param src a pointer to the data |
|
563 * @param sfunc a search function |
|
564 * @param cfunc a node creation function |
|
565 * @param cdata optional additional data |
|
566 * @param root the location where a pointer to the root node is stored |
|
567 * @param loc_parent offset in the node struct for the parent pointer |
|
568 * @param loc_children offset in the node struct for the children linked list |
|
569 * @param loc_last_child optional offset in the node struct for the pointer to |
|
570 * the last child in the linked list (negative if there is no such pointer) |
|
571 * @param loc_prev offset in the node struct for the prev pointer |
|
572 * @param loc_next offset in the node struct for the next pointer |
|
573 * @return a pointer to the new node, to an existing node, or \c NULL |
|
574 */ |
|
575 __attribute__((__nonnull__(1, 2, 3, 5))) |
445 void *cx_tree_add( |
576 void *cx_tree_add( |
446 void const *src, |
577 void const *src, |
447 cx_tree_search_func sfunc, |
578 cx_tree_search_func sfunc, |
448 cx_tree_node_create_fun cfunc, |
579 cx_tree_node_create_func cfunc, |
|
580 void *cdata, |
449 void **root, |
581 void **root, |
450 ptrdiff_t loc_parent, |
582 ptrdiff_t loc_parent, |
451 ptrdiff_t loc_children, |
583 ptrdiff_t loc_children, |
|
584 ptrdiff_t loc_last_child, |
452 ptrdiff_t loc_prev, |
585 ptrdiff_t loc_prev, |
453 ptrdiff_t loc_next |
586 ptrdiff_t loc_next |
454 ); |
587 ); |
455 |
588 |
456 #ifdef __cplusplus |
589 #ifdef __cplusplus |