From 255a49ba5a41b3854dbdfebdec75fb6229450507 Mon Sep 17 00:00:00 2001 From: Galin Simeonov Date: Mon, 31 May 2021 22:02:10 +0300 Subject: added cmake file --- src/misc/map.c | 285 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/misc/map.h | 41 ++++++++ src/misc/queue.c | 67 +++++++++++++ src/misc/queue.h | 23 +++++ src/misc/stack.c | 37 ++++++++ src/misc/stack.h | 22 +++++ 6 files changed, 475 insertions(+) create mode 100644 src/misc/map.c create mode 100644 src/misc/map.h create mode 100644 src/misc/queue.c create mode 100644 src/misc/queue.h create mode 100644 src/misc/stack.c create mode 100644 src/misc/stack.h (limited to 'src/misc') diff --git a/src/misc/map.c b/src/misc/map.c new file mode 100644 index 0000000..cd8272f --- /dev/null +++ b/src/misc/map.c @@ -0,0 +1,285 @@ +#ifndef GMAP_C +#define GMAP_C GMAP_C +#include + + + +/* + * 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; + *wheredelta[((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;tempdelta[((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(tempID; //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;wheredelta[((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(tempID!=NULL)tree->ID=id; + tree->is_final=1; + return tree; + } + + for(temp;tempdelta[((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;tempdelta[((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 diff --git a/src/misc/map.h b/src/misc/map.h new file mode 100644 index 0000000..ced43a7 --- /dev/null +++ b/src/misc/map.h @@ -0,0 +1,41 @@ +#ifndef GMAP_H +#define GMAP_H GMAP_H +#include +#include +#include +#include +#include + +typedef struct Map Map; + + + +/* + * A looples automata with things attached to the nodes + * */ +struct Map +{ + char is_final; + Map *delta[256]; + /*ID cannot point to itself ( this is used in the deletion of the map ) */ + void *ID; +}; + +void Map_Init(Map *tree); +void Map_Scour(Map *tree,void *str,size_t size,size_t *where,Map **final_node); +void Map_Push(Map *tree,void *str,size_t size,void *id); +void* Map_Check(Map *tree, void *str,size_t size); +struct Map* Map_Check_And_Get(Map *tree, void *str,size_t size); +void Map_Remove(Map *tree, void *str,size_t size); +void Map_Map(Map *tree,void (*map)(void*)); +void Map_Map_Extended(Map *tree,void (*map)(void*,void*),void* pass_data); + +void Map_Destroy(Map *tree); +void Map_Delete_Map(struct Map *tree); +struct Condensed_Map* Map_Condense(Map* tree); + +struct Map* Map_Push_And_Get(struct Map* tree,void *str,size_t size,void *id); +/*returns NULL if id is not taken , returns pointer to taken id otherwise*/ +void* Map_Check_And_Push(struct Map *tree,void *str,size_t size,void *id); + +#endif diff --git a/src/misc/queue.c b/src/misc/queue.c new file mode 100644 index 0000000..b395acf --- /dev/null +++ b/src/misc/queue.c @@ -0,0 +1,67 @@ +#ifndef GQUEUE_C +#define GQUEUE_C GQUEUE_C +#include + + +void Queue_Init(struct Queue *q) +{ + q->first=q->last=NULL; + q->size=0; +} +void Queue_Push(struct Queue *q,void *data) +{ + if(q==NULL)return; + if(q->first==NULL) + { + q->first=q->last=malloc(sizeof(struct Queue_Node)); + + q->first->data=data; + q->first->prev=NULL; + + ++q->size; + }else + { + struct Queue_Node *temp=malloc(sizeof(struct Queue_Node)); + q->last->prev=temp; + temp->data=data; + temp->prev=NULL; + q->last=temp; + ++q->size; + } + +} +void* Queue_Pop(struct Queue *q) +{ + if(q==NULL)return NULL; + if(q->size==0)return NULL; + + void *return_value=q->first->data; + + if(q->size==1) + { + free(q->last); + q->first=q->last=NULL; + q->size=0; + }else + { + struct Queue_Node *temp_first=q->first; + q->first=q->first->prev; + free(temp_first); + --q->size; + } + return return_value; +} +void Queue_Destroy(struct Queue *q) +{ + + struct Queue_Node *temp_first; + while(q->first!=NULL) + { + temp_first=q->first; + q->first=q->first->prev; + free(temp_first->data); + free(temp_first); + } + +} +#endif diff --git a/src/misc/queue.h b/src/misc/queue.h new file mode 100644 index 0000000..651d4b0 --- /dev/null +++ b/src/misc/queue.h @@ -0,0 +1,23 @@ +#ifndef GQUEUE_H +#define GQUEUE_H GQUEUE_H +#include + + +struct Queue_Node +{ + void *data; + struct Queue_Node *prev; +}; + +struct Queue +{ + struct Queue_Node *first,*last; + size_t size; + +}; + +void Queue_Init(struct Queue *q); +void Queue_Push(struct Queue *q,void *data); +void* Queue_Pop(struct Queue *q); +void Queue_Destroy(struct Queue *q); +#endif diff --git a/src/misc/stack.c b/src/misc/stack.c new file mode 100644 index 0000000..272732f --- /dev/null +++ b/src/misc/stack.c @@ -0,0 +1,37 @@ +#ifndef GSTACK_C +#define GSTACK_C GSTACK_C +#include "stack.h" + + + +void Stack_Init(Stack *stack) +{ + stack->size=0; + stack->first=NULL; +} +void Stack_Push(Stack *stack,void* data) +{ + struct Stack_Node *temp_node=malloc(sizeof(struct Stack_Node)); + temp_node->data=data; + temp_node->next=stack->first; + stack->first=temp_node; + ++stack->size; +} +void* Stack_Pop(Stack *stack) +{ + void* return_value=NULL; + if(stack->first!=NULL) + { + struct Stack_Node *temp_first=stack->first; + return_value=stack->first->data; + + --stack->size; + stack->first=stack->first->next; + free(temp_first); + } + + return return_value; +} + +#endif//#ifndef GSTACK_C + diff --git a/src/misc/stack.h b/src/misc/stack.h new file mode 100644 index 0000000..14e557a --- /dev/null +++ b/src/misc/stack.h @@ -0,0 +1,22 @@ +#ifndef GSTACK_H +#define GSTACK_H GSTACK_H +#include +typedef struct Stack Stack; + +struct Stack_Node +{ + struct Stack_Node *next; + void *data; +}; +struct Stack +{ + struct Stack_Node *first; + size_t size; +}; + +void Stack_Init(Stack *stack); +void Stack_Push(Stack *stack,void* data); +void* Stack_Pop(Stack *stack); + + +#endif -- cgit v1.2.3