linux/search.h: add tsearch tree abstraction
authorshefty <shefty@ad392aa1-c5ef-ae45-8dd8-e69d62a5ef86>
Wed, 2 Sep 2009 15:33:42 +0000 (15:33 +0000)
committershefty <shefty@ad392aa1-c5ef-ae45-8dd8-e69d62a5ef86>
Wed, 2 Sep 2009 15:33:42 +0000 (15:33 +0000)
Implement a tsearch, tfind tree abstraction for use by platform independent code.  Internally, this uses complib on windows platforms.

Signed-off-by: Sean Hefty <sean.hefty@intel.com>
git-svn-id: svn://openib.tc.cornell.edu/gen1/trunk@2414 ad392aa1-c5ef-ae45-8dd8-e69d62a5ef86

etc/user/search.c [new file with mode: 0644]
inc/user/linux/search.h [new file with mode: 0644]

diff --git a/etc/user/search.c b/etc/user/search.c
new file mode 100644 (file)
index 0000000..4e47c61
--- /dev/null
@@ -0,0 +1,107 @@
+/*\r
+ * Copyright (c) 2009 Intel Corp., Inc.\r
+ *\r
+ * This software is available to you under a choice of one of two\r
+ * licenses.  You may choose to be licensed under the terms of the GNU\r
+ * General Public License (GPL) Version 2, available from the file\r
+ * COPYING in the main directory of this source tree, or the\r
+ * OpenIB.org BSD license below:\r
+ *\r
+ *     Redistribution and use in source and binary forms, with or\r
+ *     without modification, are permitted provided that the following\r
+ *     conditions are met:\r
+ *\r
+ *      - Redistributions of source code must retain the above\r
+ *        copyright notice, this list of conditions and the following\r
+ *        disclaimer.\r
+ *\r
+ *      - Redistributions in binary form must reproduce the above\r
+ *        copyright notice, this list of conditions and the following\r
+ *        disclaimer in the documentation and/or other materials\r
+ *        provided with the distribution.\r
+ *\r
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
+ * SOFTWARE.\r
+ *\r
+ */\r
+\r
+#include <stdlib.h>\r
+#include <search.h>\r
+\r
+static int (*compare)(const void *, const void *);\r
+\r
+static intn_t fcompare(const void * const key1, const void * const key2)\r
+{\r
+       return (intn_t) compare((void *) key1, (void *) key2);\r
+}\r
+\r
+void *tsearch(const void *key, void **rootp,\r
+                         int (*compar)(const void *, const void *))\r
+{\r
+       cl_fmap_item_t *item, *map_item;\r
+\r
+       if (!*rootp) {\r
+               *rootp = malloc(sizeof(cl_fmap_t));\r
+               cl_fmap_init((cl_fmap_t *) *rootp, fcompare);\r
+       }\r
+\r
+       compare = compar;\r
+       item = malloc(sizeof(cl_fmap_item_t));\r
+       map_item = cl_fmap_insert((cl_fmap_t *) *rootp, key, item);\r
+       if (map_item != item) {\r
+               free(item);\r
+               return (void *) map_item->p_key;\r
+       }\r
+\r
+       return (void *) key;\r
+}\r
+\r
+void *tfind(const void *key, void *const *rootp,\r
+                       int (*compar)(const void *, const void *))\r
+{\r
+       cl_fmap_item_t  *item;\r
+\r
+       if (!*rootp)\r
+               return NULL;\r
+\r
+       compare = compar;\r
+       item = cl_fmap_get((cl_fmap_t *) *rootp, key);\r
+       if (item == cl_fmap_end((cl_fmap_t *) *rootp))\r
+               return NULL;\r
+\r
+       return (void *) item->p_key;\r
+}\r
+\r
+void *tdelete(const void *key, void **rootp,\r
+                         int (*compar)(const void *, const void *))\r
+{\r
+       cl_fmap_item_t  *item;\r
+       void *map_key;\r
+\r
+       if (!*rootp)\r
+               return NULL;\r
+\r
+       compare = compar;\r
+       item = cl_fmap_remove((cl_fmap_t *) *rootp, key);\r
+       if (item == cl_fmap_end((cl_fmap_t *) *rootp))\r
+               return NULL;\r
+\r
+       map_key = (void *) item->p_key;\r
+       free(item);\r
+       return map_key;\r
+}\r
+\r
+//void twalk(const void *root,\r
+//                void (*action)(const void *, VISIT, int))\r
+//{\r
+//}\r
+\r
+//void tdestroy(void *root, void (*free_node)(void *nodep))\r
+//{\r
+//}\r
diff --git a/inc/user/linux/search.h b/inc/user/linux/search.h
new file mode 100644 (file)
index 0000000..2923a59
--- /dev/null
@@ -0,0 +1,59 @@
+/*\r
+ * Copyright (c) 2009 Intel Corp, Inc.  All rights reserved.\r
+ *\r
+ * This software is available to you under a choice of one of two\r
+ * licenses.  You may choose to be licensed under the terms of the GNU\r
+ * General Public License (GPL) Version 2, available from the file\r
+ * COPYING in the main directory of this source tree, or the\r
+ * OpenIB.org BSD license below:\r
+ *\r
+ *     Redistribution and use in source and binary forms, with or\r
+ *     without modification, are permitted provided that the following\r
+ *     conditions are met:\r
+ *\r
+ *      - Redistributions of source code must retain the above\r
+ *        copyright notice, this list of conditions and the following\r
+ *        disclaimer.\r
+ *\r
+ *      - Redistributions in binary form must reproduce the above\r
+ *        copyright notice, this list of conditions and the following\r
+ *        disclaimer in the documentation and/or other materials\r
+ *        provided with the distribution.\r
+ *\r
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
+ * SOFTWARE.\r
+ *\r
+ */\r
+\r
+#ifndef _SEARCH_H_\r
+#define _SEARCH_H_\r
+\r
+#include <complib/cl_fleximap.h>\r
+\r
+//typedef enum\r
+//{\r
+//     preorder,\r
+//     postorder,\r
+//     endorder,\r
+//     leaf\r
+//\r
+//}    VISIT;\r
+\r
+void *tsearch(const void *key, void **rootp,\r
+                         int (*compar)(const void *, const void *));\r
+void *tfind(const void *key, void *const *rootp,\r
+                       int (*compar)(const void *, const void *));\r
+/* tdelete returns key if found (not parent), otherwise NULL */\r
+void *tdelete(const void *key, void **rootp,\r
+                         int (*compar)(const void *, const void *));\r
+//void twalk(const void *root,\r
+//                void (*action)(const void *, VISIT, int));\r
+//void tdestroy(void *root, void (*free_node)(void *nodep));\r
+\r
+#endif /* _SEARCH_H_ */\r