summaryrefslogtreecommitdiff
path: root/fpcsrc/packages/univint/src/AVLTree.pas
blob: 36cf335570811ea1796b628ecc0dca2d9f1e4848 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
{
     File:       CarbonCore/AVLTree.h
 
     Contains:   Interfaces for AVL balanced trees.
 
     Version:    CarbonCore-859.2~1
 
     Copyright:  © 1999-2008 by Apple Computer, Inc., all rights reserved.
 
     Bugs?:      For bug reports, consult the following page on
                 the World Wide Web:
 
                     http://www.freepascal.org/bugs.html
 
}
{       Pascal Translation Updated:  Jonas Maebe, <jonas@freepascal.org>, October 2009 }
{
    Modified for use with Free Pascal
    Version 308
    Please report any bugs to <gpc@microbizz.nl>
}

{$ifc not defined MACOSALLINCLUDE or not MACOSALLINCLUDE}
{$mode macpas}
{$packenum 1}
{$macro on}
{$inline on}
{$calling mwpascal}

unit AVLTree;
interface
{$setc UNIVERSAL_INTERFACES_VERSION := $0400}
{$setc GAP_INTERFACES_VERSION := $0308}

{$ifc not defined USE_CFSTR_CONSTANT_MACROS}
    {$setc USE_CFSTR_CONSTANT_MACROS := TRUE}
{$endc}

{$ifc defined CPUPOWERPC and defined CPUI386}
	{$error Conflicting initial definitions for CPUPOWERPC and CPUI386}
{$endc}
{$ifc defined FPC_BIG_ENDIAN and defined FPC_LITTLE_ENDIAN}
	{$error Conflicting initial definitions for FPC_BIG_ENDIAN and FPC_LITTLE_ENDIAN}
{$endc}

{$ifc not defined __ppc__ and defined CPUPOWERPC32}
	{$setc __ppc__ := 1}
{$elsec}
	{$setc __ppc__ := 0}
{$endc}
{$ifc not defined __ppc64__ and defined CPUPOWERPC64}
	{$setc __ppc64__ := 1}
{$elsec}
	{$setc __ppc64__ := 0}
{$endc}
{$ifc not defined __i386__ and defined CPUI386}
	{$setc __i386__ := 1}
{$elsec}
	{$setc __i386__ := 0}
{$endc}
{$ifc not defined __x86_64__ and defined CPUX86_64}
	{$setc __x86_64__ := 1}
{$elsec}
	{$setc __x86_64__ := 0}
{$endc}
{$ifc not defined __arm__ and defined CPUARM}
	{$setc __arm__ := 1}
{$elsec}
	{$setc __arm__ := 0}
{$endc}

{$ifc defined cpu64}
  {$setc __LP64__ := 1}
{$elsec}
  {$setc __LP64__ := 0}
{$endc}


{$ifc defined __ppc__ and __ppc__ and defined __i386__ and __i386__}
	{$error Conflicting definitions for __ppc__ and __i386__}
{$endc}

