|
DataMuseum.dkPresents historical artifacts from the history of: RC9000 |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about RC9000 Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - downloadIndex: t
Length: 5340 (0x14dc)
Names: »tsearch.3c«
└─⟦50656ff4a⟧ Bits:30010538 TX 3.1 Coldstart
└─⟦bbf173f5c⟧ »0004«
└─⟦this⟧ »./bsd/usr/man/cat3/tsearch.3c«
0x0000…0020 0a 0a 0a 5f 08 4f 5f 08 6e 5f 08 6c 5f 08 69 5f 08 6e 5f 08 65 20 5f 08 4d 5f 08 61 5f 08 6e 5f ┆ _ O_ n_ l_ i_ n_ e _ M_ a_ n_┆
0x0020…0040 08 75 5f 08 61 5f 08 6c 20 20 20 20 20 20 20 20 20 20 20 4c 69 62 72 61 72 79 20 46 75 6e 63 74 ┆ u_ a_ l Library Funct┆
0x0040…0060 69 6f 6e 73 20 20 20 20 20 20 20 20 20 20 20 20 20 74 73 65 61 72 63 68 28 33 63 29 0a 0a 0a 0a ┆ions tsearch(3c) ┆
0x0060…0080 4e 08 4e 08 4e 08 4e 41 08 41 08 41 08 41 4d 08 4d 08 4d 08 4d 45 08 45 08 45 08 45 0a 20 20 20 ┆N N N NA A A AM M M ME E E E ┆
0x0080…00a0 20 20 74 73 65 61 72 63 68 2c 20 74 64 65 6c 65 74 65 2c 20 74 77 61 6c 6b 20 2d 20 6d 61 6e 61 ┆ tsearch, tdelete, twalk - mana┆
0x00a0…00c0 67 65 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 74 72 65 65 73 0a 0a 53 08 53 08 53 08 53 59 ┆ge binary search trees S S S SY┆
0x00c0…00e0 08 59 08 59 08 59 4e 08 4e 08 4e 08 4e 54 08 54 08 54 08 54 41 08 41 08 41 08 41 58 08 58 08 58 ┆ Y Y YN N N NT T T TA A A AX X X┆
0x00e0…0100 08 58 0a 20 20 20 20 20 23 08 23 08 23 08 23 69 08 69 08 69 08 69 6e 08 6e 08 6e 08 6e 63 08 63 ┆ X # # # #i i i in n n nc c┆
0x0100…0120 08 63 08 63 6c 08 6c 08 6c 08 6c 75 08 75 08 75 08 75 64 08 64 08 64 08 64 65 08 65 08 65 08 65 ┆ c cl l l lu u u ud d d de e e e┆
0x0120…0140 20 3c 08 3c 08 3c 08 3c 73 08 73 08 73 08 73 65 08 65 08 65 08 65 61 08 61 08 61 08 61 72 08 72 ┆ < < < <s s s se e e ea a a ar r┆
0x0140…0160 08 72 08 72 63 08 63 08 63 08 63 68 08 68 08 68 08 68 2e 08 2e 08 2e 08 2e 68 08 68 08 68 08 68 ┆ r rc c c ch h h h. . . .h h h h┆
0x0160…0180 3e 08 3e 08 3e 08 3e 0a 0a 20 20 20 20 20 63 08 63 08 63 08 63 68 08 68 08 68 08 68 61 08 61 08 ┆> > > > c c c ch h h ha a ┆
0x0180…01a0 61 08 61 72 08 72 08 72 08 72 20 2a 08 2a 08 2a 08 2a 74 08 74 08 74 08 74 73 08 73 08 73 08 73 ┆a ar r r r * * * *t t t ts s s s┆
0x01a0…01c0 65 08 65 08 65 08 65 61 08 61 08 61 08 61 72 08 72 08 72 08 72 63 08 63 08 63 08 63 68 08 68 08 ┆e e e ea a a ar r r rc c c ch h ┆
0x01c0…01e0 68 08 68 20 28 08 28 08 28 08 28 28 08 28 08 28 08 28 63 08 63 08 63 08 63 68 08 68 08 68 08 68 ┆h h ( ( ( (( ( ( (c c c ch h h h┆
0x01e0…0200 61 08 61 08 61 08 61 72 08 72 08 72 08 72 20 2a 08 2a 08 2a 08 2a 29 08 29 08 29 08 29 20 6b 08 ┆a a a ar r r r * * * *) ) ) ) k ┆
0x0200…0220 6b 08 6b 08 6b 65 08 65 08 65 08 65 79 08 79 08 79 08 79 2c 08 2c 08 2c 08 2c 20 28 08 28 08 28 ┆k k ke e e ey y y y, , , , ( ( (┆
0x0220…0240 08 28 63 08 63 08 63 08 63 68 08 68 08 68 08 68 61 08 61 08 61 08 61 72 08 72 08 72 08 72 20 2a ┆ (c c c ch h h ha a a ar r r r *┆
0x0240…0260 08 2a 08 2a 08 2a 2a 08 2a 08 2a 08 2a 29 08 29 08 29 08 29 20 72 08 72 08 72 08 72 6f 08 6f 08 ┆ * * ** * * *) ) ) ) r r r ro o ┆
0x0260…0280 6f 08 6f 6f 08 6f 08 6f 08 6f 74 08 74 08 74 08 74 70 08 70 08 70 08 70 2c 08 2c 08 2c 08 2c 20 ┆o oo o o ot t t tp p p p, , , , ┆
0x0280…02a0 63 08 63 08 63 08 63 6f 08 6f 08 6f 08 6f 6d 08 6d 08 6d 08 6d 70 08 70 08 70 08 70 61 08 61 08 ┆c c c co o o om m m mp p p pa a ┆
0x02a0…02c0 61 08 61 72 08 72 08 72 08 72 29 08 29 08 29 08 29 0a 20 20 20 20 20 69 08 69 08 69 08 69 6e 08 ┆a ar r r r) ) ) ) i i i in ┆
0x02c0…02e0 6e 08 6e 08 6e 74 08 74 08 74 08 74 20 28 08 28 08 28 08 28 2a 08 2a 08 2a 08 2a 63 08 63 08 63 ┆n n nt t t t ( ( ( (* * * *c c c┆
0x02e0…0300 08 63 6f 08 6f 08 6f 08 6f 6d 08 6d 08 6d 08 6d 70 08 70 08 70 08 70 61 08 61 08 61 08 61 72 08 ┆ co o o om m m mp p p pa a a ar ┆
0x0300…0320 72 08 72 08 72 29 08 29 08 29 08 29 28 08 28 08 28 08 28 20 29 08 29 08 29 08 29 3b 08 3b 08 3b ┆r r r) ) ) )( ( ( ( ) ) ) ); ; ;┆
0x0320…0340 08 3b 0a 0a 20 20 20 20 20 63 08 63 08 63 08 63 68 08 68 08 68 08 68 61 08 61 08 61 08 61 72 08 ┆ ; c c c ch h h ha a a ar ┆
0x0340…0360 72 08 72 08 72 20 2a 08 2a 08 2a 08 2a 74 08 74 08 74 08 74 64 08 64 08 64 08 64 65 08 65 08 65 ┆r r r * * * *t t t td d d de e e┆
0x0360…0380 08 65 6c 08 6c 08 6c 08 6c 65 08 65 08 65 08 65 74 08 74 08 74 08 74 65 08 65 08 65 08 65 20 28 ┆ el l l le e e et t t te e e e (┆
0x0380…03a0 08 28 08 28 08 28 28 08 28 08 28 08 28 63 08 63 08 63 08 63 68 08 68 08 68 08 68 61 08 61 08 61 ┆ ( ( (( ( ( (c c c ch h h ha a a┆
0x03a0…03c0 08 61 72 08 72 08 72 08 72 20 2a 08 2a 08 2a 08 2a 29 08 29 08 29 08 29 20 6b 08 6b 08 6b 08 6b ┆ ar r r r * * * *) ) ) ) k k k k┆
0x03c0…03e0 65 08 65 08 65 08 65 79 08 79 08 79 08 79 2c 08 2c 08 2c 08 2c 20 28 08 28 08 28 08 28 63 08 63 ┆e e e ey y y y, , , , ( ( ( (c c┆
0x03e0…0400 08 63 08 63 68 08 68 08 68 08 68 61 08 61 08 61 08 61 72 08 72 08 72 08 72 20 2a 08 2a 08 2a 08 ┆ c ch h h ha a a ar r r r * * * ┆
0x0400…0420 2a 2a 08 2a 08 2a 08 2a 29 08 29 08 29 08 29 20 72 08 72 08 72 08 72 6f 08 6f 08 6f 08 6f 6f 08 ┆** * * *) ) ) ) r r r ro o o oo ┆
0x0420…0440 6f 08 6f 08 6f 74 08 74 08 74 08 74 70 08 70 08 70 08 70 2c 08 2c 08 2c 08 2c 20 63 08 63 08 63 ┆o o ot t t tp p p p, , , , c c c┆
0x0440…0460 08 63 6f 08 6f 08 6f 08 6f 6d 08 6d 08 6d 08 6d 70 08 70 08 70 08 70 61 08 61 08 61 08 61 72 08 ┆ co o o om m m mp p p pa a a ar ┆
0x0460…0480 72 08 72 08 72 29 08 29 08 29 08 29 0a 20 20 20 20 20 69 08 69 08 69 08 69 6e 08 6e 08 6e 08 6e ┆r r r) ) ) ) i i i in n n n┆
0x0480…04a0 74 08 74 08 74 08 74 20 28 08 28 08 28 08 28 2a 08 2a 08 2a 08 2a 63 08 63 08 63 08 63 6f 08 6f ┆t t t t ( ( ( (* * * *c c c co o┆
0x04a0…04c0 08 6f 08 6f 6d 08 6d 08 6d 08 6d 70 08 70 08 70 08 70 61 08 61 08 61 08 61 72 08 72 08 72 08 72 ┆ o om m m mp p p pa a a ar r r r┆
0x04c0…04e0 29 08 29 08 29 08 29 28 08 28 08 28 08 28 20 29 08 29 08 29 08 29 3b 08 3b 08 3b 08 3b 0a 0a 20 ┆) ) ) )( ( ( ( ) ) ) ); ; ; ; ┆
0x04e0…0500 20 20 20 20 76 08 76 08 76 08 76 6f 08 6f 08 6f 08 6f 69 08 69 08 69 08 69 64 08 64 08 64 08 64 ┆ v v v vo o o oi i i id d d d┆
0x0500…0520 20 74 08 74 08 74 08 74 77 08 77 08 77 08 77 61 08 61 08 61 08 61 6c 08 6c 08 6c 08 6c 6b 08 6b ┆ t t t tw w w wa a a al l l lk k┆
0x0520…0540 08 6b 08 6b 20 28 08 28 08 28 08 28 28 08 28 08 28 08 28 63 08 63 08 63 08 63 68 08 68 08 68 08 ┆ k k ( ( ( (( ( ( (c c c ch h h ┆
0x0540…0560 68 61 08 61 08 61 08 61 72 08 72 08 72 08 72 20 2a 08 2a 08 2a 08 2a 29 08 29 08 29 08 29 20 72 ┆ha a a ar r r r * * * *) ) ) ) r┆
0x0560…0580 08 72 08 72 08 72 6f 08 6f 08 6f 08 6f 6f 08 6f 08 6f 08 6f 74 08 74 08 74 08 74 2c 08 2c 08 2c ┆ r r ro o o oo o o ot t t t, , ,┆
0x0580…05a0 08 2c 20 61 08 61 08 61 08 61 63 08 63 08 63 08 63 74 08 74 08 74 08 74 69 08 69 08 69 08 69 6f ┆ , a a a ac c c ct t t ti i i io┆
0x05a0…05c0 08 6f 08 6f 08 6f 6e 08 6e 08 6e 08 6e 29 08 29 08 29 08 29 0a 20 20 20 20 20 76 08 76 08 76 08 ┆ o o on n n n) ) ) ) v v v ┆
0x05c0…05e0 76 6f 08 6f 08 6f 08 6f 69 08 69 08 69 08 69 64 08 64 08 64 08 64 20 28 08 28 08 28 08 28 2a 08 ┆vo o o oi i i id d d d ( ( ( (* ┆
0x05e0…0600 2a 08 2a 08 2a 61 08 61 08 61 08 61 63 08 63 08 63 08 63 74 08 74 08 74 08 74 69 08 69 08 69 08 ┆* * *a a a ac c c ct t t ti i i ┆
0x0600…0620 69 6f 08 6f 08 6f 08 6f 6e 08 6e 08 6e 08 6e 29 08 29 08 29 08 29 28 08 28 08 28 08 28 20 29 08 ┆io o o on n n n) ) ) )( ( ( ( ) ┆
0x0620…0640 29 08 29 08 29 3b 08 3b 08 3b 08 3b 0a 0a 44 08 44 08 44 08 44 45 08 45 08 45 08 45 53 08 53 08 ┆) ) ); ; ; ; D D D DE E E ES S ┆
0x0640…0660 53 08 53 43 08 43 08 43 08 43 52 08 52 08 52 08 52 49 08 49 08 49 08 49 50 08 50 08 50 08 50 54 ┆S SC C C CR R R RI I I IP P P PT┆
0x0660…0680 08 54 08 54 08 54 49 08 49 08 49 08 49 4f 08 4f 08 4f 08 4f 4e 08 4e 08 4e 08 4e 0a 20 20 20 20 ┆ T T TI I I IO O O ON N N N ┆
0x0680…06a0 20 5f 08 74 5f 08 73 5f 08 65 5f 08 61 5f 08 72 5f 08 63 5f 08 68 20 69 73 20 61 20 62 69 6e 61 ┆ _ t_ s_ e_ a_ r_ c_ h is a bina┆
0x06a0…06c0 72 79 20 74 72 65 65 20 73 65 61 72 63 68 20 72 6f 75 74 69 6e 65 20 67 65 6e 65 72 61 6c 69 7a ┆ry tree search routine generaliz┆
0x06c0…06e0 65 64 20 66 72 6f 6d 0a 20 20 20 20 20 4b 6e 75 74 68 20 28 36 2e 32 2e 32 29 20 41 6c 67 6f 72 ┆ed from Knuth (6.2.2) Algor┆
0x06e0…0700 69 74 68 6d 20 54 2e 20 20 49 74 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 69 6e ┆ithm T. It returns a pointer in┆
0x0700…0720 74 6f 20 61 20 74 72 65 65 0a 20 20 20 20 20 69 6e 64 69 63 61 74 69 6e 67 20 77 68 65 72 65 20 ┆to a tree indicating where ┆
0x0720…0740 61 20 64 61 74 75 6d 20 6d 61 79 20 62 65 20 66 6f 75 6e 64 2e 20 20 49 66 20 74 68 65 20 64 61 ┆a datum may be found. If the da┆
0x0740…0760 74 75 6d 20 64 6f 65 73 0a 20 20 20 20 20 6e 6f 74 20 6f 63 63 75 72 2c 20 69 74 20 69 73 20 61 ┆tum does not occur, it is a┆
0x0760…0780 64 64 65 64 20 61 74 20 61 6e 20 61 70 70 72 6f 70 72 69 61 74 65 20 70 6f 69 6e 74 20 69 6e 20 ┆dded at an appropriate point in ┆
0x0780…07a0 74 68 65 20 74 72 65 65 2e 0a 20 20 20 20 20 5f 08 4b 5f 08 65 5f 08 79 20 70 6f 69 6e 74 73 20 ┆the tree. _ K_ e_ y points ┆
0x07a0…07c0 74 6f 20 74 68 65 20 64 61 74 75 6d 20 74 6f 20 62 65 20 73 6f 75 67 68 74 20 69 6e 20 74 68 65 ┆to the datum to be sought in the┆
0x07c0…07e0 20 74 72 65 65 2e 20 20 5f 08 52 5f 08 6f 5f 08 6f 5f 08 74 5f 08 70 0a 20 20 20 20 20 70 6f 69 ┆ tree. _ R_ o_ o_ t_ p poi┆
0x07e0…0800 6e 74 73 20 74 6f 20 61 20 76 61 72 69 61 62 6c 65 20 74 68 61 74 20 70 6f 69 6e 74 73 20 74 6f ┆nts to a variable that points to┆
0x0800…0820 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74 68 65 20 74 72 65 65 2e 20 20 41 0a 20 20 20 20 20 4e ┆ the root of the tree. A N┆
0x0820…0840 55 4c 4c 20 70 6f 69 6e 74 65 72 20 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20 76 61 72 69 61 62 ┆ULL pointer value for the variab┆
0x0840…0860 6c 65 20 64 65 6e 6f 74 65 73 20 61 6e 20 65 6d 70 74 79 20 74 72 65 65 3b 0a 20 20 20 20 20 69 ┆le denotes an empty tree; i┆
0x0860…0880 6e 20 74 68 69 73 20 63 61 73 65 2c 20 74 68 65 20 76 61 72 69 61 62 6c 65 20 77 69 6c 6c 20 62 ┆n this case, the variable will b┆
0x0880…08a0 65 20 73 65 74 20 74 6f 20 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 64 61 74 75 6d 0a 20 20 20 20 ┆e set to point to the datum ┆
0x08a0…08c0 20 61 74 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74 68 65 20 6e 65 77 20 74 72 65 65 2e 20 20 5f ┆ at the root of the new tree. _┆
0x08c0…08e0 08 43 5f 08 6f 5f 08 6d 5f 08 70 5f 08 61 5f 08 72 20 69 73 20 74 68 65 20 6e 61 6d 65 20 6f 66 ┆ C_ o_ m_ p_ a_ r is the name of┆
0x08e0…0900 20 74 68 65 20 63 6f 6d 2d 0a 20 20 20 20 20 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 2e ┆ the com- parison function.┆
0x0900…0920 20 20 49 74 20 69 73 20 63 61 6c 6c 65 64 20 77 69 74 68 20 74 77 6f 20 61 72 67 75 6d 65 6e 74 ┆ It is called with two argument┆
0x0920…0940 73 20 74 68 61 74 0a 20 20 20 20 20 70 6f 69 6e 74 20 74 6f 20 74 68 65 20 65 6c 65 6d 65 6e 74 ┆s that point to the element┆
0x0940…0960 73 20 62 65 69 6e 67 20 63 6f 6d 70 61 72 65 64 2e 20 20 54 68 65 20 66 75 6e 63 74 69 6f 6e 20 ┆s being compared. The function ┆
0x0960…0980 6d 75 73 74 0a 20 20 20 20 20 72 65 74 75 72 6e 20 61 6e 20 69 6e 74 65 67 65 72 20 6c 65 73 73 ┆must return an integer less┆
0x0980…09a0 20 74 68 61 6e 2c 20 65 71 75 61 6c 20 74 6f 2c 20 6f 72 20 67 72 65 61 74 65 72 20 74 68 61 6e ┆ than, equal to, or greater than┆
0x09a0…09c0 20 7a 65 72 6f 0a 20 20 20 20 20 61 63 63 6f 72 64 69 6e 67 20 61 73 20 74 68 65 20 66 69 72 73 ┆ zero according as the firs┆
0x09c0…09e0 74 20 61 72 67 75 6d 65 6e 74 20 69 73 20 74 6f 20 62 65 20 63 6f 6e 73 69 64 65 72 65 64 20 6c ┆t argument is to be considered l┆
0x09e0…0a00 65 73 73 0a 20 20 20 20 20 74 68 61 6e 2c 20 65 71 75 61 6c 20 74 6f 2c 20 6f 72 20 67 72 65 61 ┆ess than, equal to, or grea┆
0x0a00…0a20 74 65 72 20 74 68 61 6e 20 74 68 65 20 73 65 63 6f 6e 64 2e 0a 0a 20 20 20 20 20 5f 08 74 5f 08 ┆ter than the second. _ t_ ┆
0x0a20…0a40 64 5f 08 65 5f 08 6c 5f 08 65 5f 08 74 5f 08 65 20 64 65 6c 65 74 65 73 20 61 20 6e 6f 64 65 20 ┆d_ e_ l_ e_ t_ e deletes a node ┆
0x0a40…0a60 66 72 6f 6d 20 61 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 74 72 65 65 2e 20 20 49 74 20 69 ┆from a binary search tree. It i┆
0x0a60…0a80 73 0a 20 20 20 20 20 67 65 6e 65 72 61 6c 69 7a 65 64 20 66 72 6f 6d 20 4b 6e 75 74 68 20 28 36 ┆s generalized from Knuth (6┆
0x0a80…0aa0 2e 32 2e 32 29 20 61 6c 67 6f 72 69 74 68 6d 20 44 2e 20 20 54 68 65 20 61 72 67 75 6d 65 6e 74 ┆.2.2) algorithm D. The argument┆
0x0aa0…0ac0 73 0a 20 20 20 20 20 61 72 65 20 74 68 65 20 73 61 6d 65 20 61 73 20 66 6f 72 20 5f 08 74 5f 08 ┆s are the same as for _ t_ ┆
0x0ac0…0ae0 73 5f 08 65 5f 08 61 5f 08 72 5f 08 63 5f 08 68 2e 20 20 54 68 65 20 76 61 72 69 61 62 6c 65 20 ┆s_ e_ a_ r_ c_ h. The variable ┆
0x0ae0…0b00 70 6f 69 6e 74 65 64 20 74 6f 20 62 79 0a 20 20 20 20 20 5f 08 72 5f 08 6f 5f 08 6f 5f 08 74 5f ┆pointed to by _ r_ o_ o_ t_┆
0x0b00…0b20 08 70 20 77 69 6c 6c 20 62 65 20 63 68 61 6e 67 65 64 20 69 66 20 74 68 65 20 64 65 6c 65 74 65 ┆ p will be changed if the delete┆
0x0b20…0b40 64 20 6e 6f 64 65 20 77 61 73 20 74 68 65 20 72 6f 6f 74 20 6f 66 0a 20 20 20 20 20 74 68 65 20 ┆d node was the root of the ┆
0x0b40…0b60 74 72 65 65 2e 20 20 5f 08 74 5f 08 64 5f 08 65 5f 08 6c 5f 08 65 5f 08 74 5f 08 65 20 72 65 74 ┆tree. _ t_ d_ e_ l_ e_ t_ e ret┆
0x0b60…0b80 75 72 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 70 61 72 65 6e 74 20 6f 66 20 ┆urns a pointer to the parent of ┆
0x0b80…0ba0 74 68 65 0a 20 20 20 20 20 64 65 6c 65 74 65 64 20 6e 6f 64 65 2c 20 6f 72 20 61 20 4e 55 4c 4c ┆the deleted node, or a NULL┆
0x0ba0…0bc0 20 70 6f 69 6e 74 65 72 20 69 66 20 74 68 65 20 6e 6f 64 65 20 69 73 20 6e 6f 74 20 66 6f 75 6e ┆ pointer if the node is not foun┆
0x0bc0…0be0 64 2e 0a 0a 20 20 20 20 20 5f 08 74 5f 08 77 5f 08 61 5f 08 6c 5f 08 6b 20 74 72 61 76 65 72 73 ┆d. _ t_ w_ a_ l_ k travers┆
0x0be0…0c00 65 73 20 61 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 20 74 72 65 65 2e 20 20 5f 08 52 5f 08 6f ┆es a binary search tree. _ R_ o┆
0x0c00…0c20 5f 08 6f 5f 08 74 20 69 73 20 74 68 65 20 72 6f 6f 74 20 6f 66 0a 20 20 20 20 20 74 68 65 20 74 ┆_ o_ t is the root of the t┆
0x0c20…0c40 72 65 65 20 74 6f 20 62 65 20 74 72 61 76 65 72 73 65 64 2e 20 20 28 41 6e 79 20 6e 6f 64 65 20 ┆ree to be traversed. (Any node ┆
0x0c40…0c60 69 6e 20 61 20 74 72 65 65 20 6d 61 79 20 62 65 20 75 73 65 64 0a 20 20 20 20 20 61 73 20 74 68 ┆in a tree may be used as th┆
0x0c60…0c80 65 20 72 6f 6f 74 20 66 6f 72 20 61 20 77 61 6c 6b 20 62 65 6c 6f 77 20 74 68 61 74 20 6e 6f 64 ┆e root for a walk below that nod┆
0x0c80…0ca0 65 2e 29 20 5f 08 41 5f 08 63 5f 08 74 5f 08 69 5f 08 6f 5f 08 6e 20 69 73 20 74 68 65 20 6e 61 ┆e.) _ A_ c_ t_ i_ o_ n is the na┆
0x0ca0…0cc0 6d 65 0a 20 20 20 20 20 6f 66 20 61 20 72 6f 75 74 69 6e 65 20 74 6f 20 62 65 20 69 6e 76 6f 6b ┆me of a routine to be invok┆
0x0cc0…0ce0 65 64 20 61 74 20 65 61 63 68 20 6e 6f 64 65 2e 20 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 69 ┆ed at each node. This routine i┆
0x0ce0…0d00 73 2c 0a 20 20 20 20 20 69 6e 20 74 75 72 6e 2c 20 63 61 6c 6c 65 64 20 77 69 74 68 20 74 68 72 ┆s, in turn, called with thr┆
0x0d00…0d20 65 65 20 61 72 67 75 6d 65 6e 74 73 2e 20 20 54 68 65 20 66 69 72 73 74 20 61 72 67 75 6d 65 6e ┆ee arguments. The first argumen┆
0x0d20…0d40 74 20 69 73 0a 20 20 20 20 20 74 68 65 20 61 64 64 72 65 73 73 20 6f 66 20 74 68 65 20 6e 6f 64 ┆t is the address of the nod┆
0x0d40…0d60 65 20 62 65 69 6e 67 20 76 69 73 69 74 65 64 2e 20 20 54 68 65 20 73 65 63 6f 6e 64 20 61 72 67 ┆e being visited. The second arg┆
0x0d60…0d80 75 6d 65 6e 74 0a 20 20 20 20 20 69 73 20 61 20 76 61 6c 75 65 20 66 72 6f 6d 20 61 6e 20 65 6e ┆ument is a value from an en┆
0x0d80…0da0 75 6d 65 72 61 74 69 6f 6e 20 64 61 74 61 20 74 79 70 65 20 5f 08 74 5f 08 79 5f 08 70 5f 08 65 ┆umeration data type _ t_ y_ p_ e┆
0x0da0…0dc0 5f 08 64 5f 08 65 5f 08 66 20 5f 08 65 5f 08 6e 5f 08 75 5f 08 6d 20 7b 0a 20 20 20 20 20 5f 08 ┆_ d_ e_ f _ e_ n_ u_ m { _ ┆
0x0dc0…0de0 70 5f 08 72 5f 08 65 5f 08 6f 5f 08 72 5f 08 64 5f 08 65 5f 08 72 2c 20 5f 08 70 5f 08 6f 5f 08 ┆p_ r_ e_ o_ r_ d_ e_ r, _ p_ o_ ┆
0x0de0…0e00 73 5f 08 74 5f 08 6f 5f 08 72 5f 08 64 5f 08 65 5f 08 72 2c 20 5f 08 65 5f 08 6e 5f 08 64 5f 08 ┆s_ t_ o_ r_ d_ e_ r, _ e_ n_ d_ ┆
0x0e00…0e20 6f 5f 08 72 5f 08 64 5f 08 65 5f 08 72 2c 20 5f 08 6c 5f 08 65 5f 08 61 5f 08 66 20 7d 20 5f 08 ┆o_ r_ d_ e_ r, _ l_ e_ a_ f } _ ┆
0x0e20…0e40 56 5f 08 49 5f 08 53 5f 08 49 5f 08 54 3b 20 28 64 65 66 69 6e 65 64 20 69 6e 20 74 68 65 0a 20 ┆V_ I_ S_ I_ T; (defined in the ┆
0x0e40…0e60 20 20 20 20 3c 73 65 61 72 63 68 2e 68 3e 20 68 65 61 64 65 72 20 66 69 6c 65 29 2c 20 64 65 70 ┆ <search.h> header file), dep┆
0x0e60…0e80 65 6e 64 69 6e 67 20 6f 6e 20 77 68 65 74 68 65 72 20 74 68 69 73 20 69 73 20 74 68 65 0a 20 20 ┆ending on whether this is the ┆
0x0e80…0ea0 20 20 20 66 69 72 73 74 2c 20 73 65 63 6f 6e 64 20 6f 72 20 74 68 69 72 64 20 74 69 6d 65 20 74 ┆ first, second or third time t┆
0x0ea0…0ec0 68 61 74 20 74 68 65 20 6e 6f 64 65 20 68 61 73 20 62 65 65 6e 20 76 69 73 69 74 65 64 0a 20 20 ┆hat the node has been visited ┆
0x0ec0…0ee0 20 20 20 28 64 75 72 69 6e 67 20 61 20 64 65 70 74 68 2d 66 69 72 73 74 2c 20 6c 65 66 74 2d 74 ┆ (during a depth-first, left-t┆
0x0ee0…0f00 6f 2d 72 69 67 68 74 20 74 72 61 76 65 72 73 61 6c 20 6f 66 20 74 68 65 20 74 72 65 65 29 2c 0a ┆o-right traversal of the tree), ┆
0x0f00…0f20 20 20 20 20 20 6f 72 20 77 68 65 74 68 65 72 20 74 68 65 20 6e 6f 64 65 20 69 73 20 61 20 6c 65 ┆ or whether the node is a le┆
0x0f20…0f40 61 66 2e 20 20 54 68 65 20 74 68 69 72 64 20 61 72 67 75 6d 65 6e 74 20 69 73 20 74 68 65 0a 20 ┆af. The third argument is the ┆
0x0f40…0f60 20 20 20 20 6c 65 76 65 6c 20 6f 66 20 74 68 65 20 6e 6f 64 65 20 69 6e 20 74 68 65 20 74 72 65 ┆ level of the node in the tre┆
0x0f60…0f80 65 2c 20 77 69 74 68 20 74 68 65 20 72 6f 6f 74 20 62 65 69 6e 67 20 6c 65 76 65 6c 0a 20 20 20 ┆e, with the root being level ┆
0x0f80…0fa0 20 20 7a 65 72 6f 2e 0a 0a 4e 08 4e 08 4e 08 4e 4f 08 4f 08 4f 08 4f 54 08 54 08 54 08 54 45 08 ┆ zero. N N N NO O O OT T T TE ┆
0x0fa0…0fc0 45 08 45 08 45 53 08 53 08 53 08 53 0a 20 20 20 20 20 54 68 65 20 70 6f 69 6e 74 65 72 73 20 74 ┆E E ES S S S The pointers t┆
0x0fc0…0fe0 6f 20 74 68 65 20 6b 65 79 20 61 6e 64 20 74 68 65 20 72 6f 6f 74 20 6f 66 20 74 68 65 20 74 72 ┆o the key and the root of the tr┆
0x0fe0…1000 65 65 20 73 68 6f 75 6c 64 20 62 65 0a 20 20 20 20 20 6f 66 20 74 79 70 65 20 70 6f 69 6e 74 65 ┆ee should be of type pointe┆
0x1000…1020 72 2d 74 6f 2d 65 6c 65 6d 65 6e 74 2c 20 61 6e 64 20 63 61 73 74 20 74 6f 20 74 79 70 65 20 70 ┆r-to-element, and cast to type p┆
0x1020…1040 6f 69 6e 74 65 72 2d 74 6f 2d 0a 20 20 20 20 20 63 68 61 72 61 63 74 65 72 2e 0a 20 20 20 20 20 ┆ointer-to- character. ┆
0x1040…1060 54 68 65 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 6e 65 65 64 20 6e 6f 74 ┆The comparison function need not┆
0x1060…1080 20 63 6f 6d 70 61 72 65 20 65 76 65 72 79 20 62 79 74 65 2c 20 73 6f 0a 20 20 20 20 20 61 72 62 ┆ compare every byte, so arb┆
0x1080…10a0 69 74 72 61 72 79 20 64 61 74 61 20 6d 61 79 20 62 65 20 63 6f 6e 74 61 69 6e 65 64 20 69 6e 20 ┆itrary data may be contained in ┆
0x10a0…10c0 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 61 64 64 69 74 69 6f 6e 0a 0a 0a 0a 0a 0a 0a 20 ┆the elements in addition ┆
0x10c0…10e0 20 20 20 20 74 6f 20 74 68 65 20 76 61 6c 75 65 73 20 62 65 69 6e 67 20 63 6f 6d 70 61 72 65 64 ┆ to the values being compared┆
0x10e0…1100 2e 0a 20 20 20 20 20 41 6c 74 68 6f 75 67 68 20 64 65 63 6c 61 72 65 64 20 61 73 20 74 79 70 65 ┆. Although declared as type┆
0x1100…1120 20 70 6f 69 6e 74 65 72 2d 74 6f 2d 63 68 61 72 61 63 74 65 72 2c 20 74 68 65 20 76 61 6c 75 65 ┆ pointer-to-character, the value┆
0x1120…1140 0a 20 20 20 20 20 72 65 74 75 72 6e 65 64 20 73 68 6f 75 6c 64 20 62 65 20 63 61 73 74 20 69 6e ┆ returned should be cast in┆
0x1140…1160 74 6f 20 74 79 70 65 20 70 6f 69 6e 74 65 72 2d 74 6f 2d 65 6c 65 6d 65 6e 74 2e 0a 20 20 20 20 ┆to type pointer-to-element. ┆
0x1160…1180 20 57 61 72 6e 69 6e 67 3a 20 74 68 65 20 5f 08 72 5f 08 6f 5f 08 6f 5f 08 74 20 61 72 67 75 6d ┆ Warning: the _ r_ o_ o_ t argum┆
0x1180…11a0 65 6e 74 20 74 6f 20 5f 08 74 5f 08 77 5f 08 61 5f 08 6c 5f 08 6b 20 69 73 20 6f 6e 65 20 6c 65 ┆ent to _ t_ w_ a_ l_ k is one le┆
0x11a0…11c0 76 65 6c 20 6f 66 20 69 6e 64 69 72 65 63 2d 0a 20 20 20 20 20 74 69 6f 6e 20 6c 65 73 73 20 74 ┆vel of indirec- tion less t┆
0x11c0…11e0 68 61 6e 20 74 68 65 20 5f 08 72 5f 08 6f 5f 08 6f 5f 08 74 5f 08 70 20 61 72 67 75 6d 65 6e 74 ┆han the _ r_ o_ o_ t_ p argument┆
0x11e0…1200 73 20 74 6f 20 5f 08 74 5f 08 73 5f 08 65 5f 08 61 5f 08 72 5f 08 63 5f 08 68 20 61 6e 64 20 5f ┆s to _ t_ s_ e_ a_ r_ c_ h and _┆
0x1200…1220 08 74 5f 08 64 5f 08 65 5f 08 6c 5f 08 65 5f 08 74 5f 08 65 2e 0a 0a 44 08 44 08 44 08 44 49 08 ┆ t_ d_ e_ l_ e_ t_ e. D D D DI ┆
0x1220…1240 49 08 49 08 49 41 08 41 08 41 08 41 47 08 47 08 47 08 47 4e 08 4e 08 4e 08 4e 4f 08 4f 08 4f 08 ┆I I IA A A AG G G GN N N NO O O ┆
0x1240…1260 4f 53 08 53 08 53 08 53 54 08 54 08 54 08 54 49 08 49 08 49 08 49 43 08 43 08 43 08 43 53 08 53 ┆OS S S ST T T TI I I IC C C CS S┆
0x1260…1280 08 53 08 53 0a 20 20 20 20 20 41 20 4e 55 4c 4c 20 70 6f 69 6e 74 65 72 20 69 73 20 72 65 74 75 ┆ S S A NULL pointer is retu┆
0x1280…12a0 72 6e 65 64 20 62 79 20 5f 08 74 5f 08 73 5f 08 65 5f 08 61 5f 08 72 5f 08 63 5f 08 68 20 69 66 ┆rned by _ t_ s_ e_ a_ r_ c_ h if┆
0x12a0…12c0 20 74 68 65 72 65 20 69 73 20 6e 6f 74 20 65 6e 6f 75 67 68 0a 20 20 20 20 20 73 70 61 63 65 20 ┆ there is not enough space ┆
0x12c0…12e0 61 76 61 69 6c 61 62 6c 65 20 74 6f 20 63 72 65 61 74 65 20 61 20 6e 65 77 20 6e 6f 64 65 2e 0a ┆available to create a new node. ┆
0x12e0…1300 20 20 20 20 20 41 20 4e 55 4c 4c 20 70 6f 69 6e 74 65 72 20 69 73 20 72 65 74 75 72 6e 65 64 20 ┆ A NULL pointer is returned ┆
0x1300…1320 62 79 20 5f 08 74 5f 08 73 5f 08 65 5f 08 61 5f 08 72 5f 08 63 5f 08 68 20 61 6e 64 20 5f 08 74 ┆by _ t_ s_ e_ a_ r_ c_ h and _ t┆
0x1320…1340 5f 08 64 5f 08 65 5f 08 6c 5f 08 65 5f 08 74 5f 08 65 20 69 66 20 5f 08 72 5f 08 6f 5f 08 6f 5f ┆_ d_ e_ l_ e_ t_ e if _ r_ o_ o_┆
0x1340…1360 08 74 5f 08 70 0a 20 20 20 20 20 69 73 20 4e 55 4c 4c 20 6f 6e 20 65 6e 74 72 79 2e 0a 0a 53 08 ┆ t_ p is NULL on entry. S ┆
0x1360…1380 53 08 53 08 53 45 08 45 08 45 08 45 45 08 45 08 45 08 45 20 41 08 41 08 41 08 41 4c 08 4c 08 4c ┆S S SE E E EE E E E A A A AL L L┆
0x1380…13a0 08 4c 53 08 53 08 53 08 53 4f 08 4f 08 4f 08 4f 0a 20 20 20 20 20 4c 69 62 72 61 72 79 20 46 75 ┆ LS S S SO O O O Library Fu┆
0x13a0…13c0 6e 63 74 69 6f 6e 73 20 28 33 29 3a 20 20 62 73 65 61 72 63 68 2c 20 68 73 65 61 72 63 68 2c 20 ┆nctions (3): bsearch, hsearch, ┆
0x13c0…13e0 6c 73 65 61 72 63 68 0a 0a 4c 08 4c 08 4c 08 4c 49 08 49 08 49 08 49 4d 08 4d 08 4d 08 4d 49 08 ┆lsearch L L L LI I I IM M M MI ┆
0x13e0…1400 49 08 49 08 49 54 08 54 08 54 08 54 41 08 41 08 41 08 41 54 08 54 08 54 08 54 49 08 49 08 49 08 ┆I I IT T T TA A A AT T T TI I I ┆
0x1400…1420 49 4f 08 4f 08 4f 08 4f 4e 08 4e 08 4e 08 4e 53 08 53 08 53 08 53 0a 20 20 20 20 20 41 77 66 75 ┆IO O O ON N N NS S S S Awfu┆
0x1420…1440 6c 20 74 68 69 6e 67 73 20 63 61 6e 20 68 61 70 70 65 6e 20 69 66 20 74 68 65 20 63 61 6c 6c 69 ┆l things can happen if the calli┆
0x1440…1460 6e 67 20 66 75 6e 63 74 69 6f 6e 20 61 6c 74 65 72 73 20 74 68 65 0a 20 20 20 20 20 70 6f 69 6e ┆ng function alters the poin┆
0x1460…1480 74 65 72 20 74 6f 20 74 68 65 20 72 6f 6f 74 2e 0a 0a 4d 61 72 63 68 20 31 39 38 39 20 20 20 20 ┆ter to the root. March 1989 ┆
0x1480…14a0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 54 58 20 50 72 6f ┆ TX Pro┆
0x14a0…14c0 67 72 61 6d 6d 65 72 27 73 20 52 65 66 65 72 65 6e 63 65 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a ┆grammer's Reference ┆
0x14c0…14dc 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a ┆ ┆