zorba-coders team mailing list archive

[Ghislain Fourny <ghislain.fourny@xxxxxxxxxx>]

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

Requested reviews:
  Matthias Brantner (matthias-brantner)
  Markos Zaharioudakis (markos-za)

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

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

The most important changes are:
- 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/~zorba-coders/zorba/qname-pool-refactoring/+merge/94953
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-02-24 03:57:49 +0000
+++ src/store/naive/atomic_items.cpp	2012-02-28 12:45:50 +0000
@@ -597,31 +597,43 @@
 /*******************************************************************************
   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());
+  QNamePool& thePool = GET_STORE().getQNamePool();
+  if (isInPool)
+  {
+    thePool.remove(this);
+    return;
+  }
+  
+  assert(!isNormalized());
+  QNameItem* lNormalizationVictim;
+  invalidate(false, &lNormalizationVictim);
+  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 +656,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 +744,19 @@
   return res;
 }
 
+void QNameItem::initializeAsQNameNotInPool(const zstring& aNamespace,
+                                           const zstring& aPrefix,
+                                           const zstring& aLocalName)
+{
+  assert(!isValid());
+
+  store::Item_t lPoolQName =
+      GET_STORE().getQNamePool().insert(aNamespace, aPrefix, aLocalName);
+  initializeAsUnnormalizedQName(
+      static_cast<QNameItem*>(lPoolQName.getp())->getNormalized(),
+      aPrefix);
+  isInPool = false;
+}
 
 /*******************************************************************************
   class NotationItem
@@ -756,8 +782,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-02-24 16:47:43 +0000
+++ src/store/naive/atomic_items.h	2012-02-28 12:45:50 +0000
@@ -338,105 +338,174 @@
 ********************************************************************************/
 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;
+    
+  bool 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; }
 
-  store::Item* getType() const;
-
-  bool getEBV() const;
-
-  zstring getStringValue() const;
-
-  void getStringValue2(zstring& val) const;
-
-  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;
+  
   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;
+    theNormalizedQName->addReference();
+    theNamespace = theNormalizedQName->theNamespace;
+    thePrefix = aPrefix;
+    theLocal = theNormalizedQName->theLocal;
+
+    assert(!isNormalized());
+    assert(isValid());
+  }
+
+  void initializeAsQNameNotInPool(const zstring& aNamespace,
+                                  const zstring& aPrefix,
+                                  const zstring& aLocalName);
+  
+  // If asynchronous is true, caller must later remove reference to returned aNormalizationVictim.
+  void invalidate(bool asynchronous, QNameItem** aNormalizationVictim)
+  {
+    assert(isValid());
+
+    if (!isNormalized())
+    {
+      if (asynchronous)
+      {
+        *aNormalizationVictim = const_cast<QNameItem*>(theNormalizedQName);
+      }
+      else
+      {
+        QNameItem* lNormalized = const_cast<QNameItem*>(theNormalizedQName);
+        lNormalized->removeReference();
+      }
+    }
+    theNormalizedQName = NULL;
+
+    assert(!isValid());
+  }
+
 };
 
 

=== modified file 'src/store/naive/qname_pool.cpp'
--- src/store/naive/qname_pool.cpp	2012-02-15 10:25:02 +0000
+++ src/store/naive/qname_pool.cpp	2012-02-28 12:45:50 +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)
@@ -110,12 +102,19 @@
     // 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
+    QNameItem* normVictim = NULL;
     theHashSet.eraseNoSync(qn);
+    qn->invalidate(true, &normVictim);
     delete qn;
+
+    if (normVictim)
+    {
+      // Tail call. Should avoid deadlock because no new stack frame.
+      normVictim->removeReference();
+    }
   }
 }
 
-
 /*******************************************************************************
   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
@@ -162,11 +161,9 @@
     {
       if (normalized)
       {
+        // Build a new QName (either new object or in cache).
         qn = cacheInsert(normVictim);
-
-        qn->theNamespace = pooledNs;
-        qn->thePrefix.clear();
-        qn->setLocalName(zstring(ln));
+        qn->initializeAsNormalizedQName(pooledNs, zstring(ln));
       }
       else
       {
@@ -176,17 +173,12 @@
           haveLock = false;)
 
           normItem = insert(ns, NULL, ln, false);
-
-          normQName = reinterpret_cast<QNameItem*>(normItem.getp());
-
+          normQName = static_cast<QNameItem*>(normItem.getp());
           goto retry;
         }
-
+        // Build a new QName (either new object or in cache).
         qn = cacheInsert(normVictim);
-
-        qn->theNamespace = normQName->theNamespace;
-        qn->thePrefix = pre;
-        qn->setNormQName(normQName);
+        qn->initializeAsUnnormalizedQName(normQName, pre);
       }
 
       bool found;
@@ -258,11 +250,9 @@
     {
       if (normalized)
       {
+        // Build a new QName (either new object or in cache).
         qn = cacheInsert(normVictim);
-
-        qn->theNamespace = pooledNs;
-        qn->thePrefix.clear();
-        qn->setLocalName(ln);
+        qn->initializeAsNormalizedQName(pooledNs, ln);
       }
       else
       {
@@ -271,18 +261,15 @@
           SYNC_CODE(theHashSet.theMutex.unlock();\
           haveLock = false;)
 
+          // This call will need the lock.
           normItem = insert(pooledNs, zstring(), ln, false);
-
-          normQName = reinterpret_cast<QNameItem*>(normItem.getp());
+          normQName = static_cast<QNameItem*>(normItem.getp());
 
           goto retry;
         }
-
+        // Build a new QName (either new object or in cache).
         qn = cacheInsert(normVictim);
-      
-        qn->theNamespace = normQName->theNamespace;
-        qn->thePrefix = pre;
-        qn->setNormQName(normQName);
+        qn->initializeAsUnnormalizedQName(normQName, pre);
       }
 
       bool found;
@@ -324,8 +311,7 @@
 ********************************************************************************/
 QNameItem* QNamePool::cacheInsert(QNameItem*& normVictim)
 {
-  normVictim = NULL;
-
+  assert (normVictim == NULL);
   if (theFirstFree != 0)
   {
     QNameItem* qn = &theCache[theFirstFree];
@@ -335,28 +321,9 @@
 
     if (qn->isValid())
     {
-      ulong hval = hashfun::h32(qn->getPrefix().c_str(),
-                                hashfun::h32(qn->getLocalName().c_str(),
-                                             hashfun::h32(qn->getNamespace().c_str())));
+      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(true, &normVictim);
     }
 
     qn->theNextFree = qn->thePrevFree = 0;

=== modified file 'src/store/naive/qname_pool.h'
--- src/store/naive/qname_pool.h	2012-02-22 16:30:24 +0000
+++ src/store/naive/qname_pool.h	2012-02-28 12:45:50 +0000
@@ -49,6 +49,9 @@
   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
 {
@@ -106,18 +109,16 @@
 
   ~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:
@@ -133,6 +134,7 @@
         ulong       prelen,
         ulong       lnlen,
         ulong       hval);
+  
 };