=BMesh: Super Knife Tool Alpha=

Implemented a new "super knife".  Activate with k.  Holding CTRL
will allow extended cutting ala old lines mode.  Confirm with enter 
and escape. You cannot cancel, btw, you can only confirm (and undo 
later if you want). Hopefully I'll support undo within the tool soon.

* Supports cutting edges, into faces, etc.  You can pretty much do whatever 
  you want.  Will snap to vertices too.
* Note that if you cut into a face, it must be valid topologically when 
  you press enter to confirm.
* It's pretty and graphical :)
* You can only cut visible geometry.
* UVs/vcols are a little buggy still

Now, thou shalt all cease and desist all lack of motivation for
testing!  No longer shall users put off testing until "it's cooler"!

:P

1 files changed, 204 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h
new file mode 100755
index 00000000000..5badff062b7
--- /dev/null
+++ b/source/blender/blenlib/BLI_smallhash.h
@@ -0,0 +1,204 @@
+/**
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2008 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+ 
+#ifndef BLI_SMALLHASH_H
+#define BLI_SMALLHASH_H
+
+/*******a light stack-friendly hash library******
+ *      (it uses stack space for smallish hash tables)     */
+
+/*based on a doubling non-chaining approach */
+
+#include "MEM_guardedalloc.h"
+#include "BLO_sys_types.h"
+#include "BKE_utildefines.h"
+
+extern unsigned int hashsizes[];
+#define NONHASH	-25436536
+typedef struct entry {intptr_t key; void *val;} entry;
+
+#define SMSTACKSIZE	521
+typedef struct SmallHash {
+	entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE];
+	entry *stacktable, *copytable;
+	int used;
+	int curhash;
+	int size;
+} SmallHash;
+
+/*CELL_UNUSED means this cell is inside a key series, while CELL_FREE
+  means this cell terminates a key series.
+  
+  no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
+  imagine.  hopefully. */
+#define CELL_UNUSED	((void*)0x7FFFFFFD)
+#define CELL_FREE	((void*)0x7FFFFFFD)
+
+#define HASHNEXT(h) (((h) + ((h)==0))*2)
+
+BM_INLINE void BLI_smallhash_init(SmallHash *hash)
+{
+	int i;
+	
+	memset(hash, 0, sizeof(*hash));
+	
+	hash->table = hash->_stacktable;
+	hash->curhash = 2;
+	hash->size = hashsizes[hash->curhash];
+	
+	hash->copytable = hash->_copytable;
+	hash->stacktable = hash->_stacktable;
+	
+	for (i=0; i<hash->size; i++) {
+		hash->table[i].val = CELL_FREE;
+	}
+}
+
+/*NOTE: does *not* free *hash itself!  only the direct data!*/
+BM_INLINE void BLI_smallhash_release(SmallHash *hash)
+{
+	if (!hash)
+		return;
+	
+	if (hash->table != hash->stacktable)
+		MEM_freeN(hash->table);
+}
+
+BM_INLINE void BLI_smallhash_insert(SmallHash *hash, intptr_t key, void *item) 
+{
+	int h;
+	
+	if (hash->size < hash->used*3) {
+		int newsize = hashsizes[++hash->curhash];
+		entry *tmp;
+		int i = 0;
+		
+		if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
+			tmp = MEM_callocN(sizeof(*hash->table)*newsize, "new hashkeys");
+		} else {
+			SWAP(entry*, hash->stacktable, hash->copytable);
+			tmp = hash->stacktable;
+		}
+		
+		SWAP(entry*, tmp, hash->table);
+		
+		hash->size = newsize;
+		
+		for (i=0; i<hash->size; i++) {
+			hash->table[i].val = CELL_FREE;
+		}
+		
+		for (i=0; i<hashsizes[hash->curhash-1]; i++) {
+			if (ELEM(tmp[i].val, CELL_UNUSED, CELL_FREE))
+				continue;
+			
+			h = tmp[i].key;
+			while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE))
+				h = HASHNEXT(h);
+			
+			h %= newsize;
+			
+			hash->table[h].key = tmp[i].key;
+			hash->table[h].val = tmp[i].val;
+		}
+		
+		if (tmp != hash->stacktable && tmp != hash->copytable) {
+			MEM_freeN(tmp);
+		}
+	}
+	
+	h = key;
+	while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE))
+		h = HASHNEXT(h);
+	
+	h %= hash->size;
+	hash->table[h].key = key;
+	hash->table[h].val = item;
+	
+	hash->used++;
+}
+
+BM_INLINE void BLI_smallhash_remove(SmallHash *hash, intptr_t key)
+{
+	int h = key;
+	
+	while (hash->table[h % hash->size].key != key 
+	      || hash->table[h % hash->size].val == CELL_UNUSED)
+	{
+		if (hash->table[h % hash->size].val == CELL_FREE)
+			return;
+		h = HASHNEXT(h);
+	}
+	
+	h %= hash->size;
+	hash->table[h].key = 0;
+	hash->table[h].val = CELL_UNUSED;
+}
+
+BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, intptr_t key)
+{
+	int h = key;
+	
+	if (!hash->table)
+		return NULL;
+	
+	while (hash->table[h % hash->size].key != key 
+	      || hash->table[h % hash->size].val == CELL_UNUSED)
+	{
+		if (hash->table[h % hash->size].val == CELL_FREE)
+			return NULL;
+		h = HASHNEXT(h);
+	}
+	
+	return hash->table[h % hash->size].val;
+}
+
+
+BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, intptr_t key)
+{
+	int h = key;
+	
+	if (!hash->table)
+		return 0;
+	
+	while (hash->table[h % hash->size].key != key 
+	      || hash->table[h % hash->size].val == CELL_UNUSED)
+	{
+		if (hash->table[h % hash->size].val == CELL_FREE)
+			return 0;
+		h = HASHNEXT(h);
+	}
+	
+	return 1;
+}
+
+BM_INLINE int BLI_smallhash_count(SmallHash *hash)
+{
+	return hash->used;
+}
+
+#endif // BLI_SMALLHASH_H