A number of years ago, I wrote a XML/C binding tool atop the gnome SAX parser. It's able to handle anything in a DTD and a lot of things from XML Schema. I stopped working on it as it could do everything I had use for.
http://xmel.sourceforge.net/
It does O(1) access to attributes as well, since it does binding.