Annotation of libwww/Library/src/HTUTree.c, revision 2.1
2.1 ! frystyk 1: /*
! 2: ** URL DATA TREE STRUCTURE
! 3: **
! 4: ** (c) COPYRIGHT MIT 1995.
! 5: ** Please first read the full copyright statement in the file COPYRIGH.
! 6: ** @(#) $Id: HTAAUtil.c,v 2.22 1996/06/28 16:30:46 frystyk Exp $
! 7: **
! 8: ** AUTHORS:
! 9: ** HFN Henrik Frystyk Nielsen <frystyk@w3.org>
! 10: **
! 11: ** An infobase is a tree structure where we can store all the information
! 12: ** we know about a remote server. Typically, each remote server will
! 13: ** have its own infobase which gets richer as we get to know more about
! 14: ** the remote web site.
! 15: **
! 16: ** This module maintains an URL information database
! 17: ** which can contain information stored by filters. This can for
! 18: ** example be used to store challenges received from remote server.
! 19: ** A infobase has the advantage that it can be searched using URLs _or_
! 20: ** using realms. The letter is most useful to "guess" information
! 21: ** about a remote URL that we haven't seen before
! 22: */
! 23:
! 24: /* Library include files */
! 25: #include "sysdep.h"
! 26: #include "WWWUtil.h"
! 27: #include "HTUTree.h" /* Implemented here */
! 28:
! 29: #define TREE_TIMEOUT 43200L /* Default tree timeout is 12 h */
! 30: #define HASH_SIZE 101 /* Arbitrary prime */
! 31:
! 32: struct _HTUTree { /* Server URL info base */
! 33: char * name;
! 34: char * host;
! 35: int port;
! 36:
! 37: HTList * templates; /* List of templates for this tres */
! 38: HTList * realms; /* List of realms for this tree */
! 39:
! 40: time_t created; /* Creation time of this object */
! 41: HTUTree_gc * gc; /* Contect garbage collector */
! 42: };
! 43:
! 44: struct _HTURealm { /* Realm specifics */
! 45: char * realm;
! 46: void * context;
! 47: HTUTemplate * tm_ptr;
! 48: };
! 49:
! 50: struct _HTUTemplate { /* Hierarchical information */
! 51: char * tmplate;
! 52: HTURealm * rm_ptr;
! 53: };
! 54:
! 55: PRIVATE HTList ** InfoTable = NULL; /* List of information bases */
! 56: PRIVATE time_t UTreeTimeout = TREE_TIMEOUT;
! 57:
! 58: /* ------------------------------------------------------------------------- */
! 59:
! 60: /*
! 61: ** Create a new realm
! 62: ** Returns new object or NULL if error
! 63: */
! 64: PRIVATE HTURealm * HTUTree_newRealm (HTUTree * tree, const char * realm,
! 65: void * context)
! 66: {
! 67: if (tree) {
! 68: HTURealm * me;
! 69: if ((me = (HTURealm *) HT_CALLOC(1, sizeof(HTURealm))) == NULL)
! 70: HT_OUTOFMEM("HTURealm_new");
! 71: if (realm) StrAllocCopy(me->realm, realm);
! 72: me->context = context;
! 73: HTList_addObject(tree->realms, (void *) me);
! 74: return me;
! 75: }
! 76: return NULL;
! 77: }
! 78:
! 79: /*
! 80: ** Delete a realm. We call the scheme gc callback to free the opaque
! 81: ** context object.
! 82: */
! 83: PRIVATE BOOL HTUTree_deleteRealm (HTUTree * tree, HTURealm * me)
! 84: {
! 85: if (tree && me) {
! 86: if (tree->gc && me->context) (*tree->gc)(me->context);
! 87: HTList_removeObject(tree->realms, (void *) me);
! 88: HT_FREE(me->realm);
! 89: HT_FREE(me);
! 90: return YES;
! 91: }
! 92: return NO;
! 93: }
! 94:
! 95: /*
! 96: ** Find a realm
! 97: */
! 98: PRIVATE HTURealm * HTUTree_findRealm (HTUTree * tree, const char * realm)
! 99: {
! 100: if (tree && tree->realms && realm) {
! 101: HTList * cur = tree->realms;
! 102: HTURealm * pres;
! 103: while ((pres = (HTURealm *) HTList_nextObject(cur))) {
! 104: if (!strcmp(pres->realm, realm)) {
! 105: if (CORE_TRACE)
! 106: HTTrace("URL Node.... Realm `%s\' found\n", realm);
! 107: return pres;
! 108: }
! 109: }
! 110: }
! 111: return NULL;
! 112: }
! 113:
! 114:
! 115: /*
! 116: ** Create a new template and add to URL tree
! 117: ** Returns new object or NULL if error
! 118: */
! 119: PRIVATE HTUTemplate * HTUTree_newTemplate (HTUTree * tree,const char * tmplate)
! 120: {
! 121: if (tree && tmplate) {
! 122: HTUTemplate * me;
! 123: if ((me = (HTUTemplate *) HT_CALLOC(1, sizeof(HTUTemplate))) == NULL)
! 124: HT_OUTOFMEM("HTUTemplate_new");
! 125: StrAllocCopy(me->tmplate, tmplate);
! 126: HTList_addObject(tree->templates, (void *) me);
! 127: return me;
! 128: }
! 129: return NULL;
! 130: }
! 131:
! 132: /*
! 133: ** Delete a template
! 134: */
! 135: PRIVATE BOOL HTUTree_deleteTemplate (HTUTree * tree, HTUTemplate * me)
! 136: {
! 137: if (tree && me) {
! 138: HTList_removeObject(tree->templates, (void *) me);
! 139: HT_FREE(me->tmplate);
! 140: HT_FREE(me);
! 141: return YES;
! 142: }
! 143: return NO;
! 144: }
! 145:
! 146: /*
! 147: ** Find a template
! 148: */
! 149: PRIVATE HTUTemplate * HTUTree_findTemplate (HTUTree * tree, const char * path)
! 150: {
! 151: if (tree && tree->templates && path) {
! 152: HTList * cur = tree->templates;
! 153: HTUTemplate * pres;
! 154: while ((pres = (HTUTemplate *) HTList_nextObject(cur))) {
! 155: if (!HTStrMatch(pres->tmplate, path)) {
! 156: if (CORE_TRACE)
! 157: HTTrace("URL Node.... Template for for `%s\'\n", path);
! 158: return pres;
! 159: }
! 160: }
! 161: }
! 162: return NULL;
! 163: }
! 164:
! 165: /*
! 166: ** Search a URL Tree for a matching template or realm
! 167: ** Return the opaque context object found or NULL if none
! 168: ** Please regard this as a first simple attempt - it can be done
! 169: ** much more efficient!
! 170: */
! 171: PUBLIC void * HTUTree_findNode (HTUTree * tree,
! 172: const char * realm, const char * path)
! 173: {
! 174: HTURealm * rm = HTUTree_findRealm(tree, realm);
! 175: if (rm)
! 176: return rm->context;
! 177: else {
! 178: HTUTemplate * tm = HTUTree_findTemplate(tree, path);
! 179: if (tm) return tm->rm_ptr ? tm->rm_ptr->context : NULL;
! 180: }
! 181: if (CORE_TRACE) HTTrace("URL Node.... Not found\n");
! 182: return NULL;
! 183: }
! 184:
! 185: /*
! 186: ** Add a new node (a template and a realm) to the tree
! 187: */
! 188: PUBLIC BOOL HTUTree_addNode (HTUTree * tree,
! 189: const char * realm, const char * path,
! 190: void * context)
! 191: {
! 192: if (tree) {
! 193: if (realm && path) { /* If both a path and a realm */
! 194: HTUTemplate * new_template = HTUTree_newTemplate(tree, path);
! 195: HTURealm * new_realm = HTUTree_newRealm(tree, realm, context);
! 196: new_realm->tm_ptr = new_template;
! 197: new_template->rm_ptr = new_realm;
! 198: return YES;
! 199: } else if (realm) { /* If only a realm */
! 200: HTUTree_newRealm(tree, realm, context);
! 201: return YES;
! 202: }
! 203: if (CORE_TRACE)
! 204: HTTrace("URL Node.... At least realm must be present\n");
! 205: }
! 206: return NO;
! 207: }
! 208:
! 209: /*
! 210: ** Replace node (insert a new context at the same node)
! 211: */
! 212: PUBLIC BOOL HTUTree_replaceNode (HTUTree * tree,
! 213: const char * realm, const char * path,
! 214: void * context)
! 215: {
! 216: HTURealm * rm = HTUTree_findRealm(tree, realm);
! 217: if (!rm) {
! 218: HTUTemplate * tm = HTUTree_findTemplate(tree, path);
! 219: if (tm) rm = tm->rm_ptr;
! 220: }
! 221: if (rm) {
! 222: if (tree->gc && rm->context) (*tree->gc)(rm->context);
! 223: rm->context = context;
! 224: return YES;
! 225: }
! 226: if (CORE_TRACE) HTTrace("URL Node.... Not found\n");
! 227: return NO;
! 228: }
! 229:
! 230: /*
! 231: ** Remove a node (a template and a realm) from the tree
! 232: */
! 233: PUBLIC BOOL HTUTree_deleteNode (HTUTree * tree,
! 234: const char * realm, const char * path)
! 235: {
! 236: if (tree) {
! 237: HTURealm * rm = HTUTree_findRealm(tree, realm);
! 238: HTUTemplate * tm = rm ? rm->tm_ptr : HTUTree_findTemplate(tree, path);
! 239: if (!rm) rm = tm ? tm->rm_ptr : NULL;
! 240: HTUTree_deleteRealm(tree, rm);
! 241: HTUTree_deleteTemplate(tree, tm);
! 242: return YES;
! 243: }
! 244: return NO;
! 245: }
! 246:
! 247:
! 248: PRIVATE BOOL delete_tree (HTUTree * tree)
! 249: {
! 250: if (tree) {
! 251: HTList * cur;
! 252:
! 253: /* Free all templates */
! 254: if ((cur = tree->templates)) {
! 255: HTUTemplate * pres;
! 256: while ((pres = (HTUTemplate *) HTList_lastObject(cur)))
! 257: HTUTree_deleteTemplate(tree, pres);
! 258: HTList_delete(tree->templates);
! 259: }
! 260:
! 261: /* Free all nodes */
! 262: if ((cur = tree->realms)) {
! 263: HTURealm * pres;
! 264: while ((pres = (HTURealm *) HTList_lastObject(cur)))
! 265: HTUTree_deleteRealm(tree, pres);
! 266: HTList_delete(tree->realms);
! 267: }
! 268:
! 269: HT_FREE(tree->name);
! 270: HT_FREE(tree->host);
! 271: HT_FREE(tree);
! 272: return YES;
! 273: }
! 274: return NO;
! 275: }
! 276:
! 277: /*
! 278: ** Find an existing URL Tree
! 279: ** Returns tree or NULL if error
! 280: */
! 281: PRIVATE HTUTree * find_tree (const char * name,
! 282: const char * host,
! 283: int port,
! 284: HTList ** hashlist)
! 285: {
! 286: HTUTree * pres = NULL;
! 287: *hashlist = NULL;
! 288: if (!name || !host) {
! 289: if (CORE_TRACE) HTTrace("URL Tree.... Bad argument\n");
! 290: return NULL;
! 291: }
! 292:
! 293: /* Find a hash for this host */
! 294: {
! 295: int hash = 0;
! 296: const char * ptr;
! 297: for (ptr=host; *ptr; ptr++)
! 298: hash = (int) ((hash * 3 + (*(unsigned char *) ptr)) % HASH_SIZE);
! 299: if (!InfoTable) {
! 300: if ((InfoTable = (HTList **) HT_CALLOC(HASH_SIZE,
! 301: sizeof(HTList *))) == NULL)
! 302: HT_OUTOFMEM("HTUTree_find");
! 303: }
! 304: if (!InfoTable[hash])
! 305: InfoTable[hash] = *hashlist = HTList_new();
! 306: else
! 307: *hashlist = InfoTable[hash];
! 308: }
! 309:
! 310: /* Search the existing list to see if we already have this entry */
! 311: {
! 312: HTList * cur = *hashlist;
! 313: while ((pres = (HTUTree *) HTList_nextObject(cur))) {
! 314: if (!strcmp(pres->name, name) && !strcmp(pres->host, host) &&
! 315: pres->port==port) {
! 316: if (time(NULL) > pres->created + UTreeTimeout) {
! 317: if (CORE_TRACE)
! 318: HTTrace("URL Tree.... Collecting URL Tree %p\n", pres);
! 319: HTList_removeObject(*hashlist, pres);
! 320: delete_tree(pres);
! 321: pres = NULL;
! 322: }
! 323: return pres;
! 324: }
! 325: }
! 326: }
! 327: return NULL;
! 328: }
! 329:
! 330: /*
! 331: ** Create a new URL Tree (or return an aready existing one)
! 332: ** Returns new object (or the one found) or NULL if error
! 333: */
! 334: PUBLIC HTUTree * HTUTree_new (const char * name,
! 335: const char * host,
! 336: int port,
! 337: HTUTree_gc * gc)
! 338: {
! 339: if (name && host) {
! 340: HTList * hashlist = NULL;
! 341: HTUTree * pres = find_tree(name, host, port, &hashlist);
! 342:
! 343: /* If not found (or gc'ed) then create a new URL tree */
! 344: if (!pres) {
! 345: if ((pres = (HTUTree *) HT_CALLOC(1, sizeof(HTUTree))) == NULL)
! 346: HT_OUTOFMEM("HTUTree_new");
! 347: StrAllocCopy(pres->name, name);
! 348: StrAllocCopy(pres->host, host);
! 349: pres->port = (port > 0 ? port : 80);
! 350: pres->templates = HTList_new();
! 351: pres->realms = HTList_new();
! 352: pres->created = time(NULL);
! 353: pres->gc = gc;
! 354:
! 355: /* Add the new URL tree to the hash table */
! 356: HTList_addObject(hashlist, (void *) pres);
! 357: if (CORE_TRACE)HTTrace("URL Tree.... Created %p with name `%s\'\n",
! 358: pres, pres->name);
! 359: } else {
! 360: if (CORE_TRACE) HTTrace("URL Tree.... Found %p with name `%s\'\n",
! 361: pres, pres->name);
! 362: }
! 363: return pres;
! 364: } else {
! 365: if (CORE_TRACE) HTTrace("URL Tree.... Bad argument\n");
! 366: return NULL;
! 367: }
! 368: }
! 369:
! 370: /*
! 371: ** Find a URL tree
! 372: */
! 373: PUBLIC HTUTree * HTUTree_find (const char * name,
! 374: const char * host,
! 375: int port)
! 376: {
! 377: if (name && host) {
! 378: HTList * hashlist = NULL;
! 379: HTUTree * pres = find_tree(name, host, port, &hashlist);
! 380: if (CORE_TRACE) HTTrace("URL Tree.... did %sfind `%s\'\n",
! 381: pres ? "" : "NOT ", name);
! 382: return pres;
! 383: } else {
! 384: if (CORE_TRACE) HTTrace("URL Tree.... Bad augument\n");
! 385: }
! 386: return NULL;
! 387: }
! 388:
! 389:
! 390: /*
! 391: ** Delete a complete server tree and everything within it.
! 392: */
! 393: PUBLIC BOOL HTUTree_delete (const char * name,
! 394: const char * host,
! 395: int port)
! 396: {
! 397: if (name && host) {
! 398: HTList * hashlist = NULL;
! 399: HTUTree * pres = find_tree(name, host, port, &hashlist);
! 400: if (pres) {
! 401: HTList_removeObject(hashlist, pres);
! 402: delete_tree(pres);
! 403: if (CORE_TRACE) HTTrace("URL Tree.... deleted %p\n", pres);
! 404: return YES;
! 405: }
! 406: }
! 407: return NO;
! 408: }
! 409:
! 410: /*
! 411: ** Delete all URL Trees
! 412: */
! 413: PUBLIC BOOL HTUTree_deleteAll (void)
! 414: {
! 415: if (InfoTable) {
! 416: int cnt;
! 417: HTList * cur;
! 418: for (cnt=0; cnt<HASH_SIZE; cnt++) {
! 419: if ((cur = InfoTable[cnt])) {
! 420: HTUTree * pres;
! 421: while ((pres = (HTUTree *) HTList_nextObject(cur)))
! 422: delete_tree(pres);
! 423: }
! 424: HTList_delete(InfoTable[cnt]);
! 425: }
! 426: HT_FREE(InfoTable);
! 427: return YES;
! 428: }
! 429: return NO;
! 430: }
Webmaster