summaryrefslogtreecommitdiff
path: root/apps/plugins/pdbox/dbestfit-3.3/bysize.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/pdbox/dbestfit-3.3/bysize.c')
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/bysize.c424
1 files changed, 0 insertions, 424 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bysize.c b/apps/plugins/pdbox/dbestfit-3.3/bysize.c
index 6808406dbc..85dc327491 100644
--- a/apps/plugins/pdbox/dbestfit-3.3/bysize.c
+++ b/apps/plugins/pdbox/dbestfit-3.3/bysize.c
@@ -422,427 +422,3 @@ void print_sizes(void)
422} 422}
423 423
424#endif 424#endif
425/*****************************************************************************
426 *
427 * Size-sorted list/tree functions.
428 *
429 * Author: Daniel Stenberg
430 * Date: March 7, 1997
431 * Version: 2.0
432 * Email: Daniel.Stenberg@sth.frontec.se
433 *
434 *
435 * v2.0
436 * - Added SPLAY TREE functionality.
437 *
438 * Adds and removes CHUNKS from a list or tree.
439 *
440 ****************************************************************************/
441
442#include <stdio.h>
443#include <stdlib.h>
444
445#define SPLAY /* we use the splay version as that is much faster */
446
447#ifndef TRUE
448#define TRUE 1
449#endif
450#ifndef FALSE
451#define FALSE 0
452#endif
453
454#ifndef SPLAY /* these routines are for the non-splay version */
455
456struct ChunkInfo {
457 struct ChunkInfo *larger;
458 struct ChunkInfo *smaller;
459 size_t size;
460};
461
462/* the CHUNK list anchor */
463struct ChunkInfo *chunkHead=NULL;
464
465/***********************************************************************
466
467 findchunkbysize()
468
469 Find the chunk that is smaller than the input size. Returns
470 NULL if none is.
471
472 **********************************************************************/
473
474static struct ChunkInfo *findchunkbysize(size_t size)
475{
476 struct ChunkInfo *test = chunkHead;
477 struct ChunkInfo *smaller = NULL;
478 while(test && (test->size < size)) {
479 smaller = test;
480 test = test->larger;
481 }
482 return smaller;
483}
484
485/***********************************************************************
486
487 remove_chunksize()
488
489 Remove the chunk from the size-sorted list.
490 ***********************************************************************/
491
492void remove_chunksize(void *data)
493{
494 struct ChunkInfo *chunk = (struct ChunkInfo *)data;
495 if(chunk->smaller)
496 chunk->smaller->larger = chunk->larger;
497 else {
498 /* if this has no smaller, this is the head */
499 chunkHead = chunk->larger; /* new head */
500 }
501 if(chunk->larger)
502 chunk->larger->smaller = chunk->smaller;
503}
504
505void insert_bysize(char *data, size_t size)
506{
507 struct ChunkInfo *newchunk = (struct ChunkInfo *)data;
508 struct ChunkInfo *chunk = findchunkbysize ( size );
509
510 newchunk->size = size;
511
512 if(chunk) {
513 /* 'chunk' is smaller than size, append the new chunk ahead of this */
514 newchunk->smaller = chunk;
515 newchunk->larger = chunk->larger;
516 if(chunk->larger)
517 chunk->larger->smaller = newchunk;
518 chunk->larger = newchunk;
519 }
520 else {
521 /* smallest CHUNK around, append first in the list */
522 newchunk->larger = chunkHead;
523 newchunk->smaller = NULL;
524
525 if(chunkHead)
526 chunkHead->smaller = newchunk;
527 chunkHead = newchunk;
528 }
529}
530
531char *obtainbysize( size_t size)
532{
533 struct ChunkInfo *chunk = findchunkbysize( size );
534
535 if(!chunk) {
536 if(size <= (chunkHead->size))
537 /* there is no smaller CHUNK, use the first one (if we fit within that)
538 */
539 chunk = chunkHead;
540 }
541 else
542 /* we're on the last CHUNK that is smaller than requested, step onto
543 the bigger one */
544 chunk = chunk->larger;
545
546 if(chunk) {
547 remove_chunksize( chunk ); /* unlink size-wise */
548 return (char *)chunk;
549 }
550 else
551 return NULL;
552}
553
554void print_sizes(void)
555{
556 struct ChunkInfo *chunk = chunkHead;
557 printf("List of CHUNKS (in size order):\n");
558#if 1
559 while(chunk) {
560 printf(" START %p END %p SIZE %d\n",
561 chunk, (char *)chunk+chunk->size, chunk->size);
562 chunk = chunk->larger;
563 }
564#endif
565 printf("End of CHUNKS:\n");
566}
567
568#else /* Here follows all routines dealing with the SPLAY TREES */
569
570typedef struct tree_node Tree;
571struct tree_node {
572 Tree *smaller; /* smaller node */
573 Tree *larger; /* larger node */
574 Tree *same; /* points to a node with identical key */
575 int key; /* the "sort" key */
576};
577
578Tree *chunkHead = NULL; /* the root */
579
580#define compare(i,j) ((i)-(j))
581
582/* Set this to a key value that will *NEVER* appear otherwise */
583#define KEY_NOTUSED -1
584
585/*
586 * Splay using the key i (which may or may not be in the tree.) The starting
587 * root is t. Weight fields are maintained.
588 */
589Tree * splay (int i, Tree *t)
590{
591 Tree N, *l, *r, *y;
592 int comp;
593
594 if (t == NULL)
595 return t;
596 N.smaller = N.larger = NULL;
597 l = r = &N;
598
599 for (;;) {
600 comp = compare(i, t->key);
601 if (comp < 0) {
602 if (t->smaller == NULL)
603 break;
604 if (compare(i, t->smaller->key) < 0) {
605 y = t->smaller; /* rotate smaller */
606 t->smaller = y->larger;
607 y->larger = t;
608
609 t = y;
610 if (t->smaller == NULL)
611 break;
612 }
613 r->smaller = t; /* link smaller */
614 r = t;
615 t = t->smaller;
616 }
617 else if (comp > 0) {
618 if (t->larger == NULL)
619 break;
620 if (compare(i, t->larger->key) > 0) {
621 y = t->larger; /* rotate larger */
622 t->larger = y->smaller;
623 y->smaller = t;
624 t = y;
625 if (t->larger == NULL)
626 break;
627 }
628 l->larger = t; /* link larger */
629 l = t;
630 t = t->larger;
631 }
632 else {
633 break;
634 }
635 }
636
637 l->larger = r->smaller = NULL;
638
639 l->larger = t->smaller; /* assemble */
640 r->smaller = t->larger;
641 t->smaller = N.larger;
642 t->larger = N.smaller;
643
644 return t;
645}
646
647/* Insert key i into the tree t. Return a pointer to the resulting tree or
648 NULL if something went wrong. */
649Tree *insert(int i, Tree *t, Tree *new)
650{
651 if (new == NULL) {
652 return t;
653 }
654
655 if (t != NULL) {
656 t = splay(i,t);
657 if (compare(i, t->key)==0) {
658 /* it already exists one of this size */
659
660 new->same = t;
661 new->key = i;
662 new->smaller = t->smaller;
663 new->larger = t->larger;
664
665 t->smaller = new;
666 t->key = KEY_NOTUSED;
667
668 return new; /* new root node */
669 }
670 }
671
672 if (t == NULL) {
673 new->smaller = new->larger = NULL;
674 }
675 else if (compare(i, t->key) < 0) {
676 new->smaller = t->smaller;
677 new->larger = t;
678 t->smaller = NULL;
679 }
680 else {
681 new->larger = t->larger;
682 new->smaller = t;
683 t->larger = NULL;
684 }
685 new->key = i;
686
687 new->same = NULL; /* no identical node (yet) */
688
689 return new;
690}
691
692/* Finds and deletes the best-fit node from the tree. Return a pointer to the
693 resulting tree. best-fit means the smallest node that fits the requested
694 size. */
695Tree *removebestfit(int i, Tree *t, Tree **removed)
696{
697 Tree *x;
698
699 if (t==NULL)
700 return NULL;
701 t = splay(i,t);
702 if(compare(i, t->key) > 0) {
703 /* too small node, try the larger chain */
704 if(t->larger)
705 t=splay(t->larger->key, t);
706 else {
707 /* fail */
708 *removed = NULL;
709 return t;
710 }
711 }
712
713 if (compare(i, t->key) <= 0) { /* found it */
714
715 /* FIRST! Check if there is a list with identical sizes */
716 x = t->same;
717 if(x) {
718 /* there is, pick one from the list */
719
720 /* 'x' is the new root node */
721
722 x->key = t->key;
723 x->larger = t->larger;
724 x->smaller = t->smaller;
725 *removed = t;
726 return x; /* new root */
727 }
728
729 if (t->smaller == NULL) {
730 x = t->larger;
731 }
732 else {
733 x = splay(i, t->smaller);
734 x->larger = t->larger;
735 }
736 *removed = t;
737
738 return x;
739 }
740 else {
741 *removed = NULL; /* no match */
742 return t; /* It wasn't there */
743 }
744}
745
746
747/* Deletes the node we point out from the tree if it's there. Return a pointer
748 to the resulting tree. */
749Tree *removebyaddr(Tree *t, Tree *remove)
750{
751 Tree *x;
752
753 if (!t || !remove)
754 return NULL;
755
756 if(KEY_NOTUSED == remove->key) {
757 /* just unlink ourselves nice and quickly: */
758 remove->smaller->same = remove->same;
759 if(remove->same)
760 remove->same->smaller = remove->smaller;
761 /* voila, we're done! */
762 return t;
763 }
764
765 t = splay(remove->key,t);
766
767 /* Check if there is a list with identical sizes */
768
769 x = t->same;
770 if(x) {
771 /* 'x' is the new root node */
772
773 x->key = t->key;
774 x->larger = t->larger;
775 x->smaller = t->smaller;
776
777 return x; /* new root */
778 }
779
780 /* Remove the actualy root node: */
781
782 if (t->smaller == NULL) {
783 x = t->larger;
784 }
785 else {
786 x = splay(remove->key, t->smaller);
787 x->larger = t->larger;
788 }
789
790 return x;
791}
792
793int printtree(Tree * t, int d, char output)
794{
795 int distance=0;
796 Tree *node;
797 int i;
798 if (t == NULL)
799 return 0;
800 distance += printtree(t->larger, d+1, output);
801 for (i=0; i<d; i++)
802 if(output)
803 printf(" ");
804
805 if(output) {
806 printf("%d[%d]", t->key, i);
807 }
808
809 for(node = t->same; node; node = node->same) {
810 distance += i; /* this has the same "virtual" distance */
811
812 if(output)
813 printf(" [+]");
814 }
815 if(output)
816 puts("");
817
818 distance += i;
819 distance += printtree(t->smaller, d+1, output);
820 return distance;
821}
822
823/* Here follow the look-alike interface so that the tree-function names are
824 the same as the list-ones to enable easy interchange */
825
826void remove_chunksize(void *data)
827{
828 chunkHead = removebyaddr(chunkHead, data);
829}
830
831void insert_bysize(char *data, size_t size)
832{
833 chunkHead = insert(size, chunkHead, (Tree *)data);
834}
835
836char *obtainbysize( size_t size)
837{
838 Tree *receive;
839 chunkHead = removebestfit(size, chunkHead, &receive);
840 return (char *)receive;
841}
842
843void print_sizes(void)
844{
845 printtree(chunkHead, 0, 1);
846}
847
848#endif