commit d0f6c341ace7375275d7a92feeb14777c8ddbb8e
parent 86f90ed12d18d29f39198a667cdcdc58e5fe3d83
Author: Andres Navarro <canavarro82@gmail.com>
Date: Mon, 18 Apr 2011 22:36:41 -0300
Added some necessary machinery for hashtables.
Diffstat:
5 files changed, 75 insertions(+), 1 deletion(-)
diff --git a/src/klimits.h b/src/klimits.h
@@ -42,4 +42,11 @@
#define cast(t, exp) ((t)(exp))
#endif
+/*
+** conversion of pointer to integer
+** this is for hashing only; there is no problem if the integer
+** cannot hold the whole pointer value
+*/
+#define IntPoint(p) ((uint32_t)(p))
+
#endif
diff --git a/src/kmem.c b/src/kmem.c
@@ -20,6 +20,8 @@
#include "kerror.h"
#include "kgc.h"
+#define MINSIZEARRAY 4
+
/*
** About the realloc function:
** void * frealloc (void *ud, void *ptr, size_t osize, size_t nsize);
@@ -38,6 +40,31 @@
** (any reallocation to an equal or smaller size cannot fail!)
*/
+void *klispM_growaux_ (klisp_State *K, void *block, int *size, size_t size_elems,
+ int32_t limit, const char *errormsg) {
+ void *newblock;
+ int32_t newsize;
+ if (*size >= limit/2) { /* cannot double it? */
+ if (*size >= limit) /* cannot grow even a little? */
+ klispE_throw(K, (char *) errormsg); /* XXX */
+ newsize = limit; /* still have at least one free place */
+ }
+ else {
+ newsize = (*size)*2;
+ if (newsize < MINSIZEARRAY)
+ newsize = MINSIZEARRAY; /* minimum size */
+ }
+ newblock = klispM_reallocv(K, block, *size, newsize, size_elems);
+ *size = newsize; /* update only when everything else is OK */
+ return newblock;
+}
+
+
+void *klispM_toobig (klisp_State *K) {
+ klispE_throw(K, "memory allocation error: block too big");
+ return NULL; /* to avoid warnings */
+}
+
/*
** generic allocation routine.
diff --git a/src/kmem.h b/src/kmem.h
@@ -8,7 +8,7 @@
#define kmem_h
/*
-** SOURCE NOTE: This is from Lua, but greatly shortened
+** SOURCE NOTE: This is from Lua
*/
#include <stddef.h>
@@ -17,13 +17,32 @@
#define MEMERRMSG "not enough memory"
+#define klispM_reallocv(L,b,on,n,e) \
+ ((cast(size_t, (n)+1) <= SIZE_MAX/(e)) ? /* +1 to avoid warnings */ \
+ klispM_realloc_(L, (b), (on)*(e), (n)*(e)) : \
+ klispM_toobig(L))
+
#define klispM_freemem(K, b, s) klispM_realloc_(K, (b), (s), 0)
#define klispM_free(K, b) klispM_realloc_(K, (b), sizeof(*(b)), 0)
+#define klispM_freearray(L, b, n, t) klispM_reallocv(L, (b), n, 0, sizeof(t))
#define klispM_malloc(K,t) klispM_realloc_(K, NULL, 0, (t))
#define klispM_new(K,t) cast(t *, klispM_malloc(K, sizeof(t)))
+#define klispM_newvector(L,n,t) \
+ cast(t *, klispM_reallocv(L, NULL, 0, n, sizeof(t)))
+
+#define klispM_growvector(L,v,nelems,size,t,limit,e) \
+ if ((nelems)+1 > (size)) \
+ ((v)=cast(t *, klispM_growaux_(L,v,&(size),sizeof(t),limit,e)))
+
+#define klispM_reallocvector(L, v,oldn,n,t) \
+ ((v)=cast(t *, klispM_reallocv(L, v, oldn, n, sizeof(t))))
void *klispM_realloc_ (klisp_State *K, void *block, size_t oldsize,
size_t size);
+void *klispM_toobig (klisp_State *K);
+void *klispM_growaux_ (klisp_State *K, void *block, int *size,
+ size_t size_elem, int limit,
+ const char *errormsg);
#endif
diff --git a/src/kobject.c b/src/kobject.c
@@ -69,3 +69,18 @@ bool kis_output_port(TValue o)
return ttisport(o) && kport_is_output(o);
}
+int32_t klispO_log2 (uint32_t x) {
+ static const uint8_t log_2[256] = {
+ 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
+ 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+ 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
+ 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
+ 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
+ 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
+ };
+ int32_t l = -1;
+ while (x >= 256) { l += 8; x >>= 8; }
+ return l + log_2[x];
+}
diff --git a/src/kobject.h b/src/kobject.h
@@ -162,6 +162,8 @@ typedef struct __attribute__ ((__packed__)) GCheader {
#define K_TPORT 39
#define K_TTABLE 40
+#define K_TDEADKEY 60
+
/* this is used to test for numbers, as returned by ttype */
#define K_LAST_NUMBER_TYPE K_TCOMPLEX
@@ -437,6 +439,10 @@ typedef struct __attribute__ ((__packed__)) {
#define twoto(x) (1<<(x))
#define sizenode(t) (twoto((t)->lsizenode))
+#define ceillog2(x) (klispO_log2((x)-1) + 1)
+
+int32_t klispO_log2 (uint32_t x);
+
/*
** RATIONALE:
**
