zorba-coders team mailing list archive

[Ghislain Fourny <ghislain.fourny@xxxxxxxxxx>]

Ghislain Fourny has proposed merging lp:~gislenius/zorba/qname-pool-refactoring into lp:zorba.

Requested reviews:
  Markos Zaharioudakis (markos-za)

For more details, see:
https://code.launchpad.net/~gislenius/zorba/qname-pool-refactoring/+merge/90447

This is a refactoring of the zorba::simplestore::QNameItem class and of the QName pool.

The most important changes are:
- Pool keeps track of all QNames that point to a given normalized QName (no more manual counter decrease needed, and simplified code).
- A QName points to its normalized counterpart with a raw pointer. Normalized QNames now point to themselves, so that no more conditional statement is needed in getNormalized() or in equals().
- A new QName constructor allows building QNames that are not in the pool, but that still point to their normalized counterpart in the pool.
- QName initialization code was delocated from QName pool to QNameItem class.
-- 
https://code.launchpad.net/~gislenius/zorba/qname-pool-refactoring/+merge/90447
Your team Zorba Coders is subscribed to branch lp:zorba.

=== modified file 'src/store/naive/atomic_items.cpp'
--- src/store/naive/atomic_items.cpp	2012-01-26 19:56:14 +0000
+++ src/store/naive/atomic_items.cpp	2012-01-27 15:07:36 +0000
@@ -597,31 +597,38 @@
 /*******************************************************************************
   class QNameItem
 ********************************************************************************/
-
-QNameItem::~QNameItem()
-{
-  if (isValid())
-  {
-    assert(theLocal.empty() || theNormQName == NULL);
-  }
-}
-
+QNameItem::QNameItem(const char* aNamespace,
+                     const char* aPrefix,
+                     const char* aLocalName)
+  : isInPool(false)
+{
+  initializeAsQNameNotInPool(zstring(aNamespace),
+                             zstring(aPrefix),
+                             zstring(aLocalName));
+}
+  
+QNameItem::QNameItem(const zstring& aNamespace,
+                     const zstring& aPrefix,
+                     const zstring& aLocalName)
+  : isInPool(false)
+{
+  initializeAsQNameNotInPool(aNamespace, aPrefix, aLocalName);
+}
 
 void QNameItem::free()
 {
-  GET_STORE().getQNamePool().remove(this);
-}
-
-
-QNameItem* QNameItem::getNormalized() const
-{
-  return (isNormalized() ? const_cast<QNameItem*>(this) : theNormQName.getp());
+  if (isInPool)
+  {
+    GET_STORE().getQNamePool().remove(this);
+  } else {
+    delete this;
+  }
 }
 
 
 uint32_t QNameItem::hash(long timezone, const XQPCollator* aCollation) const
 {
-  const void* tmp = getNormalized();
+  const void* tmp = theNormalizedQName;
   return hashfun::h32(&tmp, sizeof(void*), FNV_32_INIT);
 }
 
@@ -644,7 +651,8 @@
     long timezone,
     const XQPCollator* aCollation) const
 {
-  return (getNormalized() == static_cast<const QNameItem*>(item)->getNormalized());
+  return theNormalizedQName ==
+      static_cast<const QNameItem*>(item)->theNormalizedQName;
 }
 
 
@@ -731,6 +739,17 @@
   return res;
 }
 
