00001 /* file "tree_string_index.h" */
00002
00003
00004 /*
00005 Copyright (c) 1996, 1997 Stanford University
00006
00007 All rights reserved.
00008
00009 This software is provided under the terms described in
00010 the "suif_copyright.h" include file.
00011 */
00012
00013 #include <common/suif_copyright.h>
00014
00015
00016 #ifndef STY_TREE_STRING_INDEX_H
00017 #define STY_TREE_STRING_INDEX_H
00018
00019 //#ifndef SUPPRESS_PRAGMA_INTERFACE
00020 //#pragma interface
00021 //#endif
00022
00023
00024 /*
00025 This is the definition of the tree_string_index template and
00026 related templates, which are templates for classes implementing
00027 mappings from character strings to arbitrary types using a tree
00028 representation for fast lookups, for sty, the first-level main
00029 library of the SUIF system.
00030 */
00031
00032 #include "index.h"
00033 #include "zero.h"
00034
00035 template <class elem_t> class tsi_node;
00036 template <class elem_t> class tsi_entry;
00037
00038 template <class elem_t> class tree_string_index : public
00039 Index<const char *, elem_t>
00040 {
00041 friend class tsi_node<elem_t>;
00042
00043 private:
00044 tsi_node<elem_t> *_root_node;
00045 size_t _list_size;
00046 char _expected_lower;
00047 char _expected_upper;
00048
00049 tsi_node<elem_t> *follow_prefix_match(const char *string,
00050 size_t *prefix_length) const;
00051 void internal_development_dump(char **buffer, size_t *buf_size,
00052 size_t position,
00053 tsi_node<elem_t> *base_node, ion *ip,
00054 void (*node_func)(elem_t data, ion *ip),
00055 bool show_internals);
00056 void get_development_stats(tsi_node<elem_t> *base_node,
00057 size_t *entry_count,
00058 size_t *substring_node_count,
00059 size_t *char_list_node_count,
00060 size_t *char_table_node_count,
00061 size_t *leaf_node_count,
00062 size_t *substring_char_count,
00063 size_t *char_list_place_count,
00064 size_t *char_list_used_count,
00065 size_t *char_table_place_count,
00066 size_t *char_table_used_count);
00067 tsi_entry<elem_t> *lookup_entry(const char *the_key) const;
00068
00069 public:
00070 tree_string_index(char expected_lower = ' ', char expected_upper = '~',
00071 size_t list_size = 4);
00072 ~tree_string_index(void);
00073
00074 elem_t lookup(const char *the_key) const;
00075 elem_t lookup_prefix(const char *the_key, const char **suffix) const;
00076 bool exists(const char *the_key) const;
00077 index_handle<const char *, elem_t> enter(const char *the_key, elem_t);
00078 void remove(const char *the_key);
00079
00080 index_handle<const char *, elem_t> lookup_handle(const char *the_key)
00081 const;
00082 elem_t elem(index_handle<const char *, elem_t>) const;
00083 void remove(index_handle<const char *, elem_t>);
00084
00085 void clear(void);
00086
00087 void development_dump(ion *ip = stderr_ion,
00088 void (*node_func)(elem_t data, ion *ip) = 0);
00089 void development_internals_dump(ion *ip = stderr_ion);
00090 void development_stats_dump(ion *ip = stderr_ion);
00091 };
00092
00093
00094 #ifndef ANTIQUE_CPP
00095 /*
00096 * OPTIMIZATION: To limit duplication of generated code, we put in
00097 * an automatic optimization that reuses the ``void *'' instantiation
00098 * of tree_string index plus appropriate pointer casts for all
00099 * tree_string_index instantiations of pointer types.
00100 */
00101
00102 class void_holder
00103 {
00104 public:
00105 void *v;
00106
00107 void_holder(void *init_v) : v(init_v) { }
00108 void_holder(const void_holder &other) : v(other.v) { }
00109 ~void_holder(void) { }
00110
00111 const void_holder &operator=(const void_holder &other) {
00112 v = other.v; return(*this); }
00113 bool operator==(const void_holder other) { return (v == other.v); }
00114 bool operator!=(const void_holder other) { return (v != other.v); }
00115
00116 operator void *(void) const { return v; }
00117 template <class elem_t> operator elem_t *(void) const
00118 { return (elem_t *)v; }
00119 };
00120
00121 inline void_holder zero(void_holder *) { return 0; }
00122
00123 extern void (*indirection_function)(void *, ion *);
00124 extern void indirect_print(void_holder data, ion *ip);
00125
00126 template <class elem_t> class tree_string_index<elem_t *> :
00127 public Index<const char *, elem_t *>
00128 {
00129 private:
00130 tree_string_index<void_holder> _wrapped;
00131
00132 public:
00133 tree_string_index(char expected_lower = ' ', char expected_upper = '~',
00134 size_t list_size = 4) :
00135 _wrapped(expected_lower, expected_upper, list_size)
00136 { }
00137 ~tree_string_index(void) { }
00138
00139 elem_t *lookup(const char *the_key) const
00140 { return (elem_t *)(_wrapped.lookup(the_key)); }
00141 elem_t *lookup_prefix(const char *the_key, const char **suffix) const
00142 { return (elem_t *)(_wrapped.lookup_prefix(the_key, suffix)); }
00143 bool exists(const char *the_key) const
00144 { return _wrapped.exists(the_key); }
00145 index_handle<const char *, elem_t *> enter(const char *the_key,
00146 elem_t *the_elem)
00147 {
00148 return build_handle(_wrapped.enter(the_key, (void *)the_elem).
00149 raw_referenced_item());
00150 }
00151 void remove(const char *the_key) { _wrapped.remove(the_key); }
00152
00153 index_handle<const char *, elem_t *> lookup_handle(const char *the_key)
00154 const
00155 {
00156 return build_handle(_wrapped.lookup_handle(the_key).
00157 raw_referenced_item());
00158 }
00159 elem_t *elem(index_handle<const char *, elem_t *> the_handle) const
00160 {
00161 index_handle<const char *, void_holder> void_handle;
00162 void_handle.set_raw_referenced_item(the_handle.raw_referenced_item());
00163 return (elem_t *)(_wrapped.elem(void_handle));
00164 }
00165 void remove(index_handle<const char *, elem_t *> the_handle)
00166 {
00167 index_handle<const char *, void_holder> void_handle;
00168 void_handle.set_raw_referenced_item(the_handle.raw_referenced_item());
00169 _wrapped.remove(void_handle);
00170 }
00171
00172 void clear(void) { _wrapped.clear(); }
00173
00174 void development_dump(ion *ip = stderr_ion,
00175 void (*node_func)(elem_t *data, ion *ip) = 0)
00176 {
00177 void (*orig_func)(void *, ion *) = indirection_function;
00178 indirection_function = (void (*)(void *, ion *))node_func;
00179 _wrapped.development_dump(ip, indirect_print);
00180 indirection_function = orig_func;
00181 }
00182 void development_internals_dump(ion *ip = stderr_ion)
00183 { _wrapped.development_internals_dump(ip); }
00184 void development_stats_dump(ion *ip = stderr_ion)
00185 { _wrapped.development_stats_dump(ip); }
00186 };
00187 #endif /* not ANTIQUE_CPP */
00188
00189
00190 #ifdef INLINE_ALL_TEMPLATES
00191 #define DOING_TEMPLATE_INLINING
00192 #ifdef STY_H
00193 #include <sty/tree_string_index.cpp>
00194 #else
00195 #include "tree_string_index.cpp"
00196 #endif
00197 #undef DOING_TEMPLATE_INLINING
00198 #endif /* INLINE_ALL_TEMPLATES */
00199
00200
00201 #endif /* STY_TREE_STRING_INDEX_H */
