#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
+#include <ctype.h>
#include <time.h>
#ifdef HAVE_SYS_TIME_H
#include <unistd.h>
#endif
-#ifdef _WIN32
-#include <windows.h> /* VirtualAlloc, VirtualProtect */
-#include <process.h> /* getpid */
-#endif
-
#include <glib.h>
#include <proto.h>
#include "emem.h"
#include <wiretap/file_util.h>
+#ifdef _WIN32
+#include <windows.h> /* VirtualAlloc, VirtualProtect */
+#include <process.h> /* getpid */
+#endif
+
/*
* Tools like Valgrind and ElectricFence don't work well with memchunks.
/* Do we want to use canaries ? */
#define DEBUG_USE_CANARIES 1
-
#ifdef WANT_GUARD_PAGES
/* Add guard pages at each end of our allocated memory */
#if defined(HAVE_SYSCONF) && defined(HAVE_MMAP) && defined(HAVE_MPROTECT) && defined(HAVE_STDINT_H)
emem_chunk_t *used_list;
} emem_header_t;
-static emem_header_t ep_packet_mem;
-static emem_header_t se_packet_mem;
+emem_header_t ep_packet_mem;
+emem_header_t se_packet_mem;
#if !defined(SE_DEBUG_FREE)
#if defined (_WIN32)
size_t sz;
/* Try /dev/urandom */
if ((fp = eth_fopen("/dev/urandom", "r")) != NULL) {
- sz = fread(canary, EMEM_CANARY_DATA_SIZE, 1, fp);
+ sz = fread(canary, 1, EMEM_CANARY_DATA_SIZE, fp);
fclose(fp);
if (sz == EMEM_CANARY_SIZE) {
return;
gchar* dst = ep_alloc(len+1);
guint i;
- for (i = 0; src[i] && i < len; i++)
+ for (i = 0; (i < len) && src[i]; i++)
dst[i] = src[i];
dst[i] = '\0';
gchar* dst = se_alloc(len+1);
guint i;
- for (i = 0; src[i] && i < len; i++)
+ for (i = 0; (i < len) && src[i]; i++)
dst[i] = src[i];
dst[i] = '\0';
emem_tree_t *se_trees=NULL;
emem_tree_t *
-se_tree_create(int type, char *name)
+se_tree_create(int type, const char *name)
{
emem_tree_t *tree_list;
node->right=NULL;
node->key32=key;
node->data=data;
+ node->u.is_subtree = EMEM_TREE_NODE_IS_DATA;
se_tree->tree=node;
return;
}
new_node->right=NULL;
new_node->key32=key;
new_node->data=data;
+ new_node->u.is_subtree=EMEM_TREE_NODE_IS_DATA;
node=new_node;
break;
}
new_node->right=NULL;
new_node->key32=key;
new_node->data=data;
+ new_node->u.is_subtree=EMEM_TREE_NODE_IS_DATA;
node=new_node;
break;
}
}
}
-static void* lookup_or_insert32(emem_tree_t *se_tree, guint32 key, void*(*func)(void*),void* ud) {
+static void* lookup_or_insert32(emem_tree_t *se_tree, guint32 key, void*(*func)(void*),void* ud, int is_subtree) {
emem_tree_node_t *node;
node=se_tree->tree;
node->right=NULL;
node->key32=key;
node->data= func(ud);
+ node->u.is_subtree = is_subtree;
se_tree->tree=node;
return node->data;
}
new_node->right=NULL;
new_node->key32=key;
new_node->data= func(ud);
+ new_node->u.is_subtree = is_subtree;
node=new_node;
break;
}
new_node->right=NULL;
new_node->key32=key;
new_node->data= func(ud);
+ new_node->u.is_subtree = is_subtree;
node=new_node;
break;
}
* never existed including all metadata associated with the tree.
*/
emem_tree_t *
-se_tree_create_non_persistent(int type, char *name)
+se_tree_create_non_persistent(int type, const char *name)
{
emem_tree_t *tree_list;
return;
}
- next_tree=lookup_or_insert32(se_tree, *key[0].key, create_sub_tree, se_tree);
+ next_tree=lookup_or_insert32(se_tree, *key[0].key, create_sub_tree, se_tree, EMEM_TREE_NODE_IS_SUBTREE);
if(key[0].length==1){
key++;
}
+/* Strings are stored as an array of uint32 containing the string characters
+ with 4 characters in each uint32.
+ The first byte of the string is stored as the most significant byte.
+ If the string is not a multiple of 4 characters in length the last
+ uint32 containing the string bytes are padded with 0 bytes.
+ After the uint32's containing the string, there is one final terminator
+ uint32 with the value 0x00000001
+*/
void
-emem_tree_insert_string(emem_tree_t* se_tree, const gchar* k, void* v) {
+emem_tree_insert_string(emem_tree_t* se_tree, const gchar* k, void* v, guint32 flags)
+{
+ emem_tree_key_t key[2];
+ guint32 *aligned=NULL;
guint32 len = strlen(k);
- guint32 div = (len-1)/4;
- guint32 residual = 0;
- emem_tree_key_t key[] = {
- {1,NULL},
- {0,NULL},
- {1,NULL},
- {0,NULL}
- };
-
- key[0].key = &len;
- key[1].length = div;
- key[1].key = (guint32*)(&k[0]);
- key[2].key = &residual;
-
- if (! div) {
- key[1].length = key[2].length;
- key[1].key = key[2].key;
- key[2].length = 0;
- key[2].key = NULL;
- }
+ guint32 div = (len+3)/4+1;
+ guint32 i;
+ guint32 tmp;
- div *= 4;
-
- switch(len%4) {
- case 0:
- residual |= ( k[div+3] << 24 );
- case 3:
- residual |= ( k[div+2] << 16 );
- case 2:
- residual |= ( k[div+1] << 8 );
- case 1:
- residual |= k[div];
- break;
+ aligned = malloc(div * sizeof (guint32));
+
+ /* pack the bytes one one by one into guint32s */
+ tmp = 0;
+ for (i = 0;i < len;i++) {
+ unsigned char ch;
+
+ ch = (unsigned char)k[i];
+ if (flags & EMEM_TREE_STRING_NOCASE) {
+ if(isupper(ch)) {
+ ch = tolower(ch);
+ }
+ }
+ tmp <<= 8;
+ tmp |= ch;
+ if (i%4 == 3) {
+ aligned[i/4] = tmp;
+ tmp = 0;
+ }
}
+ /* add required padding to the last uint32 */
+ if (i%4 != 0) {
+ while (i%4 != 0) {
+ i++;
+ tmp <<= 8;
+ }
+ aligned[i/4-1] = tmp;
+ }
+
+ /* add the terminator */
+ aligned[div-1] = 0x00000001;
+
+ key[0].length = div;
+ key[0].key = aligned;
+ key[1].length = 0;
+ key[1].key = NULL;
+
- emem_tree_insert32_array(se_tree,key,v);
+ emem_tree_insert32_array(se_tree, key, v);
+ free(aligned);
}
void *
-emem_tree_lookup_string(emem_tree_t* se_tree, const gchar* k) {
+emem_tree_lookup_string(emem_tree_t* se_tree, const gchar* k, guint32 flags)
+{
+ emem_tree_key_t key[2];
+ guint32 *aligned=NULL;
guint32 len = strlen(k);
- guint32 div = (len-1)/4;
- guint32 residual = 0;
- emem_tree_key_t key[] = {
- {1,NULL},
- {0,NULL},
- {1,NULL},
- {0,NULL}
- };
-
- key[0].key = &len;
- key[1].length = div;
- key[1].key = (guint32*)(&k[0]);
- key[2].key = &residual;
-
- if (! div) {
- key[1].length = key[2].length;
- key[1].key = key[2].key;
- key[2].length = 0;
- key[2].key = NULL;
+ guint32 div = (len+3)/4+1;
+ guint32 i;
+ guint32 tmp;
+ void *ret;
+
+ aligned = malloc(div * sizeof (guint32));
+
+ /* pack the bytes one one by one into guint32s */
+ tmp = 0;
+ for (i = 0;i < len;i++) {
+ unsigned char ch;
+
+ ch = (unsigned char)k[i];
+ if (flags & EMEM_TREE_STRING_NOCASE) {
+ if(isupper(ch)) {
+ ch = tolower(ch);
+ }
+ }
+ tmp <<= 8;
+ tmp |= ch;
+ if (i%4 == 3) {
+ aligned[i/4] = tmp;
+ tmp = 0;
+ }
}
+ /* add required padding to the last uint32 */
+ if (i%4 != 0) {
+ while (i%4 != 0) {
+ i++;
+ tmp <<= 8;
+ }
+ aligned[i/4-1] = tmp;
+ }
+
+ /* add the terminator */
+ aligned[div-1] = 0x00000001;
- div *= 4;
-
- switch(len%4) {
- case 0:
- residual |= k[div+3] << 24;
- case 3:
- residual |= k[div+2] << 16;
- case 2:
- residual |= k[div+1] << 8;
- case 1:
- residual |= k[div];
- break;
+ key[0].length = div;
+ key[0].key = aligned;
+ key[1].length = 0;
+ key[1].key = NULL;
+
+
+ ret = emem_tree_lookup32_array(se_tree, key);
+ free(aligned);
+ return ret;
+}
+
+static gboolean
+emem_tree_foreach_nodes(emem_tree_node_t* node, tree_foreach_func callback, void *user_data)
+{
+ gboolean stop_traverse = FALSE;
+
+ if (!node)
+ return FALSE;
+
+ if(node->left) {
+ stop_traverse = emem_tree_foreach_nodes(node->left, callback, user_data);
+ if (stop_traverse) {
+ return TRUE;
+ }
+ }
+
+ if (node->u.is_subtree == EMEM_TREE_NODE_IS_SUBTREE) {
+ stop_traverse = emem_tree_foreach(node->data, callback, user_data);
+ } else {
+ stop_traverse = callback(node->data, user_data);
+ }
+
+ if (stop_traverse) {
+ return TRUE;
+ }
+
+ if(node->right) {
+ stop_traverse = emem_tree_foreach_nodes(node->right, callback, user_data);
+ if (stop_traverse) {
+ return TRUE;
+ }
}
- return emem_tree_lookup32_array(se_tree, key);
+ return FALSE;
+}
+
+gboolean
+emem_tree_foreach(emem_tree_t* emem_tree, tree_foreach_func callback, void *user_data)
+{
+ if (!emem_tree)
+ return FALSE;
+
+ if(!emem_tree->tree)
+ return FALSE;
+
+ return emem_tree_foreach_nodes(emem_tree->tree, callback, user_data);
}
printf(" ");
}
- printf("NODE:%08x parent:%08x left:0x%08x right:%08x key:%d data:0x%08x\n",(int)node,(int)node->parent,(int)node->left,(int)node->right,node->key32,(int)node->data);
+ printf("NODE:%p parent:%p left:0x%p right:%px key:%d data:%p\n",
+ (void *)node,(void *)(node->parent),(void *)(node->left),(void *)(node->right),
+ (node->key32),node->data);
if(node->left)
emem_tree_print_nodes(node->left, level+1);
if(node->right)
if (!emem_tree)
return;
- printf("EMEM tree type:%d name:%s tree:0x%08x\n",emem_tree->type,emem_tree->name,(int)emem_tree->tree);
+ printf("EMEM tree type:%d name:%s tree:%p\n",emem_tree->type,emem_tree->name,(void *)(emem_tree->tree));
if(emem_tree->tree)
emem_tree_print_nodes(emem_tree->tree, 0);
}