diff options
Diffstat (limited to 'map.c')
| -rw-r--r-- | map.c | 285 |
1 files changed, 285 insertions, 0 deletions
@@ -0,0 +1,285 @@ +#ifndef GMAP_C +#define GMAP_C GMAP_C +#include <map.h> + + + +/* + * ID and residue and all of delta is assigned to NULL + * */ +void Map_Init(Map *tree) +{ + tree->is_final=0; + for(int i=0;i<256;++i)tree->delta[i] = NULL; + tree->ID = NULL; +} + +void Map_Scour(Map *tree,void *str,size_t size,size_t *where,Map **final_node) +{ + for( + *where=0,*final_node=tree; + *where<size && final_node[0]->delta[((unsigned char*)str)[ where[0] ]]!=NULL; + ++where[0] + ) + { + (*final_node) = (*final_node)->delta[((unsigned char*)str)[*where]]; + } +} + + + +/* + * tree must not be null + * */ +void Map_Push(Map *tree,void *str,size_t size,void *id) +{ + size_t temp; + Map_Scour(tree,str,size,&temp,&tree); + + if(temp == size) + { + assert(tree->ID==NULL); + tree->ID=id; + tree->is_final=1; + return; + } + for(temp;temp<size;++temp) + { + tree=tree->delta[((unsigned char*)str)[temp]]=calloc(1,sizeof(Map)); + /* + Map_Init( + tree=tree->delta[((unsigned char*)str)[temp]]=malloc(sizeof(Map)) + ); + */ + } + + tree->ID=id; + tree->is_final=1; + +} + + +/* + * scours the tree and returns the id of the node that recognises the str + * returns NULL if the string is not recognised + * */ +void* Map_Check(Map *tree, void *str,size_t size) +{ + size_t temp; + Map_Scour(tree,str,size,&temp,&tree); + + if(temp<size) + { + return NULL; + }else + { + return tree->ID; //this has been set to be the last reached node + } +} + +void Map_Remove(Map *tree, void *str,size_t size) +{ + Stack stk; + Stack_Init(&stk); + size_t where; + char what_to_null=((char*)str)[0]; + + Stack_Push(&stk,tree); + + for(where=0;where<size-1 && tree->delta[((unsigned char*)str)[where]]!=NULL;++where) + { + tree = tree->delta[((unsigned char*)str)[where]]; + if(tree->is_final==1) + { + while(stk.size>0)Stack_Pop(&stk); + what_to_null=((char*)str)[where+1]; + } + Stack_Push(&stk,tree); + } + if(tree->delta[((unsigned char*)str)[where]] == NULL)return; + free(tree->delta[((unsigned char*)str)[where]]); + while(stk.size>1)free(Stack_Pop(&stk)); + tree=(Map*)Stack_Pop(&stk); + tree->delta[(unsigned char)what_to_null]=NULL; + +} +/*This function especially requires that the map has no loops*/ +void Map_Map(Map *tree,void (*map)(void*)) +{ + if(tree->is_final==1)map(tree->ID); + for(int i=0;i<256;++i) + { + if(tree->delta[i]!=NULL) + { + Map_Map(tree->delta[i],map); + } + } +} + +/*first argument of map is the node id , the second is pass_data*/ +void Map_Map_Extended(Map *tree,void (*map)(void*,void*),void* pass_data) +{ + if(tree->is_final==1)map(tree->ID,pass_data); + for(int i=0;i<256;++i) + { + if(tree->delta[i]!=NULL) + { + Map_Map_Extended(tree->delta[i],map,pass_data); + } + } +} + + +/*this does not destroy(free) any memory pointed to by a node in the Map. This does not free() the root (Map *tree) */ +/*This function especially does not require that the map has no loop ( for example after grepification )*/ +void Map_Destroy(Map *tree) +{ + Stack path; + Stack nodes; + Map *current_node; + unsigned int i; + + + Stack_Init(&path); + Stack_Init(&nodes); + + Stack_Push(&path,tree); + Stack_Push(&nodes,tree); + + /* + using DFS we fill up the nodes stack with all the used + (accessible) nodes. + */ + while(path.size>0) + { + current_node=Stack_Pop(&path); + current_node->ID=&(current_node->ID);/*mark the node*/ + for(i=0;i<256;++i) + { + if(current_node->delta[i]!=NULL && current_node->delta[i]->ID != &(current_node->delta[i]->ID) ) + { + Stack_Push(&path,current_node->delta[i]); + + + /*we mark the unmarked child of the current_node*/ + current_node->delta[i]->ID=&(current_node->delta[i]->ID); + /*every node in nodes continues to be marked*/ + Stack_Push(&nodes,current_node->delta[i]); + } + } + + } + /* + There should not be any duplicates in here + */ + while(nodes.size>1) + { + current_node=Stack_Pop(&nodes); + /*Again the things that ID points to is not freed ( this structure is used to map the structure of data ) + deletion of it is up to you. + */ + free(current_node); + } + /*this is where the root is at- we don't delete it , but we must free the last stack node*/ + Stack_Pop(&nodes); + + +} + +/*requres that cpy has no loops*/ +Map* Map_Copy(Map *cpy) +{ + short i; + Map *ret; + + if(cpy==NULL) + { + return NULL; + } + + ret=malloc(sizeof(Map)); + ret->is_final=cpy->is_final; + ret->ID=cpy->ID; + + for(i=0;i<256;++i) + { + ret->delta[i]=Map_Copy(cpy->delta[i]); + } + return ret; +} + +struct Map* Map_Check_And_Get(Map *tree, void *str,size_t size) +{ + size_t temp; + Map_Scour(tree,str,size,&temp,&tree); + + if(temp<size) + { + return NULL; + }else + { + return tree; + } +} + +struct Map* Map_Push_And_Get(struct Map* tree,void *str,size_t size,void *id) +{ + size_t temp; + Map_Scour(tree,str,size,&temp,&tree); + + if(temp == size) + { + if(tree->ID!=NULL)tree->ID=id; + tree->is_final=1; + return tree; + } + + for(temp;temp<size;++temp) + { + Map_Init( + tree= + tree->delta[((unsigned char*)str)[temp]]= + malloc(sizeof(Map)) + ); + } + + tree->ID=id; + tree->is_final=1; + return tree; +} + +void* Map_Check_And_Push(struct Map *tree,void *str,size_t size,void *id) +{ + size_t temp; + Map_Scour(tree,str,size,&temp,&tree); + + if(temp == size) + { + if(!tree->is_final) + { + tree->ID=id; + tree->is_final=1; + } + return tree->ID; + } + for(temp;temp<size;++temp) + { + tree=tree->delta[((unsigned char*)str)[temp]]=calloc(1,sizeof(Map)); + /* + Map_Init( + tree=tree->delta[((unsigned char*)str)[temp]]=malloc(sizeof(Map)) + ); + */ + } + + tree->ID=id; + tree->is_final=1; + return NULL; +} +/*requires that the map has no loops. does not free the root node*/ +/*TODO*/ +void Map_Delete_Map(struct Map *tree) +{ + +} +#endif //#ifndef GMAP |