{$ifc defined __ppc__ and __ppc__}
	{$setc TARGET_CPU_PPC := TRUE}
	{$setc TARGET_CPU_PPC64 := FALSE}
	{$setc TARGET_CPU_X86 := FALSE}
	{$setc TARGET_CPU_X86_64 := FALSE}
	{$setc TARGET_CPU_ARM := FALSE}
	{$setc TARGET_OS_MAC := TRUE}
	{$setc TARGET_OS_IPHONE := FALSE}
	{$setc TARGET_IPHONE_SIMULATOR := FALSE}
{$elifc defined __ppc64__ and __ppc64__}
	{$setc TARGET_CPU_PPC := FALSE}
	{$setc TARGET_CPU_PPC64 := TRUE}
	{$setc TARGET_CPU_X86 := FALSE}
	{$setc TARGET_CPU_X86_64 := FALSE}
	{$setc TARGET_CPU_ARM := FALSE}
	{$setc TARGET_OS_MAC := TRUE}
	{$setc TARGET_OS_IPHONE := FALSE}
	{$setc TARGET_IPHONE_SIMULATOR := FALSE}
{$elifc defined __i386__ and __i386__}
	{$setc TARGET_CPU_PPC := FALSE}
	{$setc TARGET_CPU_PPC64 := FALSE}
	{$setc TARGET_CPU_X86 := TRUE}
	{$setc TARGET_CPU_X86_64 := FALSE}
	{$setc TARGET_CPU_ARM := FALSE}
{$ifc defined(iphonesim)}
 	{$setc TARGET_OS_MAC := FALSE}
	{$setc TARGET_OS_IPHONE := TRUE}
	{$setc TARGET_IPHONE_SIMULATOR := TRUE}
{$elsec}
	{$setc TARGET_OS_MAC := TRUE}
	{$setc TARGET_OS_IPHONE := FALSE}
	{$setc TARGET_IPHONE_SIMULATOR := FALSE}
{$endc}
{$elifc defined __x86_64__ and __x86_64__}
	{$setc TARGET_CPU_PPC := FALSE}
	{$setc TARGET_CPU_PPC64 := FALSE}
	{$setc TARGET_CPU_X86 := FALSE}
	{$setc TARGET_CPU_X86_64 := TRUE}
	{$setc TARGET_CPU_ARM := FALSE}
	{$setc TARGET_OS_MAC := TRUE}
	{$setc TARGET_OS_IPHONE := FALSE}
	{$setc TARGET_IPHONE_SIMULATOR := FALSE}
{$elifc defined __arm__ and __arm__}
	{$setc TARGET_CPU_PPC := FALSE}
	{$setc TARGET_CPU_PPC64 := FALSE}
	{$setc TARGET_CPU_X86 := FALSE}
	{$setc TARGET_CPU_X86_64 := FALSE}
	{$setc TARGET_CPU_ARM := TRUE}
	{ will require compiler define when/if other Apple devices with ARM cpus ship }
	{$setc TARGET_OS_MAC := FALSE}
	{$setc TARGET_OS_IPHONE := TRUE}
	{$setc TARGET_IPHONE_SIMULATOR := FALSE}
{$elsec}
	{$error __ppc__ nor __ppc64__ nor __i386__ nor __x86_64__ nor __arm__ is defined.}
{$endc}

{$ifc defined __LP64__ and __LP64__ }
  {$setc TARGET_CPU_64 := TRUE}
{$elsec}
  {$setc TARGET_CPU_64 := FALSE}
{$endc}

{$ifc defined FPC_BIG_ENDIAN}
	{$setc TARGET_RT_BIG_ENDIAN := TRUE}
	{$setc TARGET_RT_LITTLE_ENDIAN := FALSE}
{$elifc defined FPC_LITTLE_ENDIAN}
	{$setc TARGET_RT_BIG_ENDIAN := FALSE}
	{$setc TARGET_RT_LITTLE_ENDIAN := TRUE}
{$elsec}
	{$error Neither FPC_BIG_ENDIAN nor FPC_LITTLE_ENDIAN are defined.}
{$endc}
{$setc ACCESSOR_CALLS_ARE_FUNCTIONS := TRUE}
{$setc CALL_NOT_IN_CARBON := FALSE}
{$setc OLDROUTINENAMES := FALSE}
{$setc OPAQUE_TOOLBOX_STRUCTS := TRUE}
{$setc OPAQUE_UPP_TYPES := TRUE}
{$setc OTCARBONAPPLICATION := TRUE}
{$setc OTKERNEL := FALSE}
{$setc PM_USE_SESSION_APIS := TRUE}
{$setc TARGET_API_MAC_CARBON := TRUE}
{$setc TARGET_API_MAC_OS8 := FALSE}
{$setc TARGET_API_MAC_OSX := TRUE}
{$setc TARGET_CARBON := TRUE}
{$setc TARGET_CPU_68K := FALSE}
{$setc TARGET_CPU_MIPS := FALSE}
{$setc TARGET_CPU_SPARC := FALSE}
{$setc TARGET_OS_UNIX := FALSE}
{$setc TARGET_OS_WIN32 := FALSE}
{$setc TARGET_RT_MAC_68881 := FALSE}
{$setc TARGET_RT_MAC_CFM := FALSE}
{$setc TARGET_RT_MAC_MACHO := TRUE}
{$setc TYPED_FUNCTION_POINTERS := TRUE}
{$setc TYPE_BOOL := FALSE}
{$setc TYPE_EXTENDED := FALSE}
{$setc TYPE_LONGLONG := TRUE}
uses MacTypes;
{$endc} {not MACOSALLINCLUDE}


