[Bf-blender-cvs] [83cbcef] master: Add edgehash remove, clear functions, Heap clear

Campbell Barton noreply at git.blender.org
Tue Dec 9 00:34:37 CET 2014


Commit: 83cbcefac8349d5ff46b721318ca180dd8817af5
Author: Campbell Barton
Date:   Tue Dec 9 00:32:20 2014 +0100
Branches: master
https://developer.blender.org/rB83cbcefac8349d5ff46b721318ca180dd8817af5

Add edgehash remove, clear functions, Heap clear

Edgehash was missing removal functions (remove, popkey, clear),
since it wasn't needed so far, but is based on same code as ghash which has them.

also add heap clear() method so we can reuse heaps.

(needed for upcoming fix).

===================================================================

M	source/blender/blenlib/BLI_edgehash.h
M	source/blender/blenlib/BLI_heap.h
M	source/blender/blenlib/intern/BLI_heap.c
M	source/blender/blenlib/intern/edgehash.c

===================================================================

diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h
index a045548..c5323a4 100644
--- a/source/blender/blenlib/BLI_edgehash.h
+++ b/source/blender/blenlib/BLI_edgehash.h
@@ -55,6 +55,9 @@ bool            BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned in
 void           *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
 void           *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val_default) ATTR_WARN_UNUSED_RESULT;
 void          **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
+bool            BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp);
+
+void           *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
 bool            BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1) ATTR_WARN_UNUSED_RESULT;
 int             BLI_edgehash_size(EdgeHash *eh) ATTR_WARN_UNUSED_RESULT;
 void            BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h
index ac9edfd..ea36109 100644
--- a/source/blender/blenlib/BLI_heap.h
+++ b/source/blender/blenlib/BLI_heap.h
@@ -37,6 +37,7 @@ typedef void (*HeapFreeFP)(void *ptr);
  * are recycled, so memory usage will not shrink. */
 Heap           *BLI_heap_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT;
 Heap           *BLI_heap_new(void) ATTR_WARN_UNUSED_RESULT;
+void            BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1);
 void            BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1);
 
 /* Insert heap node with a value (often a 'cost') and pointer into the heap,
diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index 05bd107..66dfa87 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -138,9 +138,9 @@ Heap *BLI_heap_new(void)
 
 void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
 {
-	unsigned int i;
-
 	if (ptrfreefp) {
+		unsigned int i;
+
 		for (i = 0; i < heap->size; i++) {
 			ptrfreefp(heap->tree[i]->ptr);
 		}
@@ -151,6 +151,21 @@ void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp)
 	MEM_freeN(heap);
 }
 
+void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp)
+{
+	if (ptrfreefp) {
+		unsigned int i;
+
+		for (i = 0; i < heap->size; i++) {
+			ptrfreefp(heap->tree[i]->ptr);
+		}
+	}
+
+	heap->size = 0;
+	BLI_memarena_clear(heap->arena);
+	heap->freenodes = NULL;
+}
+
 HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
 {
 	HeapNode *node;
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c
index 4ed82f8..385d9ec 100644
--- a/source/blender/blenlib/intern/edgehash.c
+++ b/source/blender/blenlib/intern/edgehash.c
@@ -146,7 +146,7 @@ BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentri
 
 /**
  * Internal lookup function.
- * Takes a hash argument to avoid calling #ghash_keyhash multiple times.
+ * Takes a hash argument to avoid calling #edgehash_keyhash multiple times.
  */
 BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1,
                                                const unsigned int hash)
@@ -256,6 +256,35 @@ BLI_INLINE void edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1,
 }
 
 /**
+ * Remove the entry and return it, caller must free from eh->epool.
+ */
+static EdgeEntry *edgehash_remove_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp,
+                                     unsigned int hash)
+{
+	EdgeEntry *e;
+	EdgeEntry *e_prev = NULL;
+
+	BLI_assert(v0 < v1);
+
+	for (e = eh->buckets[hash]; e; e = e->next) {
+		if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
+			EdgeEntry *e_next = e->next;
+
+			if (valfreefp) valfreefp(e->val);
+
+			if (e_prev) e_prev->next = e_next;
+			else   eh->buckets[hash] = e_next;
+
+			eh->nentries--;
+			return e;
+		}
+		e_prev = e;
+	}
+
+	return NULL;
+}
+
+/**
  * Run free callbacks for freeing entries.
  */
 static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp)
@@ -366,6 +395,57 @@ void *BLI_edgehash_lookup_default(EdgeHash *eh, unsigned int v0, unsigned int v1
 }
 
 /**
+ * Remove \a key from \a eh, or return false if the key wasn't found.
+ *
+ * \param key  The key to remove.
+ * \param valfreefp  Optional callback to free the value.
+ * \return true if \a key was removed from \a eh.
+ */
+bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP valfreefp)
+{
+	unsigned int hash;
+	EdgeEntry *e;
+
+	EDGE_ORD(v0, v1); /* ensure v0 is smaller */
+	hash = edgehash_keyhash(eh, v0, v1);
+	e = edgehash_remove_ex(eh, v0, v1, valfreefp, hash);
+	if (e) {
+		BLI_mempool_free(eh->epool, e);
+		return true;
+	}
+	else {
+		return false;
+	}
+}
+
+/* same as above but return the value,
+ * no free value argument since it will be returned */
+/**
+ * Remove \a key from \a eh, returning the value or NULL if the key wasn't found.
+ *
+ * \param key  The key to remove.
+ * \return the value of \a key int \a eh or NULL.
+ */
+void *BLI_edgehash_popkey(EdgeHash *eh, unsigned int v0, unsigned int v1)
+{
+	unsigned int hash;
+	EdgeEntry *e;
+
+	EDGE_ORD(v0, v1); /* ensure v0 is smaller */
+	hash = edgehash_keyhash(eh, v0, v1);
+	e = edgehash_remove_ex(eh, v0, v1, NULL, hash);
+	IS_EDGEHASH_ASSERT(eh);
+	if (e) {
+		void *val = e->val;
+		BLI_mempool_free(eh->epool, e);
+		return val;
+	}
+	else {
+		return NULL;
+	}
+}
+
+/**
  * Return boolean true/false if edge (v0,v1) in hash.
  */
 bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1)
@@ -404,6 +484,14 @@ void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
 	BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1);
 }
 
+/**
+ * Wraps #BLI_edgehash_clear_ex with zero entries reserved.
+ */
+void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp)
+{
+	BLI_edgehash_clear_ex(eh, valfreefp, 0);
+}
+
 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
 {
 	BLI_assert((int)eh->nentries == BLI_mempool_count(eh->epool));
@@ -440,7 +528,7 @@ void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag)
 /**
  * Create a new EdgeHashIterator. The hash table must not be mutated
  * while the iterator is in use, and the iterator will step exactly
- * BLI_edgehash_size(gh) times before becoming done.
+ * BLI_edgehash_size(eh) times before becoming done.
  */
 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
 {




More information about the Bf-blender-cvs mailing list