Finish <search.h>.

I'm unable to find a bug, but we've had requests for this internally
once or twice (though I pointed those folks at the STL), and there's
code we build for the host or in our bootloaders that would use this,
and there's reasonable-looking FreeBSD implementation ready and waiting.

Bug: N/A
Test: ran tests
Change-Id: I6ddee4b71bea4c22ed015debd31d3eaac4fcdd35
diff --git a/libc/include/search.h b/libc/include/search.h
index 0015699..5930bcd 100644
--- a/libc/include/search.h
+++ b/libc/include/search.h
@@ -13,18 +13,26 @@
 #include <sys/types.h>
 
 typedef enum {
+  FIND,
+  ENTER
+} ACTION;
+
+typedef struct entry {
+  char* key;
+  void* data;
+} ENTRY;
+
+typedef enum {
   preorder,
   postorder,
   endorder,
   leaf
 } VISIT;
 
-#ifdef _SEARCH_PRIVATE
-typedef struct node {
-  char* key;
-  struct node* llink;
-  struct node* rlink;
-} node_t;
+#if defined(__USE_BSD) || defined(__USE_GNU)
+struct hsearch_data {
+  struct __hsearch* __hsearch;
+};
 #endif
 
 __BEGIN_DECLS
@@ -32,6 +40,16 @@
 void insque(void* __element, void* __previous) __INTRODUCED_IN(21);
 void remque(void* __element) __INTRODUCED_IN(21);
 
+int hcreate(size_t) __INTRODUCED_IN_FUTURE;
+void hdestroy(void) __INTRODUCED_IN_FUTURE;
+ENTRY* hsearch(ENTRY, ACTION) __INTRODUCED_IN_FUTURE;
+
+#if defined(__USE_BSD) || defined(__USE_GNU)
+int hcreate_r(size_t, struct hsearch_data*) __INTRODUCED_IN_FUTURE;
+void hdestroy_r(struct hsearch_data*) __INTRODUCED_IN_FUTURE;
+int hsearch_r(ENTRY, ACTION, ENTRY**, struct hsearch_data*) __INTRODUCED_IN_FUTURE;
+#endif
+
 void* lfind(const void* __key, const void* __base, size_t* __count, size_t __size, int (*__comparator)(const void*, const void*))
   __INTRODUCED_IN(21);
 void* lsearch(const void* __key, void* __base, size_t* __count, size_t __size, int (*__comparator)(const void*, const void*))