{$ifc TARGET_OS_MAC}

{$ALIGN MAC68K}


{
 *  AVLVisitStage
 *  
 *  Discussion:
 *    The visit stage for AVLWalk() walkProcs
 }
type
	AVLVisitStage = UInt16;
const
{
   * Passed the first time AVLWalk iterates thru a given node.
   }
	kAVLPreOrder = 0;

  {
   * Passed the AVLWalk iterates thru a given node when it is 'in
   * order'.
   }
	kAVLInOrder = 1;

  {
   * Passed the last time AVLWalk iterates thru a given node.
   }
	kAVLPostOrder = 2;


{
 *  AVLOrder
 *  
 *  Discussion:
 *    The order the tree is walked or disposed of.
 }
type
	AVLOrder = UInt16;
const
{
   * Walk the tree in left-to-right order ( smaller to bigger, usually )
   }
	kLeftToRight = 0;

  {
   * Walk the tree in right-to-left order ( bigger to smaller, usually )
   }
	kRightToLeft = 1;


{
 *  AVLNodeType
 *  
 *  Discussion:
 *    The type of the node being passed to a callback proc.
 }
type
	AVLNodeType = UInt16;
const
	kAVLIsTree = 0;
	kAVLIsLeftBranch = 1;
	kAVLIsRightBranch = 2;
	kAVLIsLeaf = 3;
	kAVLNullNode = 4;

const
	errItemAlreadyInTree = -960;
	errNotValidTree = -961;
	errItemNotFoundInTree = -962;
	errCanNotInsertWhileWalkProcInProgress = -963;
	errTreeIsLocked = -964;


{
 *  AVLTreeStruct
 *  
 *  Summary:
 *    An opaque structure for a balanced binary tree.
 *  
 *  Discussion:
 *    The structure of a tree.  It's opaque; don't assume it's 36 bytes
 *    in size.
 }
type
	AVLTreeStructPtr = ^AVLTreeStruct;
	AVLTreeStruct = record
		signature: OSType;
		privateStuff:			array [0..7] of UNSIGNEDLONG;
	end;
type
	AVLTreePtr = AVLTreeStructPtr;

{
 *  AVLCompareItemsProcPtr
 *  
 *  Summary:
 *    A callback function which compares two data items and returns
 *    their ordering.
 *  
 *  Discussion:
 *    Every tree must have a function which compares the data for two
 *    items and returns < 0, 0, or >0 for the items - < 0 if the first
 *    item is 'before' the second item according to some criteria, == 0
 *    if the two items are identical according to the criteria, or > 0
 *    if the first item is 'after' the second item according to the
 *    criteria.  The comparison function is also passed the node type,
 *    but most of the time this can be ignored.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree which contains the items being compared
 *    
 *    i1:
 *      A pointer to the first item
 *    
 *    i2:
 *      A pointer to the second item
 *    
 *    nd_typ:
 *      The type of the nodes being compared.  This is not terribly
 *      useful most of the time.
 *  
 *  Result:
 *    A value < 0 if i1 is 'before' i2, > 0 if i1 is 'after' i2, or ==
 *    0 if i1 is equal to i2.
 }
type
	AVLCompareItemsProcPtr = function( tree: AVLTreePtr; i1: {const} UnivPtr; i2: {const} UnivPtr; nd_typ: AVLNodeType ): SInt32;

{
 *  AVLItemSizeProcPtr
 *  
 *  Summary:
 *    A callback function which returns the size of an item.
 *  
 *  Discussion:
 *    Every tree must have a itemSizeProc; this routine gets passed a
 *    pointer to the item's data and returns the size of the data.  If
 *    a tree contains records of a fixed size, this function can just
 *    return sizeof( that-struct ); otherwise it should calculate the
 *    size of the item based on the data for the item.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree which contains the item whose size is being requested.
 *    
 *    itemPtr:
 *      A pointer to the item whose size is being returned.
 *  
 *  Result:
 *    The size of the item.
 }
type
	AVLItemSizeProcPtr = function( tree: AVLTreePtr; itemPtr: {const} UnivPtr ): ByteCount;