+void QNameItem::initializeAsQNameNotInPool(const zstring& aNamespace,
+                                           const zstring& aPrefix,
+                                           const zstring& aLocalName)
+{
+  store::Item_t lPoolQName =
+      GET_STORE().getQNamePool().insert(aNamespace, aPrefix, aLocalName);
+  
+  initializeAsUnnormalizedQName(
+      static_cast<QNameItem*>(lPoolQName.getp())->getNormalized(),
+      aPrefix);
+}
 
 /*******************************************************************************
   class NotationItem
@@ -756,8 +775,8 @@
                           long timezone,
                           const XQPCollator* aCollation) const
 {
-  return (theQName->getNormalized() == 
-          static_cast<const NotationItem*>(item)->theQName->getNormalized());
+  return theQName->equals(
+      static_cast<const NotationItem*>(item)->theQName);
 }
 
 

=== modified file 'src/store/naive/atomic_items.h'
--- src/store/naive/atomic_items.h	2012-01-26 19:56:14 +0000
+++ src/store/naive/atomic_items.h	2012-01-27 15:07:36 +0000
@@ -334,40 +334,71 @@
 ********************************************************************************/
 class QNameItem : public AtomicItem
 {
+  /*****************************************************************************
+   Instances of this class can be classified into two categories:
+   - QNames in the pool. They are owned by the pool. There
+   can be only one QName in the pool with a given namespace, prefix and local name.
+   - QNames that are not in the pool. The user owns them and is responsible
+   for their destruction. The ternary constructors construct such QNames.
+   
+   Normalized QNames are QNames without a prefix and that are in the
+   pool. There is only one normalized QName with a given namespace and local name,
+   so that direct pointer comparison can be used to compare them.
+   
+   Each QName points to the equivalent normalized QName (same namespace and prefix)
+   which provides an efficient way of comparing two QNames.
+
+   A newly constructed instance of this class can be initialized as a normalized
+   QName (always in the pool), as an unnormalized QName in the pool or as an
+   unnormalized QName not in the pool. It can also be invalidated and initialized
+   again.
+  ****************************************************************************/
+  
+  // The QName pool is the only class authorized to edit namespace/prefix/local name.
   friend class QNamePool;
 
-protected:
-
-  zstring      theNamespace;
-  zstring      thePrefix;
-  zstring      theLocal;
-
-  QNameItem_t  theNormQName;
-
-  uint16_t     thePosition;
-  uint16_t     theNextFree;
-  uint16_t     thePrevFree;
+private:
+  zstring          theNamespace;
+  zstring          thePrefix;
+  zstring          theLocal;
+
+  // Points to the corresponding normalized QName in the pool (pool owns this pointer).
+  const QNameItem* theNormalizedQName;
+  
+  bool             isInPool;
+
+  // Used by the pool for managing the cache.
+  uint16_t         thePosition;
+  uint16_t         theNextFree;
+  uint16_t         thePrevFree;
 
 public:
-  virtual ~QNameItem();
-
-  QNameItem* getNormalized() const;
-
-  uint32_t hash(long timezone = 0, const XQPCollator* aCollation = 0) const;
-
-  bool equals(
-        const store::Item* item,
-        long timezone = 0,
-        const XQPCollator* aCollation = 0) const;
-
+  virtual ~QNameItem() {}
+
+  // zorba::store::Item interface.
+  void appendStringValue(zstring& buf) const;
+    
+  bool equals(const store::Item* item,
+              long timezone = 0,
+              const XQPCollator* aCollation = 0) const;
+    
+  store::Item_t getEBV() const;
+    
+  const zstring& getLocalName() const { return theLocal; }
+  
   const zstring& getNamespace() const { return theNamespace; }
-
+    
   const zstring& getPrefix() const { return thePrefix; }
-
-  const zstring& getLocalName() const { return getNormalized()->theLocal; }
-
+    
+  zstring getStringValue() const;
+  
+  void getStringValue2(zstring& val) const;
+  
+  store::Item* getType() const;
+    
   store::SchemaTypeCode getTypeCode() const { return store::XS_QNAME; }
 
+<<<<<<< TREE
   store::Item* getType() const;
 
   bool getEBV() const;
@@ -378,61 +409,98 @@
 
   void appendStringValue(zstring& buf) const;
 
+=======
+  uint32_t hash(long timezone = 0, const XQPCollator* aCollation = 0) const;
+  
+  // Class-specific extensions.
+  // Returns the normalized QName. Pointer comparison on normalized QNames is
+  // equivalent to using the equals() method. For example, a pointer to the
+  // normalized QName can be used as a key.
+  const QNameItem* getNormalized() const { return theNormalizedQName; }
+  
+  bool isBaseUri() const;
+  
+>>>>>>> MERGE-SOURCE
   bool isIdQName() const;
 
-  bool isBaseUri() const;
-
   zstring show() const;
 
 protected:
-  QNameItem() : thePosition(0), theNextFree(0), thePrevFree(0)
-  {
-  }
+  QNameItem() : theNormalizedQName(NULL),
+                isInPool(true),
+                thePosition(0),
+                theNextFree(0),
+                thePrevFree(0) {}
+  
+  QNameItem(const char* aNamespace,
+            const char* aPrefix,
+            const char* aLocalName);
+
+  QNameItem(const zstring& aNamespace,
+            const zstring& aPrefix,
+            const zstring& aLocalName);
 
   void free();
 
-  bool isValid() const { return !theLocal.empty() || theNormQName != NULL; }
+  bool isValid() const {
+    assert(theNormalizedQName == NULL || (
+        theNormalizedQName->isNormalized() &&
+        theNamespace == theNormalizedQName->theNamespace &&
+        theLocal == theNormalizedQName->theLocal));
+    return theNormalizedQName != NULL;
+  }
 
   bool isInCache() const { return thePosition != 0; }
 
   bool isOverflow() const { return thePosition == 0; }
 
-  bool isNormalized() const { return thePrefix.empty(); }
-
-  void setNormQName(QNameItem* qn)
-  {
-    assert(theLocal.empty() && theNormQName == NULL && !isNormalized());
-
-    theNormQName = qn;
-  }
-
-  void unsetNormQName()
-  {
-    assert(theLocal.empty() && theNormQName != NULL && !isNormalized());
-
-    theNormQName = NULL;
-  }
-
-  QNameItem* detachNormQName()
-  {
-    assert(theLocal.empty() && theNormQName != NULL && !isNormalized());
-
-    return theNormQName.release();
-  }
-
-  void setLocalName(const zstring& local)
-  {
-    assert(theLocal.empty() && theNormQName == NULL && isNormalized());
-
-    theLocal = local;
-  }
-
-  void unsetLocalName()
-  {
-    assert(!theLocal.empty() && theNormQName == NULL && isNormalized());
-
-    theLocal.clear();
-  }
+  bool isNormalized() const {
+    assert(theNormalizedQName != this || thePrefix.empty());
+    assert(theNormalizedQName == this || !thePrefix.empty());
+    return theNormalizedQName == this;
+  }
+
+  void initializeAsNormalizedQName(const zstring& aNamespace,
+                                   const zstring& aLocalName)
+  {
+    assert(!isValid());
+
+    theNormalizedQName = this;
+    theNamespace = aNamespace;
+    thePrefix.clear();
+    theLocal = aLocalName;
+
+    assert(isNormalized());
+    assert(isValid());
+  }
+  
+  void initializeAsUnnormalizedQName(const QNameItem* aNormalizedQName,
+                                     const zstring& aPrefix)
+  {
+    assert(!isValid());
+
+    theNormalizedQName = aNormalizedQName;
+    theNamespace = theNormalizedQName->theNamespace;
+    thePrefix = aPrefix;
+    theLocal = theNormalizedQName->theLocal;
+
+    assert(!isNormalized());
+    assert(isValid());
+  }
+
+  void initializeAsQNameNotInPool(const zstring& aNamespace,
+                                  const zstring& aPrefix,
+                                  const zstring& aLocalName);
+  
+  void invalidate()
+  {
+    assert(isValid());
+
+    theNormalizedQName = NULL;
+
+    assert(!isValid());
+  }
+
 };
 
 

