[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [40054] branches/bmesh/blender/source/ blender/blenlib: missed adding the C file last commit, also names the structs more logically.
Campbell Barton
ideasman42 at gmail.com
Fri Sep 9 05:11:19 CEST 2011
Revision: 40054
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=40054
Author: campbellbarton
Date: 2011-09-09 03:11:15 +0000 (Fri, 09 Sep 2011)
Log Message:
-----------
missed adding the C file last commit, also names the structs more logically.
Modified Paths:
--------------
branches/bmesh/blender/source/blender/blenlib/BLI_smallhash.h
Added Paths:
-----------
branches/bmesh/blender/source/blender/blenlib/intern/smallhash.c
Modified: branches/bmesh/blender/source/blender/blenlib/BLI_smallhash.h
===================================================================
--- branches/bmesh/blender/source/blender/blenlib/BLI_smallhash.h 2011-09-09 02:52:20 UTC (rev 40053)
+++ branches/bmesh/blender/source/blender/blenlib/BLI_smallhash.h 2011-09-09 03:11:15 UTC (rev 40054)
@@ -37,21 +37,24 @@
/* based on a doubling non-chaining approach */
-extern unsigned int hashsizes[];
-#define NONHASH -25436536
-typedef struct entry {uintptr_t key; void *val;} entry;
+typedef struct {
+ uintptr_t key;
+ void *val;
+} SmallHashEntry;
/*how much stack space to use before dynamically allocating memory*/
#define SMSTACKSIZE 521
typedef struct SmallHash {
- entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE];
- entry *stacktable, *copytable;
+ SmallHashEntry *table;
+ SmallHashEntry _stacktable[SMSTACKSIZE];
+ SmallHashEntry _copytable[SMSTACKSIZE];
+ SmallHashEntry *stacktable, *copytable;
int used;
int curhash;
int size;
} SmallHash;
-typedef struct SmallHashIter {
+typedef struct {
SmallHash *hash;
int i;
} SmallHashIter;
Added: branches/bmesh/blender/source/blender/blenlib/intern/smallhash.c
===================================================================
--- branches/bmesh/blender/source/blender/blenlib/intern/smallhash.c (rev 0)
+++ branches/bmesh/blender/source/blender/blenlib/intern/smallhash.c 2011-09-09 03:11:15 UTC (rev 40054)
@@ -0,0 +1,280 @@
+/**
+ * ***** 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 *****
+ */
+
+#include "MEM_guardedalloc.h"
+#include "BLI_utildefines.h"
+#include <string.h>
+
+#include "BLI_smallhash.h"
+
+/* SMHASH_CELL_UNUSED means this cell is inside a key series,
+ * while SMHASH_CELL_FREE means this cell terminates a key series.
+ *
+ * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
+ * imagine. hopefully.
+ *
+ * note: these have the SMHASH suffix because we may want to make them public.
+ */
+#define SMHASH_CELL_UNUSED ((void *)0x7FFFFFFF)
+#define SMHASH_CELL_FREE ((void *)0x7FFFFFFD)
+
+#define SMHASH_NONZERO(n) ((n) + !(n))
+#define SMHASH_NEXT(h, hoff) ABS(((h) + ((hoff=SMHASH_NONZERO(hoff*2)+1), hoff)))
+
+extern unsigned int hashsizes[];
+
+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 = SMHASH_CELL_FREE;
+ }
+}
+
+/*NOTE: does *not* free *hash itself! only the direct data!*/
+void BLI_smallhash_release(SmallHash *hash)
+{
+ if (hash == NULL) {
+ return;
+ }
+
+ if (hash->table != hash->stacktable) {
+ MEM_freeN(hash->table);
+ }
+}
+
+void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
+{
+ int h, hoff=1;
+
+ if (hash->size < hash->used * 3) {
+ int newsize = hashsizes[++hash->curhash];
+ SmallHashEntry *tmp;
+ int i = 0;
+
+ if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
+ tmp = MEM_callocN(sizeof(*hash->table) * newsize, "new hashkeys");
+ }
+ else {
+ SWAP(SmallHashEntry *, hash->stacktable, hash->copytable);
+ tmp = hash->stacktable;
+ }
+
+ SWAP(SmallHashEntry *, tmp, hash->table);
+
+ hash->size = newsize;
+
+ for (i=0; i<hash->size; i++) {
+ hash->table[i].val = SMHASH_CELL_FREE;
+ }
+
+ for (i=0; i<hashsizes[hash->curhash-1]; i++) {
+ if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+ continue;
+ }
+
+ h = ABS((int)(tmp[i].key));
+ hoff = 1;
+ while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+ h = SMHASH_NEXT(h, hoff);
+ }
+
+ 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 = ABS((int)key);
+ hoff = 1;
+
+ while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+ h = SMHASH_NEXT(h, hoff);
+ }
+
+ h %= hash->size;
+ hash->table[h].key = key;
+ hash->table[h].val = item;
+
+ hash->used++;
+}
+
+void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
+{
+ int h, hoff=1;
+
+ h = ABS((int)key);
+
+ while ((hash->table[h % hash->size].key != key) ||
+ (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+ {
+ if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
+ return;
+ }
+
+ h = SMHASH_NEXT(h, hoff);
+ }
+
+ h %= hash->size;
+ hash->table[h].key = 0;
+ hash->table[h].val = SMHASH_CELL_UNUSED;
+}
+
+void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
+{
+ int h, hoff=1;
+ void *v;
+
+ h = ABS((int)key);
+
+ if (hash->table == NULL) {
+ return NULL;
+ }
+
+ while ((hash->table[h % hash->size].key != key) ||
+ (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+ {
+ if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
+ return NULL;
+ }
+
+ h = SMHASH_NEXT(h, hoff);
+ }
+
+ v = hash->table[h % hash->size].val;
+ if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
+ return NULL;
+ }
+
+ return v;
+}
+
+
+int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
+{
+ int h = ABS((int)key);
+ int hoff =1;
+
+ if (hash->table == NULL) {
+ return 0;
+ }
+
+ while ((hash->table[h % hash->size].key != key) ||
+ (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+ {
+ if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
+ return 0;
+ }
+
+ h = SMHASH_NEXT(h, hoff);
+ }
+
+ return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
+}
+
+int BLI_smallhash_count(SmallHash *hash)
+{
+ return hash->used;
+}
+
+void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
+{
+ while (iter->i < iter->hash->size) {
+ if ( (iter->hash->table[iter->i].val != SMHASH_CELL_UNUSED) &&
+ (iter->hash->table[iter->i].val != SMHASH_CELL_FREE))
+ {
+ if (key) {
+ *key = iter->hash->table[iter->i].key;
+ }
+
+ iter->i++;
+
+ return iter->hash->table[iter->i-1].val;
+ }
+
+ iter->i++;
+ }
+
+ return NULL;
+}
+
+void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key)
+{
+ iter->hash = hash;
+ iter->i = 0;
+
+ return BLI_smallhash_iternext(iter, key);
+}
+
+/* note, this was called _print_smhash in knifetool.c
+ * it may not be intended for general use - campbell */
+#if 0
+void BLI_smallhash_print(SmallHash *hash)
+{
+ int i, linecol=79, c=0;
+
+ printf("{");
+ for (i=0; i<hash->size; i++) {
+ if (hash->table[i].val == SMHASH_CELL_UNUSED) {
+ printf("--u-");
+ }
+ else if (hash->table[i].val == SMHASH_CELL_FREE) {
+ printf("--f-");
+ }
+ else {
+ printf("%2x", (unsigned int)hash->table[i].key);
+ }
+
+ if (i != hash->size-1)
+ printf(", ");
+
+ c += 6;
+
+ if (c >= linecol) {
+ printf("\n ");
+ c = 0;
+ }
+ }
+
+ fflush(stdout);
+}
+#endif
More information about the Bf-blender-cvs
mailing list