Annotation of libwww/Library/src/HTUTree.c, revision 2.4
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.4 ! frystyk 6: ** @(#) $Id: HTUTree.c,v 2.3 1996/08/24 18:10:22 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 */
2.4 ! frystyk 25: #include "wwwsys.h"
2.1 frystyk 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) {
2.3 frystyk 152: HTUTemplate * pres;
2.1 frystyk 153: HTList * cur = tree->templates;
154: while ((pres = (HTUTemplate *) HTList_nextObject(cur))) {
2.3 frystyk 155: if (HTStrMatch(pres->tmplate, path)) {
2.1 frystyk 156: if (CORE_TRACE)
2.3 frystyk 157: HTTrace("URL Node.... Found template `%s\' for for `%s\'\n",
158: pres->tmplate, path);
2.1 frystyk 159: return pres;
160: }
161: }
162: }
163: return NULL;
164: }
165:
166: /*
167: ** Search a URL Tree for a matching template or realm
168: ** Return the opaque context object found or NULL if none
169: ** Please regard this as a first simple attempt - it can be done
170: ** much more efficient!
171: */
172: PUBLIC void * HTUTree_findNode (HTUTree * tree,
173: const char * realm, const char * path)
174: {
175: HTURealm * rm = HTUTree_findRealm(tree, realm);
176: if (rm)
177: return rm->context;
178: else {
179: HTUTemplate * tm = HTUTree_findTemplate(tree, path);
180: if (tm) return tm->rm_ptr ? tm->rm_ptr->context : NULL;
181: }
182: if (CORE_TRACE) HTTrace("URL Node.... Not found\n");
183: return NULL;
184: }
185:
186: /*
187: ** Add a new node (a template and a realm) to the tree
188: */
189: PUBLIC BOOL HTUTree_addNode (HTUTree * tree,
190: const char * realm, const char * path,
191: void * context)
192: {
193: if (tree) {
194: if (realm && path) { /* If both a path and a realm */
195: HTUTemplate * new_template = HTUTree_newTemplate(tree, path);
196: HTURealm * new_realm = HTUTree_newRealm(tree, realm, context);
197: new_realm->tm_ptr = new_template;
198: new_template->rm_ptr = new_realm;
199: return YES;
200: } else if (realm) { /* If only a realm */
201: HTUTree_newRealm(tree, realm, context);
202: return YES;
203: }
204: if (CORE_TRACE)
205: HTTrace("URL Node.... At least realm must be present\n");
206: }
207: return NO;
208: }
209:
210: /*
211: ** Replace node (insert a new context at the same node)
212: */
213: PUBLIC BOOL HTUTree_replaceNode (HTUTree * tree,
214: const char * realm, const char * path,
215: void * context)
216: {
217: HTURealm * rm = HTUTree_findRealm(tree, realm);
218: if (!rm) {
219: HTUTemplate * tm = HTUTree_findTemplate(tree, path);
220: if (tm) rm = tm->rm_ptr;
221: }
222: if (rm) {
223: if (tree->gc && rm->context) (*tree->gc)(rm->context);
224: rm->context = context;
225: return YES;
226: }
227: if (CORE_TRACE) HTTrace("URL Node.... Not found\n");
228: return NO;
229: }
230:
231: /*
232: ** Remove a node (a template and a realm) from the tree
233: */
234: PUBLIC BOOL HTUTree_deleteNode (HTUTree * tree,
235: const char * realm, const char * path)
236: {
237: if (tree) {
238: HTURealm * rm = HTUTree_findRealm(tree, realm);
239: HTUTemplate * tm = rm ? rm->tm_ptr : HTUTree_findTemplate(tree, path);
240: if (!rm) rm = tm ? tm->rm_ptr : NULL;
241: HTUTree_deleteRealm(tree, rm);
242: HTUTree_deleteTemplate(tree, tm);
243: return YES;
244: }
245: return NO;
246: }
247:
248:
249: PRIVATE BOOL delete_tree (HTUTree * tree)
250: {
251: if (tree) {
252: HTList * cur;
253:
254: /* Free all templates */
255: if ((cur = tree->templates)) {
256: HTUTemplate * pres;
257: while ((pres = (HTUTemplate *) HTList_lastObject(cur)))
258: HTUTree_deleteTemplate(tree, pres);
259: HTList_delete(tree->templates);
260: }
261:
262: /* Free all nodes */
263: if ((cur = tree->realms)) {
264: HTURealm * pres;
265: while ((pres = (HTURealm *) HTList_lastObject(cur)))
266: HTUTree_deleteRealm(tree, pres);
267: HTList_delete(tree->realms);
268: }
269:
270: HT_FREE(tree->name);
271: HT_FREE(tree->host);
272: HT_FREE(tree);
273: return YES;
274: }
275: return NO;
276: }
277:
278: /*
279: ** Find an existing URL Tree
280: ** Returns tree or NULL if error
281: */
282: PRIVATE HTUTree * find_tree (const char * name,
283: const char * host,
284: int port,
285: HTList ** hashlist)
286: {
287: HTUTree * pres = NULL;
288: *hashlist = NULL;
289: if (!name || !host) {
290: if (CORE_TRACE) HTTrace("URL Tree.... Bad argument\n");
291: return NULL;
292: }
293:
294: /* Find a hash for this host */
295: {
296: int hash = 0;
297: const char * ptr;
298: for (ptr=host; *ptr; ptr++)
299: hash = (int) ((hash * 3 + (*(unsigned char *) ptr)) % HASH_SIZE);
300: if (!InfoTable) {
301: if ((InfoTable = (HTList **) HT_CALLOC(HASH_SIZE,
302: sizeof(HTList *))) == NULL)
303: HT_OUTOFMEM("HTUTree_find");
304: }
305: if (!InfoTable[hash])
306: InfoTable[hash] = *hashlist = HTList_new();
307: else
308: *hashlist = InfoTable[hash];
309: }
310:
311: /* Search the existing list to see if we already have this entry */
312: {
313: HTList * cur = *hashlist;
314: while ((pres = (HTUTree *) HTList_nextObject(cur))) {
315: if (!strcmp(pres->name, name) && !strcmp(pres->host, host) &&
316: pres->port==port) {
317: if (time(NULL) > pres->created + UTreeTimeout) {
318: if (CORE_TRACE)
319: HTTrace("URL Tree.... Collecting URL Tree %p\n", pres);
320: HTList_removeObject(*hashlist, pres);
321: delete_tree(pres);
322: pres = NULL;
323: }
324: return pres;
325: }
326: }
327: }
328: return NULL;
329: }
330:
331: /*
332: ** Create a new URL Tree (or return an aready existing one)
333: ** Returns new object (or the one found) or NULL if error
334: */
335: PUBLIC HTUTree * HTUTree_new (const char * name,
336: const char * host,
337: int port,
338: HTUTree_gc * gc)
339: {
340: if (name && host) {
341: HTList * hashlist = NULL;
342: HTUTree * pres = find_tree(name, host, port, &hashlist);
343:
344: /* If not found (or gc'ed) then create a new URL tree */
345: if (!pres) {
346: if ((pres = (HTUTree *) HT_CALLOC(1, sizeof(HTUTree))) == NULL)
347: HT_OUTOFMEM("HTUTree_new");
348: StrAllocCopy(pres->name, name);
349: StrAllocCopy(pres->host, host);
350: pres->port = (port > 0 ? port : 80);
351: pres->templates = HTList_new();
352: pres->realms = HTList_new();
353: pres->created = time(NULL);
354: pres->gc = gc;
355:
356: /* Add the new URL tree to the hash table */
357: HTList_addObject(hashlist, (void *) pres);
358: if (CORE_TRACE)HTTrace("URL Tree.... Created %p with name `%s\'\n",
359: pres, pres->name);
360: } else {
361: if (CORE_TRACE) HTTrace("URL Tree.... Found %p with name `%s\'\n",
362: pres, pres->name);
363: }
364: return pres;
365: } else {
366: if (CORE_TRACE) HTTrace("URL Tree.... Bad argument\n");
367: return NULL;
368: }
369: }
370:
371: /*
372: ** Find a URL tree
373: */
374: PUBLIC HTUTree * HTUTree_find (const char * name,
375: const char * host,
376: int port)
377: {
378: if (name && host) {
379: HTList * hashlist = NULL;
380: HTUTree * pres = find_tree(name, host, port, &hashlist);
381: if (CORE_TRACE) HTTrace("URL Tree.... did %sfind `%s\'\n",
382: pres ? "" : "NOT ", name);
383: return pres;
384: } else {
385: if (CORE_TRACE) HTTrace("URL Tree.... Bad augument\n");
386: }
387: return NULL;
388: }
389:
390:
391: /*
392: ** Delete a complete server tree and everything within it.
393: */
394: PUBLIC BOOL HTUTree_delete (const char * name,
395: const char * host,
396: int port)
397: {
398: if (name && host) {
399: HTList * hashlist = NULL;
400: HTUTree * pres = find_tree(name, host, port, &hashlist);
401: if (pres) {
402: HTList_removeObject(hashlist, pres);
403: delete_tree(pres);
404: if (CORE_TRACE) HTTrace("URL Tree.... deleted %p\n", pres);
405: return YES;
406: }
407: }
408: return NO;
409: }
410:
411: /*
412: ** Delete all URL Trees
413: */
414: PUBLIC BOOL HTUTree_deleteAll (void)
415: {
416: if (InfoTable) {
417: int cnt;
418: HTList * cur;
419: for (cnt=0; cnt<HASH_SIZE; cnt++) {
420: if ((cur = InfoTable[cnt])) {
421: HTUTree * pres;
422: while ((pres = (HTUTree *) HTList_nextObject(cur)))
423: delete_tree(pres);
424: }
425: HTList_delete(InfoTable[cnt]);
426: }
427: HT_FREE(InfoTable);
428: return YES;
429: }
430: return NO;
431: }
Webmaster