/* ******************************************************************************* * Copyright (c) 1996 Martin Poole * ******************************************************************************* ** ** WARNING !! WARNING !! WARNING !! WARNING !! WARNING !! WARNING !! ** ** Any changes to be made to this file should first be checked with ** mplib1 source control for library integrity. ** ** mplib1 source control can be reached at mplib1@quatermass.co.uk ** * * $Source$ * $Author$ * $Date$ * $Revision$ * ******************************************************************************* * * Change History * * $Log$ * ******************************************************************************* */ #ident "$Header$" /* ------------------------------------------------------------------ Include files ------------------------------------------------------------------ */ #include #include #include #include #include #include #include #include #include #include #include #include "../include/dl_lru_private.h" #include /* ------------------------------------------------------------------ defines ------------------------------------------------------------------ */ #ifndef NULL #define NULL ((void *)0) #endif struct vchar_gen { unsigned short len; unsigned char arr[1]; }; typedef struct vchar_gen *vchar_ptr; struct cps { struct Cache_List *cl; int nrl; struct full_search_rule *srp; void **sv; struct Cache_Item *ci; struct Cache_Item *si; struct Cache_Item *rv; }; /* ------------------------------------------------------------------ Some static variables ------------------------------------------------------------------ */ /* ------------------------------------------------------------------ Code starts here ------------------------------------------------------------------ */ static int vcharcmp( vchar_ptr vp1, vchar_ptr vp2 ) { int t,rv=0; unsigned char *cp; static char estr[]="\0"; t=vp1->len; if (vp2->len != t) { if (vp2->len < t) { t=vp2->len; cp=vp1->arr + t; }else { cp=vp2->arr + t; } rv = memcmp( vp1->arr, vp2->arr, (size_t)t ); if (rv==0) { /* Check remainder */ rv=memcmp( cp, estr, 1 ); } }else { /* same length, may be equal, have to check */ rv = memcmp( vp1->arr, vp2->arr, (size_t)t ); } return(rv); } static int vcharcasecmp( vchar_ptr vp1, vchar_ptr vp2 ) { return(0); } static int fail( void *vp1, void *vp2 ) { return(0); } #define COMP_FUNC(a,b,c) static int a##_##b (void *p1, void *p2){return( *(a *)p1 c *(a *)p2 ); } #define COMP_FFUNC(a,b,c,d,e) static int a##_##b (void *p1, void *p2){return( d ( p1, p2 ) c e ); } COMP_FUNC( int, eq, == ) COMP_FUNC( int, gt, > ) COMP_FUNC( int, ge, >= ) COMP_FUNC( int, lt, < ) COMP_FUNC( int, le, <= ) COMP_FUNC( int, ne, != ) COMP_FUNC( double, eq, == ) COMP_FUNC( double, gt, > ) COMP_FUNC( double, ge, >= ) COMP_FUNC( double, lt, < ) COMP_FUNC( double, le, <= ) COMP_FUNC( double, ne, != ) COMP_FUNC( char, eq, == ) COMP_FUNC( char, gt, > ) COMP_FUNC( char, ge, >= ) COMP_FUNC( char, lt, < ) COMP_FUNC( char, le, <= ) COMP_FUNC( char, ne, != ) COMP_FFUNC( string, eq, ==, strcmp, 0 ) COMP_FFUNC( string, gt, >, strcmp, 0 ) COMP_FFUNC( string, ge, >=, strcmp, 0 ) COMP_FFUNC( string, lt, <, strcmp, 0 ) COMP_FFUNC( string, le, <=, strcmp, 0 ) COMP_FFUNC( string, ne, !=, strcmp, 0 ) COMP_FFUNC( casestring, eq, ==, stricmp, 0 ) COMP_FFUNC( casestring, gt, >, stricmp, 0 ) COMP_FFUNC( casestring, ge, >=, stricmp, 0 ) COMP_FFUNC( casestring, lt, <, stricmp, 0 ) COMP_FFUNC( casestring, le, <=, stricmp, 0 ) COMP_FFUNC( casestring, ne, !=, stricmp, 0 ) COMP_FFUNC( varchar, eq, ==, vcharcmp, 0 ) COMP_FFUNC( varchar, gt, >, vcharcmp, 0 ) COMP_FFUNC( varchar, ge, >=, vcharcmp, 0 ) COMP_FFUNC( varchar, lt, <, vcharcmp, 0 ) COMP_FFUNC( varchar, le, <=, vcharcmp, 0 ) COMP_FFUNC( varchar, ne, !=, vcharcmp, 0 ) COMP_FFUNC( casevarchar, eq, ==, vcharcasecmp, 0 ) COMP_FFUNC( casevarchar, gt, >, vcharcasecmp, 0 ) COMP_FFUNC( casevarchar, ge, >=, vcharcasecmp, 0 ) COMP_FFUNC( casevarchar, lt, <, vcharcasecmp, 0 ) COMP_FFUNC( casevarchar, le, <=, vcharcasecmp, 0 ) COMP_FFUNC( casevarchar, ne, !=, vcharcasecmp, 0 ) /* Sorry about putting a data structure here, but I didn't want to have to type in all the function definitions again */ static (* comp_funcs[NUM_SEARCH_COMPS][CF_NUM_FIELD_TYPES*2])(void *,void *) = { { fail, int_eq, double_eq, char_eq, string_eq, varchar_eq, fail, int_eq, double_eq, char_eq, casestring_eq, casevarchar_eq }, { fail, int_ge, double_ge, char_ge, string_ge, varchar_ge, fail, int_ge, double_ge, char_ge, casestring_ge, casevarchar_ge }, { fail, int_gt, double_gt, char_gt, string_gt, varchar_gt, fail, int_gt, double_gt, char_gt, casestring_gt, casevarchar_gt }, { fail, int_le, double_le, char_le, string_le, varchar_le, fail, int_le, double_le, char_le, casestring_le, casevarchar_le }, { fail, int_lt, double_lt, char_lt, string_lt, varchar_lt, fail, int_lt, double_lt, char_lt, casestring_lt, casevarchar_lt }, { fail, int_ne, double_ne, char_ne, string_ne, varchar_ne, fail, int_ne, double_ne, char_ne, casestring_ne, casevarchar_ne } }; static int multi_match( struct Cache_Item *ci, struct cps *cpsp ) { struct full_search_rule *srp; int nrl; int rv=1; nrl = cpsp->nrl; srp = cpsp->srp; /* fprintf(stderr,"multi_match: entry\n");*/ while (nrl && rv) { /* fprintf(stderr,"matching: multi_match: %s\n", search_rule_strs[srp->comparison_method] );*/ /* hex_dump( stderr, (char *)(ci->ci_Item) + srp->cf->cf_f_offset, srp->cf->cf_field_size );*/ /* hex_dump( stderr, (char *)(cpsp->si->ci_Item) + srp->cf->cf_f_offset, srp->cf->cf_field_size );*/ rv = (* srp->cmpfunc)( (char *)(ci->ci_Item) + srp->cf->cf_f_offset, (char *)(cpsp->si->ci_Item) + srp->cf->cf_f_offset ); nrl--; srp++; }; if (rv) cpsp->rv = ci; return(rv); } static int Find_This_Item( struct Cache_Item *ci, struct cps *cpsp ) { int rv=0; /* fprintf(stderr,"matching: Find_This_Item\n");*/ /* hex_dump( stderr, (char *)(ci->ci_Item) + cpsp->srp->cf->cf_f_offset, cpsp->srp->cf->cf_field_size );*/ /* hex_dump( stderr, (char *)(cpsp->si->ci_Item) + cpsp->srp->cf->cf_f_offset, cpsp->srp->cf->cf_field_size );*/ rv = (* cpsp->srp->cmpfunc)( (char *)(ci->ci_Item) + cpsp->srp->cf->cf_f_offset, (char *)(cpsp->si->ci_Item) + cpsp->srp->cf->cf_f_offset ); if (rv) cpsp->rv = ci; return(rv); } static int Init_This_Item( struct Cache_Item *ci, size_t data_size, void *data_item, int expire_time ) { Init_Node( &ci->ci_S_Node, NULL, ci ); Init_Node( &ci->ci_L_Node, NULL, ci ); ci->ci_data_size = data_size; ci->ci_str_size = 0; ci->ci_Item = data_item; /*fprintf(stderr,"Init Item: %p,%p\n", ci, ci->ci_Item );*/ ci->ci_Name = NULL; ci->ci_expire_time = (expire_time) ? time(NULL) + expire_time : 0; return(1); } static struct Cache_Group_Item * New_CGI( struct Cache_List *cl, size_t data_size ) { struct Cache_Group_Item *cgi; if ( (cgi = Remove_Head_Item( &cl->cl_Free_cgi )) ==NULL ) { cgi = malloc( sizeof(struct Cache_Group_Item) + data_size ); } return(cgi); } static struct Cache_Group_Item * Find_CGI( struct Cache_List *cl, struct Full_List *flp, struct full_search_rule *fsrp, struct Cache_Item *ci, size_t data_size, int expire_time ) { struct cps my_cps; struct Cache_Group_Item *cgi; my_cps.ci = NULL; my_cps.srp = fsrp; my_cps.rv = NULL; my_cps.si = ci; /*fprintf(stderr,"About to search %p for %p - First = %p\n", flp, ci, flp->fl_Search_List.ln_Head.ln_Succ );*/ Walk_List2( &flp->fl_Search_List, (Walk_List2_t)Find_This_Item, &my_cps ); if (my_cps.rv==NULL) { /* Doesn't exist. allocate this one */ cgi = New_CGI( cl, data_size ); if (cgi!=NULL) { /* init this cgi */ Init_This_Item( &cgi->cgi_Item, data_size, cgi + 1, expire_time ); Init_Full_List( &cgi->cgi_Items, NULL, 0 ); /*hex_dump( stderr, ci->ci_Item, data_size );*/ memcpy( cgi+1, ci->ci_Item, data_size ); Add_Head( &flp->fl_Search_List, &cgi->cgi_Item.ci_S_Node ); Add_Head( &flp->fl_LRU_List, &cgi->cgi_Item.ci_L_Node ); cgi->cgi_Flags = 0; } }else { cgi = (struct Cache_Group_Item *)my_cps.rv; /*fprintf(stderr, "cgi already exists\n");*/ } return(cgi); } static struct Cache_Item * Build_Search_Item( struct Cache_List *cl, void **keys ) { struct Cache_Item *sci; struct full_search_rule *srp; int nrl; char *tp; sci = malloc( CACHE_ITEM_SIZE + cl->cl_data_size ); /*fprintf(stderr,"search item: %p %d %d\n", sci, CACHE_ITEM_SIZE, cl->cl_data_size );*/ if (sci) { /* copy the various fields */ Init_This_Item( sci, cl->cl_data_size, sci + 1, cl->cl_expire_time ); srp = cl->cl_search_rules; nrl = cl->cl_num_search_rules; tp = (char *)(sci +1); while(nrl--) { /* copy each field in turn */ memcpy( tp + srp->cf->cf_f_offset, *keys++, srp->cf->cf_field_size ); /*hex_dump( stderr, tp + srp->cf->cf_f_offset, srp->cf->cf_field_size );*/ srp++; }; } return(sci); } struct Cache_Item * Cache_Find_Requested_Item( struct Cache_List *cl, const void *keys, int *rv ) { char *single_key; struct Cache_Item *ci; struct Cache_Item *sci; struct Cache_Group_Item *cgi; int nrl; struct full_search_rule *srp; struct Full_List *flp; *rv = CACHE_MISSED; if (cl->cl_num_search_rules == 0) { /* Ah, an old style enquiry. */ single_key = keys; ci = (struct Cache_Item *)Find_Full_Item( &cl->cl_Items, single_key ); *rv = (ci) ? CACHE_FOUND_ITEM : CACHE_MISSED; }else { sci = Build_Search_Item( cl, (void **)keys ); if (sci==NULL) return(NULL); /* time to search done multiple lists */ nrl = cl->cl_num_search_rules; srp = cl->cl_search_rules; flp = &cl->cl_Items; ci = NULL; /* Now, we walk each list in turn, checking each equality item */ do { cgi = Find_CGI( cl, flp, srp, sci, cl->cl_data_size, cl->cl_expire_time ); nrl--; srp++; flp = &cgi->cgi_Items; } while ( nrl && srp->comparison_method == SEARCH_EQ && cgi ); if (cgi && (nrl==0 || srp->comparison_method != SEARCH_EQ) ) { if (cgi->cgi_Flags & CGI_COMPLETE_MISS) { /*fprintf(stderr,"cgi (%p) marked as complete miss\n",cgi);*/ *rv = CACHE_COMPLETE_MISS; } else if (nrl==0) { ci = Remove_Head_Item( &cgi->cgi_Items.fl_Search_List ); Add_Head( &cgi->cgi_Items.fl_Search_List, &ci->ci_S_Node ); *rv = CACHE_FOUND_ITEM; } else { /* Time to do partial check */ struct cps my_cps; my_cps.nrl = nrl; my_cps.srp = srp; my_cps.si = sci; my_cps.rv = NULL; if (Walk_List2( &flp->fl_Search_List, (Walk_List2_t)multi_match, &my_cps )) { *rv = CACHE_FOUND_ITEM; ci = my_cps.rv; }else { ci = Remove_Head_Item( &flp->fl_Search_List ); if (ci) Add_Head( &flp->fl_Search_List, &ci->ci_S_Node ); *rv = ((cl->cl_flags & CACHE_INSERT_MANY) && ci ) ? CACHE_COMPLETE_MISS : CACHE_MISSED; ci = NULL; } } } /*else fprintf(stderr,"cannot find cgi before end of search\n");*/ /*fprintf(stderr,"Freeing: %p\n", sci );*/ free(sci); } return(ci); } static int Build_Search_Rules( struct Cache_List *cl, struct search_rule *srulep ) { int rv=0; /* struct Cache_Field *cf;*/ struct search_rule *trulep; struct full_search_rule *fsrp,*tfsrp; int num_rules=0,toff; #ifdef CACHE_DEBUG /* fprintf(stderr, "Build_Search_Rules: Entry\n" );*/ #endif trulep = srulep; while (trulep->field_name) { trulep++; num_rules++; }; #ifdef CACHE_DEBUG /* fprintf(stderr, "Build_Search_Rules: %d number of rules\n", num_rules );*/ #endif /* Now allocate the correct number of full rules */ fsrp = malloc( num_rules * sizeof(struct full_search_rule) ); if (fsrp) { #ifdef CACHE_DEBUG /* fprintf(stderr, "Build_Search_Rules: rules: <%p>\n", fsrp );*/ #endif tfsrp = fsrp; /* Now initialise each rule */ while(srulep->field_name) { tfsrp->cf = Find_Item_By_Name( &cl->cl_Fields, srulep->field_name ); if (tfsrp->cf == NULL) { free( fsrp ); return(0); } #ifdef CACHE_DEBUG /* fprintf(stderr, "Build_Search_Rules: <%s> <%p> <%d>\n",*/ /* srulep->field_name, tfsrp->cf, srulep->comparison_method );*/ #endif tfsrp->comparison_method = srulep->comparison_method; if ( tfsrp->comparison_method < 0 || tfsrp->comparison_method >= NUM_SEARCH_COMPS ) { /* bad vbalue */ free( fsrp ); return(0); } toff = (tfsrp->cf->cf_field_flags & CF_FLG_IGNORECASE) ? CF_NUM_FIELD_TYPES:0; tfsrp->cmpfunc = comp_funcs[srulep->comparison_method] [tfsrp->cf->cf_field_type + toff]; srulep++; tfsrp++; }; cl->cl_search_rules = fsrp; cl->cl_num_search_rules = num_rules; rv = 1; } #ifdef CACHE_DEBUG /* fprintf(stderr, "Build_Search_Rules: returns %d\n", rv );*/ #endif return(rv); } int Create_Range_Cache( const char *list_name, int max_items, int list_flags, struct search_rule *srulep, const char *format_str, const char *field_names ) { int rv=0; struct Cache_List *cl; List_t *Master_List; Master_List = Get_Cache_Master_List(); cl = (struct Cache_List *)Find_Item_By_Name( Master_List, list_name ); if ( cl == NULL && (cl=New_Cache_List( list_name, max_items, list_flags, CACHE_RANGE_DEFAULTS, CACHE_RANGE_DEFAULTS )) ) { /*fprintf(stderr, "flags: %x %x %x\n", cl->cl_flags,*/ /* list_flags, CACHE_RANGE_DEFAULTS );*/ /* Build the field list */ rv = Cache_Build_Field_List( cl, format_str, field_names ); /* Now parse the search rules */ if (rv==1) rv = Build_Search_Rules( cl, srulep ); if (rv==1) Add_Head( Master_List, &cl->cl_Node ); } #ifdef CACHE_DEBUG if (cache_debug) fprintf(stderr,"%s\n",(rv)?"successfull":"failed"); #endif return(rv); } struct Cache_Item * Cache_Get_Item_From_Free( struct Cache_List *cl ) { struct Cache_Item *ci; ci = Remove_Head_Item( &cl->cl_Free ); if ( ci == NULL ) { /* Need a new one so allocate */ ci = malloc( CACHE_ITEM_SIZE + cl->cl_data_size ); #ifdef CACHE_DEBUG fprintf(stderr, "malloc item %p (from %d & %d)\n", ci, CACHE_ITEM_SIZE, cl->cl_data_size ); #endif Init_This_Item( ci, cl->cl_data_size, ci + 1, cl->cl_expire_time ); #ifdef CACHE_DEBUG fprintf(stderr, "inited\n" ); #endif } if (ci) { #ifdef CACHE_DEBUG if (cache_debug) fprintf(stderr, "About to add to build list\n" ); #endif /* clear this one out */ Add_Tail( &cl->cl_Build, &ci->ci_S_Node ); #ifdef CACHE_DEBUG if (cache_debug) fprintf(stderr, "added to build list\n" ); #endif } return(ci); } int Cache_End_Of_Many( struct Cache_List *cl ) { struct Cache_Item *ci; /* struct Cache_Field *cf;*/ struct Cache_Group_Item *cgi; struct full_search_rule *fsrp; struct Full_List *flp; int nrl; /*fprintf(stderr,"End_Of_Many: starting\n");*/ ci = Remove_Head_Item( &cl->cl_Build ); if (ci==NULL) return(0); Add_Head( &cl->cl_Build, &ci->ci_S_Node ); /*fprintf(stderr," There are items to add\n");*/ while( (ci = Remove_Head_Item( &cl->cl_Build )) ) { flp = &cl->cl_Items; fsrp = cl->cl_search_rules; nrl = cl->cl_num_search_rules; while ( nrl && fsrp->comparison_method == SEARCH_EQ ) { cgi = Find_CGI( cl, flp, fsrp, ci, cl->cl_data_size, cl->cl_expire_time ); /*fprintf(stderr,"Found cgi %p\n", cgi );*/ if (cgi==NULL) { /* big problem. Can't allocate cgi for adding this list, so return items on build list to free list and return failure */ while( (ci = Remove_Head_Item( &cl->cl_Build )) ) { Add_Tail( &cl->cl_Free, &ci->ci_S_Node ); }; return(0); } flp = &cgi->cgi_Items; cgi->cgi_Flags &= ~CGI_COMPLETE_MISS; nrl--; fsrp++; }; /*fprintf(stderr,"About to add items to CGI %p\n", cgi );*/ /* We now have the cgi which will take the current item from the build list */ cgi->cgi_Flags &= ~CGI_COMPLETE_MISS; cl->cl_curr_items++; Add_Tail( &cgi->cgi_Items.fl_Search_List, &ci->ci_S_Node ); Add_Head( &cgi->cgi_Items.fl_LRU_List, &ci->ci_L_Node ); }; return( 1 ); } int Range_Complete_Miss( struct Cache_List *cl, const void *keys ) { struct Cache_Item *ci; struct Cache_Item *sci; struct Cache_Group_Item *cgi; int nrl; struct full_search_rule *srp; struct Full_List *flp; sci = Build_Search_Item( cl, (void **)keys ); if (sci==NULL) return(0); /* time to search done multiple lists */ nrl = cl->cl_num_search_rules; srp = cl->cl_search_rules; flp = &cl->cl_Items; ci = NULL; /* Now, we walk each list in turn, checking each equality item */ do { cgi = Find_CGI( cl, flp, srp, sci, cl->cl_data_size, cl->cl_expire_time ); nrl--; srp++; flp = &cgi->cgi_Items; } while ( nrl && srp->comparison_method == SEARCH_EQ && cgi ); if (cgi && (nrl==0 || srp->comparison_method != SEARCH_EQ) ) cgi->cgi_Flags |= CGI_COMPLETE_MISS; return(1); } static void Flush_Items( struct Cache_Item *ci, struct Cache_List *cl ) { Remove_Node( &ci->ci_S_Node ); Remove_Node( &ci->ci_L_Node ); Add_Tail( &cl->cl_Free, &ci->ci_S_Node ); return; } static void Flush_CGI( struct Cache_Group_Item *cgi, struct cps *cpsp ) { struct cps my_cps; struct full_search_rule *srp; srp = cpsp->srp; memcpy( &my_cps, cpsp, sizeof(struct cps) ); srp++; my_cps.nrl--; my_cps.srp = srp; if (my_cps.nrl==0 || srp->comparison_method != SEARCH_EQ) { /* End of the line */ Walk_List( &cgi->cgi_Items.fl_Search_List, (Walk_List_t)Flush_Items, cpsp->cl ); }else { Walk_List( &cgi->cgi_Items.fl_Search_List, (Walk_List_t)Flush_CGI, &my_cps ); } /* whichever varient it is, this cgi is now redundant */ Remove_Node( &cgi->cgi_Item.ci_S_Node ); Remove_Node( &cgi->cgi_Item.ci_L_Node ); Add_Tail( &cpsp->cl->cl_Free_cgi, &cgi->cgi_Item.ci_S_Node ); return; } int Range_Flush( struct Cache_List *cl ) { struct Cache_Item *ci; int nrl; struct full_search_rule *srp; struct Full_List *flp; struct cps my_cps; /* time to search done multiple lists */ nrl = cl->cl_num_search_rules; srp = cl->cl_search_rules; flp = &cl->cl_Items; ci = NULL; if (srp->comparison_method == SEARCH_EQ) { /* Time to walk each cgi list until we meet real items */ my_cps.cl = cl; my_cps.nrl = nrl; my_cps.srp = srp; Walk_List( &flp->fl_Search_List, (Walk_List_t)Flush_CGI, &my_cps ); }else { Walk_List( &flp->fl_Search_List, (Walk_List_t)Flush_Items, cl ); } return(1); } /* -- End of File -- */