Utility Libraries for BREW – A Hash Table Class

Abstract

This article is the last one in a series that presents possible implementations of utility libraries in BREW. A hash table is introduced together with a XML parser.

A (Hash) Table…

Hash tables are unfortunately not part of the STL, even if unofficially several implementations are available ^[1]. They are very popular constructs in Java 1.1 (as well as J2ME) so that having a C++ equivalent implementation allows smooth code porting from one language to the other. Our implementation is very simple and offers no surprises:

template<class K, class V > 
class BrewHashtable ;

BrewHashtable() ;

BrewHashtable(int hashSize);

BrewHashtable(const BrewHashtable<K, V>&);

void put(const K& k, const V& d)  ;

int get(const K& k, V& d); //returns 0 for success, 1 otherwise

template<class T >
void keys(T& bk);

template<class T>
void elements(T& bk);

int remove(const K& key);

void remove_all();

int size() const;

bool isEmpty() const;

The only thing that might rise an eyebrow is how the return value is passed by refrence in get(), keys(), and elements() — a marginally better approach in terms of efficiency. Using BrewHashtable is straightforward:

BrewHashtable<int, int> hint;
   hint.put(10, 20);
   int res;
   hint.get(10, res);

BrewHashtable< String, int> hstr;
   hstr.put("1", 220);
   hstr.put("2", 333);
   hstr.put("3", 22440);
   hstr.put("4", 888);
   hstr.get("2", res);

…For the grand finale…

I decided to demonstrate the usage of the 3 libraries in an example of a naive XML parser. Whether XML on BREW is appropriate is another subject — and the advent of Web services complicated the matter. For the sake of this discussion suffices to say that as long as the developer is in control of the whole process and keeps the upside/downside balance in equilibrium, then nothing bad can happen.

To be capable of such a fine-grain of control, adequate tools are needed. Such a tool may be a parser that can be easily tailored to the extent of the application. Consider that the vast majority of XML files used by BREW devices (if any) are generated and checked for conformance on the server side and send via HTTP to the device. This reduces the need for a fully conformant parser on the BREW side. Moreover unused constructs (like comments) can be easily removed to decrease the size of the file, mitigating even more of the implementation needs of the parser.

Taking into account the above premises, it looks like a light and easily adaptable parser might be exactly what’s needed for BREW projects. The developer can immediately customize it to accept various XML constructs. An additional requirement might be avoidance of recursion, as stack size and performance penalties might make the product unusable.

My unsophisticated attempt (XMLParser) is mostly a template that you can easily build on. It is designed as a finite state machine (FSM) accepting states like:

• EXIT_LOOP, END_FOUND, END, START, CONTENT
• START – looking for start of tag
• END – looking for end of tag
• END_FOUND
• CONTENT – looking for XML content
• EXIT_LOOP – an exit condition

Additional states can be added as needed (for example COMMENT or CDATA).
Every state has a member function associated, and states are kept in a hash table defined like:

enum STATE {EXIT_LOOP, END_FOUND, END, START, CONTENT};
typedef STATE (XMLParser::*FUNC)() ;
typedef BrewHashtable<int, FUNC> States;
States states_; 

XMLParser fills the states_ hash table at construct time:

states_.put(START, &XMLParser::findStart);
states_.put(END, &XMLParser::findEnd);
states_.put(END_FOUND, &XMLParser::endFound);
states_.put(CONTENT, &XMLParser::findContent);

Please note that if a state is not needed it can be conveniently bypassed. For example, assuming we are not interested in CONTENT we can replace:

states_.put(CONTENT, &XMLParser::findContent);

with

states_.put(CONTENT, &XMLParser::findStart);

The main loop of the FSM can now be easily expressed as:

while (state != EXIT_LOOP)
{
   states_.get(state, f);
   state = (*this.*f)();
}

Basically that’s all. XMLParser can work as a DOM or SAX parser. I provided a small interface for DOM manipulation — XMLbit. This class wraps a XML element and allows DOM traversals. As I mentioned before the implementation is minimal, methods like nextSibling(), firstChild(), and findChild() are missing. If you ever need these missing methods, they can be added and customized to the actual requirements.

The whole parsing process is hidden behind a facade:

XMLbit* root = XMLParser::getRoot(xmlSource);
XMLbit keeps internally all its children in a BrewVector. 

XMLParser is very small (due to extensive use of containers) and offers a good performance (being comparable or faster than similar parsers). But the main benefit in my opinion lies in the capability of easily devising the right parser for the job.

Downloads

The source code: BREWUtil.zip – 85 kb.

References:

^[1] Nicolai M. Josuttis – The C++ Standard Library. A Tutorial and Reference; Addison-Wesley, 2001

About the Author

Radu Braniste is Director of Technology at Epicad. He can be contacted at rbraniste@epicad.com

# # #