a20c0a7ba762e49942095aff62bb6418c106d1bc
kent
  Tue Feb 26 22:51:45 2013 -0800
Adding support for multiple values with same key to bPlusTree.
diff --git src/lib/bPlusTree.c src/lib/bPlusTree.c
index 86398c3..fcffba8 100644
--- src/lib/bPlusTree.c
+++ src/lib/bPlusTree.c
@@ -150,30 +150,89 @@
     /* Scan info for first file offset. */
     bits64 fileOffset = udcReadBits64(bpt->udc, isSwapped);
 
     /* Loop through remainder. */
     for (i=1; i<childCount; ++i)
 	{
 	udcMustRead(bpt->udc, keyBuf, bpt->keySize);
 	if (memcmp(key, keyBuf, bpt->keySize) < 0)
 	    break;
 	fileOffset = udcReadBits64(bpt->udc, isSwapped);
 	}
     return rFind(bpt, fileOffset, key, val);
     }
 }
 
+static void rFindMulti(struct bptFile *bpt, bits64 blockStart, void *key, struct slRef **pList)
+/* Find values corresponding to key and add them to pList */
+{
+/* Seek to start of block. */
+udcSeek(bpt->udc, blockStart);
+
+/* Read block header. */
+UBYTE isLeaf;
+UBYTE reserved;
+bits16 i, childCount;
+udcMustReadOne(bpt->udc, isLeaf);
+udcMustReadOne(bpt->udc, reserved);
+boolean isSwapped = bpt->isSwapped;
+childCount = udcReadBits16(bpt->udc, isSwapped);
+
+int keySize = bpt->keySize;
+UBYTE keyBuf[keySize];   /* Place to put a key, buffered on stack. */
+UBYTE valBuf[bpt->valSize];   /* Place to put a value, buffered on stack. */
+
+if (isLeaf)
+    {
+    for (i=0; i<childCount; ++i)
+        {
+	udcMustRead(bpt->udc, keyBuf, keySize);
+	udcMustRead(bpt->udc, valBuf, bpt->valSize);
+	if (memcmp(key, keyBuf, keySize) == 0)
+	    {
+	    void *val = cloneMem(valBuf, bpt->valSize);
+	    refAdd(pList, val);
+	    }
+	}
+    }
+else
+    {
+    /* Read first key and first file offset. */
+    udcMustRead(bpt->udc, keyBuf, keySize);
+    bits64 lastFileOffset = udcReadBits64(bpt->udc, isSwapped);
+    bits64 fileOffset = lastFileOffset;
+    int lastCmp = memcmp(key, keyBuf, keySize);
+
+    /* Loop through remainder. */
+    for (i=1; i<childCount; ++i)
+	{
+	udcMustRead(bpt->udc, keyBuf, keySize);
+	fileOffset = udcReadBits64(bpt->udc, isSwapped);
+	int cmp = memcmp(key, keyBuf, keySize);
+	if (lastCmp >= 0 && cmp <= 0)
+	    rFindMulti(bpt, lastFileOffset, key, pList);
+	if (cmp < 0)
+	    return;
+	lastCmp = cmp;
+	lastFileOffset = fileOffset;
+	}
+    /* If made it all the way to end, do last one too. */
+    rFindMulti(bpt, fileOffset, key, pList);
+    }
+}
+
+
 static void rTraverse(struct bptFile *bpt, bits64 blockStart, void *context, 
     void (*callback)(void *context, void *key, int keySize, void *val, int valSize) )
 /* Recursively go across tree, calling callback at leaves. */
 {
 /* Seek to start of block. */
 udcSeek(bpt->udc, blockStart);
 
 /* Read block header. */
 UBYTE isLeaf;
 UBYTE reserved;
 bits16 i, childCount;
 udcMustReadOne(bpt->udc, isLeaf);
 udcMustReadOne(bpt->udc, reserved);
 boolean isSwapped = bpt->isSwapped;
 childCount = udcReadBits16(bpt->udc, isSwapped);
@@ -258,57 +317,80 @@
 {
 bits64 offset = bptDataOffset(bpt, itemPos);
 udcSeek(bpt->udc, offset);
 udcMustRead(bpt->udc, result, bpt->keySize);
 }
 
 void bptStringKeyAtPos(struct bptFile *bpt, bits64 itemPos, char *result, int maxResultSize)
 /* Fill in result with the key at given itemPos.  The maxResultSize should be 1+bpt->keySize
  * to accommodate zero termination of string. */
 {
 assert(maxResultSize > bpt->keySize);
 bptKeyAtPos(bpt, itemPos, result);
 result[bpt->keySize] = 0;
 }
 
-boolean bptFileFind(struct bptFile *bpt, void *key, int keySize, void *val, int valSize)
-/* Find value associated with key.  Return TRUE if it's found. 
-*  Parameters:
-*     bpt - file handle returned by bptFileOpen
-*     key - pointer to key string, which needs to be bpt->keySize long
-*     val - pointer to where to put retrieved value
-*/
+static boolean bptFileFindMaybeMulti(struct bptFile *bpt, void *key, int keySize, int valSize,
+    boolean multi, void *singleVal, struct slRef **multiVal)
+/* Do either a single or multiple find depending in multi parameter.  Only one of singleVal
+ * or multiVal should be non-NULL, depending on the same parameter. */
 {
 /* Check key size vs. file key size, and act appropriately.  If need be copy key to a local
  * buffer and zero-extend it. */
 if (keySize > bpt->keySize)
     return FALSE;
 char keyBuf[keySize];
 if (keySize != bpt->keySize)
     {
     memcpy(keyBuf, key, keySize);
     memset(keyBuf+keySize, 0, bpt->keySize - keySize);
     key = keyBuf;
     }
 
 /* Make sure the valSize matches what's in file. */
 if (valSize != bpt->valSize)
     errAbort("Value size mismatch between bptFileFind (valSize=%d) and %s (valSize=%d)",
     	valSize, bpt->fileName, bpt->valSize);
 
-/* Call recursive finder. */
-return rFind(bpt, bpt->rootOffset, key, val);
+if (multi)
+    {
+    rFindMulti(bpt, bpt->rootOffset, key, multiVal);
+    return *multiVal != NULL;
+    }
+else
+    return rFind(bpt, bpt->rootOffset, key, singleVal);
+}
+
+boolean bptFileFind(struct bptFile *bpt, void *key, int keySize, void *val, int valSize)
+/* Find value associated with key.  Return TRUE if it's found. 
+*  Parameters:
+*     bpt - file handle returned by bptFileOpen
+*     key - pointer to key string, which needs to be bpt->keySize long
+*     val - pointer to where to put retrieved value
+*/
+{
+return bptFileFindMaybeMulti(bpt, key, keySize, valSize, FALSE, val, NULL);
+}
+
+struct slRef *bptFileFindMultiple(struct bptFile *bpt, void *key, int keySize, int valSize)
+/* Find all values associated with key.  Store this in ->val item of returned list. 
+ * Do a slRefFreeListAndVals() on list when done. */
+{
+struct slRef *list = NULL;
+bptFileFindMaybeMulti(bpt, key, keySize, valSize, TRUE, NULL, &list);
+slReverse(&list);
+return list;
 }
 
 void bptFileTraverse(struct bptFile *bpt, void *context,
     void (*callback)(void *context, void *key, int keySize, void *val, int valSize) )
 /* Traverse bPlusTree on file, calling supplied callback function at each
  * leaf item. */
 {
 return rTraverse(bpt, bpt->rootOffset, context, callback);
 }
 
 
 /* This section of code deals with making balanced b+ trees given a sorted array as input.
  * The difficult part is mostly just calculating the offsets of various things.  As an example
  * if you had the sorted array:
  *   01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27