Annotation of libwww/Library/src/HTUTree.c, revision 2.2
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.
2.2 ! frystyk 6: ** @(#) $Id: HTUTree.c,v 2.2 1996/07/19 07:41:59 frystyk Exp $
2.1 frystyk 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)
2.2 ! frystyk 157: HTTrace("URL Node.... Did find template for for `%s\'\n", path);
2.1 frystyk 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