=== modified file 'src/store/naive/qname_pool.cpp'
--- src/store/naive/qname_pool.cpp	2012-01-24 11:24:56 +0000
+++ src/store/naive/qname_pool.cpp	2012-01-27 15:07:36 +0000
@@ -66,17 +66,9 @@
   csize n = theHashSet.theHashTab.size();
   for (csize i = 0; i < n; ++i)
   {
-    if (!theHashSet.theHashTab[i].isFree())
-    {
-      QNameItem* qn = theHashSet.theHashTab[i].theItem;
-
-      // Make sure that the associated normalized QN will not be destroyed here
-      if (!qn->isNormalized())
-        qn->detachNormQName();
-
-      if (theHashSet.theHashTab[i].theItem->isOverflow())
-        delete theHashSet.theHashTab[i].theItem;
-    }
+    if (!theHashSet.theHashTab[i].isFree() &&
+        theHashSet.theHashTab[i].theItem->isOverflow())
+      delete theHashSet.theHashTab[i].theItem;
   }
 
   if (theCache != NULL)
@@ -94,7 +86,8 @@
 {
   SYNC_CODE(AutoMutex lock(&theHashSet.theMutex);)
 
-  if (qn->getRefCount() > 0)
+  if (qn->getRefCount() > 0 ||
+      hasNormalizingBackPointers(qn))
     return;
 
   if (qn->isInCache())
@@ -110,12 +103,29 @@
     // qn in the pool, and let the pool garbage-collect it later (if it still
     // unused). If however QNameItems may be referenced by regular pointers as
     // well, then qn must be removed from the pool and really deleted
+    unregisterNormalizingBackPointer(qn);
     theHashSet.eraseNoSync(qn);
+    qn->invalidate();
     delete qn;
   }
 }
 
