Mac OS 9
AVLTree.h
Go to the documentation of this file.
1 
17 #ifndef __AVLTREE__
18 #define __AVLTREE__
19 
20 #ifndef __MACTYPES__
21 #include <MacTypes.h>
22 #endif
23 
24 #ifndef __MIXEDMODE__
25 #include <MixedMode.h>
26 #endif
27 
28 #if PRAGMA_ONCE
29 #pragma once
30 #endif
31 
32 #ifdef __cplusplus
33 extern "C"
34 {
35 #endif
36 
37 #if PRAGMA_IMPORT
38 #pragma import on
39 #endif
40 
41 #if PRAGMA_STRUCT_ALIGN
42 #pragma options align = mac68k
43 #elif PRAGMA_STRUCT_PACKPUSH
44 #pragma pack(push, 2)
45 #elif PRAGMA_STRUCT_PACK
46 #pragma pack(2)
47 #endif
48 
49  typedef UInt32 AVLFlags;
50  enum
51  {
52  kAVLFlagUseHandleForDataStorageMask = 0x00000001
53  };
54 
56  typedef UInt16 AVLVisitStage;
57  enum
58  {
59  kAVLPreOrder = 0,
60  kAVLInOrder = 1,
61  kAVLPostOrder = 2
62  };
63 
65  typedef UInt16 AVLOrder;
66  enum
67  {
68  kAVLLeftToRight = 0,
69  kAVLRightToLeft = 1
70  };
71 
73  typedef UInt16 AVLNodeType;
74  enum
75  {
76  kAVLIsTree = 0,
77  kAVLIsLeftBranch = 1,
78  kAVLIsRightBranch = 2,
79  kAVLIsLeaf = 3,
80  kAVLNullNode = 4
81  };
82 
83  enum
84  {
85  errItemAlreadyInTree = -960,
86  errNotValidTree = -961,
87  errItemNotFoundInTree = -962,
88  errCanNotInsertWhileWalkProcInProgress = -963,
89  errTreeIsLocked = -964,
90  errTreeIsCorrupt = -965
91  };
92 
95  struct AVLTreeStruct
96  {
97  OSType signature;
98  unsigned long privateStuff[12];
99  };
100  typedef struct AVLTreeStruct AVLTreeStruct;
101  typedef AVLTreeStruct *AVLTreePtr;
111  typedef CALLBACK_API(SInt32, AVLCompareItemsProcPtr)(AVLTreePtr tree,
112  const void *i1,
113  const void *i2,
114  AVLNodeType nd_typ);
122  typedef CALLBACK_API(UInt32, AVLItemSizeProcPtr)(AVLTreePtr tree,
123  const void *itemPtr);
131  typedef CALLBACK_API(void, AVLDisposeItemProcPtr)(AVLTreePtr tree,
132  const void *dataP);
146  typedef CALLBACK_API(OSErr, AVLWalkProcPtr)(AVLTreePtr tree, const void *dataP,
147  AVLVisitStage visitStage,
148  AVLNodeType node, UInt32 level,
149  SInt32 balance, void *refCon);
150  typedef STACK_UPP_TYPE(AVLCompareItemsProcPtr) AVLCompareItemsUPP;
151  typedef STACK_UPP_TYPE(AVLItemSizeProcPtr) AVLItemSizeUPP;
152  typedef STACK_UPP_TYPE(AVLDisposeItemProcPtr) AVLDisposeItemUPP;
153  typedef STACK_UPP_TYPE(AVLWalkProcPtr) AVLWalkUPP;
162  AVLCompareItemsUPP
163  NewAVLCompareItemsUPP(AVLCompareItemsProcPtr userRoutine);
164 #if !OPAQUE_UPP_TYPES
165  enum
166  {
167  uppAVLCompareItemsProcInfo = 0x00002FF0
168  };
169 #ifdef __cplusplus
170  inline AVLCompareItemsUPP
171  NewAVLCompareItemsUPP(AVLCompareItemsProcPtr userRoutine)
172  {
173  return (AVLCompareItemsUPP)NewRoutineDescriptor((ProcPtr)(userRoutine),
174  uppAVLCompareItemsProcInfo,
175  GetCurrentArchitecture());
176  }
177 #else
178 #define NewAVLCompareItemsUPP(userRoutine) \
179  (AVLCompareItemsUPP) \
180  NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLCompareItemsProcInfo, \
181  GetCurrentArchitecture())
182 #endif
183 #endif
184 
193  AVLItemSizeUPP
194  NewAVLItemSizeUPP(AVLItemSizeProcPtr userRoutine);
195 #if !OPAQUE_UPP_TYPES
196  enum
197  {
198  uppAVLItemSizeProcInfo = 0x000003F0
199  };
200 #ifdef __cplusplus
201  inline AVLItemSizeUPP NewAVLItemSizeUPP(AVLItemSizeProcPtr userRoutine)
202  {
203  return (AVLItemSizeUPP)NewRoutineDescriptor(
204  (ProcPtr)(userRoutine), uppAVLItemSizeProcInfo, GetCurrentArchitecture());
205  }
206 #else
207 #define NewAVLItemSizeUPP(userRoutine) \
208  (AVLItemSizeUPP) \
209  NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLItemSizeProcInfo, \
210  GetCurrentArchitecture())
211 #endif
212 #endif
213 
222  AVLDisposeItemUPP
223  NewAVLDisposeItemUPP(AVLDisposeItemProcPtr userRoutine);
224 #if !OPAQUE_UPP_TYPES
225  enum
226  {
227  uppAVLDisposeItemProcInfo = 0x000003C0
228  };
229 #ifdef __cplusplus
230  inline AVLDisposeItemUPP
231  NewAVLDisposeItemUPP(AVLDisposeItemProcPtr userRoutine)
232  {
233  return (AVLDisposeItemUPP)NewRoutineDescriptor((ProcPtr)(userRoutine),
234  uppAVLDisposeItemProcInfo,
235  GetCurrentArchitecture());
236  }
237 #else
238 #define NewAVLDisposeItemUPP(userRoutine) \
239  (AVLDisposeItemUPP) \
240  NewRoutineDescriptor((ProcPtr)(userRoutine), uppAVLDisposeItemProcInfo, \
241  GetCurrentArchitecture())
242 #endif
243 #endif
244 
253  AVLWalkUPP
254  NewAVLWalkUPP(AVLWalkProcPtr userRoutine);
255 #if !OPAQUE_UPP_TYPES
256  enum
257  {
258  uppAVLWalkProcInfo = 0x000FEBE0
259  };
261 #ifdef __cplusplus
262  inline AVLWalkUPP NewAVLWalkUPP(AVLWalkProcPtr userRoutine)
263  {
264  return (AVLWalkUPP)NewRoutineDescriptor(
265  (ProcPtr)(userRoutine), uppAVLWalkProcInfo, GetCurrentArchitecture());
266  }
267 #else
268 #define NewAVLWalkUPP(userRoutine) \
269  (AVLWalkUPP) NewRoutineDescriptor( \
270  (ProcPtr)(userRoutine), uppAVLWalkProcInfo, GetCurrentArchitecture())
271 #endif
272 #endif
273 
282  void
283  DisposeAVLCompareItemsUPP(AVLCompareItemsUPP userUPP);
284 #if !OPAQUE_UPP_TYPES
285 #ifdef __cplusplus
286  inline void DisposeAVLCompareItemsUPP(AVLCompareItemsUPP userUPP)
287  {
288  DisposeRoutineDescriptor((UniversalProcPtr)userUPP);
289  }
290 #else
291 #define DisposeAVLCompareItemsUPP(userUPP) DisposeRoutineDescriptor(userUPP)
292 #endif
293 #endif
294 
303  void
304  DisposeAVLItemSizeUPP(AVLItemSizeUPP userUPP);
305 #if !OPAQUE_UPP_TYPES
306 #ifdef __cplusplus
307  inline void DisposeAVLItemSizeUPP(AVLItemSizeUPP userUPP)
308  {
309  DisposeRoutineDescriptor((UniversalProcPtr)userUPP);
310  }
311 #else
312 #define DisposeAVLItemSizeUPP(userUPP) DisposeRoutineDescriptor(userUPP)
313 #endif
314 #endif
315 
324  void
325  DisposeAVLDisposeItemUPP(AVLDisposeItemUPP userUPP);
326 #if !OPAQUE_UPP_TYPES
327 #ifdef __cplusplus
328  inline void DisposeAVLDisposeItemUPP(AVLDisposeItemUPP userUPP)
329  {
330  DisposeRoutineDescriptor((UniversalProcPtr)userUPP);
331  }
332 #else
333 #define DisposeAVLDisposeItemUPP(userUPP) DisposeRoutineDescriptor(userUPP)
334 #endif
335 #endif
336 
345  void
346  DisposeAVLWalkUPP(AVLWalkUPP userUPP);
347 #if !OPAQUE_UPP_TYPES
348 #ifdef __cplusplus
349  inline void DisposeAVLWalkUPP(AVLWalkUPP userUPP)
350  {
351  DisposeRoutineDescriptor((UniversalProcPtr)userUPP);
352  }
353 #else
354 #define DisposeAVLWalkUPP(userUPP) DisposeRoutineDescriptor(userUPP)
355 #endif
356 #endif
357 
366  SInt32
367  InvokeAVLCompareItemsUPP(AVLTreePtr tree, const void *i1, const void *i2,
368  AVLNodeType nd_typ, AVLCompareItemsUPP userUPP);
369 #if !OPAQUE_UPP_TYPES
370 #ifdef __cplusplus
371  inline SInt32 InvokeAVLCompareItemsUPP(AVLTreePtr tree, const void *i1,
372  const void *i2, AVLNodeType nd_typ,
373  AVLCompareItemsUPP userUPP)
374  {
375  return (SInt32)CALL_FOUR_PARAMETER_UPP(userUPP, uppAVLCompareItemsProcInfo,
376  tree, i1, i2, nd_typ);
377  }
378 #else
379 #define InvokeAVLCompareItemsUPP(tree, i1, i2, nd_typ, userUPP) \
380  (SInt32) CALL_FOUR_PARAMETER_UPP((userUPP), uppAVLCompareItemsProcInfo, \
381  (tree), (i1), (i2), (nd_typ))
382 #endif
383 #endif
384 
393  UInt32
394  InvokeAVLItemSizeUPP(AVLTreePtr tree, const void *itemPtr,
395  AVLItemSizeUPP userUPP);
396 #if !OPAQUE_UPP_TYPES
397 #ifdef __cplusplus
398  inline UInt32 InvokeAVLItemSizeUPP(AVLTreePtr tree, const void *itemPtr,
399  AVLItemSizeUPP userUPP)
400  {
401  return (UInt32)CALL_TWO_PARAMETER_UPP(userUPP, uppAVLItemSizeProcInfo, tree,
402  itemPtr);
403  }
404 #else
405 #define InvokeAVLItemSizeUPP(tree, itemPtr, userUPP) \
406  (UInt32) CALL_TWO_PARAMETER_UPP((userUPP), uppAVLItemSizeProcInfo, (tree), \
407  (itemPtr))
408 #endif
409 #endif
410 
419  void
420  InvokeAVLDisposeItemUPP(AVLTreePtr tree, const void *dataP,
421  AVLDisposeItemUPP userUPP);
422 #if !OPAQUE_UPP_TYPES
423 #ifdef __cplusplus
424  inline void InvokeAVLDisposeItemUPP(AVLTreePtr tree, const void *dataP,
425  AVLDisposeItemUPP userUPP)
426  {
427  CALL_TWO_PARAMETER_UPP(userUPP, uppAVLDisposeItemProcInfo, tree, dataP);
428  }
429 #else
430 #define InvokeAVLDisposeItemUPP(tree, dataP, userUPP) \
431  CALL_TWO_PARAMETER_UPP((userUPP), uppAVLDisposeItemProcInfo, (tree), (dataP))
432 #endif
433 #endif
434 
443  OSErr
444  InvokeAVLWalkUPP(AVLTreePtr tree, const void *dataP, AVLVisitStage visitStage,
445  AVLNodeType node, UInt32 level, SInt32 balance, void *refCon,
446  AVLWalkUPP userUPP);
447 #if !OPAQUE_UPP_TYPES
448 #ifdef __cplusplus
449  inline OSErr InvokeAVLWalkUPP(AVLTreePtr tree, const void *dataP,
450  AVLVisitStage visitStage, AVLNodeType node,
451  UInt32 level, SInt32 balance, void *refCon,
452  AVLWalkUPP userUPP)
453  {
454  return (OSErr)CALL_SEVEN_PARAMETER_UPP(userUPP, uppAVLWalkProcInfo, tree,
455  dataP, visitStage, node, level,
456  balance, refCon);
457  }
458 #else
459 #define InvokeAVLWalkUPP(tree, dataP, visitStage, node, level, balance, \
460  refCon, userUPP) \
461  (OSErr) CALL_SEVEN_PARAMETER_UPP((userUPP), uppAVLWalkProcInfo, (tree), \
462  (dataP), (visitStage), (node), (level), \
463  (balance), (refCon))
464 #endif
465 #endif
466 
467 #if CALL_NOT_IN_CARBON || OLDROUTINENAMES
469 #define NewAVLCompareItemsProc(userRoutine) NewAVLCompareItemsUPP(userRoutine)
470 #define NewAVLItemSizeProc(userRoutine) NewAVLItemSizeUPP(userRoutine)
471 #define NewAVLDisposeItemProc(userRoutine) NewAVLDisposeItemUPP(userRoutine)
472 #define NewAVLWalkProc(userRoutine) NewAVLWalkUPP(userRoutine)
473 #define CallAVLCompareItemsProc(userRoutine, tree, i1, i2, nd_typ) \
474  InvokeAVLCompareItemsUPP(tree, i1, i2, nd_typ, userRoutine)
475 #define CallAVLItemSizeProc(userRoutine, tree, itemPtr) \
476  InvokeAVLItemSizeUPP(tree, itemPtr, userRoutine)
477 #define CallAVLDisposeItemProc(userRoutine, tree, dataP) \
478  InvokeAVLDisposeItemUPP(tree, dataP, userRoutine)
479 #define CallAVLWalkProc(userRoutine, tree, dataP, visitStage, node, level, \
480  balance, refCon) \
481  InvokeAVLWalkUPP(tree, dataP, visitStage, node, level, balance, refCon, \
482  userRoutine)
483 #endif
502  OSErr
503  AVLInit(UInt32 flags, AVLCompareItemsUPP compareItemsProc,
504  AVLItemSizeUPP sizeItemProc, AVLDisposeItemUPP disposeItemProc,
505  void *refCon, AVLTreePtr *tree);
506 
520  OSErr
521  AVLDispose(AVLTreePtr *tree, AVLOrder order);
522 
556  OSErr
557  AVLWalk(AVLTreePtr tree, AVLWalkUPP walkProc, AVLOrder order, void *walkRefCon);
558 
568  OSErr
569  AVLCount(AVLTreePtr tree, UInt32 *count);
570 
586  OSErr
587  AVLGetIndItem(AVLTreePtr tree, UInt32 index, void *dataPtr, UInt32 *itemSize);
588 
605  OSErr
606  AVLInsert(AVLTreePtr tree, const void *data);
607 
625  OSErr
626  AVLRemove(AVLTreePtr tree, const void *key, void *dataPtr, UInt32 *itemSize);
627 
644  OSErr
645  AVLFind(AVLTreePtr tree, const void *key, void *dataPtr, UInt32 *itemSize);
646 
659  OSErr
660  AVLGetRefcon(AVLTreePtr tree, void **refCon);
661 
666 #if CALL_NOT_IN_CARBON
675  OSErr
676  AVLLockTree(AVLTreePtr tree);
677 
690  OSErr
691  AVLUnlockTree(AVLTreePtr tree);
692 
705  OSErr
706  AVLCheckTree(AVLTreePtr tree);
707 
708 #endif
710 #if PRAGMA_STRUCT_ALIGN
711 #pragma options align = reset
712 #elif PRAGMA_STRUCT_PACKPUSH
713 #pragma pack(pop)
714 #elif PRAGMA_STRUCT_PACK
715 #pragma pack()
716 #endif
717 
718 #ifdef PRAGMA_IMPORT_OFF
719 #pragma import off
720 #elif PRAGMA_IMPORT
721 #pragma import reset
722 #endif
723 
724 #ifdef __cplusplus
725 }
726 #endif
727 
728 #endif
AVLFind
OSErr AVLFind(AVLTreePtr tree, const void *key, void *dataPtr, UInt32 *itemSize)
NewAVLWalkUPP
#define NewAVLWalkUPP(userRoutine)
Definition: AVLTree.h:268
AVLGetRefcon
OSErr AVLGetRefcon(AVLTreePtr tree, void **refCon)
AVLNodeType
UInt16 AVLNodeType
Definition: AVLTree.h:73
NewAVLItemSizeUPP
#define NewAVLItemSizeUPP(userRoutine)
Definition: AVLTree.h:207
AVLCheckTree
OSErr AVLCheckTree(AVLTreePtr tree)
AVLCount
OSErr AVLCount(AVLTreePtr tree, UInt32 *count)
AVLVisitStage
UInt16 AVLVisitStage
Definition: AVLTree.h:56
InvokeAVLItemSizeUPP
UInt32 InvokeAVLItemSizeUPP(AVLTreePtr tree, const void *itemPtr, AVLItemSizeUPP userUPP)
AVLInsert
OSErr AVLInsert(AVLTreePtr tree, const void *data)
InvokeAVLWalkUPP
OSErr InvokeAVLWalkUPP(AVLTreePtr tree, const void *dataP, AVLVisitStage visitStage, AVLNodeType node, UInt32 level, SInt32 balance, void *refCon, AVLWalkUPP userUPP)
AVLGetIndItem
OSErr AVLGetIndItem(AVLTreePtr tree, UInt32 index, void *dataPtr, UInt32 *itemSize)
DisposeAVLCompareItemsUPP
void DisposeAVLCompareItemsUPP(AVLCompareItemsUPP userUPP)
AVLInit
OSErr AVLInit(UInt32 flags, AVLCompareItemsUPP compareItemsProc, AVLItemSizeUPP sizeItemProc, AVLDisposeItemUPP disposeItemProc, void *refCon, AVLTreePtr *tree)
AVLRemove
OSErr AVLRemove(AVLTreePtr tree, const void *key, void *dataPtr, UInt32 *itemSize)
InvokeAVLDisposeItemUPP
void InvokeAVLDisposeItemUPP(AVLTreePtr tree, const void *dataP, AVLDisposeItemUPP userUPP)
DisposeAVLWalkUPP
void DisposeAVLWalkUPP(AVLWalkUPP userUPP)
AVLOrder
UInt16 AVLOrder
Definition: AVLTree.h:65
AVLDispose
OSErr AVLDispose(AVLTreePtr *tree, AVLOrder order)
NewAVLDisposeItemUPP
#define NewAVLDisposeItemUPP(userRoutine)
Definition: AVLTree.h:238
DisposeAVLDisposeItemUPP
void DisposeAVLDisposeItemUPP(AVLDisposeItemUPP userUPP)
AVLLockTree
OSErr AVLLockTree(AVLTreePtr tree)
AVLWalk
OSErr AVLWalk(AVLTreePtr tree, AVLWalkUPP walkProc, AVLOrder order, void *walkRefCon)
AVLUnlockTree
OSErr AVLUnlockTree(AVLTreePtr tree)
DisposeAVLItemSizeUPP
void DisposeAVLItemSizeUPP(AVLItemSizeUPP userUPP)
CALLBACK_API
typedef CALLBACK_API(SInt32, AVLCompareItemsProcPtr)(AVLTreePtr tree
InvokeAVLCompareItemsUPP
SInt32 InvokeAVLCompareItemsUPP(AVLTreePtr tree, const void *i1, const void *i2, AVLNodeType nd_typ, AVLCompareItemsUPP userUPP)
NewAVLCompareItemsUPP
#define NewAVLCompareItemsUPP(userRoutine)
Definition: AVLTree.h:178
MacTypes.h
Basic Macintosh data types.
MixedMode.h
Mixed Mode Manager Interfaces.
DisposeRoutineDescriptor
void DisposeRoutineDescriptor(UniversalProcPtr theUPP)
STACK_UPP_TYPE
#define STACK_UPP_TYPE(name)
Definition: MixedMode.h:734
NewRoutineDescriptor
UniversalProcPtr NewRoutineDescriptor(ProcPtr theProc, ProcInfoType theProcInfo, ISAType theISA)
AVLTreeStruct
Definition: AVLTree.h:96