From 253bd8d0ee679e72731308456cea91eb9600ff70 Mon Sep 17 00:00:00 2001
From: simonmar <unknown>
Date: Tue, 28 Sep 2004 12:38:55 +0000
Subject: [PATCH] [project @ 2004-09-28 12:38:55 by simonmar] Add update, and
 improve documentation of insert.

---
 Data/HashTable.hs |   48 ++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 46 insertions(+), 2 deletions(-)

diff --git a/Data/HashTable.hs b/Data/HashTable.hs
index 37ddb5e..cc4c32b 100644
--- a/Data/HashTable.hs
+++ b/Data/HashTable.hs
@@ -19,7 +19,7 @@
 
 module Data.HashTable (
 	-- * Basic hash table operations
-	HashTable, new, insert, delete, lookup,
+	HashTable, new, insert, delete, lookup, update,
 	-- * Converting to and from lists
 	fromList, toList,
 	-- * Hash functions
@@ -209,7 +209,14 @@ new cmp hash_fn = do
 -- -----------------------------------------------------------------------------
 -- Inserting a key\/value pair into the hash table
 
--- | Inserts an key\/value mapping into the hash table.
+-- | Inserts an key\/value mapping into the hash table.  
+--
+-- Note that 'insert' doesn't remove the old entry from the table -
+-- the behaviour is like an association list, where 'lookup' returns
+-- the most-recently-inserted mapping for a key in the table.  The
+-- reason for this is to keep 'insert' as efficient as possible.  If
+-- you need to update a mapping, then we provide 'update'.
+--
 insert :: HashTable key val -> key -> val -> IO ()
 
 insert (HashTable ref) key val = do
@@ -311,6 +318,43 @@ delete (HashTable ref) key = do
   return ()
 
 -- -----------------------------------------------------------------------------
+-- Deleting a mapping from the hash table
+
+-- | Updates an entry in the hash table, returning 'True' if there was
+-- already an entry for this key, or 'False' otherwise.  After 'update'
+-- there will always be exactly one entry for the given key in the table.
+--
+-- 'insert' is more efficient than 'update' if you don't care about
+-- multiple entries, or you know for sure that multiple entries can't
+-- occur.  However, 'update' is more efficient than 'delete' followed
+-- by 'insert'.
+update :: HashTable key val -> key -> val -> IO Bool
+
+update (HashTable ref) key val = do
+  table@HT{ kcount=k, bcount=b, dir=dir, cmp=cmp } <- readIORef ref
+  let table1 = table{ kcount = k+1 }
+  -- optimistically expand the table
+  table2 <-
+	if (k > hLOAD * b)
+	   then expandHashTable table1
+	   else return table1
+  writeIORef ref table2
+  (segment_index,segment_offset) <- tableLocation table2 key
+  segment <- myReadArray dir segment_index
+  bucket <- myReadArray segment segment_offset
+  let 
+    (deleted,bucket') = foldr filt (0,[]) bucket
+    filt pair@(k,v) (deleted,bucket)
+	| key `cmp` k = (deleted+1, bucket)
+	| otherwise   = (deleted,   pair:bucket)
+  -- in  
+  myWriteArray segment segment_offset ((key,val):bucket')
+  -- update the table load, taking into account the number of
+  -- items we just deleted.
+  writeIORef ref table2{ kcount = kcount table2 - deleted }
+  return (deleted /= 0)
+
+-- -----------------------------------------------------------------------------
 -- Looking up an entry in the hash table
 
 -- | Looks up the value of a key in the hash table.
-- 
1.7.10.4