+store::Item_t QNamePool::insert(const char* ns,
+                                const char* pre,
+                                const char* ln,
+                                bool        sync)
+{
+  return insert_internal(ns, pre, ln, sync);
+}
 
+store::Item_t QNamePool::insert(const zstring& ns,
+                                const zstring& pre,
+                                const zstring& ln,
+                                bool        sync)
+{
+  return insert_internal(ns, pre, ln, sync);
+}
+  
 /*******************************************************************************
   If the pool does not already contain a qname with the given namespace, prefix,
   and local name, then create such a qname, insert it in the pool and return an
@@ -126,16 +136,14 @@
   copied internally into zstring objects. So, it's always the caller who is
   resposnible for freeing the given strings.
 ********************************************************************************/
-store::Item_t QNamePool::insert(
+QNameItem* QNamePool::insert_internal(
     const char* ns,
     const char* pre,
     const char* ln,
     bool        sync)
 {
   QNameItem* qn;
-  QNameItem* normVictim = NULL;
   SYNC_CODE(bool haveLock = false;)
-  store::Item_t normItem;
   QNameItem* normQName = NULL;
 
   bool normalized = (pre == NULL || *pre == '\0');
@@ -160,13 +168,11 @@
                                   hval);
     if (entry == 0)
     {
+      // Build a new QName (either new object or in cache).
+      qn = cacheInsert();
       if (normalized)
       {
-        qn = cacheInsert(normVictim);
-
-        qn->theNamespace = pooledNs;
-        qn->thePrefix.clear();
-        qn->setLocalName(zstring(ln));
+        qn->initializeAsNormalizedQName(pooledNs, zstring(ln));
       }
       else
       {
@@ -175,18 +181,12 @@
           SYNC_CODE(theHashSet.theMutex.unlock();\
           haveLock = false;)
 
-          normItem = insert(ns, NULL, ln, false);
-
-          normQName = reinterpret_cast<QNameItem*>(normItem.getp());
+          normQName = insert_internal(ns, NULL, ln, false);
 
           goto retry;
         }
-
-        qn = cacheInsert(normVictim);
-
-        qn->theNamespace = normQName->theNamespace;
-        qn->thePrefix = pre;
-        qn->setNormQName(normQName);
+        qn->initializeAsUnnormalizedQName(normQName, pre);
+        registerNormalizingBackPointer(qn);
       }
 
       bool found;
@@ -211,11 +211,6 @@
     ZORBA_FATAL(0, "Unexpected exception");
   }
 
