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