#ifndef extc_hash_h #define extc_hash_h #include <string.h> #include <stdlib.h> /*************************************************************************** * (place-holder file) hash.h * * Tue Jul 26 13:42:18 2005 * Copyright 2005 James Scully- aka jtox * Email jtoxification @ the-only-free-2-gig-account-service-online *************************************************************************** * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA *************************************************************************** * Todo: typedef out unsigned long long and test using macros: Windows and Borland compilers don't know what this is at all, which is a real shame. * NOTE: this is a //Horribly// inefficient table: *Think of the backend and this hashtable as slabs of wood, glued together by an interface: Then this particular interface is analogous to elmer's glue stick. Why? Because there's too much memory allocation and deallocation. THE BEST BACKEND ADTs for this project are: obj_db : a splay tree. -- (implemented as a pseudo-array- pointer to resized memory(realloc). why? because we'll always need to search for a specific item linearly, since we don't know which item it could be. That may improve slightly, after organizing the object table into individual tables for each type, but it'll still be a full search. Yes, a splay tree does take extra operations to move the found object to the top of the tree after each search -> this actually creates a slight speedup for objects that are accessed frequently, as they will be closest to the top. An extra feature to be used could be an ordered reference count in array form of the objects, and during the time that objects are accessed, an extra thread or process is continually monitoring the access and using a secondary array to re-order the tree as this happens, and after each re-order, the process then locks the tree in question, and swaps out address locations of the array. In this way, there are two arrays of addresses kept, and while one is being accessed, the other is being re-ordered for speed. This particular design WILL require a reader-writer structure with reader-preference/writer-priority for optimal throughput, such that when the monitor thread/process is checking access counts it is reading and when it is swapping array pointers, it is writing. (and updated automatically ONLY by the backend, so that anyone who wants to make their own backend doesn't have to watch for this, too. self_db: a hash tree. -- why? because we know the data, we know its location, and we know which process and which thread will want to access it. Furthermore, we will want to ensure that there's only one entry per thread so that when a member-function is accessed without arguments, extra memory will not get called as a result. Hence, this tree will never get too big, and it never exceed a specific size limit due to the restraints on # of processes and threads per user/OS. * Hence, this is a "PLACE-HOLDER" backend. * The aircraft-glue version will come later with: + buffering -- most likely a splay tree. + less-frequent memory allocation, mostly static mem instead. * what do you need to make your own backend? #1: unless this is the final version, in which case this particular message will no longer be present, you MUST IMPLEMENT the backend WITHOUT Extended C utilities! Why? Well, you can if you want, but the whole point of implementing your own backend is for speed and memory, right? Well, this doesn't really implement either one all that well. You need one function and two objects: //This is what the system uses to initialize the objects. void initialize_database(); //These are the objects. treat 'em like pre-allocated const pointers. database_type1 self_db[1]; This must have the following pointer-to-function members: void (*add) (void*);//adds an object address to the obj_db database void*(*search)( );//searches for an object whose _id_ member changed //copy these utilities to test alteration: //static int is_callback(void* v) //{return *(void**)v != v;} void*(*remove)(void*);//removes the object address from the database. //Note you need not worry about removing local objects (well, you can, //but since gcc keeps local-variable addresses the same across function //calls, you'll only be re-allocating the majority of these addresses //later if you implement testing of out-of-scope variables. //and besides, there are very few ways of doing this, and the only //one I can think of requires #define Return deletestuff , return database_type2 obj_db[1]; void (*add )(void*,unsigned long long id); //adds an object address to the self_db database, //using "id" as the lookup key. void*(*search)(unsigned long long key); //searches for an object whose _id_ member changed //copy the below utility (and its definition) to test alteration: //static int is_callback(void* v) void*(*remove)(unsigned long long key); //returns address and removes it from the database. ****************************************************************************/ #define HASHSIZE 0x1000 #define max(a,b) ((a >= b)?a:b) #define min(a,b) ((a >= b)?b:a) /* The below expression is caught and set to a constant by gcc */ #define MEMHASHSIZE (sizeof(void*)*HASHSIZE) /* If your compiler doesn't do that, comment the above, and uncomment this: */ /* int MEMHASHSIZE=sizeof(void*)*HASHSIZE; */ #define Int(x) ((int)x) #define Uns(x) ((unsigned)x) #define Item(x) ((ITEM*)(x->item)) #define Next(x) ((x)->next) #define Data(x) (((ITEM*)x)->data) #define Key(x) (((ITEM*)x)->key) /* *************************************************************************** Types *************************************************************************** */ typedef struct ITEM { unsigned long long key; void* data; } ITEM; typedef struct llist { void* item; struct llist* next; int count; } llist; typedef struct htab { unsigned int size; unsigned(*hash )(); void* (*search)(); void (*add )(); void* (*remove)(); void* *entries; } htab[1]; /* *************************************************************************** Globals : TODO: make accessor functions local to the registry file and hide these properly (relocate them safely somewhere else) *************************************************************************** */ htab obj_db; htab self_db; /* *************************************************************************** Prototypes *************************************************************************** */ int mclear (void* mem, size_t length); static void* find_altered (llist*); static int is_callback (void* ); void initialize_database(); static void newTable (struct htab* t,unsigned int num_entries,unsigned (*hashfunc)()); unsigned int hash(void* p); unsigned int t_hash(unsigned long long ull); #if defined(DEBUG_EXTC) unsigned int _exists (void* item); #endif static void _add (void* item); static void* _remove (void* item); static void* _search ( ); static void t_add (void* data,unsigned long long id ); static void* t_remove( unsigned long long key); static void* t_search( unsigned long long key); /* *************************************************************************** Function definitions memory utilities *************************************************************************** */ int mclear(void* mem,size_t length) /* this is actually pretty fast. */ { if (!mem || length <=0) return -1; int i; unsigned long long* l=(unsigned long long*)mem; unsigned char* c=(unsigned char*)mem; int r=(length-length%sizeof(unsigned long long))/sizeof(unsigned long long); for (i = r*sizeof(unsigned long long); i<length ; ++i) c[i]=0; for (i = r-1; i>=0 ; --i) l[i]=0; return 0; } /* *************************************************************************** Function definitions search utilities *************************************************************************** */ static void* find_altered(llist* n) { while (n!=NULL) { if (is_callback(n->item)) break; n = n->next; } return (void*)n; } /* *************************************************************************** */ static int is_callback(void* v) { if (v == ((void**)v)[0]) return 0; DBGALSO((" ! ")); /*((void**)v)[0]++;*/ ((void**)v)[0] = v; return 1; } /* *************************************************************************** Function definitions hash functions (much to be desired? they seem pretty good in practice) *************************************************************************** */ unsigned hash(void* p) { DBGMSG((" hashing item.\n")); return Uns((Int(p)-Int(obj_db->entries)) % obj_db->size); } /* *************************************************************************** */ unsigned int t_hash(unsigned long long i) { return Uns((Int(i)-Int(self_db->entries)) % self_db->size); } /* *************************************************************************** Function definitions Type-allocation utilities *************************************************************************** */ void initialize_database() { DBGMSG(("databases intitialized.\n")); newTable( obj_db,HASHSIZE,hash); newTable(self_db,HASHSIZE,t_hash); DBGMSG(("Sizes %i\n",obj_db->size)); DBGMSG((" %i\n",self_db->size)); } /* *************************************************************************** */ static llist* newLLIST(void* data) { DBGMSG((" New llist item.\n")); llist* l = (llist*)malloc(sizeof(llist)); Next(l) = NULL; l->item = data; return l; } /* *************************************************************************** */ static ITEM* newITEM(void* data, unsigned long long key) { DBGMSG((" New ITEM.\n")); ITEM* i = (ITEM*)malloc(sizeof(ITEM)); i->key = key; i->data = data; return i; } /* *************************************************************************** */ static void newTable(struct htab* t,unsigned int num_entries,unsigned (*hashfunc)()) { DBGMSG(("New Table.\n")); mclear(t,sizeof(struct htab)); t->size = num_entries; num_entries *= sizeof(void*); t->entries = (void*)malloc(num_entries); mclear(t->entries,num_entries); t->hash = hashfunc; if (hashfunc == t_hash) { t->search = t_search; t->add = t_add ; t->remove = t_remove; } else { t->search = _search; t->add = _add ; t->remove = _remove; } return; } /* *************************************************************************** Function definitions Registry implementations *************************************************************************** */ /* This one is only really needed during debugging, but I may include it as a required registry member function later ... */ #if defined(DEBUG_EXTC) unsigned int _exists(void* item) { DBGMSG(("Searching for receipt of item.\n")); unsigned int x = obj_db->hash(item); DBGMSG((" hash = %i.\n",x)); llist* l = obj_db->entries[x]; if (!l) { DBGMSG((" No record of that object exists.\n")); return FALSE; } if (l->item == item) { DBGMSG((" Item *is* in registry.\n")); return TRUE; } while (l->next) { l = l->next; if (l->item == item) { DBGMSG((" Item *is* already in registry.\n")); return TRUE; } } DBGMSG((" No record of that object exists.\n")); return FALSE; } #endif /* *************************************************************************** */ /* Here, we only want to add an item if we've not seen it before. Since gcc keeps local object adresses the same across function calls, even recursively so, this allows us support for local objects on top of the function stack. */ static void _add(void* item) { DBGMSG(("adding item.\n")); unsigned int x = obj_db->hash(item); DBGMSG((" hash = %i.\n",x)); llist* l = obj_db->entries[x]; if (!l) { DBGMSG((" allocating new space.\n")); obj_db->entries[x]=(void*)newLLIST(item); return; } if (l->item == item) { DBGMSG((" Item is already in registry.\n")); return; } while (l->next) { l = l->next; if (l->item == item) { DBGMSG((" Item is already in registry.\n")); return; } } DBGMSG((" allocating new space.\n")); l->next = newLLIST(item); return; } /* *************************************************************************** */ /* Since some programmers may legitimately call obj->func without arguments, we need to ensure that multiple calls on the same process will not add new entries. hence we overwrite older process/thread combo entries. */ static void t_add(void* data,unsigned long long id) { DBGMSG((" adding 'this'.\n")); llist* l = self_db->entries[self_db->hash(id)]; if (!l) { DBGMSG((" allocating new space:\n")); self_db->entries[self_db->hash(id)] = newLLIST(newITEM(data,id)); DBGMSG((" Returning @ top of func\n")); return; } if (id == Key(Item(l))) { DBGMSG((" using old space:\n")); Data(Item(l)) = data; DBGMSG((" Returning.\n")); return; } while (Next(l)) { if (id == Key(Item(Next(l)))) { DBGMSG((" using old space:\n")); Data(Item(Next(l))) = data; DBGMSG((" Returning.\n")); return; } l = Next(l); } DBGMSG((" allocating new space:\n")); Next(l) = newLLIST(newITEM(data,id)); DBGMSG((" Returning @ endloop.\n")); return; } /* *************************************************************************** */ static void * _remove(void* item) { DBGMSG(("removing item.\n")); unsigned int x = obj_db->hash(item); llist *a; llist *l = (llist*)obj_db->entries[x]; if (!l) { DBGMSG((" Item NOT FOUND! (top-level)\n")); return item; } if (l->item == item) { DBGMSG((" Found item. Removing...\n")); obj_db->entries[x]= (void*)Next(l); free(l); return item; } while (Next(l)) { if (Next(l)->item == item) { DBGMSG((" Found item. Removing...\n")); a = Next(l); Next(l) = Next(a); free(a); return item; } l = Next(l); } DBGMSG((" Item NOT FOUND! (bottom-level)\n")); return item; } /* *************************************************************************** */ static void* t_remove(unsigned long long key) { DBGMSG(("searching for 'this'")); llist *a,*l=self_db->entries[self_db->hash(key)]; void* data; if (!l) { DBGALSO((" NOT FOUND!\n")); return NULL; } if (Key(Item(l)) == key) { DBGALSO(("\n removing 'this'")); /*1*/ self_db->entries[self_db->hash(key)] = (void*)Next(l); DBGALSO((".")); /*2*/ data = Data(Item(l)); DBGALSO((".")); /*3*/ free(Item(l)); DBGALSO((".")); /*4*/ free(l); DBGALSO((".\n")); return data; } else { while (Next(l)) { if (Item(Next(l))->key == key) { DBGALSO(("\n removing 'this'")); data=Data(Item(Next(l))); DBGALSO((".")); a = Next(l); DBGALSO((".")); Next(l) = Next(a); DBGALSO((".")); free(Item(a)); DBGALSO((".")); free(a); DBGALSO((".\n")); return data; } l = Next(l); } } DBGALSO((" NOT FOUND!\n")); return NULL; } /* *************************************************************************** */ static void* _search() { DBGMSG(("searching for item.")); int i; void* v; for (i=0;i < obj_db->size;i++) { if (! obj_db->entries[i] ) continue; DBGALSO((".")) v = find_altered(obj_db->entries[i]); if (v) {DBGALSO(("found\n"));break;} } return v; } /* *************************************************************************** */ static void* t_search(unsigned long long key) { DBGMSG(("searching for 'this'.\n")); llist* l=self_db->entries[self_db->hash(key)]; if (!l) { DBGMSG((" NOT FOUND!.\n")); return NULL; } if (Key(Item(l)) == key) return Data(Item(l)); while (Next(l)) { if (Item(Next(l))->key == key) return Data(Item(Next(l))); l = Next(l); } return NULL; } /* End hash table */ #endif