-  if (normVictim != NULL)
-  {
-    normVictim->removeReference();
-  }
-
   return qn;
 }
 
@@ -225,16 +220,14 @@
   and local name, then create such a qname, insert it in the pool and return an
   rchandle to it. Otherwise, return an rchandle to the existing qname. 
 ********************************************************************************/
-store::Item_t QNamePool::insert(
+QNameItem* QNamePool::insert_internal(
     const zstring& ns,
     const zstring& pre,
     const zstring& ln,
     bool sync)
 {
   QNameItem* qn = NULL;
-  QNameItem* normVictim = NULL;
   SYNC_CODE(bool haveLock = false;)
-  store::Item_t normItem;
   QNameItem* normQName = NULL;
 
   bool normalized = pre.empty();
@@ -256,13 +249,11 @@
                                   hval);
     if (entry == 0)
     {
+      // Build a new QName (either new object or in cache).
+      qn = cacheInsert();
       if (normalized)
       {
-        qn = cacheInsert(normVictim);
-
-        qn->theNamespace = pooledNs;
-        qn->thePrefix.clear();
-        qn->setLocalName(ln);
+        qn->initializeAsNormalizedQName(pooledNs, ln);
       }
       else
       {
@@ -271,18 +262,13 @@
           SYNC_CODE(theHashSet.theMutex.unlock();\
           haveLock = false;)
 
-          normItem = insert(pooledNs, zstring(), ln, false);
-
-          normQName = reinterpret_cast<QNameItem*>(normItem.getp());
+          normQName = insert_internal(pooledNs, zstring(), ln, false);
 
           goto retry;
         }
 
-        qn = cacheInsert(normVictim);
-      
-        qn->theNamespace = normQName->theNamespace;
-        qn->thePrefix = pre;
-        qn->setNormQName(normQName);
+        qn->initializeAsUnnormalizedQName(normQName, pre);
+        registerNormalizingBackPointer(qn);
       }
 
       bool found;
@@ -306,12 +292,6 @@
 
     ZORBA_FATAL(0, "Unexpected exception");
   }
-
-  if (normVictim != NULL)
-  {
-    normVictim->removeReference();
-  }
-
   return qn;
 }
 
@@ -322,10 +302,8 @@
   slot (if any) is removed from the pool. If the cache free list is empty a new
   QNameItem is allocated from the heap.
 ********************************************************************************/
-QNameItem* QNamePool::cacheInsert(QNameItem*& normVictim)
+QNameItem* QNamePool::cacheInsert()
 {
-  normVictim = NULL;
-
   if (theFirstFree != 0)
   {
     QNameItem* qn = &theCache[theFirstFree];
@@ -335,28 +313,10 @@
 
     if (qn->isValid())
     {
-      ulong hval = hashfun::h32(qn->getPrefix().c_str(),
-                                hashfun::h32(qn->getLocalName().c_str(),
-                                             hashfun::h32(qn->getNamespace().c_str())));
+      unregisterNormalizingBackPointer(qn);
+      ulong hval = CompareFunction::hash(qn);
       theHashSet.eraseNoSync(qn, hval);
-
-      if (!qn->isNormalized())
-      {
-        // Let NQ be the associated normalized qname. Here, wave the pointer
-        // to NQ and then set that pointer to null, without decrementing NQ's
-        // ref count of the. This way (a) we can decerement NQ's ref counter
-        // *after* releasing theHashSet.theMutex (otherwise, we would run into
-        // a self-deadlock if NQ must be be freed because it is not referenced
-        // from anywhere else), and (b) removeReference is not called
-        // when we overwite the pointer with the new local name.
-        normVictim = qn->detachNormQName();
-      }
-      else
-      {
-        // Unset qn->theLocal so that the assertion in setNormQName() (which is
-        // invoked later by the caller of this method) will not trigger.
-        qn->unsetLocalName();
-      }
+      qn->invalidate();
     }
 
     qn->theNextFree = qn->thePrevFree = 0;
@@ -428,6 +388,32 @@
 
   return NULL;
 }
+  
+bool QNamePool::hasNormalizingBackPointers(const QNameItem* aNormalizedQName)
+{
+  return !theWhoNormalizesToMe[aNormalizedQName].empty();
+}
+
+void QNamePool::registerNormalizingBackPointer(const QNameItem* aQName)
+{
+  if (!aQName->isNormalized())
+  {
+    theWhoNormalizesToMe[aQName->getNormalized()].insert(aQName);
+  }
+}
+
+void QNamePool::unregisterNormalizingBackPointer(const QNameItem* aQName)
+{
+  if (!aQName->isNormalized())
+  {
+    assert(theWhoNormalizesToMe[aQName->getNormalized()].find(aQName)
+         != theWhoNormalizesToMe[aQName->getNormalized()].end());
+    theWhoNormalizesToMe[aQName->getNormalized()].erase(aQName);
+  }
+}
+  
+  
+
 
 
 } // namespace store