{
 *  AVLDisposeItemProcPtr
 *  
 *  Summary:
 *    Dispose of any additional memory associated with an item in the
 *    tree.
 *  
 *  Discussion:
 *    A tree may have an optional disposeItemProc, which gets called
 *    whenever an item is removed from the tree ( via AVLRemove() or
 *    when AVLDispose() deletes all of the items in the tree ). This
 *    might be useful if the nodes in the tree own 'resources'  ( like,
 *    open files ) which should be released before the item is removed.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree containing the item being disposed.
 *    
 *    dataP:
 *      A pointer to the data for the item being disposed.
 }
type
	AVLDisposeItemProcPtr = procedure( tree: AVLTreePtr; dataP: {const} UnivPtr );

{
 *  AVLWalkProcPtr
 *  
 *  Summary:
 *    A callback function which gets passed each item in the tree, in a
 *    specified order.
 *  
 *  Discussion:
 *    The common way to iterate across all of the items in a tree is
 *    via AVLWalk(), which takes a walkProcPtr.  This function will get
 *    called for every item in the tree three times, as the tree is
 *    being walked across.  First, the walkProc will get called with
 *    visitStage == kAVLPreOrder, at which point internally the node of
 *    the tree for the given data has just been reached.  Later, this
 *    function will get called with visitStage == kAVLInOrder, and
 *    lastly this function will get called with visitStage ==
 *    kAVLPostOrder. The 'minimum' item in the tree will get called
 *    with visitStage == kInOrder first, followed by the 'next' item in
 *    the tree, up until the last item in the tree structure is called.
 *    In general, you'll only care about calls to this function when
 *    visitStage == kAVLInOrder.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree being walked.
 *    
 *    dataPtr:
 *      A pointer to the data for an item in the tree.
 *    
 *    visitStage:
 *      The stage of the walk for the given node.
 *    
 *    node:
 *      The type of the given node. This is not terribly useful most of
 *      the time.
 *    
 *    level:
 *      How 'deep' in the tree the given node is.  This is not terribly
 *      useful most of the time.
 *    
 *    balance:
 *      How balanced the given node in the tree is.  This is not
 *      terribly useful most of the time.
 *    
 *    refCon:
 *      The refCon passed into AVLWalk() for this call.
 *  
 *  Result:
 *    Return 0 to continue walking the tree, or 1 to terminate.
 }
type
	AVLWalkProcPtr = function( tree: AVLTreePtr; dataPtr: {const} UnivPtr; visitStage: AVLVisitStage; node: AVLNodeType; level: UInt32; balance: SInt32; refCon: UnivPtr ): OSErr;
	AVLCompareItemsUPP = AVLCompareItemsProcPtr;
	AVLItemSizeUPP = AVLItemSizeProcPtr;
	AVLDisposeItemUPP = AVLDisposeItemProcPtr;
	AVLWalkUPP = AVLWalkProcPtr;
{
 *  NewAVLCompareItemsUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function NewAVLCompareItemsUPP( userRoutine: AVLCompareItemsProcPtr ): AVLCompareItemsUPP; external name '_NewAVLCompareItemsUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  NewAVLItemSizeUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function NewAVLItemSizeUPP( userRoutine: AVLItemSizeProcPtr ): AVLItemSizeUPP; external name '_NewAVLItemSizeUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  NewAVLDisposeItemUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function NewAVLDisposeItemUPP( userRoutine: AVLDisposeItemProcPtr ): AVLDisposeItemUPP; external name '_NewAVLDisposeItemUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  NewAVLWalkUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function NewAVLWalkUPP( userRoutine: AVLWalkProcPtr ): AVLWalkUPP; external name '_NewAVLWalkUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  DisposeAVLCompareItemsUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
procedure DisposeAVLCompareItemsUPP( userUPP: AVLCompareItemsUPP ); external name '_DisposeAVLCompareItemsUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  DisposeAVLItemSizeUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
procedure DisposeAVLItemSizeUPP( userUPP: AVLItemSizeUPP ); external name '_DisposeAVLItemSizeUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  DisposeAVLDisposeItemUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
procedure DisposeAVLDisposeItemUPP( userUPP: AVLDisposeItemUPP ); external name '_DisposeAVLDisposeItemUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  DisposeAVLWalkUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
procedure DisposeAVLWalkUPP( userUPP: AVLWalkUPP ); external name '_DisposeAVLWalkUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  InvokeAVLCompareItemsUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function InvokeAVLCompareItemsUPP( tree: AVLTreePtr; i1: {const} UnivPtr; i2: {const} UnivPtr; nd_typ: AVLNodeType; userUPP: AVLCompareItemsUPP ): SInt32; external name '_InvokeAVLCompareItemsUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  InvokeAVLItemSizeUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function InvokeAVLItemSizeUPP( tree: AVLTreePtr; itemPtr: {const} UnivPtr; userUPP: AVLItemSizeUPP ): ByteCount; external name '_InvokeAVLItemSizeUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  InvokeAVLDisposeItemUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
procedure InvokeAVLDisposeItemUPP( tree: AVLTreePtr; dataP: {const} UnivPtr; userUPP: AVLDisposeItemUPP ); external name '_InvokeAVLDisposeItemUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{
 *  InvokeAVLWalkUPP()
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   available as macro/inline
 }
