xml-dev - Re: SAX2: Interning names in namespaces

[terje@in-progress.com (Terje Norderhaug)]

At 4:46 AM 2/5/00, Stefan Haustein wrote:
>>
>> PROPOSAL
>>
>> I suggest that parsers interns each name as a separate string in the
>> namespace it belong to. This should guarantee that two equal names in the
>> same namespace are identical, and that two equal names in different
>> namespaces are unidentical.
>
>Sounds too complicated for broad acceptance [...]

It is straight-forward to implement. Here is pseudo code for one possible
implementation using hash tables:

constant namespaces = make new hashtable with equality as test

function internName (namestring, URI):
  namespace = namespaces.find(URI)
  if no namespace
    namespace = make new hashtable with equality as test
    namespaces.insert(URI, namespace)
  end if
  name = namespace.find(namestring)
  if no name
    name = namestring.copy
    namespace.insert(name, name)
  end if
  return name
end function

Parsers should of course be free to choose more complex implementations if
they find it beneficial. A parser might for example avoid using hash tables
but instead do the interning during reading time by navigating a structure
based on each character read.

> [...] and I must admit that I do not see the great benefit.

One of several benefits is that it simplifies and speeds up determining
whether two names are the same as defined by the namespace recommendation.

If names are not interned, determining whether two names are the same
involves testing both namespaces and names for equality. Two names are the
same if:

  namespace1.equals(namespace2) && name1.equals(name2)

If the names are interned globally, it only speeds up testing the two names
while still requiring comparing the namespaces:

  namespace1.equals(namespace2) && name1 == name2

Given that names are interned in namespaces, one only have to test whether
the two names are identical to determine whether the two names are the
same:

  name1 == name2

Note that in the latter case, comparing namespaces are no longer required.
This allows major simplifications of code as one no longer have to pass
namespaces with names.

-- Terje <terje@in-progress.com> | Media Design in*Progress

   Software for Mac Web Professionals at <http://www.in-progress.com>
   Take advantage of XML with Emile, the first XML editor for Mac!