diff --git a/src/fccache.c b/src/fccache.c
index c9e7256..dfe9520 100644
--- a/src/fccache.c
+++ b/src/fccache.c
@@ -62,6 +62,7 @@
 	int fd;
 	uuid_t uuid;
 	char out[37];
+	FcBool (* hash_add) (FcHashTable *, void*, void*);
 
 	atomic = FcAtomicCreate (uuidname);
 	if (!atomic)
@@ -81,7 +82,11 @@
 	    goto bail3;
 	}
 	uuid_generate_random (uuid);
-	if (!FcHashTableAdd (config->uuid_table, dir, uuid))
+	if (force)
+	    hash_add = FcHashTableReplace;
+	else
+	    hash_add = FcHashTableAdd;
+	if (!hash_add (config->uuid_table, dir, uuid))
 	{
 	    ret = FcFalse;
 	    goto bail3;
diff --git a/src/fchash.c b/src/fchash.c
index 54e2334..32e59c5 100644
--- a/src/fchash.c
+++ b/src/fchash.c
@@ -137,10 +137,11 @@
     return FcFalse;
 }
 
-FcBool
-FcHashTableAdd (FcHashTable *table,
-		void        *key,
-		void        *value)
+static FcBool
+FcHashTableAddInternal (FcHashTable *table,
+			void        *key,
+			void        *value,
+			FcBool       replace)
 {
     FcHashBucket **prev, *bucket, *b;
     FcChar32 hash = table->hash_func (key);
@@ -167,17 +168,43 @@
 	    table->value_destroy_func (bucket->value);
 	free (bucket);
 
-	return FcFalse;
+	return !ret;
     }
   retry:
     for (prev = &table->buckets[hash % FC_HASH_SIZE];
 	 (b = fc_atomic_ptr_get (prev)); prev = &(b->next))
     {
 	if (!table->compare_func (bucket->key, key))
+	{
+	    if (replace)
+	    {
+		if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
+		    goto retry;
+		bucket = b;
+	    }
+	    else
+		ret = FcTrue;
 	    goto destroy;
+	}
     }
     if (!fc_atomic_ptr_cmpexch (prev, b, bucket))
 	goto retry;
 
     return FcTrue;
 }
+
+FcBool
+FcHashTableAdd (FcHashTable *table,
+		void        *key,
+		void        *value)
+{
+    return FcHashTableAddInternal (table, key, value, FcFalse);
+}
+
+FcBool
+FcHashTableReplace (FcHashTable *table,
+		    void        *key,
+		    void        *value)
+{
+    return FcHashTableAddInternal (table, key, value, FcTrue);
+}
diff --git a/src/fcint.h b/src/fcint.h
index 3559ad6..6185f5a 100644
--- a/src/fcint.h
+++ b/src/fcint.h
@@ -1335,5 +1335,9 @@
 		void        *key,
 		void        *value);
 
+FcPrivate FcBool
+FcHashTableReplace (FcHashTable *table,
+		    void        *key,
+		    void        *value);
 
 #endif /* _FC_INT_H_ */