1*6030f04aSchristos /* $NetBSD: search.h,v 1.22 2014/07/20 20:17:21 christos Exp $ */ 24d2cbfceScgd 3e6bcfeafSjtc /* 46ac55ad4Ssalo * Written by J.T. Conklin <jtc@NetBSD.org> 533b1cf86Sjtc * Public domain. 6e6bcfeafSjtc */ 7e6bcfeafSjtc 8e6bcfeafSjtc #ifndef _SEARCH_H_ 9e6bcfeafSjtc #define _SEARCH_H_ 10276331d1Skleink 11e6bcfeafSjtc #include <sys/cdefs.h> 1289a508fbSjoerg #include <sys/featuretest.h> 13d822defcSjtc #include <machine/ansi.h> 14d822defcSjtc 152922de74Scgd #ifdef _BSD_SIZE_T_ 162922de74Scgd typedef _BSD_SIZE_T_ size_t; 172922de74Scgd #undef _BSD_SIZE_T_ 18d822defcSjtc #endif 19e6bcfeafSjtc 205ca7ef77Sjtc typedef struct entry { 215ca7ef77Sjtc char *key; 22276331d1Skleink void *data; 235ca7ef77Sjtc } ENTRY; 245ca7ef77Sjtc 25711f328eSchristos #ifdef _NETBSD_SOURCE 26711f328eSchristos struct _ENTRY; 27711f328eSchristos struct hsearch_data { 28711f328eSchristos struct _ENTRY *table; 29711f328eSchristos size_t size; 30711f328eSchristos size_t filled; 31711f328eSchristos }; 32711f328eSchristos #endif 33711f328eSchristos 345ca7ef77Sjtc typedef enum { 355ca7ef77Sjtc FIND, ENTER 365ca7ef77Sjtc } ACTION; 375ca7ef77Sjtc 38de3db4cbSjtc typedef enum { 39de3db4cbSjtc preorder, 40de3db4cbSjtc postorder, 41de3db4cbSjtc endorder, 42de3db4cbSjtc leaf 43de3db4cbSjtc } VISIT; 44de3db4cbSjtc 45f4287ac1Schristos #ifdef _SEARCH_PRIVATE 46f4287ac1Schristos typedef struct node { 47f4287ac1Schristos char *key; 48f4287ac1Schristos struct node *llink, *rlink; 49f4287ac1Schristos } node_t; 50f4287ac1Schristos #endif 51f4287ac1Schristos 52e6bcfeafSjtc __BEGIN_DECLS 530b49c770Schristos #ifndef __BSEARCH_DECLARED 540b49c770Schristos #define __BSEARCH_DECLARED 550b49c770Schristos /* also in stdlib.h */ 5619b7469aSperry void *bsearch(const void *, const void *, size_t, size_t, 5719b7469aSperry int (*)(const void *, const void *)); 580b49c770Schristos #endif /* __BSEARCH_DECLARED */ 59711f328eSchristos 6019b7469aSperry int hcreate(size_t); 6119b7469aSperry void hdestroy(void); 6219b7469aSperry ENTRY *hsearch(ENTRY, ACTION); 635ca7ef77Sjtc 64711f328eSchristos #ifdef _NETBSD_SOURCE 65*6030f04aSchristos void hdestroy1(void (*)(void *), void (*)(void *)); 66711f328eSchristos int hcreate_r(size_t, struct hsearch_data *); 67711f328eSchristos void hdestroy_r(struct hsearch_data *); 68*6030f04aSchristos void hdestroy1_r(struct hsearch_data *, void (*)(void *), void (*)(void *)); 69711f328eSchristos int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 70711f328eSchristos #endif /* _NETBSD_SOURCE */ 71711f328eSchristos 7219b7469aSperry void *lfind(const void *, const void *, size_t *, size_t, 7319b7469aSperry int (*)(const void *, const void *)); 74ecef4b3dSdrochner void *lsearch(const void *, void *, size_t *, size_t, 7519b7469aSperry int (*)(const void *, const void *)); 7619b7469aSperry void insque(void *, void *); 7719b7469aSperry void remque(void *); 78de3db4cbSjtc 7998061f1fSkleink void *tdelete(const void * __restrict, void ** __restrict, 8019b7469aSperry int (*)(const void *, const void *)); 8198061f1fSkleink void *tfind(const void *, void * const *, 8219b7469aSperry int (*)(const void *, const void *)); 8319b7469aSperry void *tsearch(const void *, void **, 8419b7469aSperry int (*)(const void *, const void *)); 8519b7469aSperry void twalk(const void *, void (*)(const void *, VISIT, int)); 86e6bcfeafSjtc __END_DECLS 87e6bcfeafSjtc 88276331d1Skleink #endif /* !_SEARCH_H_ */ 89