=== modified file 'src/store/naive/qname_pool.h'
--- src/store/naive/qname_pool.h	2011-11-07 06:04:55 +0000
+++ src/store/naive/qname_pool.h	2012-01-27 15:07:36 +0000
@@ -17,6 +17,7 @@
 #define ZORBA_SIMPLE_STORE_QNAME_POOL
 
 #include <vector>
+#include <map>
 
 #include "zorbautils/hashfun.h"
 #include "zorbautils/hashset.h"
@@ -49,9 +50,14 @@
   theHashSet     : A hash set mapping qnames (i.e. triplets of strings) to
                    QName slots.
 
+ theWhoNormalizesToMe : theWhoNormalizesToMe[q] is the array of all QNames of 
+                   which q is the normalized QName. This allows to prevent
+                   removing q from the pool if there are QNames pointing to it.
 ********************************************************************************/
 class QNamePool
 {
+  // Allow QName items to register/unregister pointers to normalized QName.
+  friend class QNameItem;
 protected:
 
   class CompareFunction
@@ -101,27 +107,38 @@
 
   StringPool        * theNamespacePool;
 
+  std::map<const QNameItem*, std::set<const QNameItem*> >
+                      theWhoNormalizesToMe;
+
 public:
   QNamePool(ulong size, StringPool* nspool);
 
   ~QNamePool();
 
-  store::Item_t insert(
-        const char* ns,
-        const char* pre,
-        const char* ln,
-        bool        sync = true);
-
-  store::Item_t insert(
-        const zstring& ns,
-        const zstring& pre,
-        const zstring& ln,
-        bool sync = true);
-
+  store::Item_t insert(const char* ns,
+                       const char* pre,
+                       const char* ln,
+                       bool        sync = true);
+  
+  store::Item_t insert(const zstring& ns,
+                       const zstring& pre,
+                       const zstring& ln,
+                       bool sync = true);
+  
   void remove(QNameItem* qn);
 
 protected:
-  QNameItem* cacheInsert(QNameItem*& normVictim);
+  QNameItem* insert_internal(const char* ns,
+                             const char* pre,
+                             const char* ln,
+                             bool sync = true);
+  
+  QNameItem* insert_internal(const zstring& ns,
+                             const zstring& pre,
+                             const zstring& ln,
+                             bool sync = true);
+  
+  QNameItem* cacheInsert();
 
   void cachePin(QNameItem* qn);
 
@@ -133,6 +150,10 @@
         ulong       prelen,
         ulong       lnlen,
         ulong       hval);
+  
+  bool hasNormalizingBackPointers(const QNameItem* aNormalizedQName);
+  void registerNormalizingBackPointer(const QNameItem* aQName);
+  void unregisterNormalizingBackPointer(const QNameItem* aQName);
 };