function InvokeAVLWalkUPP( tree: AVLTreePtr; dataPtr: {const} UnivPtr; visitStage: AVLVisitStage; node: AVLNodeType; level: UInt32; balance: SInt32; refCon: UnivPtr; userUPP: AVLWalkUPP ): OSErr; external name '_InvokeAVLWalkUPP';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)

{$ifc not TARGET_CPU_64}
{
 *  AVLInit()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Create an AVL ( balanced binary ) tree
 *  
 *  Discussion:
 *    Create an AVL tree.  The compareItemsProc and the sizeItemProc
 *    are required; disposeItemProc is optional and can be nil.  The
 *    refCon is stored with the list, and is passed back to the
 *    compareItemsProc, sizeItemProc, and disposeItemsProc calls.  The
 *    allocation of the tree ( and all nodes later added to the list
 *    with AVLInsert ) will be created in what is the current zone at
 *    the time AVLInit() is called.  Always call AVLDispose() to
 *    dispose of a list created with AVLInit().
 *  
 *  Mac OS X threading:
 *    Thread safe
 *  
 *  Parameters:
 *    
 *    flags:
 *      Creation flags.  Currently, no flags are defined, so pass 0.
 *    
 *    compareItemsProc:
 *      A UPP for a function which compares two data items, and returns
 *      a value which is < 0, == 0, or > 0 depending on whether the
 *      first item is 'before', 'equal', or 'after' the first item.
 *    
 *    sizeItemProc:
 *      A UPP for a function which takes a pointer to a data item, and
 *      returns the size in bytes which it requires to store.
 *    
 *    disposeItemProc:
 *      A UPP for a function which takes a pointer to a data item, and
 *      disposes of any memory which may have been allocated for the
 *      item.  This does not need to dispose of the item itself ( the
 *      AVLTree Manager will do that ), only any memory which the item
 *      passed in may be pointing to.  This function may be NULL if
 *      data items do not use any memory besides that taken up by the
 *      item itself.
 *    
 *    refCon:
 *      A 32 bit quantity which is stored with this tree, and can be
 *      retrieved at an time ( and in a callback, if desired ) with
 *      AVLGetRefcon().
 *    
 *    tree:
 *      The created AVLTree, or NULL if there is an error.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLInit( flags: UInt32; compareItemsProc: AVLCompareItemsUPP; sizeItemProc: AVLItemSizeUPP; disposeItemProc: AVLDisposeItemUPP; refCon: UnivPtr; var tree: AVLTreePtr ): OSErr; external name '_AVLInit';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLDispose()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Dispose of an AVL tree created with AVLInit()
 *  
 *  Discussion:
 *    Dispose of an AVL tree.  This will dispose of each item in the
 *    tree in the order specified, call the tree's disposeProc proc for
 *    each item, and then dispose of the space allocated for the tree
 *    itself.
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLDispose is thread safe provided no other thread is still using
 *    the tree being dispose.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to dispose, which was created with AVLInit().
 *    
 *    order:
 *      The order to dispose of the items in the tree.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLDispose( var tree: AVLTreePtr; order: AVLOrder ): OSErr; external name '_AVLDispose';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLWalk()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Iterate across all of the items in an AVL tree, in a specified
 *    order.
 *  
 *  Discussion:
 *    Iterate across all of the items in the tree, in the order
 *    specified.  kLeftToRight is basically lowest-to-highest order,
 *    kRightToLeft is highest-to-lowest order.  For each node in the
 *    tree, it will call the walkProc with three messages ( at the
 *    appropriate time ).  First, with kAVLPreOrder when the walking
 *    gets to this node in the tree, before handling either the left or
 *    right subtree, secondly, with kAVLInOrder after handling one
 *    subtree but before handling the other, and lastly with
 *    kAVLPostOrder after handling both subtrees.  If you want to
 *    handle items in order, then only do something if the visit stage
 *    is kAVLInOrder.  You can only call AVLRemove() from inside a
 *    walkProc if visit stage is kAVLPostOrder ( because if you remove
 *    a node during the pre or in order stages you will corrupt the
 *    list ) OR if you return a non-zero result from the walkProc call
 *    which called AVLRemove() to immediately terminate the walkProc. 
 *    Do not call AVLInsert() to insert a node into the tree from
 *    inside a walkProc. The walkProc function gets called with the
 *    AVLTreePtr, a pointer to the data for the current node ( which
 *    you can change in place as long as you do not affect the order
 *    within the tree ), the visit stage, the type of the current node
 *    ( leaf node, right or left branch, or full tree ), the level
 *    within the tree ( the root is level 1 ), the balance for the
 *    current node, and the refCon passed to AVLWalk().  This refCon is
 *    different from the one passed into AVLInit(); use AVLGetRefCon()
 *    to get that refCon if you want it inside a walkProc. ( Most
 *    walkProcs will not care about the values for node type, level, or
 *    balance. )
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLWalk is thread safe as long as no other thread tries to modify
 *    the tree by inserting or removing an item, or disposing of the
 *    tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to dispose, which was created with AVLInit().
 *    
 *    walkProc:
 *      A UPP for a function which is called during the walk thru the
 *      tree for each item.
 *    
 *    order:
 *      The order to iterate thru the tree.
 *    
 *    walkRefCon:
 *      A 32 bit value passed to the walkProc each time it is called.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLWalk( tree: AVLTreePtr; walkProc: AVLWalkUPP; order: AVLOrder; walkRefCon: UnivPtr ): OSErr; external name '_AVLWalk';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLCount()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Return the number of items in the given tree.
 *  
 *  Discussion:
 *    Return the number of items in the given tree.
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLCount is thread safe as long as no other thread tries to
 *    modify the tree by inserting or removing an item, or disposing of
 *    the tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to return the count of items for.
 *    
 *    count:
 *      On return, the count of items ( 1-based ) in the tree.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLCount( tree: AVLTreePtr; var count: UInt32 ): OSErr; external name '_AVLCount';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLGetIndItem()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Return the data of the index-th item from the tree.
 *  
 *  Discussion:
 *    Return the one-based index-th item from the tree by putting it's
 *    data at dataPtr if dataPtr is non-nil, and it's size into
 *    *itemSize if itemSize is non-nil. If index is out of range,
 *    return errItemNotFoundInTree.  ( Internally, this does an
 *    AVLWalk(), so the tree can not be modified while this call is in
 *    progress ).
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLGetIndItem is thread safe as long as no other thread tries to
 *    modify the tree by inserting or removing an item, or disposing of
 *    the tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to return the index-th items for.
 *    
 *    index:
 *      A index of the item to return.  The 'first' item in the tree is
 *      index = 1, the last item is index = the count of items in the
 *      tree.
 *    
 *    dataPtr:
 *      An address in memory to return the data for the item, or NULL
 *      if you don not want data returned.  The memory point to must be
 *      large enough to hold all of the data for the item.
 *    
 *    itemSize:
 *      On return, the size of the data for the index-th item.  If you
 *      do not care about the size of the data, pass NULL.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLGetIndItem( tree: AVLTreePtr; index: UInt32; dataPtr: UnivPtr; var itemSize: ByteCount ): OSErr; external name '_AVLGetIndItem';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLInsert()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Insert an item into the tree.
 *  
 *  Discussion:
 *    Insert the given item into the tree.  This will call the tree's
 *    sizeItemProc to determine how big the item at data is, and then
 *    will make a copy of the item and insert it into the tree in the
 *    appropriate place.  If an item already exists in the tree with
 *    the same key ( so that the compareItemsUPP returns 0 when asked
 *    to compare this item to an existing one ), then it will return
 *    errItemNotFoundInTree.
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLInsert is thread safe as long as no other thread tries to walk
 *    or modify the tree by inserting or removing an item, or disposing
 *    of the tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to return the index-th items for.
 *    
 *    data:
 *      A pointer to the item to be inserted.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLInsert( tree: AVLTreePtr; data: {const} UnivPtr ): OSErr; external name '_AVLInsert';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLRemove()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Remove an item from the tree.
 *  
 *  Discussion:
 *    Remove any item from the tree with the given key.  If dataPtr !=
 *    nil, then copy the item's data to dataPtr before removing it from
 *    the tree.  Before removing the item, call the tree's
 *    disposeItemProc to let it release anything used by the data in
 *    the tree.  It is not necessary to fill in a complete record for
 *    key, only that the compareItemsProc return 0 when asked to
 *    compare the data at key with the node in the tree to be deleted. 
 *    If the item cannot be found in the tree, this will return
 *    errItemNotFoundInTree.
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLRemove is thread safe as long as no other thread tries to walk
 *    or modify the tree by inserting or removing an item, or disposing
 *    of the tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to return the index-th items for.
 *    
 *    key:
 *      A pointer to the item to be removed ( or, enough of the item
 *      that it can be found in the tree ).
 *    
 *    dataPtr:
 *      An address in memory to return the data for the item, or NULL
 *      if you don not want data returned.  The memory point to must be
 *      large enough to hold all of the data for the item.
 *    
 *    itemSize:
 *      On return, the size of the data for the index-th item.  If you
 *      do not care about the size of the data, pass NULL.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLRemove( tree: AVLTreePtr; key: {const} UnivPtr; dataPtr: UnivPtr; var itemSize: ByteCount ): OSErr; external name '_AVLRemove';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLFind()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Remove an item from the tree.
 *  
 *  Discussion:
 *    Find the item in the tree with the given key, and return it's
 *    data in dataPtr ( if dataPtr != nil ), and it's size in *itemSize
 *    ( if itemSize != nil ).  It is not necessary to fill in a
 *    complete record for key, only that the compareItemsProc return 0
 *    when asked to compare the data at key with the node in the tree
 *    to be deleted.  If the item cannot be found in the tree, this
 *    will return errItemNotFoundInTree.
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLRemove is thread safe as long as no other thread tries to walk
 *    or modify the tree by inserting or removing an item, or disposing
 *    of the tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to return the index-th items for.
 *    
 *    key:
 *      A pointer to the item to be found ( or, enough of the item that
 *      it can be found in the tree ).
 *    
 *    dataPtr:
 *      An address in memory to return the data for the item, or NULL
 *      if you don not want data returned.  The memory point to must be
 *      large enough to hold all of the data for the item.
 *    
 *    itemSize:
 *      On return, the size of the data for the index-th item.  If you
 *      do not care about the size of the data, pass NULL.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLFind( tree: AVLTreePtr; key: {const} UnivPtr; dataPtr: UnivPtr; var itemSize: ByteCount ): OSErr; external name '_AVLFind';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{
 *  AVLGetRefcon()   *** DEPRECATED ***
 *  
 *  Summary:
 *    Return the refCon set when the tree was created.
 *  
 *  Discussion:
 *    Get the refCon for the given tree ( set in AVLInit ) and return
 *    it.
 *  
 *  Mac OS X threading:
 *    Thread safe
 *    AVLGetRefcon is thread safe as long as no other thread tries to
 *    dispose of the tree itself.
 *  
 *  Parameters:
 *    
 *    tree:
 *      The tree to return the refcon for.
 *    
 *    refCon:
 *      On return, the refCon for the tree, or NULL if tree is invalid.
 *  
 *  Availability:
 *    Mac OS X:         in version 10.0 and later in CoreServices.framework [32-bit only] but deprecated in 10.5
 *    CarbonLib:        in CarbonLib 1.0 and later
 *    Non-Carbon CFM:   in InterfaceLib 9.0 and later
 }
function AVLGetRefcon( tree: AVLTreePtr; var refCon: UnivPtr ): OSErr; external name '_AVLGetRefcon';
(* AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION_10_5 *)


{$endc} {not TARGET_CPU_64}

{$endc} {TARGET_OS_MAC}
{$ifc not defined MACOSALLINCLUDE or not MACOSALLINCLUDE}

end.
{$endc} {not MACOSALLINCLUDE}