Blender  V3.3
CCGSubSurf_util.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include <math.h>
8 #include <stdlib.h>
9 #include <string.h>
10 
11 #include "BLI_sys_types.h" /* for intptr_t support */
12 #include "MEM_guardedalloc.h"
13 
14 #include "BLI_utildefines.h" /* for BLI_assert */
15 
16 #include "CCGSubSurf.h"
17 #include "CCGSubSurf_intern.h"
18 
23 static int kHashSizes[] = {
24  1, 3, 5, 11, 17, 37, 67, 131, 257, 521,
25  1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309,
26  1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
27 };
28 
29 /* Generic hash functions. */
30 
31 EHash *ccg_ehash_new(int estimatedNumEntries,
32  CCGAllocatorIFC *allocatorIFC,
33  CCGAllocatorHDL allocator)
34 {
35  EHash *eh = allocatorIFC->alloc(allocator, sizeof(*eh));
36  eh->allocatorIFC = *allocatorIFC;
37  eh->allocator = allocator;
38  eh->numEntries = 0;
39  eh->curSizeIdx = 0;
40  while (kHashSizes[eh->curSizeIdx] < estimatedNumEntries) {
41  eh->curSizeIdx++;
42  }
43  eh->curSize = kHashSizes[eh->curSizeIdx];
44  eh->buckets = EHASH_alloc(eh, eh->curSize * sizeof(*eh->buckets));
45  memset(eh->buckets, 0, eh->curSize * sizeof(*eh->buckets));
46 
47  return eh;
48 }
49 
50 void ccg_ehash_free(EHash *eh, EHEntryFreeFP freeEntry, void *userData)
51 {
52  int numBuckets = eh->curSize;
53 
54  while (numBuckets--) {
55  EHEntry *entry = eh->buckets[numBuckets];
56 
57  while (entry) {
58  EHEntry *next = entry->next;
59 
60  freeEntry(entry, userData);
61 
62  entry = next;
63  }
64  }
65 
66  EHASH_free(eh, eh->buckets);
67  EHASH_free(eh, eh);
68 }
69 
70 void ccg_ehash_insert(EHash *eh, EHEntry *entry)
71 {
72  int numBuckets = eh->curSize;
73  int hash = EHASH_hash(eh, entry->key);
74  entry->next = eh->buckets[hash];
75  eh->buckets[hash] = entry;
76  eh->numEntries++;
77 
78  if (UNLIKELY(eh->numEntries > (numBuckets * 3))) {
79  EHEntry **oldBuckets = eh->buckets;
80  eh->curSize = kHashSizes[++eh->curSizeIdx];
81 
82  eh->buckets = EHASH_alloc(eh, eh->curSize * sizeof(*eh->buckets));
83  memset(eh->buckets, 0, eh->curSize * sizeof(*eh->buckets));
84 
85  while (numBuckets--) {
86  for (entry = oldBuckets[numBuckets]; entry;) {
87  EHEntry *next = entry->next;
88 
89  hash = EHASH_hash(eh, entry->key);
90  entry->next = eh->buckets[hash];
91  eh->buckets[hash] = entry;
92 
93  entry = next;
94  }
95  }
96 
97  EHASH_free(eh, oldBuckets);
98  }
99 }
100 
101 void *ccg_ehash_lookupWithPrev(EHash *eh, void *key, void ***prevp_r)
102 {
103  int hash = EHASH_hash(eh, key);
104  void **prevp = (void **)&eh->buckets[hash];
105  EHEntry *entry;
106 
107  for (; (entry = *prevp); prevp = (void **)&entry->next) {
108  if (entry->key == key) {
109  *prevp_r = (void **)prevp;
110  return entry;
111  }
112  }
113 
114  return NULL;
115 }
116 
117 void *ccg_ehash_lookup(EHash *eh, void *key)
118 {
119  int hash = EHASH_hash(eh, key);
120  EHEntry *entry;
121 
122  for (entry = eh->buckets[hash]; entry; entry = entry->next) {
123  if (entry->key == key) {
124  break;
125  }
126  }
127 
128  return entry;
129 }
130 
131 /* Hash elements iteration. */
132 
134 {
135  /* fill all members */
136  ehi->eh = eh;
137  ehi->curBucket = -1;
138  ehi->curEntry = NULL;
139 
140  while (!ehi->curEntry) {
141  ehi->curBucket++;
142  if (ehi->curBucket == ehi->eh->curSize) {
143  break;
144  }
145  ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
146  }
147 }
148 
150 {
151  return ehi->curEntry;
152 }
153 
155 {
156  if (ehi->curEntry) {
157  ehi->curEntry = ehi->curEntry->next;
158  while (!ehi->curEntry) {
159  ehi->curBucket++;
160  if (ehi->curBucket == ehi->eh->curSize) {
161  break;
162  }
163  ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
164  }
165  }
166 }
168 {
169  return !ehi->curEntry;
170 }
171 
176 static void *_stdAllocator_alloc(CCGAllocatorHDL UNUSED(a), int numBytes)
177 {
178  return MEM_mallocN(numBytes, "CCG standard alloc");
179 }
180 
182  void *ptr,
183  int newSize,
184  int UNUSED(oldSize))
185 {
186  return MEM_reallocN(ptr, newSize);
187 }
188 
190 {
191  MEM_freeN(ptr);
192 }
193 
195 {
196  static CCGAllocatorIFC ifc;
197 
200  ifc.free = _stdAllocator_free;
201  ifc.release = NULL;
202 
203  return &ifc;
204 }
205 
210 #ifdef DUMP_RESULT_GRIDS
211 void ccgSubSurf__dumpCoords(CCGSubSurf *ss)
212 {
213  int vertDataSize = ss->meshIFC.vertDataSize;
214  int subdivLevels = ss->subdivLevels;
215  int gridSize = ccg_gridsize(subdivLevels);
216  int edgeSize = ccg_edgesize(subdivLevels);
217  int i, index, S;
218 
219  for (i = 0, index = 0; i < ss->vMap->curSize; i++) {
220  CCGVert *v = (CCGVert *)ss->vMap->buckets[i];
221  for (; v; v = v->next, index++) {
222  float *co = VERT_getCo(v, subdivLevels);
223  printf("vertex index=%d, co=(%f, %f, %f)\n", index, co[0], co[1], co[2]);
224  }
225  }
226 
227  for (i = 0, index = 0; i < ss->eMap->curSize; i++) {
228  CCGEdge *e = (CCGEdge *)ss->eMap->buckets[i];
229  for (; e; e = e->next, index++) {
230  int x;
231  float *co = VERT_getCo(e->v0, subdivLevels);
232  printf("edge index=%d, start_co=(%f, %f, %f)\n", index, co[0], co[1], co[2]);
233  for (x = 0; x < edgeSize; x++) {
234  float *co = EDGE_getCo(e, subdivLevels, x);
235  printf("edge index=%d, seg=%d, co=(%f, %f, %f)\n", index, x, co[0], co[1], co[2]);
236  }
237  co = VERT_getCo(e->v1, subdivLevels);
238  printf("edge index=%d, end_co=(%f, %f, %f)\n", index, co[0], co[1], co[2]);
239  }
240  }
241 
242  for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
243  CCGFace *f = (CCGFace *)ss->fMap->buckets[i];
244  for (; f; f = f->next, index++) {
245  for (S = 0; S < f->numVerts; S++) {
246  CCGVert *v = FACE_getVerts(f)[S];
247  float *co = VERT_getCo(v, subdivLevels);
248  printf("face index=%d, vertex=%d, coord=(%f, %f, %f)\n", index, S, co[0], co[1], co[2]);
249  }
250  }
251  }
252 
253  for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
254  CCGFace *f = (CCGFace *)ss->fMap->buckets[i];
255  for (; f; f = f->next, index++) {
256  for (S = 0; S < f->numVerts; S++) {
257  CCGEdge *e = FACE_getEdges(f)[S];
258  float *co1 = VERT_getCo(e->v0, subdivLevels);
259  float *co2 = VERT_getCo(e->v1, subdivLevels);
260  printf("face index=%d, edge=%d, coord1=(%f, %f, %f), coord2=(%f, %f, %f)\n",
261  index,
262  S,
263  co1[0],
264  co1[1],
265  co1[2],
266  co2[0],
267  co2[1],
268  co2[2]);
269  }
270  }
271  }
272 
273  for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
274  CCGFace *f = (CCGFace *)ss->fMap->buckets[i];
275  for (; f; f = f->next, index++) {
276  for (S = 0; S < f->numVerts; S++) {
277  int x, y;
278  for (x = 0; x < gridSize; x++) {
279  for (y = 0; y < gridSize; y++) {
280  float *co = FACE_getIFCo(f, subdivLevels, S, x, y);
281  printf("face index=%d. corner=%d, x=%d, y=%d, coord=(%f, %f, %f)\n",
282  index,
283  S,
284  x,
285  y,
286  co[0],
287  co[1],
288  co[2]);
289  }
290  }
291  for (x = 0; x < gridSize; x++) {
292  float *co = FACE_getIECo(f, subdivLevels, S, x);
293  printf("face index=%d. corner=%d, ie_index=%d, coord=(%f, %f, %f)\n",
294  index,
295  S,
296  x,
297  co[0],
298  co[1],
299  co[2]);
300  }
301  }
302  }
303  }
304 }
305 #endif /* DUMP_RESULT_GRIDS */
#define UNUSED(x)
#define UNLIKELY(x)
void * CCGAllocatorHDL
Definition: CCGSubSurf.h:28
BLI_INLINE int ccg_edgesize(int level)
BLI_INLINE int ccg_gridsize(int level)
BLI_INLINE CCGEdge ** FACE_getEdges(CCGFace *f)
BLI_INLINE CCGVert ** FACE_getVerts(CCGFace *f)
#define EHASH_alloc(eh, nb)
#define EDGE_getCo(e, lvl, x)
#define FACE_getIFCo(f, lvl, S, x, y)
#define EHASH_free(eh, ptr)
#define VERT_getCo(v, lvl)
void(* EHEntryFreeFP)(EHEntry *, void *)
#define EHASH_hash(eh, item)
#define FACE_getIECo(f, lvl, S, x)
void * ccg_ehash_lookupWithPrev(EHash *eh, void *key, void ***prevp_r)
void ccg_ehashIterator_init(EHash *eh, EHashIterator *ehi)
void ccg_ehashIterator_next(EHashIterator *ehi)
void * ccg_ehash_lookup(EHash *eh, void *key)
void ccg_ehash_insert(EHash *eh, EHEntry *entry)
static void * _stdAllocator_alloc(CCGAllocatorHDL UNUSED(a), int numBytes)
EHash * ccg_ehash_new(int estimatedNumEntries, CCGAllocatorIFC *allocatorIFC, CCGAllocatorHDL allocator)
void ccg_ehash_free(EHash *eh, EHEntryFreeFP freeEntry, void *userData)
void * ccg_ehashIterator_getCurrent(EHashIterator *ehi)
int ccg_ehashIterator_isStopped(EHashIterator *ehi)
CCGAllocatorIFC * ccg_getStandardAllocatorIFC(void)
static void _stdAllocator_free(CCGAllocatorHDL UNUSED(a), void *ptr)
static int kHashSizes[]
static void * _stdAllocator_realloc(CCGAllocatorHDL UNUSED(a), void *ptr, int newSize, int UNUSED(oldSize))
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
Read Guarded memory(de)allocation.
#define MEM_reallocN(vmemh, len)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static ulong * next
static unsigned a[3]
Definition: RandGen.cpp:78
#define hash
Definition: noise.c:153
void(* free)(CCGAllocatorHDL a, void *ptr)
Definition: CCGSubSurf.h:33
void(* release)(CCGAllocatorHDL a)
Definition: CCGSubSurf.h:34
void *(* realloc)(CCGAllocatorHDL a, void *ptr, int newSize, int oldSize)
Definition: CCGSubSurf.h:32
void *(* alloc)(CCGAllocatorHDL a, int numBytes)
Definition: CCGSubSurf.h:31
CCGFace * next
int vertDataSize
Definition: CCGSubSurf.h:22
CCGMeshIFC meshIFC
struct _EHEntry * next
struct _EHEntry * curEntry
Definition: CCGSubSurf.h:41
struct _EHash * eh
Definition: CCGSubSurf.h:39
EHEntry ** buckets
CCGAllocatorIFC allocatorIFC
CCGAllocatorHDL allocator
PointerRNA * ptr
Definition: wm_files.c:3480