1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <assert.h>
18#include <stdio.h>
19#include <stdlib.h>
20
21#include "apr_pools.h"
22#include "apr_tables.h"
23#include "apr.h"
24#include "apr_hooks.h"
25#include "apr_hash.h"
26#include "apr_optional_hooks.h"
27#include "apr_optional.h"
28#define APR_WANT_MEMFUNC
29#define APR_WANT_STRFUNC
30#include "apr_want.h"
31
32#if 0
33#define apr_palloc(pool,size)	malloc(size)
34#endif
35
36APU_DECLARE_DATA apr_pool_t *apr_hook_global_pool = NULL;
37APU_DECLARE_DATA int apr_hook_debug_enabled = 0;
38APU_DECLARE_DATA const char *apr_hook_debug_current = NULL;
39
40/** @deprecated @see apr_hook_global_pool */
41APU_DECLARE_DATA apr_pool_t *apr_global_hook_pool = NULL;
42
43/** @deprecated @see apr_hook_debug_enabled */
44APU_DECLARE_DATA int apr_debug_module_hooks = 0;
45
46/** @deprecated @see apr_hook_debug_current */
47APU_DECLARE_DATA const char *apr_current_hooking_module = NULL;
48
49/* NB: This must echo the LINK_##name structure */
50typedef struct
51{
52    void (*dummy)(void *);
53    const char *szName;
54    const char * const *aszPredecessors;
55    const char * const *aszSuccessors;
56    int nOrder;
57} TSortData;
58
59typedef struct tsort_
60{
61    void *pData;
62    int nPredecessors;
63    struct tsort_ **ppPredecessors;
64    struct tsort_ *pNext;
65} TSort;
66
67#ifdef NETWARE
68#include "apr_private.h"
69#define get_apd                 APP_DATA* apd = (APP_DATA*)get_app_data(gLibId);
70#define s_aHooksToSort          ((apr_array_header_t *)(apd->gs_aHooksToSort))
71#define s_phOptionalHooks       ((apr_hash_t *)(apd->gs_phOptionalHooks))
72#define s_phOptionalFunctions   ((apr_hash_t *)(apd->gs_phOptionalFunctions))
73#endif
74
75static int crude_order(const void *a_,const void *b_)
76{
77    const TSortData *a=a_;
78    const TSortData *b=b_;
79
80    return a->nOrder-b->nOrder;
81}
82
83static TSort *prepare(apr_pool_t *p,TSortData *pItems,int nItems)
84{
85    TSort *pData=apr_palloc(p,nItems*sizeof *pData);
86    int n;
87
88    qsort(pItems,nItems,sizeof *pItems,crude_order);
89    for(n=0 ; n < nItems ; ++n) {
90	pData[n].nPredecessors=0;
91	pData[n].ppPredecessors=apr_pcalloc(p,nItems*sizeof *pData[n].ppPredecessors);
92	pData[n].pNext=NULL;
93	pData[n].pData=&pItems[n];
94    }
95
96    for(n=0 ; n < nItems ; ++n) {
97	int i,k;
98
99	for(i=0 ; pItems[n].aszPredecessors && pItems[n].aszPredecessors[i] ; ++i)
100	    for(k=0 ; k < nItems ; ++k)
101		if(!strcmp(pItems[k].szName,pItems[n].aszPredecessors[i])) {
102		    int l;
103
104		    for(l=0 ; l < pData[n].nPredecessors ; ++l)
105			if(pData[n].ppPredecessors[l] == &pData[k])
106			    goto got_it;
107		    pData[n].ppPredecessors[pData[n].nPredecessors]=&pData[k];
108		    ++pData[n].nPredecessors;
109		got_it:
110		    break;
111		}
112	for(i=0 ; pItems[n].aszSuccessors && pItems[n].aszSuccessors[i] ; ++i)
113	    for(k=0 ; k < nItems ; ++k)
114		if(!strcmp(pItems[k].szName,pItems[n].aszSuccessors[i])) {
115		    int l;
116
117		    for(l=0 ; l < pData[k].nPredecessors ; ++l)
118			if(pData[k].ppPredecessors[l] == &pData[n])
119			    goto got_it2;
120		    pData[k].ppPredecessors[pData[k].nPredecessors]=&pData[n];
121		    ++pData[k].nPredecessors;
122		got_it2:
123		    break;
124		}
125    }
126
127    return pData;
128}
129
130/* Topologically sort, dragging out-of-order items to the front. Note that
131   this tends to preserve things that want to be near the front better, and
132   changing that behaviour might compromise some of Apache's behaviour (in
133   particular, mod_log_forensic might otherwise get pushed to the end, and
134   core.c's log open function used to end up at the end when pushing items
135   to the back was the methedology). Also note that the algorithm could
136   go back to its original simplicity by sorting from the back instead of
137   the front.
138*/
139static TSort *tsort(TSort *pData,int nItems)
140{
141    int nTotal;
142    TSort *pHead=NULL;
143    TSort *pTail=NULL;
144
145    for(nTotal=0 ; nTotal < nItems ; ++nTotal) {
146	int n,i,k;
147
148	for(n=0 ; ; ++n) {
149	    if(n == nItems)
150		assert(0);      /* we have a loop... */
151	    if(!pData[n].pNext) {
152		if(pData[n].nPredecessors) {
153		    for(k=0 ; ; ++k) {
154			assert(k < nItems);
155			if(pData[n].ppPredecessors[k])
156			    break;
157		    }
158		    for(i=0 ; ; ++i) {
159			assert(i < nItems);
160			if(&pData[i] == pData[n].ppPredecessors[k]) {
161			    n=i-1;
162			    break;
163			}
164		    }
165		} else
166		    break;
167	    }
168	}
169	if(pTail)
170	    pTail->pNext=&pData[n];
171	else
172	    pHead=&pData[n];
173	pTail=&pData[n];
174	pTail->pNext=pTail;     /* fudge it so it looks linked */
175	for(i=0 ; i < nItems ; ++i)
176	    for(k=0 ; k < nItems ; ++k)
177		if(pData[i].ppPredecessors[k] == &pData[n]) {
178		    --pData[i].nPredecessors;
179		    pData[i].ppPredecessors[k]=NULL;
180		    break;
181		}
182    }
183    pTail->pNext=NULL;  /* unfudge the tail */
184    return pHead;
185}
186
187static apr_array_header_t *sort_hook(apr_array_header_t *pHooks,
188				     const char *szName)
189{
190    apr_pool_t *p;
191    TSort *pSort;
192    apr_array_header_t *pNew;
193    int n;
194
195    apr_pool_create(&p, apr_hook_global_pool);
196    pSort=prepare(p,(TSortData *)pHooks->elts,pHooks->nelts);
197    pSort=tsort(pSort,pHooks->nelts);
198    pNew=apr_array_make(apr_hook_global_pool,pHooks->nelts,sizeof(TSortData));
199    if(apr_hook_debug_enabled)
200	printf("Sorting %s:",szName);
201    for(n=0 ; pSort ; pSort=pSort->pNext,++n) {
202	TSortData *pHook;
203	assert(n < pHooks->nelts);
204	pHook=apr_array_push(pNew);
205	memcpy(pHook,pSort->pData,sizeof *pHook);
206	if(apr_hook_debug_enabled)
207	    printf(" %s",pHook->szName);
208    }
209    if(apr_hook_debug_enabled)
210	fputc('\n',stdout);
211    return pNew;
212}
213
214#ifndef NETWARE
215static apr_array_header_t *s_aHooksToSort;
216#endif
217
218typedef struct
219{
220    const char *szHookName;
221    apr_array_header_t **paHooks;
222} HookSortEntry;
223
224APU_DECLARE(void) apr_hook_sort_register(const char *szHookName,
225					apr_array_header_t **paHooks)
226{
227#ifdef NETWARE
228    get_apd
229#endif
230    HookSortEntry *pEntry;
231
232    if(!s_aHooksToSort)
233        s_aHooksToSort=apr_array_make(apr_hook_global_pool,1,sizeof(HookSortEntry));
234    pEntry=apr_array_push(s_aHooksToSort);
235    pEntry->szHookName=szHookName;
236    pEntry->paHooks=paHooks;
237}
238
239APU_DECLARE(void) apr_hook_sort_all(void)
240{
241#ifdef NETWARE
242    get_apd
243#endif
244    int n;
245
246    for(n=0 ; n < s_aHooksToSort->nelts ; ++n) {
247	HookSortEntry *pEntry=&((HookSortEntry *)s_aHooksToSort->elts)[n];
248	*pEntry->paHooks=sort_hook(*pEntry->paHooks,pEntry->szHookName);
249    }
250}
251
252#ifndef NETWARE
253static apr_hash_t *s_phOptionalHooks;
254static apr_hash_t *s_phOptionalFunctions;
255#endif
256
257APU_DECLARE(void) apr_hook_deregister_all(void)
258{
259#ifdef NETWARE
260    get_apd
261#endif
262    int n;
263
264    for(n=0 ; n < s_aHooksToSort->nelts ; ++n) {
265        HookSortEntry *pEntry=&((HookSortEntry *)s_aHooksToSort->elts)[n];
266        *pEntry->paHooks=NULL;
267    }
268    s_aHooksToSort=NULL;
269    s_phOptionalHooks=NULL;
270    s_phOptionalFunctions=NULL;
271}
272
273APU_DECLARE(void) apr_hook_debug_show(const char *szName,
274                                      const char * const *aszPre,
275			              const char * const *aszSucc)
276{
277    int nFirst;
278
279    printf("  Hooked %s",szName);
280    if(aszPre) {
281	fputs(" pre(",stdout);
282	nFirst=1;
283	while(*aszPre) {
284	    if(!nFirst)
285		fputc(',',stdout);
286	    nFirst=0;
287	    fputs(*aszPre,stdout);
288	    ++aszPre;
289	}
290	fputc(')',stdout);
291    }
292    if(aszSucc) {
293	fputs(" succ(",stdout);
294	nFirst=1;
295	while(*aszSucc) {
296	    if(!nFirst)
297		fputc(',',stdout);
298	    nFirst=0;
299	    fputs(*aszSucc,stdout);
300	    ++aszSucc;
301	}
302	fputc(')',stdout);
303    }
304    fputc('\n',stdout);
305}
306
307/* Optional hook support */
308
309APR_DECLARE_EXTERNAL_HOOK(apr,APU,void,_optional,(void))
310
311APU_DECLARE(apr_array_header_t *) apr_optional_hook_get(const char *szName)
312{
313#ifdef NETWARE
314    get_apd
315#endif
316    apr_array_header_t **ppArray;
317
318    if(!s_phOptionalHooks)
319	return NULL;
320    ppArray=apr_hash_get(s_phOptionalHooks,szName,strlen(szName));
321    if(!ppArray)
322	return NULL;
323    return *ppArray;
324}
325
326APU_DECLARE(void) apr_optional_hook_add(const char *szName,void (*pfn)(void),
327					const char * const *aszPre,
328					const char * const *aszSucc,int nOrder)
329{
330#ifdef NETWARE
331    get_apd
332#endif
333    apr_array_header_t *pArray=apr_optional_hook_get(szName);
334    apr_LINK__optional_t *pHook;
335
336    if(!pArray) {
337	apr_array_header_t **ppArray;
338
339	pArray=apr_array_make(apr_hook_global_pool,1,
340			      sizeof(apr_LINK__optional_t));
341	if(!s_phOptionalHooks)
342	    s_phOptionalHooks=apr_hash_make(apr_hook_global_pool);
343	ppArray=apr_palloc(apr_hook_global_pool,sizeof *ppArray);
344	*ppArray=pArray;
345	apr_hash_set(s_phOptionalHooks,szName,strlen(szName),ppArray);
346	apr_hook_sort_register(szName,ppArray);
347    }
348    pHook=apr_array_push(pArray);
349    pHook->pFunc=pfn;
350    pHook->aszPredecessors=aszPre;
351    pHook->aszSuccessors=aszSucc;
352    pHook->nOrder=nOrder;
353    pHook->szName=apr_hook_debug_current;
354    if(apr_hook_debug_enabled)
355	apr_hook_debug_show(szName,aszPre,aszSucc);
356}
357
358/* optional function support */
359
360APU_DECLARE(apr_opt_fn_t *) apr_dynamic_fn_retrieve(const char *szName)
361{
362#ifdef NETWARE
363    get_apd
364#endif
365    if(!s_phOptionalFunctions)
366	return NULL;
367    return (void(*)(void))apr_hash_get(s_phOptionalFunctions,szName,strlen(szName));
368}
369
370/* Deprecated */
371APU_DECLARE_NONSTD(void) apr_dynamic_fn_register(const char *szName,
372                                                  apr_opt_fn_t *pfn)
373{
374#ifdef NETWARE
375    get_apd
376#endif
377    if(!s_phOptionalFunctions)
378	s_phOptionalFunctions=apr_hash_make(apr_hook_global_pool);
379    apr_hash_set(s_phOptionalFunctions,szName,strlen(szName),(void *)pfn);
380}
381
382#if 0
383void main()
384{
385    const char *aszAPre[]={"b","c",NULL};
386    const char *aszBPost[]={"a",NULL};
387    const char *aszCPost[]={"b",NULL};
388    TSortData t1[]=
389    {
390	{ "a",aszAPre,NULL },
391	{ "b",NULL,aszBPost },
392	{ "c",NULL,aszCPost }
393    };
394    TSort *pResult;
395
396    pResult=prepare(t1,3);
397    pResult=tsort(pResult,3);
398
399    for( ; pResult ; pResult=pResult->pNext)
400	printf("%s\n",pResult->pData->szName);
401}
402#endif
403