API tools faq
paste
Advertisement
stasn77

weburl kernel patch

stasn77
Feb 14th, 2015
487
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Diff 79.17 KB | None | 0 0
raw download clone embed print report
  1. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  2. +++ b/include/linux/netfilter_ipv4/ipt_weburl.h 2015-01-25 11:36:00.000000000 +0300
  3. @@ -0,0 +1,45 @@
  4. +/*  weburl --  A netfilter module to match URLs in HTTP requests
  5. + *         This module can match using string match or regular expressions
  6. + *         Originally designed for use with Gargoyle router firmware (gargoyle-router.com)
  7. + *
  8. + *
  9. + *  Copyright © 2008 by Eric Bishop <eric@gargoyle-router.com>
  10. + *
  11. + *  This file is free software: you may copy, redistribute and/or modify it
  12. + *  under the terms of the GNU General Public License as published by the
  13. + *  Free Software Foundation, either version 2 of the License, or (at your
  14. + *  option) any later version.
  15. + *
  16. + *  This file is distributed in the hope that it will be useful, but
  17. + *  WITHOUT ANY WARRANTY; without even the implied warranty of
  18. + *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19. + *  General Public License for more details.
  20. + *
  21. + *  You should have received a copy of the GNU General Public License
  22. + *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  23. + */
  24. +
  25. +
  26. +
  27. +
  28. +#ifndef _IPT_WEBURL_H
  29. +#define _IPT_WEBURL_H
  30. +
  31. +
  32. +#define MAX_TEST_STR 1024
  33. +
  34. +#define WEBURL_CONTAINS_TYPE 1
  35. +#define WEBURL_REGEX_TYPE 2
  36. +#define WEBURL_EXACT_TYPE 3
  37. +#define WEBURL_ALL_PART 4
  38. +#define WEBURL_DOMAIN_PART 5
  39. +#define WEBURL_PATH_PART 6
  40. +
  41. +struct ipt_weburl_info
  42. +{
  43. +   char test_str[MAX_TEST_STR];
  44. +   unsigned char match_type;
  45. +   unsigned char match_part;
  46. +   unsigned char invert;
  47. +};
  48. +#endif /*_IPT_WEBURL_H*/
  49. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  50. +++ b/net/ipv4/netfilter/ipt_weburl.c   2015-01-26 07:44:03.260212259 +0300
  51. @@ -0,0 +1,398 @@
  52. +/*  weburl --  A netfilter module to match URLs in HTTP requests
  53. + *         This module can match using string match or regular expressions
  54. + *         Originally designed for use with Gargoyle router firmware (gargoyle-router.com)
  55. + *
  56. + *
  57. + *  Copyright © 2008-2010 by Eric Bishop <eric@gargoyle-router.com>
  58. + *
  59. + *  This file is free software: you may copy, redistribute and/or modify it
  60. + *  under the terms of the GNU General Public License as published by the
  61. + *  Free Software Foundation, either version 2 of the License, or (at your
  62. + *  option) any later version.
  63. + *
  64. + *  This file is distributed in the hope that it will be useful, but
  65. + *  WITHOUT ANY WARRANTY; without even the implied warranty of
  66. + *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  67. + *  General Public License for more details.
  68. + *
  69. + *  You should have received a copy of the GNU General Public License
  70. + *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  71. + */
  72. +
  73. +#include <linux/kernel.h>
  74. +#include <linux/version.h>
  75. +#include <linux/module.h>
  76. +#include <linux/skbuff.h>
  77. +#include <linux/if_ether.h>
  78. +#include <linux/string.h>
  79. +#include <linux/ctype.h>
  80. +#include <net/sock.h>
  81. +#include <net/ip.h>
  82. +#include <net/tcp.h>
  83. +
  84. +#include <linux/netfilter_ipv4/ip_tables.h>
  85. +#include <linux/netfilter_ipv4/ipt_weburl.h>
  86. +
  87. +#include "weburl_deps/regexp.c"
  88. +#include "weburl_deps/tree_map.h"
  89. +
  90. +
  91. +#include <linux/ip.h>
  92. +
  93. +
  94. +#include <linux/netfilter/x_tables.h>
  95. +
  96. +
  97. +
  98. +MODULE_LICENSE("GPL");
  99. +MODULE_AUTHOR("Eric Bishop");
  100. +MODULE_DESCRIPTION("Match URL in HTTP requests, designed for use with Gargoyle web interface (www.gargoyle-router.com)");
  101. +
  102. +string_map* compiled_map = NULL;
  103. +
  104. +int strnicmp(const char * cs,const char * ct,size_t count)
  105. +{
  106. +   register signed char __res = 0;
  107. +
  108. +   while (count)
  109. +   {
  110. +       if ((__res = toupper( *cs ) - toupper( *ct++ ) ) != 0 || !*cs++)
  111. +       {
  112. +           break;
  113. +       }
  114. +       count--;
  115. +   }
  116. +   return __res;
  117. +}
  118. +
  119. +char *strnistr(const char *s, const char *find, size_t slen)
  120. +{
  121. +   char c, sc;
  122. +   size_t len;
  123. +
  124. +
  125. +   if ((c = *find++) != '\0')
  126. +   {
  127. +       len = strlen(find);
  128. +       do
  129. +       {
  130. +           do
  131. +           {
  132. +                   if (slen < 1 || (sc = *s) == '\0')
  133. +               {
  134. +                       return (NULL);
  135. +               }
  136. +                   --slen;
  137. +                   ++s;
  138. +               }
  139. +           while ( toupper(sc) != toupper(c));
  140. +              
  141. +           if (len > slen)
  142. +           {
  143. +                   return (NULL);
  144. +           }
  145. +           }
  146. +       while (strnicmp(s, find, len) != 0);
  147. +          
  148. +       s--;
  149. +       }
  150. +       return ((char *)s);
  151. +}
  152. +
  153. +
  154. +int do_match_test(unsigned char match_type,  const char* reference, char* query)
  155. +{
  156. +   int matches = 0;
  157. +   struct regexp* r;
  158. +   switch(match_type)
  159. +   {
  160. +       case WEBURL_CONTAINS_TYPE:
  161. +           matches = (strstr(query, reference) != NULL);
  162. +           break;
  163. +       case WEBURL_REGEX_TYPE:
  164. +
  165. +           if(compiled_map == NULL)
  166. +           {
  167. +               compiled_map = initialize_map(0);
  168. +               if(compiled_map == NULL) /* test for malloc failure */
  169. +               {
  170. +                   return 0;
  171. +               }
  172. +           }
  173. +           r = (struct regexp*)get_map_element(compiled_map, reference);
  174. +           if(r == NULL)
  175. +           {
  176. +               int rlen = strlen(reference);
  177. +               r= regcomp((char*)reference, &rlen);
  178. +               if(r == NULL) /* test for malloc failure */
  179. +               {
  180. +                   return 0;
  181. +               }
  182. +               set_map_element(compiled_map, reference, (void*)r);
  183. +           }
  184. +           matches = regexec(r, query);
  185. +           break;
  186. +       case WEBURL_EXACT_TYPE:
  187. +           matches = (strstr(query, reference) != NULL) && strlen(query) == strlen(reference);
  188. +           break;
  189. +   }
  190. +   return matches;
  191. +}
  192. +
  193. +int http_match(const struct ipt_weburl_info* info, const unsigned char* packet_data, int packet_length)
  194. +{
  195. +   int test = 0;
  196. +  
  197. +   /* first test if we're dealing with a web page request */
  198. +   if(strnicmp((char*)packet_data, "GET ", 4) == 0 || strnicmp(  (char*)packet_data, "POST ", 5) == 0 || strnicmp((char*)packet_data, "HEAD ", 5) == 0)
  199. +   {
  200. +       /* printk("found a  web page request\n"); */
  201. +       char path[625] = "";
  202. +       char host[625] = "";
  203. +       int path_start_index;
  204. +       int path_end_index;
  205. +       int last_header_index;
  206. +       char last_two_buf[2];
  207. +       int end_found;
  208. +       char* host_match;
  209. +       char* test_prefixes[6];
  210. +       int prefix_index;
  211. +  
  212. +       /* get path portion of URL */
  213. +       path_start_index = (int)(strstr((char*)packet_data, " ") - (char*)packet_data);
  214. +       while( packet_data[path_start_index] == ' ')
  215. +       {
  216. +           path_start_index++;
  217. +       }
  218. +       path_end_index= (int)(strstr( (char*)(packet_data+path_start_index), " ") -  (char*)packet_data);
  219. +       if(path_end_index > 0)
  220. +       {
  221. +           int path_length = path_end_index-path_start_index;
  222. +           path_length = path_length < 625 ? path_length : 624; /* prevent overflow */
  223. +           memcpy(path, packet_data+path_start_index, path_length);
  224. +           path[ path_length] = '\0';
  225. +       }
  226. +      
  227. +       /* get header length */
  228. +       last_header_index = 2;
  229. +       memcpy(last_two_buf,(char*)packet_data, 2);
  230. +       end_found = 0;
  231. +       while(end_found == 0 && last_header_index < packet_length)
  232. +       {
  233. +           char next = (char)packet_data[last_header_index];
  234. +           if(next == '\n')
  235. +           {
  236. +               end_found = last_two_buf[1] == '\n' || (last_two_buf[0] == '\n' && last_two_buf[1] == '\r') ? 1 : 0;
  237. +           }
  238. +           if(end_found == 0)
  239. +           {
  240. +               last_two_buf[0] = last_two_buf[1];
  241. +               last_two_buf[1] = next;
  242. +               last_header_index++;
  243. +           }
  244. +       }
  245. +      
  246. +       /* get host portion of URL */
  247. +       host_match = strnistr( (char*)packet_data, "Host:", last_header_index);
  248. +       if(host_match != NULL)
  249. +       {
  250. +           int host_end_index;
  251. +           host_match = host_match + 5; /* character after "Host:" */
  252. +           while(host_match[0] == ' ')
  253. +           {
  254. +               host_match = host_match+1;
  255. +           }
  256. +          
  257. +           host_end_index = 0;
  258. +           while(  host_match[host_end_index] != '\n' &&
  259. +               host_match[host_end_index] != '\r' &&
  260. +               host_match[host_end_index] != ' ' &&
  261. +               host_match[host_end_index] != ':' &&
  262. +               ((char*)host_match - (char*)packet_data)+host_end_index < last_header_index
  263. +               )
  264. +           {
  265. +               host_end_index++;
  266. +           }
  267. +           memcpy(host, host_match, host_end_index);
  268. +           host_end_index = host_end_index < 625 ? host_end_index : 624; /* prevent overflow */
  269. +           host[host_end_index] = '\0';
  270. +
  271. +          
  272. +       }
  273. +  
  274. +       /* printk("host = \"%s\", path =\"%s\"\n", host, path); */
  275. +      
  276. +
  277. +       switch(info->match_part)
  278. +       {
  279. +           case WEBURL_DOMAIN_PART:
  280. +               test = do_match_test(info->match_type, info->test_str, host);
  281. +               if(!test && strstr(host, "www.") == host)
  282. +               {
  283. +                   test = do_match_test(info->match_type, info->test_str, ((char*)host+4) );  
  284. +               }
  285. +               break;
  286. +           case WEBURL_PATH_PART:
  287. +               test = do_match_test(info->match_type, info->test_str, path);
  288. +               if( !test && path[0] == '/' )
  289. +               {
  290. +                   test = do_match_test(info->match_type, info->test_str, ((char*)path+1) );
  291. +               }
  292. +               break;
  293. +           case WEBURL_ALL_PART:
  294. +              
  295. +               test_prefixes[0] = "http://";
  296. +               test_prefixes[1] = "";
  297. +               test_prefixes[2] = NULL;
  298. +
  299. +              
  300. +               for(prefix_index=0; test_prefixes[prefix_index] != NULL && test == 0; prefix_index++)
  301. +               {
  302. +                   char test_url[1250];
  303. +                   test_url[0] = '\0';
  304. +                   strcat(test_url, test_prefixes[prefix_index]);
  305. +                   strcat(test_url, host);
  306. +                   if(strcmp(path, "/") != 0)
  307. +                   {
  308. +                       strcat(test_url, path);
  309. +                   }
  310. +                   test = do_match_test(info->match_type, info->test_str, test_url);
  311. +                   if(!test && strcmp(path, "/") == 0)
  312. +                   {
  313. +                       strcat(test_url, path);
  314. +                       test = do_match_test(info->match_type, info->test_str, test_url);
  315. +                   }
  316. +                  
  317. +                   /* printk("test_url = \"%s\", test=%d\n", test_url, test); */
  318. +               }
  319. +               if(!test && strstr(host, "www.") == host)
  320. +               {
  321. +                   char* www_host = ((char*)host+4);
  322. +                   for(prefix_index=0; test_prefixes[prefix_index] != NULL && test == 0; prefix_index++)
  323. +                   {
  324. +                       char test_url[1250];
  325. +                       test_url[0] = '\0';
  326. +                       strcat(test_url, test_prefixes[prefix_index]);
  327. +                       strcat(test_url, www_host);
  328. +                       if(strcmp(path, "/") != 0)
  329. +                       {
  330. +                           strcat(test_url, path);
  331. +                       }
  332. +                       test = do_match_test(info->match_type, info->test_str, test_url);
  333. +                       if(!test && strcmp(path, "/") == 0)
  334. +                       {
  335. +                           strcat(test_url, path);
  336. +                           test = do_match_test(info->match_type, info->test_str, test_url);
  337. +                       }
  338. +                  
  339. +                       /* printk("test_url = \"%s\", test=%d\n", test_url, test); */
  340. +                   }
  341. +               }
  342. +               break;
  343. +          
  344. +       }      
  345. +
  346. +
  347. +       /*
  348. +        * If invert flag is set, return true if this IS a web request, but it didn't match
  349. +        * Always return false for non-web requests
  350. +        */
  351. +       test = info->invert ? !test : test;
  352. +   }
  353. +
  354. +   return test;
  355. +}
  356. +
  357. +
  358. +static bool match(const struct sk_buff *skb, struct xt_action_param *par)
  359. +{
  360. +
  361. +   const struct ipt_weburl_info *info = (const struct ipt_weburl_info*)(par->matchinfo);
  362. +
  363. +  
  364. +   int test = 0;
  365. +   struct iphdr* iph; 
  366. +
  367. +   /* linearize skb if necessary */
  368. +   struct sk_buff *linear_skb;
  369. +   int skb_copied;
  370. +   if(skb_is_nonlinear(skb))
  371. +   {
  372. +       linear_skb = skb_copy(skb, GFP_ATOMIC);
  373. +       skb_copied = 1;
  374. +   }
  375. +   else
  376. +   {
  377. +       linear_skb = (struct sk_buff*)skb;
  378. +       skb_copied = 0;
  379. +   }
  380. +
  381. +  
  382. +
  383. +   /* ignore packets that are not TCP */
  384. +   iph = (struct iphdr*)(skb_network_header(linear_skb));
  385. +   if(iph->protocol == IPPROTO_TCP)
  386. +   {
  387. +       /* get payload */
  388. +       struct tcphdr* tcp_hdr      = (struct tcphdr*)( ((unsigned char*)iph) + (iph->ihl*4) );
  389. +       unsigned short payload_offset   = (tcp_hdr->doff*4) + (iph->ihl*4);
  390. +       unsigned char* payload      = ((unsigned char*)iph) + payload_offset;
  391. +       unsigned short payload_length   = ntohs(iph->tot_len) - payload_offset;
  392. +
  393. +  
  394. +
  395. +       /* if payload length <= 10 bytes don't bother doing a check, otherwise check for match */
  396. +       if(payload_length > 10)
  397. +       {
  398. +           test = http_match(info, payload, payload_length);
  399. +       }
  400. +   }
  401. +  
  402. +   /* free skb if we made a copy to linearize it */
  403. +   if(skb_copied == 1)
  404. +   {
  405. +       kfree_skb(linear_skb);
  406. +   }
  407. +
  408. +
  409. +   /* printk("returning %d from weburl\n\n\n", test); */
  410. +   return test;
  411. +}
  412. +
  413. +
  414. +static int checkentry(const struct xt_mtchk_param *par)
  415. +{
  416. +   return 0;
  417. +}
  418. +
  419. +
  420. +static struct xt_match weburl_match  __read_mostly  =
  421. +{
  422. +   .name       = "weburl",
  423. +   .match      = &match,
  424. +   .family     = AF_INET,
  425. +   .matchsize  = sizeof(struct ipt_weburl_info),
  426. +   .checkentry = &checkentry,
  427. +   .me     = THIS_MODULE,
  428. +};
  429. +
  430. +static int __init init(void)
  431. +{
  432. +   compiled_map = NULL;
  433. +   return xt_register_match(&weburl_match);
  434. +
  435. +}
  436. +
  437. +static void __exit fini(void)
  438. +{
  439. +   xt_unregister_match(&weburl_match);
  440. +   if(compiled_map != NULL)
  441. +   {
  442. +       unsigned long num_destroyed;
  443. +       destroy_map(compiled_map, DESTROY_MODE_FREE_VALUES, &num_destroyed);
  444. +   }
  445. +}
  446. +
  447. +module_init(init);
  448. +module_exit(fini);
  449. +
  450. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  451. +++ b/net/ipv4/netfilter/ipt_weburl.mod.c   2015-01-26 07:43:59.997209775 +0300
  452. @@ -0,0 +1,23 @@
  453. +#include <linux/module.h>
  454. +#include <linux/vermagic.h>
  455. +#include <linux/compiler.h>
  456. +
  457. +MODULE_INFO(vermagic, VERMAGIC_STRING);
  458. +
  459. +__visible struct module __this_module
  460. +__attribute__((section(".gnu.linkonce.this_module"))) = {
  461. +   .name = KBUILD_MODNAME,
  462. +   .init = init_module,
  463. +#ifdef CONFIG_MODULE_UNLOAD
  464. +   .exit = cleanup_module,
  465. +#endif
  466. +   .arch = MODULE_ARCH_INIT,
  467. +};
  468. +
  469. +MODULE_INFO(intree, "Y");
  470. +
  471. +static const char __module_depends[]
  472. +__used
  473. +__attribute__((section(".modinfo"))) =
  474. +"depends=";
  475. +
  476. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  477. +++ b/net/ipv4/netfilter/weburl_deps/regexp.c   2015-01-25 11:36:00.000000000 +0300
  478. @@ -0,0 +1,1197 @@
  479. +/*
  480. + * regcomp and regexec -- regsub and regerror are elsewhere
  481. + * @(#)regexp.c    1.3 of 18 April 87
  482. + *
  483. + * Copyright (c) 1986 by University of Toronto.
  484. + * Written by Henry Spencer.  Not derived from licensed software.
  485. + *
  486. + * Permission is granted to anyone to use this software for any
  487. + * purpose on any computer system, and to redistribute it freely,
  488. + * subject to the following restrictions:
  489. + *
  490. + * 1. The author is not responsible for the consequences of use of
  491. + *     this software, no matter how awful, even if they arise
  492. + *     from defects in it.
  493. + *
  494. + * 2. The origin of this software must not be misrepresented, either
  495. + *     by explicit claim or by omission.
  496. + *
  497. + * 3. Altered versions must be plainly marked as such, and must not
  498. + *     be misrepresented as being the original software.
  499. + *
  500. + * Beware that some of this code is subtly aware of the way operator
  501. + * precedence is structured in regular expressions.  Serious changes in
  502. + * regular-expression syntax might require a total rethink.
  503. + *
  504. + * This code was modified by Ethan Sommer to work within the kernel
  505. + * (it now uses kmalloc etc..)
  506. + *
  507. + * Modified slightly by Matthew Strait to use more modern C.
  508. + */
  509. +
  510. +#include "regexp.h"
  511. +#include "regmagic.h"
  512. +
  513. +/* added by ethan and matt.  Lets it work in both kernel and user space.
  514. +(So iptables can use it, for instance.)  Yea, it goes both ways... */
  515. +#if __KERNEL__
  516. +  #define malloc(foo) kmalloc(foo,GFP_ATOMIC)
  517. +#else
  518. +  #define printk(format,args...) printf(format,##args)
  519. +#endif
  520. +
  521. +void regerror(char * s)
  522. +{
  523. +        printk("<3>Regexp: %s\n", s);
  524. +        /* NOTREACHED */
  525. +}
  526. +
  527. +/*
  528. + * The "internal use only" fields in regexp.h are present to pass info from
  529. + * compile to execute that permits the execute phase to run lots faster on
  530. + * simple cases.  They are:
  531. + *
  532. + * regstart    char that must begin a match; '\0' if none obvious
  533. + * reganch is the match anchored (at beginning-of-line only)?
  534. + * regmust string (pointer into program) that match must include, or NULL
  535. + * regmlen length of regmust string
  536. + *
  537. + * Regstart and reganch permit very fast decisions on suitable starting points
  538. + * for a match, cutting down the work a lot.  Regmust permits fast rejection
  539. + * of lines that cannot possibly match.  The regmust tests are costly enough
  540. + * that regcomp() supplies a regmust only if the r.e. contains something
  541. + * potentially expensive (at present, the only such thing detected is * or +
  542. + * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  543. + * supplied because the test in regexec() needs it and regcomp() is computing
  544. + * it anyway.
  545. + */
  546. +
  547. +/*
  548. + * Structure for regexp "program".  This is essentially a linear encoding
  549. + * of a nondeterministic finite-state machine (aka syntax charts or
  550. + * "railroad normal form" in parsing technology).  Each node is an opcode
  551. + * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  552. + * all nodes except BRANCH implement concatenation; a "next" pointer with
  553. + * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  554. + * have one of the subtle syntax dependencies:  an individual BRANCH (as
  555. + * opposed to a collection of them) is never concatenated with anything
  556. + * because of operator precedence.)  The operand of some types of node is
  557. + * a literal string; for others, it is a node leading into a sub-FSM.  In
  558. + * particular, the operand of a BRANCH node is the first node of the branch.
  559. + * (NB this is *not* a tree structure:  the tail of the branch connects
  560. + * to the thing following the set of BRANCHes.)  The opcodes are:
  561. + */
  562. +
  563. +/* definition  number  opnd?   meaning */
  564. +#define    END 0   /* no   End of program. */
  565. +#define    BOL 1   /* no   Match "" at beginning of line. */
  566. +#define    EOL 2   /* no   Match "" at end of line. */
  567. +#define    ANY 3   /* no   Match any one character. */
  568. +#define    ANYOF   4   /* str  Match any character in this string. */
  569. +#define    ANYBUT  5   /* str  Match any character not in this string. */
  570. +#define    BRANCH  6   /* node Match this alternative, or the next... */
  571. +#define    BACK    7   /* no   Match "", "next" ptr points backward. */
  572. +#define    EXACTLY 8   /* str  Match this string. */
  573. +#define    NOTHING 9   /* no   Match empty string. */
  574. +#define    STAR    10  /* node Match this (simple) thing 0 or more times. */
  575. +#define    PLUS    11  /* node Match this (simple) thing 1 or more times. */
  576. +#define    OPEN    20  /* no   Mark this point in input as start of #n. */
  577. +           /*  OPEN+1 is number 1, etc. */
  578. +#define    CLOSE   30  /* no   Analogous to OPEN. */
  579. +
  580. +/*
  581. + * Opcode notes:
  582. + *
  583. + * BRANCH  The set of branches constituting a single choice are hooked
  584. + *     together with their "next" pointers, since precedence prevents
  585. + *     anything being concatenated to any individual branch.  The
  586. + *     "next" pointer of the last BRANCH in a choice points to the
  587. + *     thing following the whole choice.  This is also where the
  588. + *     final "next" pointer of each individual branch points; each
  589. + *     branch starts with the operand node of a BRANCH node.
  590. + *
  591. + * BACK        Normal "next" pointers all implicitly point forward; BACK
  592. + *     exists to make loop structures possible.
  593. + *
  594. + * STAR,PLUS   '?', and complex '*' and '+', are implemented as circular
  595. + *     BRANCH structures using BACK.  Simple cases (one character
  596. + *     per match) are implemented with STAR and PLUS for speed
  597. + *     and to minimize recursive plunges.
  598. + *
  599. + * OPEN,CLOSE  ...are numbered at compile time.
  600. + */
  601. +
  602. +/*
  603. + * A node is one char of opcode followed by two chars of "next" pointer.
  604. + * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  605. + * value is a positive offset from the opcode of the node containing it.
  606. + * An operand, if any, simply follows the node.  (Note that much of the
  607. + * code generation knows about this implicit relationship.)
  608. + *
  609. + * Using two bytes for the "next" pointer is vast overkill for most things,
  610. + * but allows patterns to get big without disasters.
  611. + */
  612. +#define    OP(p)   (*(p))
  613. +#define    NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  614. +#define    OPERAND(p)  ((p) + 3)
  615. +
  616. +/*
  617. + * See regmagic.h for one further detail of program structure.
  618. + */
  619. +
  620. +
  621. +/*
  622. + * Utility definitions.
  623. + */
  624. +#ifndef CHARBITS
  625. +#define    UCHARAT(p)  ((int)*(unsigned char *)(p))
  626. +#else
  627. +#define    UCHARAT(p)  ((int)*(p)&CHARBITS)
  628. +#endif
  629. +
  630. +#define    FAIL(m) { regerror(m); return(NULL); }
  631. +#define    ISMULT(c)   ((c) == '*' || (c) == '+' || (c) == '?')
  632. +#define    META    "^$.[()|?+*\\"
  633. +
  634. +/*
  635. + * Flags to be passed up and down.
  636. + */
  637. +#define    HASWIDTH    01  /* Known never to match null string. */
  638. +#define    SIMPLE      02  /* Simple enough to be STAR/PLUS operand. */
  639. +#define    SPSTART     04  /* Starts with * or +. */
  640. +#define    WORST       0   /* Worst case. */
  641. +
  642. +/*
  643. + * Global work variables for regcomp().
  644. + */
  645. +struct match_globals {
  646. +char *reginput;        /* String-input pointer. */
  647. +char *regbol;      /* Beginning of input, for ^ check. */
  648. +char **regstartp;  /* Pointer to startp array. */
  649. +char **regendp;        /* Ditto for endp. */
  650. +char *regparse;        /* Input-scan pointer. */
  651. +int regnpar;       /* () count. */
  652. +char regdummy;
  653. +char *regcode;     /* Code-emit pointer; &regdummy = don't. */
  654. +long regsize;      /* Code size. */
  655. +};
  656. +
  657. +/*
  658. + * Forward declarations for regcomp()'s friends.
  659. + */
  660. +#ifndef STATIC
  661. +#define    STATIC  static
  662. +#endif
  663. +STATIC char *reg(struct match_globals *g, int paren,int *flagp);
  664. +STATIC char *regbranch(struct match_globals *g, int *flagp);
  665. +STATIC char *regpiece(struct match_globals *g, int *flagp);
  666. +STATIC char *regatom(struct match_globals *g, int *flagp);
  667. +STATIC char *regnode(struct match_globals *g, char op);
  668. +STATIC char *regnext(struct match_globals *g, char *p);
  669. +STATIC void regc(struct match_globals *g, char b);
  670. +STATIC void reginsert(struct match_globals *g, char op, char *opnd);
  671. +STATIC void regtail(struct match_globals *g, char *p, char *val);
  672. +STATIC void regoptail(struct match_globals *g, char *p, char *val);
  673. +
  674. +
  675. +__kernel_size_t my_strcspn(const char *s1,const char *s2)
  676. +{
  677. +        char *scan1;
  678. +        char *scan2;
  679. +        int count;
  680. +
  681. +        count = 0;
  682. +        for (scan1 = (char *)s1; *scan1 != '\0'; scan1++) {
  683. +                for (scan2 = (char *)s2; *scan2 != '\0';)       /* ++ moved down. */
  684. +                        if (*scan1 == *scan2++)
  685. +                                return(count);
  686. +                count++;
  687. +        }
  688. +        return(count);
  689. +}
  690. +
  691. +/*
  692. + - regcomp - compile a regular expression into internal code
  693. + *
  694. + * We can't allocate space until we know how big the compiled form will be,
  695. + * but we can't compile it (and thus know how big it is) until we've got a
  696. + * place to put the code.  So we cheat:  we compile it twice, once with code
  697. + * generation turned off and size counting turned on, and once "for real".
  698. + * This also means that we don't allocate space until we are sure that the
  699. + * thing really will compile successfully, and we never have to move the
  700. + * code and thus invalidate pointers into it.  (Note that it has to be in
  701. + * one piece because free() must be able to free it all.)
  702. + *
  703. + * Beware that the optimization-preparation code in here knows about some
  704. + * of the structure of the compiled regexp.
  705. + */
  706. +regexp *
  707. +regcomp(char *exp,int *patternsize)
  708. +{
  709. +   register regexp *r;
  710. +   register char *scan;
  711. +   register char *longest;
  712. +   register int len;
  713. +   int flags;
  714. +   struct match_globals g;
  715. +
  716. +   /* commented out by ethan
  717. +      extern char *malloc();
  718. +   */
  719. +
  720. +   if (exp == NULL)
  721. +       FAIL("NULL argument");
  722. +
  723. +   /* First pass: determine size, legality. */
  724. +   g.regparse = exp;
  725. +   g.regnpar = 1;
  726. +   g.regsize = 0L;
  727. +   g.regcode = &g.regdummy;
  728. +   regc(&g, MAGIC);
  729. +   if (reg(&g, 0, &flags) == NULL)
  730. +       return(NULL);
  731. +
  732. +   /* Small enough for pointer-storage convention? */
  733. +   if (g.regsize >= 32767L)        /* Probably could be 65535L. */
  734. +       FAIL("regexp too big");
  735. +
  736. +   /* Allocate space. */
  737. +   *patternsize=sizeof(regexp) + (unsigned)g.regsize;
  738. +   r = (regexp *)malloc(sizeof(regexp) + (unsigned)g.regsize);
  739. +   if (r == NULL)
  740. +       FAIL("out of space");
  741. +
  742. +   /* Second pass: emit code. */
  743. +   g.regparse = exp;
  744. +   g.regnpar = 1;
  745. +   g.regcode = r->program;
  746. +   regc(&g, MAGIC);
  747. +   if (reg(&g, 0, &flags) == NULL)
  748. +       return(NULL);
  749. +
  750. +   /* Dig out information for optimizations. */
  751. +   r->regstart = '\0'; /* Worst-case defaults. */
  752. +   r->reganch = 0;
  753. +   r->regmust = NULL;
  754. +   r->regmlen = 0;
  755. +   scan = r->program+1;            /* First BRANCH. */
  756. +   if (OP(regnext(&g, scan)) == END) {     /* Only one top-level choice. */
  757. +       scan = OPERAND(scan);
  758. +
  759. +       /* Starting-point info. */
  760. +       if (OP(scan) == EXACTLY)
  761. +           r->regstart = *OPERAND(scan);
  762. +       else if (OP(scan) == BOL)
  763. +           r->reganch++;
  764. +
  765. +       /*
  766. +        * If there's something expensive in the r.e., find the
  767. +        * longest literal string that must appear and make it the
  768. +        * regmust.  Resolve ties in favor of later strings, since
  769. +        * the regstart check works with the beginning of the r.e.
  770. +        * and avoiding duplication strengthens checking.  Not a
  771. +        * strong reason, but sufficient in the absence of others.
  772. +        */
  773. +       if (flags&SPSTART) {
  774. +           longest = NULL;
  775. +           len = 0;
  776. +           for (; scan != NULL; scan = regnext(&g, scan))
  777. +               if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  778. +                   longest = OPERAND(scan);
  779. +                   len = strlen(OPERAND(scan));
  780. +               }
  781. +           r->regmust = longest;
  782. +           r->regmlen = len;
  783. +       }
  784. +   }
  785. +
  786. +   return(r);
  787. +}
  788. +
  789. +/*
  790. + - reg - regular expression, i.e. main body or parenthesized thing
  791. + *
  792. + * Caller must absorb opening parenthesis.
  793. + *
  794. + * Combining parenthesis handling with the base level of regular expression
  795. + * is a trifle forced, but the need to tie the tails of the branches to what
  796. + * follows makes it hard to avoid.
  797. + */
  798. +static char *
  799. +reg(struct match_globals *g, int paren, int *flagp /* Parenthesized? */ )
  800. +{
  801. +   register char *ret;
  802. +   register char *br;
  803. +   register char *ender;
  804. +   register int parno = 0; /* 0 makes gcc happy */
  805. +   int flags;
  806. +
  807. +   *flagp = HASWIDTH;  /* Tentatively. */
  808. +
  809. +   /* Make an OPEN node, if parenthesized. */
  810. +   if (paren) {
  811. +       if (g->regnpar >= NSUBEXP)
  812. +           FAIL("too many ()");
  813. +       parno = g->regnpar;
  814. +       g->regnpar++;
  815. +       ret = regnode(g, OPEN+parno);
  816. +   } else
  817. +       ret = NULL;
  818. +
  819. +   /* Pick up the branches, linking them together. */
  820. +   br = regbranch(g, &flags);
  821. +   if (br == NULL)
  822. +       return(NULL);
  823. +   if (ret != NULL)
  824. +       regtail(g, ret, br);    /* OPEN -> first. */
  825. +   else
  826. +       ret = br;
  827. +   if (!(flags&HASWIDTH))
  828. +       *flagp &= ~HASWIDTH;
  829. +   *flagp |= flags&SPSTART;
  830. +   while (*g->regparse == '|') {
  831. +       g->regparse++;
  832. +       br = regbranch(g, &flags);
  833. +       if (br == NULL)
  834. +           return(NULL);
  835. +       regtail(g, ret, br);    /* BRANCH -> BRANCH. */
  836. +       if (!(flags&HASWIDTH))
  837. +           *flagp &= ~HASWIDTH;
  838. +       *flagp |= flags&SPSTART;
  839. +   }
  840. +
  841. +   /* Make a closing node, and hook it on the end. */
  842. +   ender = regnode(g, (paren) ? CLOSE+parno : END);
  843. +   regtail(g, ret, ender);
  844. +
  845. +   /* Hook the tails of the branches to the closing node. */
  846. +   for (br = ret; br != NULL; br = regnext(g, br))
  847. +       regoptail(g, br, ender);
  848. +
  849. +   /* Check for proper termination. */
  850. +   if (paren && *g->regparse++ != ')') {
  851. +       FAIL("unmatched ()");
  852. +   } else if (!paren && *g->regparse != '\0') {
  853. +       if (*g->regparse == ')') {
  854. +           FAIL("unmatched ()");
  855. +       } else
  856. +           FAIL("junk on end");    /* "Can't happen". */
  857. +       /* NOTREACHED */
  858. +   }
  859. +
  860. +   return(ret);
  861. +}
  862. +
  863. +/*
  864. + - regbranch - one alternative of an | operator
  865. + *
  866. + * Implements the concatenation operator.
  867. + */
  868. +static char *
  869. +regbranch(struct match_globals *g, int *flagp)
  870. +{
  871. +   register char *ret;
  872. +   register char *chain;
  873. +   register char *latest;
  874. +   int flags;
  875. +
  876. +   *flagp = WORST;     /* Tentatively. */
  877. +
  878. +   ret = regnode(g, BRANCH);
  879. +   chain = NULL;
  880. +   while (*g->regparse != '\0' && *g->regparse != '|' && *g->regparse != ')') {
  881. +       latest = regpiece(g, &flags);
  882. +       if (latest == NULL)
  883. +           return(NULL);
  884. +       *flagp |= flags&HASWIDTH;
  885. +       if (chain == NULL)  /* First piece. */
  886. +           *flagp |= flags&SPSTART;
  887. +       else
  888. +           regtail(g, chain, latest);
  889. +       chain = latest;
  890. +   }
  891. +   if (chain == NULL)  /* Loop ran zero times. */
  892. +       (void) regnode(g, NOTHING);
  893. +
  894. +   return(ret);
  895. +}
  896. +
  897. +/*
  898. + - regpiece - something followed by possible [*+?]
  899. + *
  900. + * Note that the branching code sequences used for ? and the general cases
  901. + * of * and + are somewhat optimized:  they use the same NOTHING node as
  902. + * both the endmarker for their branch list and the body of the last branch.
  903. + * It might seem that this node could be dispensed with entirely, but the
  904. + * endmarker role is not redundant.
  905. + */
  906. +static char *
  907. +regpiece(struct match_globals *g, int *flagp)
  908. +{
  909. +   register char *ret;
  910. +   register char op;
  911. +   register char *next;
  912. +   int flags;
  913. +
  914. +   ret = regatom(g, &flags);
  915. +   if (ret == NULL)
  916. +       return(NULL);
  917. +
  918. +   op = *g->regparse;
  919. +   if (!ISMULT(op)) {
  920. +       *flagp = flags;
  921. +       return(ret);
  922. +   }
  923. +
  924. +   if (!(flags&HASWIDTH) && op != '?')
  925. +       FAIL("*+ operand could be empty");
  926. +   *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  927. +
  928. +   if (op == '*' && (flags&SIMPLE))
  929. +       reginsert(g, STAR, ret);
  930. +   else if (op == '*') {
  931. +       /* Emit x* as (x&|), where & means "self". */
  932. +       reginsert(g, BRANCH, ret);          /* Either x */
  933. +       regoptail(g, ret, regnode(g, BACK));        /* and loop */
  934. +       regoptail(g, ret, ret);         /* back */
  935. +       regtail(g, ret, regnode(g, BRANCH));        /* or */
  936. +       regtail(g, ret, regnode(g, NOTHING));       /* null. */
  937. +   } else if (op == '+' && (flags&SIMPLE))
  938. +       reginsert(g, PLUS, ret);
  939. +   else if (op == '+') {
  940. +       /* Emit x+ as x(&|), where & means "self". */
  941. +       next = regnode(g, BRANCH);          /* Either */
  942. +       regtail(g, ret, next);
  943. +       regtail(g, regnode(g, BACK), ret);      /* loop back */
  944. +       regtail(g, next, regnode(g, BRANCH));       /* or */
  945. +       regtail(g, ret, regnode(g, NOTHING));       /* null. */
  946. +   } else if (op == '?') {
  947. +       /* Emit x? as (x|) */
  948. +       reginsert(g, BRANCH, ret);          /* Either x */
  949. +       regtail(g, ret, regnode(g, BRANCH));        /* or */
  950. +       next = regnode(g, NOTHING);     /* null. */
  951. +       regtail(g, ret, next);
  952. +       regoptail(g, ret, next);
  953. +   }
  954. +   g->regparse++;
  955. +   if (ISMULT(*g->regparse))
  956. +       FAIL("nested *?+");
  957. +
  958. +   return(ret);
  959. +}
  960. +
  961. +/*
  962. + - regatom - the lowest level
  963. + *
  964. + * Optimization:  gobbles an entire sequence of ordinary characters so that
  965. + * it can turn them into a single node, which is smaller to store and
  966. + * faster to run.  Backslashed characters are exceptions, each becoming a
  967. + * separate node; the code is simpler that way and it's not worth fixing.
  968. + */
  969. +static char *
  970. +regatom(struct match_globals *g, int *flagp)
  971. +{
  972. +   register char *ret;
  973. +   int flags;
  974. +
  975. +   *flagp = WORST;     /* Tentatively. */
  976. +
  977. +   switch (*g->regparse++) {
  978. +   case '^':
  979. +       ret = regnode(g, BOL);
  980. +       break;
  981. +   case '$':
  982. +       ret = regnode(g, EOL);
  983. +       break;
  984. +   case '.':
  985. +       ret = regnode(g, ANY);
  986. +       *flagp |= HASWIDTH|SIMPLE;
  987. +       break;
  988. +   case '[': {
  989. +           register int class;
  990. +           register int classend;
  991. +
  992. +           if (*g->regparse == '^') {  /* Complement of range. */
  993. +               ret = regnode(g, ANYBUT);
  994. +               g->regparse++;
  995. +           } else
  996. +               ret = regnode(g, ANYOF);
  997. +           if (*g->regparse == ']' || *g->regparse == '-')
  998. +               regc(g, *g->regparse++);
  999. +           while (*g->regparse != '\0' && *g->regparse != ']') {
  1000. +               if (*g->regparse == '-') {
  1001. +                   g->regparse++;
  1002. +                   if (*g->regparse == ']' || *g->regparse == '\0')
  1003. +                       regc(g, '-');
  1004. +                   else {
  1005. +                       class = UCHARAT(g->regparse-2)+1;
  1006. +                       classend = UCHARAT(g->regparse);
  1007. +                       if (class > classend+1)
  1008. +                           FAIL("invalid [] range");
  1009. +                       for (; class <= classend; class++)
  1010. +                           regc(g, class);
  1011. +                       g->regparse++;
  1012. +                   }
  1013. +               } else
  1014. +                   regc(g, *g->regparse++);
  1015. +           }
  1016. +           regc(g, '\0');
  1017. +           if (*g->regparse != ']')
  1018. +               FAIL("unmatched []");
  1019. +           g->regparse++;
  1020. +           *flagp |= HASWIDTH|SIMPLE;
  1021. +       }
  1022. +       break;
  1023. +   case '(':
  1024. +       ret = reg(g, 1, &flags);
  1025. +       if (ret == NULL)
  1026. +           return(NULL);
  1027. +       *flagp |= flags&(HASWIDTH|SPSTART);
  1028. +       break;
  1029. +   case '\0':
  1030. +   case '|':
  1031. +   case ')':
  1032. +       FAIL("internal urp");   /* Supposed to be caught earlier. */
  1033. +       break;
  1034. +   case '?':
  1035. +   case '+':
  1036. +   case '*':
  1037. +       FAIL("?+* follows nothing");
  1038. +       break;
  1039. +   case '\\':
  1040. +       if (*g->regparse == '\0')
  1041. +           FAIL("trailing \\");
  1042. +       ret = regnode(g, EXACTLY);
  1043. +       regc(g, *g->regparse++);
  1044. +       regc(g, '\0');
  1045. +       *flagp |= HASWIDTH|SIMPLE;
  1046. +       break;
  1047. +   default: {
  1048. +           register int len;
  1049. +           register char ender;
  1050. +
  1051. +           g->regparse--;
  1052. +           len = my_strcspn((const char *)g->regparse, (const char *)META);
  1053. +           if (len <= 0)
  1054. +               FAIL("internal disaster");
  1055. +           ender = *(g->regparse+len);
  1056. +           if (len > 1 && ISMULT(ender))
  1057. +               len--;      /* Back off clear of ?+* operand. */
  1058. +           *flagp |= HASWIDTH;
  1059. +           if (len == 1)
  1060. +               *flagp |= SIMPLE;
  1061. +           ret = regnode(g, EXACTLY);
  1062. +           while (len > 0) {
  1063. +               regc(g, *g->regparse++);
  1064. +               len--;
  1065. +           }
  1066. +           regc(g, '\0');
  1067. +       }
  1068. +       break;
  1069. +   }
  1070. +
  1071. +   return(ret);
  1072. +}
  1073. +
  1074. +/*
  1075. + - regnode - emit a node
  1076. + */
  1077. +static char *          /* Location. */
  1078. +regnode(struct match_globals *g, char op)
  1079. +{
  1080. +   register char *ret;
  1081. +   register char *ptr;
  1082. +
  1083. +   ret = g->regcode;
  1084. +   if (ret == &g->regdummy) {
  1085. +       g->regsize += 3;
  1086. +       return(ret);
  1087. +   }
  1088. +
  1089. +   ptr = ret;
  1090. +   *ptr++ = op;
  1091. +   *ptr++ = '\0';      /* Null "next" pointer. */
  1092. +   *ptr++ = '\0';
  1093. +   g->regcode = ptr;
  1094. +
  1095. +   return(ret);
  1096. +}
  1097. +
  1098. +/*
  1099. + - regc - emit (if appropriate) a byte of code
  1100. + */
  1101. +static void
  1102. +regc(struct match_globals *g, char b)
  1103. +{
  1104. +   if (g->regcode != &g->regdummy)
  1105. +       *g->regcode++ = b;
  1106. +   else
  1107. +       g->regsize++;
  1108. +}
  1109. +
  1110. +/*
  1111. + - reginsert - insert an operator in front of already-emitted operand
  1112. + *
  1113. + * Means relocating the operand.
  1114. + */
  1115. +static void
  1116. +reginsert(struct match_globals *g, char op, char* opnd)
  1117. +{
  1118. +   register char *src;
  1119. +   register char *dst;
  1120. +   register char *place;
  1121. +
  1122. +   if (g->regcode == &g->regdummy) {
  1123. +       g->regsize += 3;
  1124. +       return;
  1125. +   }
  1126. +
  1127. +   src = g->regcode;
  1128. +   g->regcode += 3;
  1129. +   dst = g->regcode;
  1130. +   while (src > opnd)
  1131. +       *--dst = *--src;
  1132. +
  1133. +   place = opnd;       /* Op node, where operand used to be. */
  1134. +   *place++ = op;
  1135. +   *place++ = '\0';
  1136. +   *place++ = '\0';
  1137. +}
  1138. +
  1139. +/*
  1140. + - regtail - set the next-pointer at the end of a node chain
  1141. + */
  1142. +static void
  1143. +regtail(struct match_globals *g, char *p, char *val)
  1144. +{
  1145. +   register char *scan;
  1146. +   register char *temp;
  1147. +   register int offset;
  1148. +
  1149. +   if (p == &g->regdummy)
  1150. +       return;
  1151. +
  1152. +   /* Find last node. */
  1153. +   scan = p;
  1154. +   for (;;) {
  1155. +       temp = regnext(g, scan);
  1156. +       if (temp == NULL)
  1157. +           break;
  1158. +       scan = temp;
  1159. +   }
  1160. +
  1161. +   if (OP(scan) == BACK)
  1162. +       offset = scan - val;
  1163. +   else
  1164. +       offset = val - scan;
  1165. +   *(scan+1) = (offset>>8)&0377;
  1166. +   *(scan+2) = offset&0377;
  1167. +}
  1168. +
  1169. +/*
  1170. + - regoptail - regtail on operand of first argument; nop if operandless
  1171. + */
  1172. +static void
  1173. +regoptail(struct match_globals *g, char *p, char *val)
  1174. +{
  1175. +   /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  1176. +   if (p == NULL || p == &g->regdummy || OP(p) != BRANCH)
  1177. +       return;
  1178. +   regtail(g, OPERAND(p), val);
  1179. +}
  1180. +
  1181. +/*
  1182. + * regexec and friends
  1183. + */
  1184. +
  1185. +
  1186. +/*
  1187. + * Forwards.
  1188. + */
  1189. +STATIC int regtry(struct match_globals *g, regexp *prog, char *string);
  1190. +STATIC int regmatch(struct match_globals *g, char *prog);
  1191. +STATIC int regrepeat(struct match_globals *g, char *p);
  1192. +
  1193. +#ifdef DEBUG
  1194. +int regnarrate = 0;
  1195. +void regdump();
  1196. +STATIC char *regprop(char *op);
  1197. +#endif
  1198. +
  1199. +/*
  1200. + - regexec - match a regexp against a string
  1201. + */
  1202. +int
  1203. +regexec(regexp *prog, char *string)
  1204. +{
  1205. +   register char *s;
  1206. +   struct match_globals g;
  1207. +
  1208. +   /* Be paranoid... */
  1209. +   if (prog == NULL || string == NULL) {
  1210. +       printk("<3>Regexp: NULL parameter\n");
  1211. +       return(0);
  1212. +   }
  1213. +
  1214. +   /* Check validity of program. */
  1215. +   if (UCHARAT(prog->program) != MAGIC) {
  1216. +       printk("<3>Regexp: corrupted program\n");
  1217. +       return(0);
  1218. +   }
  1219. +
  1220. +   /* If there is a "must appear" string, look for it. */
  1221. +   if (prog->regmust != NULL) {
  1222. +       s = string;
  1223. +       while ((s = strchr(s, prog->regmust[0])) != NULL) {
  1224. +           if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  1225. +               break;  /* Found it. */
  1226. +           s++;
  1227. +       }
  1228. +       if (s == NULL)  /* Not present. */
  1229. +           return(0);
  1230. +   }
  1231. +
  1232. +   /* Mark beginning of line for ^ . */
  1233. +   g.regbol = string;
  1234. +
  1235. +   /* Simplest case:  anchored match need be tried only once. */
  1236. +   if (prog->reganch)
  1237. +       return(regtry(&g, prog, string));
  1238. +
  1239. +   /* Messy cases:  unanchored match. */
  1240. +   s = string;
  1241. +   if (prog->regstart != '\0')
  1242. +       /* We know what char it must start with. */
  1243. +       while ((s = strchr(s, prog->regstart)) != NULL) {
  1244. +           if (regtry(&g, prog, s))
  1245. +               return(1);
  1246. +           s++;
  1247. +       }
  1248. +   else
  1249. +       /* We don't -- general case. */
  1250. +       do {
  1251. +           if (regtry(&g, prog, s))
  1252. +               return(1);
  1253. +       } while (*s++ != '\0');
  1254. +
  1255. +   /* Failure. */
  1256. +   return(0);
  1257. +}
  1258. +
  1259. +/*
  1260. + - regtry - try match at specific point
  1261. + */
  1262. +static int         /* 0 failure, 1 success */
  1263. +regtry(struct match_globals *g, regexp *prog, char *string)
  1264. +{
  1265. +   register int i;
  1266. +   register char **sp;
  1267. +   register char **ep;
  1268. +
  1269. +   g->reginput = string;
  1270. +   g->regstartp = prog->startp;
  1271. +   g->regendp = prog->endp;
  1272. +
  1273. +   sp = prog->startp;
  1274. +   ep = prog->endp;
  1275. +   for (i = NSUBEXP; i > 0; i--) {
  1276. +       *sp++ = NULL;
  1277. +       *ep++ = NULL;
  1278. +   }
  1279. +   if (regmatch(g, prog->program + 1)) {
  1280. +       prog->startp[0] = string;
  1281. +       prog->endp[0] = g->reginput;
  1282. +       return(1);
  1283. +   } else
  1284. +       return(0);
  1285. +}
  1286. +
  1287. +/*
  1288. + - regmatch - main matching routine
  1289. + *
  1290. + * Conceptually the strategy is simple:  check to see whether the current
  1291. + * node matches, call self recursively to see whether the rest matches,
  1292. + * and then act accordingly.  In practice we make some effort to avoid
  1293. + * recursion, in particular by going through "ordinary" nodes (that don't
  1294. + * need to know whether the rest of the match failed) by a loop instead of
  1295. + * by recursion.
  1296. + */
  1297. +static int         /* 0 failure, 1 success */
  1298. +regmatch(struct match_globals *g, char *prog)
  1299. +{
  1300. +   register char *scan = prog; /* Current node. */
  1301. +   char *next;         /* Next node. */
  1302. +
  1303. +#ifdef DEBUG
  1304. +   if (scan != NULL && regnarrate)
  1305. +       fprintf(stderr, "%s(\n", regprop(scan));
  1306. +#endif
  1307. +   while (scan != NULL) {
  1308. +#ifdef DEBUG
  1309. +       if (regnarrate)
  1310. +           fprintf(stderr, "%s...\n", regprop(scan));
  1311. +#endif
  1312. +       next = regnext(g, scan);
  1313. +
  1314. +       switch (OP(scan)) {
  1315. +       case BOL:
  1316. +           if (g->reginput != g->regbol)
  1317. +               return(0);
  1318. +           break;
  1319. +       case EOL:
  1320. +           if (*g->reginput != '\0')
  1321. +               return(0);
  1322. +           break;
  1323. +       case ANY:
  1324. +           if (*g->reginput == '\0')
  1325. +               return(0);
  1326. +           g->reginput++;
  1327. +           break;
  1328. +       case EXACTLY: {
  1329. +               register int len;
  1330. +               register char *opnd;
  1331. +
  1332. +               opnd = OPERAND(scan);
  1333. +               /* Inline the first character, for speed. */
  1334. +               if (*opnd != *g->reginput)
  1335. +                   return(0);
  1336. +               len = strlen(opnd);
  1337. +               if (len > 1 && strncmp(opnd, g->reginput, len) != 0)
  1338. +                   return(0);
  1339. +               g->reginput += len;
  1340. +           }
  1341. +           break;
  1342. +       case ANYOF:
  1343. +           if (*g->reginput == '\0' || strchr(OPERAND(scan), *g->reginput) == NULL)
  1344. +               return(0);
  1345. +           g->reginput++;
  1346. +           break;
  1347. +       case ANYBUT:
  1348. +           if (*g->reginput == '\0' || strchr(OPERAND(scan), *g->reginput) != NULL)
  1349. +               return(0);
  1350. +           g->reginput++;
  1351. +           break;
  1352. +       case NOTHING:
  1353. +       case BACK:
  1354. +           break;
  1355. +       case OPEN+1:
  1356. +       case OPEN+2:
  1357. +       case OPEN+3:
  1358. +       case OPEN+4:
  1359. +       case OPEN+5:
  1360. +       case OPEN+6:
  1361. +       case OPEN+7:
  1362. +       case OPEN+8:
  1363. +       case OPEN+9: {
  1364. +               register int no;
  1365. +               register char *save;
  1366. +
  1367. +               no = OP(scan) - OPEN;
  1368. +               save = g->reginput;
  1369. +
  1370. +               if (regmatch(g, next)) {
  1371. +                   /*
  1372. +                    * Don't set startp if some later
  1373. +                    * invocation of the same parentheses
  1374. +                    * already has.
  1375. +                    */
  1376. +                   if (g->regstartp[no] == NULL)
  1377. +                       g->regstartp[no] = save;
  1378. +                   return(1);
  1379. +               } else
  1380. +                   return(0);
  1381. +           }
  1382. +           break;
  1383. +       case CLOSE+1:
  1384. +       case CLOSE+2:
  1385. +       case CLOSE+3:
  1386. +       case CLOSE+4:
  1387. +       case CLOSE+5:
  1388. +       case CLOSE+6:
  1389. +       case CLOSE+7:
  1390. +       case CLOSE+8:
  1391. +       case CLOSE+9:
  1392. +           {
  1393. +               register int no;
  1394. +               register char *save;
  1395. +
  1396. +               no = OP(scan) - CLOSE;
  1397. +               save = g->reginput;
  1398. +
  1399. +               if (regmatch(g, next)) {
  1400. +                   /*
  1401. +                    * Don't set endp if some later
  1402. +                    * invocation of the same parentheses
  1403. +                    * already has.
  1404. +                    */
  1405. +                   if (g->regendp[no] == NULL)
  1406. +                       g->regendp[no] = save;
  1407. +                   return(1);
  1408. +               } else
  1409. +                   return(0);
  1410. +           }
  1411. +           break;
  1412. +       case BRANCH: {
  1413. +               register char *save;
  1414. +
  1415. +               if (OP(next) != BRANCH)     /* No choice. */
  1416. +                   next = OPERAND(scan);   /* Avoid recursion. */
  1417. +               else {
  1418. +                   do {
  1419. +                       save = g->reginput;
  1420. +                       if (regmatch(g, OPERAND(scan)))
  1421. +                           return(1);
  1422. +                       g->reginput = save;
  1423. +                       scan = regnext(g, scan);
  1424. +                   } while (scan != NULL && OP(scan) == BRANCH);
  1425. +                   return(0);
  1426. +                   /* NOTREACHED */
  1427. +               }
  1428. +           }
  1429. +           break;
  1430. +       case STAR:
  1431. +       case PLUS: {
  1432. +               register char nextch;
  1433. +               register int no;
  1434. +               register char *save;
  1435. +               register int min;
  1436. +
  1437. +               /*
  1438. +                * Lookahead to avoid useless match attempts
  1439. +                * when we know what character comes next.
  1440. +                */
  1441. +               nextch = '\0';
  1442. +               if (OP(next) == EXACTLY)
  1443. +                   nextch = *OPERAND(next);
  1444. +               min = (OP(scan) == STAR) ? 0 : 1;
  1445. +               save = g->reginput;
  1446. +               no = regrepeat(g, OPERAND(scan));
  1447. +               while (no >= min) {
  1448. +                   /* If it could work, try it. */
  1449. +                   if (nextch == '\0' || *g->reginput == nextch)
  1450. +                       if (regmatch(g, next))
  1451. +                           return(1);
  1452. +                   /* Couldn't or didn't -- back up. */
  1453. +                   no--;
  1454. +                   g->reginput = save + no;
  1455. +               }
  1456. +               return(0);
  1457. +           }
  1458. +           break;
  1459. +       case END:
  1460. +           return(1);  /* Success! */
  1461. +           break;
  1462. +       default:
  1463. +           printk("<3>Regexp: memory corruption\n");
  1464. +           return(0);
  1465. +           break;
  1466. +       }
  1467. +
  1468. +       scan = next;
  1469. +   }
  1470. +
  1471. +   /*
  1472. +    * We get here only if there's trouble -- normally "case END" is
  1473. +    * the terminating point.
  1474. +    */
  1475. +   printk("<3>Regexp: corrupted pointers\n");
  1476. +   return(0);
  1477. +}
  1478. +
  1479. +/*
  1480. + - regrepeat - repeatedly match something simple, report how many
  1481. + */
  1482. +static int
  1483. +regrepeat(struct match_globals *g, char *p)
  1484. +{
  1485. +   register int count = 0;
  1486. +   register char *scan;
  1487. +   register char *opnd;
  1488. +
  1489. +   scan = g->reginput;
  1490. +   opnd = OPERAND(p);
  1491. +   switch (OP(p)) {
  1492. +   case ANY:
  1493. +       count = strlen(scan);
  1494. +       scan += count;
  1495. +       break;
  1496. +   case EXACTLY:
  1497. +       while (*opnd == *scan) {
  1498. +           count++;
  1499. +           scan++;
  1500. +       }
  1501. +       break;
  1502. +   case ANYOF:
  1503. +       while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1504. +           count++;
  1505. +           scan++;
  1506. +       }
  1507. +       break;
  1508. +   case ANYBUT:
  1509. +       while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1510. +           count++;
  1511. +           scan++;
  1512. +       }
  1513. +       break;
  1514. +   default:        /* Oh dear.  Called inappropriately. */
  1515. +       printk("<3>Regexp: internal foulup\n");
  1516. +       count = 0;  /* Best compromise. */
  1517. +       break;
  1518. +   }
  1519. +   g->reginput = scan;
  1520. +
  1521. +   return(count);
  1522. +}
  1523. +
  1524. +/*
  1525. + - regnext - dig the "next" pointer out of a node
  1526. + */
  1527. +static char*
  1528. +regnext(struct match_globals *g, char *p)
  1529. +{
  1530. +   register int offset;
  1531. +
  1532. +   if (p == &g->regdummy)
  1533. +       return(NULL);
  1534. +
  1535. +   offset = NEXT(p);
  1536. +   if (offset == 0)
  1537. +       return(NULL);
  1538. +
  1539. +   if (OP(p) == BACK)
  1540. +       return(p-offset);
  1541. +   else
  1542. +       return(p+offset);
  1543. +}
  1544. +
  1545. +#ifdef DEBUG
  1546. +
  1547. +STATIC char *regprop();
  1548. +
  1549. +/*
  1550. + - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1551. + */
  1552. +void
  1553. +regdump(regexp *r)
  1554. +{
  1555. +   register char *s;
  1556. +   register char op = EXACTLY; /* Arbitrary non-END op. */
  1557. +   register char *next;
  1558. +   /* extern char *strchr(); */
  1559. +
  1560. +
  1561. +   s = r->program + 1;
  1562. +   while (op != END) { /* While that wasn't END last time... */
  1563. +       op = OP(s);
  1564. +       printf("%2d%s", s-r->program, regprop(s));  /* Where, what. */
  1565. +       next = regnext(s);
  1566. +       if (next == NULL)       /* Next ptr. */
  1567. +           printf("(0)");
  1568. +       else
  1569. +           printf("(%d)", (s-r->program)+(next-s));
  1570. +       s += 3;
  1571. +       if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1572. +           /* Literal string, where present. */
  1573. +           while (*s != '\0') {
  1574. +               putchar(*s);
  1575. +               s++;
  1576. +           }
  1577. +           s++;
  1578. +       }
  1579. +       putchar('\n');
  1580. +   }
  1581. +
  1582. +   /* Header fields of interest. */
  1583. +   if (r->regstart != '\0')
  1584. +       printf("start `%c' ", r->regstart);
  1585. +   if (r->reganch)
  1586. +       printf("anchored ");
  1587. +   if (r->regmust != NULL)
  1588. +       printf("must have \"%s\"", r->regmust);
  1589. +   printf("\n");
  1590. +}
  1591. +
  1592. +/*
  1593. + - regprop - printable representation of opcode
  1594. + */
  1595. +static char *
  1596. +regprop(char *op)
  1597. +{
  1598. +#define BUFLEN 50
  1599. +   register char *p;
  1600. +   static char buf[BUFLEN];
  1601. +
  1602. +   strcpy(buf, ":");
  1603. +
  1604. +   switch (OP(op)) {
  1605. +   case BOL:
  1606. +       p = "BOL";
  1607. +       break;
  1608. +   case EOL:
  1609. +       p = "EOL";
  1610. +       break;
  1611. +   case ANY:
  1612. +       p = "ANY";
  1613. +       break;
  1614. +   case ANYOF:
  1615. +       p = "ANYOF";
  1616. +       break;
  1617. +   case ANYBUT:
  1618. +       p = "ANYBUT";
  1619. +       break;
  1620. +   case BRANCH:
  1621. +       p = "BRANCH";
  1622. +       break;
  1623. +   case EXACTLY:
  1624. +       p = "EXACTLY";
  1625. +       break;
  1626. +   case NOTHING:
  1627. +       p = "NOTHING";
  1628. +       break;
  1629. +   case BACK:
  1630. +       p = "BACK";
  1631. +       break;
  1632. +   case END:
  1633. +       p = "END";
  1634. +       break;
  1635. +   case OPEN+1:
  1636. +   case OPEN+2:
  1637. +   case OPEN+3:
  1638. +   case OPEN+4:
  1639. +   case OPEN+5:
  1640. +   case OPEN+6:
  1641. +   case OPEN+7:
  1642. +   case OPEN+8:
  1643. +   case OPEN+9:
  1644. +       snprintf(buf+strlen(buf),BUFLEN-strlen(buf), "OPEN%d", OP(op)-OPEN);
  1645. +       p = NULL;
  1646. +       break;
  1647. +   case CLOSE+1:
  1648. +   case CLOSE+2:
  1649. +   case CLOSE+3:
  1650. +   case CLOSE+4:
  1651. +   case CLOSE+5:
  1652. +   case CLOSE+6:
  1653. +   case CLOSE+7:
  1654. +   case CLOSE+8:
  1655. +   case CLOSE+9:
  1656. +       snprintf(buf+strlen(buf),BUFLEN-strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1657. +       p = NULL;
  1658. +       break;
  1659. +   case STAR:
  1660. +       p = "STAR";
  1661. +       break;
  1662. +   case PLUS:
  1663. +       p = "PLUS";
  1664. +       break;
  1665. +   default:
  1666. +       printk("<3>Regexp: corrupted opcode\n");
  1667. +       break;
  1668. +   }
  1669. +   if (p != NULL)
  1670. +       strncat(buf, p, BUFLEN-strlen(buf));
  1671. +   return(buf);
  1672. +}
  1673. +#endif
  1674. +
  1675. +
  1676. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  1677. +++ b/net/ipv4/netfilter/weburl_deps/regexp.h   2015-01-25 11:36:00.000000000 +0300
  1678. @@ -0,0 +1,41 @@
  1679. +/*
  1680. + * Definitions etc. for regexp(3) routines.
  1681. + *
  1682. + * Caveat:  this is V8 regexp(3) [actually, a reimplementation thereof],
  1683. + * not the System V one.
  1684. + */
  1685. +
  1686. +#ifndef REGEXP_H
  1687. +#define REGEXP_H
  1688. +
  1689. +
  1690. +/*
  1691. +http://www.opensource.apple.com/darwinsource/10.3/expect-1/expect/expect.h ,
  1692. +which contains a version of this library, says:
  1693. +
  1694. + *
  1695. + * NSUBEXP must be at least 10, and no greater than 117 or the parser
  1696. + * will not work properly.
  1697. + *
  1698. +
  1699. +However, it looks rather like this library is limited to 10.  If you think
  1700. +otherwise, let us know.
  1701. +*/
  1702. +
  1703. +#define NSUBEXP  10
  1704. +typedef struct regexp {
  1705. +   char *startp[NSUBEXP];
  1706. +   char *endp[NSUBEXP];
  1707. +   char regstart;      /* Internal use only. */
  1708. +   char reganch;       /* Internal use only. */
  1709. +   char *regmust;      /* Internal use only. */
  1710. +   int regmlen;        /* Internal use only. */
  1711. +   char program[1];    /* Unwarranted chumminess with compiler. */
  1712. +} regexp;
  1713. +
  1714. +regexp * regcomp(char *exp, int *patternsize);
  1715. +int regexec(regexp *prog, char *string);
  1716. +void regsub(regexp *prog, char *source, char *dest);
  1717. +void regerror(char *s);
  1718. +
  1719. +#endif
  1720. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  1721. +++ b/net/ipv4/netfilter/weburl_deps/regmagic.h 2015-01-25 11:36:00.000000000 +0300
  1722. @@ -0,0 +1,5 @@
  1723. +/*
  1724. + * The first byte of the regexp internal "program" is actually this magic
  1725. + * number; the start node begins in the second byte.
  1726. + */
  1727. +#define    MAGIC   0234
  1728. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  1729. +++ b/net/ipv4/netfilter/weburl_deps/regsub.c   2015-01-25 11:35:00.000000000 +0300
  1730. @@ -0,0 +1,95 @@
  1731. +/*
  1732. + * regsub
  1733. + * @(#)regsub.c    1.3 of 2 April 86
  1734. + *
  1735. + * Copyright (c) 1986 by University of Toronto.
  1736. + * Written by Henry Spencer.  Not derived from licensed software.
  1737. + *
  1738. + * Permission is granted to anyone to use this software for any
  1739. + * purpose on any computer system, and to redistribute it freely,
  1740. + * subject to the following restrictions:
  1741. + *
  1742. + * 1. The author is not responsible for the consequences of use of
  1743. + *     this software, no matter how awful, even if they arise
  1744. + *     from defects in it.
  1745. + *
  1746. + * 2. The origin of this software must not be misrepresented, either
  1747. + *     by explicit claim or by omission.
  1748. + *
  1749. + * 3. Altered versions must be plainly marked as such, and must not
  1750. + *     be misrepresented as being the original software.
  1751. + *
  1752. + *
  1753. + * This code was modified by Ethan Sommer to work within the kernel
  1754. + * (it now uses kmalloc etc..)
  1755. + *
  1756. + */
  1757. +#include "regexp.h"
  1758. +#include "regmagic.h"
  1759. +#include <linux/string.h>
  1760. +
  1761. +
  1762. +#ifndef CHARBITS
  1763. +#define    UCHARAT(p)  ((int)*(unsigned char *)(p))
  1764. +#else
  1765. +#define    UCHARAT(p)  ((int)*(p)&CHARBITS)
  1766. +#endif
  1767. +
  1768. +#if 0
  1769. +//void regerror(char * s)
  1770. +//{
  1771. +//        printk("regexp(3): %s", s);
  1772. +//        /* NOTREACHED */
  1773. +//}
  1774. +#endif
  1775. +
  1776. +/*
  1777. + - regsub - perform substitutions after a regexp match
  1778. + */
  1779. +void
  1780. +regsub(regexp * prog, char * source, char * dest)
  1781. +{
  1782. +   register char *src;
  1783. +   register char *dst;
  1784. +   register char c;
  1785. +   register int no;
  1786. +   register int len;
  1787. +
  1788. +   /* Not necessary and gcc doesn't like it -MLS */
  1789. +   /*extern char *strncpy();*/
  1790. +
  1791. +   if (prog == NULL || source == NULL || dest == NULL) {
  1792. +       regerror("NULL parm to regsub");
  1793. +       return;
  1794. +   }
  1795. +   if (UCHARAT(prog->program) != MAGIC) {
  1796. +       regerror("damaged regexp fed to regsub");
  1797. +       return;
  1798. +   }
  1799. +
  1800. +   src = source;
  1801. +   dst = dest;
  1802. +   while ((c = *src++) != '\0') {
  1803. +       if (c == '&')
  1804. +           no = 0;
  1805. +       else if (c == '\\' && '0' <= *src && *src <= '9')
  1806. +           no = *src++ - '0';
  1807. +       else
  1808. +           no = -1;
  1809. +
  1810. +       if (no < 0) {   /* Ordinary character. */
  1811. +           if (c == '\\' && (*src == '\\' || *src == '&'))
  1812. +               c = *src++;
  1813. +           *dst++ = c;
  1814. +       } else if (prog->startp[no] != NULL && prog->endp[no] != NULL) {
  1815. +           len = prog->endp[no] - prog->startp[no];
  1816. +           (void) strncpy(dst, prog->startp[no], len);
  1817. +           dst += len;
  1818. +           if (len != 0 && *(dst-1) == '\0') { /* strncpy hit NUL. */
  1819. +               regerror("damaged match string");
  1820. +               return;
  1821. +           }
  1822. +       }
  1823. +   }
  1824. +   *dst++ = '\0';
  1825. +}
  1826. --- /dev/null   2015-01-27 10:36:31.203991198 +0300
  1827. +++ b/net/ipv4/netfilter/weburl_deps/tree_map.h 2015-01-25 11:35:00.000000000 +0300
  1828. @@ -0,0 +1,1084 @@
  1829. +/*
  1830. + * Copyright © 2008 by Eric Bishop <eric@gargoyle-router.com>
  1831. + *
  1832. + * This work 'as-is' we provide.
  1833. + * No warranty, express or implied.
  1834. + * We've done our best,
  1835. + * to debug and test.
  1836. + * Liability for damages denied.
  1837. + *
  1838. + * Permission is granted hereby,
  1839. + * to copy, share, and modify.
  1840. + * Use as is fit,
  1841. + * free or for profit.
  1842. + * On this notice these rights rely.
  1843. + *
  1844. + *
  1845. + *
  1846. + *  Note that unlike other portions of Gargoyle this code
  1847. + *  does not fall under the GPL, but the rather whimsical
  1848. + *  'Poetic License' above.
  1849. + *
  1850. + *  Basically, this library contains a bunch of utilities
  1851. + *  that I find useful.  I'm sure other libraries exist
  1852. + *  that are just as good or better, but I like these tools
  1853. + *  because I personally wrote them, so I know their quirks.
  1854. + *  (i.e. I know where the bodies are buried).  I want to
  1855. + *  make sure that I can re-use these utilities for whatever
  1856. + *  code I may want to write in the future be it
  1857. + *  proprietary or open-source, so I've put them under
  1858. + *  a very, very permissive license.
  1859. + *
  1860. + *  If you find this code useful, use it.  If not, don't.
  1861. + *  I really don't care.
  1862. + *
  1863. + */
  1864. +
  1865. +
  1866. +#if __KERNEL__
  1867. +   #define malloc(foo) kmalloc(foo,GFP_ATOMIC)
  1868. +   #define free(foo)   kfree(foo)
  1869. +   #define printf(format,args...)  printk(format,##args)
  1870. +
  1871. +   /* kernel strdup */
  1872. +   static inline char *kernel_strdup(const char *str);
  1873. +   static inline char *kernel_strdup(const char *str)
  1874. +   {
  1875. +       char *tmp;
  1876. +       long int s;
  1877. +       s=strlen(str) + 1;
  1878. +       tmp = kmalloc(s, GFP_ATOMIC);
  1879. +       if (tmp != NULL)
  1880. +       {
  1881. +           memcpy(tmp, str, s);
  1882. +       }
  1883. +       return tmp;
  1884. +   }
  1885. +   #define strdup kernel_strdup
  1886. +
  1887. +#endif
  1888. +
  1889. +
  1890. +
  1891. +/* tree_map structs / prototypes */
  1892. +typedef struct long_tree_map_node
  1893. +{
  1894. +   unsigned long key;
  1895. +   void* value;
  1896. +  
  1897. +   signed char balance;
  1898. +   struct long_tree_map_node* left;
  1899. +   struct long_tree_map_node* right;
  1900. +} long_map_node;
  1901. +
  1902. +typedef struct
  1903. +{
  1904. +   long_map_node* root;
  1905. +   unsigned long num_elements;
  1906. +
  1907. +}long_map;
  1908. +
  1909. +typedef struct
  1910. +{
  1911. +   long_map lm;
  1912. +   unsigned char store_keys;
  1913. +   unsigned long num_elements;
  1914. +
  1915. +}string_map;
  1916. +
  1917. +
  1918. +
  1919. +/* long map functions */
  1920. +long_map* initialize_long_map(void);
  1921. +void* get_long_map_element(long_map* map, unsigned long key);
  1922. +void* get_smallest_long_map_element(long_map* map, unsigned long* smallest_key);
  1923. +void* get_largest_long_map_element(long_map* map, unsigned long* largest_key);
  1924. +void* remove_smallest_long_map_element(long_map* map, unsigned long* smallest_key);
  1925. +void* remove_largest_long_map_element(long_map* map, unsigned long* largest_key);
  1926. +void* set_long_map_element(long_map* map, unsigned long key, void* value);
  1927. +void* remove_long_map_element(long_map* map, unsigned long key);
  1928. +unsigned long* get_sorted_long_map_keys(long_map* map, unsigned long* num_keys_returned);
  1929. +void** get_sorted_long_map_values(long_map* map, unsigned long* num_values_returned);
  1930. +void** destroy_long_map(long_map* map, int destruction_type, unsigned long* num_destroyed);
  1931. +void apply_to_every_long_map_value(long_map* map, void (*apply_func)(unsigned long key, void* value));
  1932. +
  1933. +/* string map functions */
  1934. +string_map* initialize_string_map(unsigned char store_keys);
  1935. +void* get_string_map_element(string_map* map, const char* key);
  1936. +void* set_string_map_element(string_map* map, const char* key, void* value);
  1937. +void* remove_string_map_element(string_map* map, const char* key);
  1938. +char** get_string_map_keys(string_map* map, unsigned long* num_keys_returned);
  1939. +void** get_string_map_values(string_map* map, unsigned long* num_values_returned);
  1940. +void** destroy_string_map(string_map* map, int destruction_type, unsigned long* num_destroyed);
  1941. +void apply_to_every_string_map_value(string_map* map, void (*apply_func)(char* key, void* value));
  1942. +
  1943. +
  1944. +/*
  1945. + * three different ways to deal with values when data structure is destroyed
  1946. + */
  1947. +#define DESTROY_MODE_RETURN_VALUES 20
  1948. +#define DESTROY_MODE_FREE_VALUES   21
  1949. +#define DESTROY_MODE_IGNORE_VALUES 22
  1950. +
  1951. +
  1952. +/*
  1953. + * for convenience & backwards compatibility alias _string_map_ functions to
  1954. + *  _map_ functions since string map is used more often than long map
  1955. + */
  1956. +#define initialize_map     initialize_string_map
  1957. +#define set_map_element        set_string_map_element
  1958. +#define get_map_element        get_string_map_element
  1959. +#define remove_map_element remove_string_map_element
  1960. +#define get_map_keys       get_string_map_keys
  1961. +#define get_map_values     get_string_map_values
  1962. +#define destroy_map        destroy_string_map
  1963. +
  1964. +
  1965. +/* internal utility structures/ functions */
  1966. +typedef struct stack_node_struct
  1967. +{
  1968. +   long_map_node** node_ptr;
  1969. +   signed char direction;
  1970. +   struct stack_node_struct* previous;
  1971. +} stack_node;
  1972. +
  1973. +static void free_stack(stack_node* stack);
  1974. +static void** destroy_long_map_values(long_map* map, int destruction_type, unsigned long* num_destroyed);
  1975. +static void apply_to_every_long_map_node(long_map_node* node, void (*apply_func)(unsigned long key, void* value));
  1976. +static void apply_to_every_string_map_node(long_map_node* node, unsigned char has_key, void (*apply_func)(char* key, void* value));
  1977. +static void get_sorted_node_keys(long_map_node* node, unsigned long* key_list, unsigned long* next_key_index, int depth);
  1978. +static void get_sorted_node_values(long_map_node* node, void** value_list, unsigned long* next_value_index, int depth);
  1979. +static signed char rebalance (long_map_node** n, signed char direction, signed char update_op);
  1980. +static void rotate_right (long_map_node** parent);
  1981. +static void rotate_left (long_map_node** parent);
  1982. +
  1983. +/* internal for string map */
  1984. +typedef struct
  1985. +{
  1986. +   char* key;
  1987. +   void* value;
  1988. +} string_map_key_value;
  1989. +static unsigned long sdbm_string_hash(const char *key);
  1990. +
  1991. +
  1992. +
  1993. +
  1994. +/***************************************************
  1995. + * For testing only
  1996. + ***************************************************/
  1997. +/*
  1998. +void print_list(stack_node *l);
  1999. +
  2000. +void print_list(stack_node *l)
  2001. +{
  2002. +   if(l != NULL)
  2003. +   {
  2004. +       printf(" list key = %ld, dir=%d, \n", (*(l->node_ptr))->key, l->direction);
  2005. +       print_list(l->previous);
  2006. +   }
  2007. +}
  2008. +*/
  2009. +/******************************************************
  2010. + * End testing Code
  2011. + *******************************************************/
  2012. +
  2013. +
  2014. +
  2015. +
  2016. +/***************************************************
  2017. + * string_map function definitions
  2018. + ***************************************************/
  2019. +
  2020. +string_map* initialize_string_map(unsigned char store_keys)
  2021. +{
  2022. +   string_map* map = (string_map*)malloc(sizeof(string_map));
  2023. +   if(map != NULL)
  2024. +   {
  2025. +       map->store_keys = store_keys;
  2026. +       map->lm.root = NULL;
  2027. +       map->lm.num_elements = 0;
  2028. +       map->num_elements = map->lm.num_elements;
  2029. +   }
  2030. +   return map;
  2031. +}
  2032. +
  2033. +void* get_string_map_element(string_map* map, const char* key)
  2034. +{
  2035. +   unsigned long hashed_key = sdbm_string_hash(key);
  2036. +   void* return_value =  get_long_map_element( &(map->lm), hashed_key);
  2037. +   if(return_value != NULL && map->store_keys)
  2038. +   {
  2039. +       string_map_key_value* r = (string_map_key_value*)return_value;
  2040. +       return_value = r->value;
  2041. +   }
  2042. +   map->num_elements = map->lm.num_elements;
  2043. +   return return_value;
  2044. +}
  2045. +
  2046. +void* set_string_map_element(string_map* map, const char* key, void* value)
  2047. +{
  2048. +   unsigned long hashed_key = sdbm_string_hash(key);
  2049. +   void* return_value = NULL;
  2050. +   if(map->store_keys)
  2051. +   {
  2052. +       string_map_key_value* kv = (string_map_key_value*)malloc(sizeof(string_map_key_value));
  2053. +       if(kv == NULL) /* deal with malloc failure */
  2054. +       {
  2055. +           return NULL;
  2056. +       }
  2057. +       kv->key = strdup(key);
  2058. +       if(kv->key == NULL) /* deal with malloc failure */
  2059. +       {
  2060. +           free(kv);
  2061. +           return NULL;
  2062. +       }
  2063. +       kv->value = value;
  2064. +       return_value = set_long_map_element(  &(map->lm), hashed_key, kv);
  2065. +       if(return_value != NULL)
  2066. +       {
  2067. +           string_map_key_value* r = (string_map_key_value*)return_value;
  2068. +           return_value = r->value;
  2069. +           free(r->key);
  2070. +           free(r);
  2071. +       }
  2072. +   }
  2073. +   else
  2074. +   {
  2075. +       return_value = set_long_map_element( &(map->lm), hashed_key, value);
  2076. +   }
  2077. +   map->num_elements = map->lm.num_elements;
  2078. +   return return_value;
  2079. +}
  2080. +
  2081. +void* remove_string_map_element(string_map* map, const char* key)
  2082. +{
  2083. +   unsigned long hashed_key = sdbm_string_hash(key);
  2084. +   void* return_value =  remove_long_map_element( &(map->lm), hashed_key);
  2085. +  
  2086. +   if(return_value != NULL && map->store_keys)
  2087. +   {
  2088. +       string_map_key_value* r = (string_map_key_value*)return_value;
  2089. +       return_value = r->value;
  2090. +       free(r->key);
  2091. +       free(r);
  2092. +   }
  2093. +   map->num_elements = map->lm.num_elements;
  2094. +   return return_value;
  2095. +}
  2096. +
  2097. +char** get_string_map_keys(string_map* map, unsigned long* num_keys_returned)
  2098. +{
  2099. +   char** str_keys;
  2100. +   str_keys = (char**)malloc((map->num_elements+1)*sizeof(char*));
  2101. +   if(str_keys == NULL) /* deal with malloc failure */
  2102. +   {
  2103. +       return NULL;
  2104. +   }
  2105. +   str_keys[0] = NULL;
  2106. +   *num_keys_returned = 0;
  2107. +   if(map->store_keys && map->num_elements > 0)
  2108. +   {
  2109. +       unsigned long list_length;
  2110. +       void** long_values = get_sorted_long_map_values( &(map->lm),  &list_length);
  2111. +       unsigned long key_index;
  2112. +       /*list_length will be 0 on malloc failure in get_sorted_long_map_values, so this code shouldn't seg fault if that happens */
  2113. +       for(key_index = 0; key_index < list_length; key_index++)
  2114. +       {
  2115. +           str_keys[key_index] = strdup( ((string_map_key_value*)(long_values[key_index]))->key);
  2116. +           if(str_keys[key_index] == NULL) /* deal with malloc failure */
  2117. +           {
  2118. +               //just return the incomplete list (hey, it's null terminated...)
  2119. +               free(long_values);
  2120. +               return str_keys;
  2121. +           }
  2122. +           *num_keys_returned = *num_keys_returned + 1;
  2123. +       }
  2124. +       str_keys[list_length] = NULL;
  2125. +       free(long_values);
  2126. +   }
  2127. +   return str_keys;
  2128. +}
  2129. +
  2130. +
  2131. +void** get_string_map_values(string_map* map, unsigned long* num_values_returned)
  2132. +{
  2133. +   void** values = NULL;
  2134. +   if(map != NULL)
  2135. +   {
  2136. +       values = get_sorted_long_map_values ( &(map->lm), num_values_returned );
  2137. +   }
  2138. +   return values;
  2139. +}
  2140. +
  2141. +
  2142. +void** destroy_string_map(string_map* map, int destruction_type, unsigned long* num_destroyed)
  2143. +{
  2144. +   void** return_values = NULL;
  2145. +   if(map != NULL)
  2146. +   {
  2147. +       if(map->store_keys)
  2148. +       {
  2149. +           void** kvs = destroy_long_map_values( &(map->lm), DESTROY_MODE_RETURN_VALUES, num_destroyed );
  2150. +           unsigned long kv_index = 0;
  2151. +           for(kv_index=0; kv_index < *num_destroyed; kv_index++)
  2152. +           {
  2153. +               string_map_key_value* kv = (string_map_key_value*)kvs[kv_index];
  2154. +               void* value = kv->value;
  2155. +              
  2156. +               free(kv->key);
  2157. +               free(kv);
  2158. +               if(destruction_type == DESTROY_MODE_FREE_VALUES)
  2159. +               {
  2160. +                   free(value);
  2161. +               }
  2162. +               if(destruction_type == DESTROY_MODE_RETURN_VALUES)
  2163. +               {
  2164. +                   kvs[kv_index] = value;
  2165. +               }
  2166. +           }
  2167. +           if(destruction_type == DESTROY_MODE_RETURN_VALUES)
  2168. +           {
  2169. +               return_values = kvs;
  2170. +           }
  2171. +           else
  2172. +           {
  2173. +               free(kvs);
  2174. +           }
  2175. +       }
  2176. +       else
  2177. +       {
  2178. +           return_values = destroy_long_map_values( &(map->lm), destruction_type, num_destroyed );
  2179. +       }
  2180. +       free(map);
  2181. +   }
  2182. +   return return_values;
  2183. +}
  2184. +
  2185. +
  2186. +
  2187. +
  2188. +/***************************************************
  2189. + * long_map function definitions
  2190. + ***************************************************/
  2191. +
  2192. +long_map* initialize_long_map(void)
  2193. +{
  2194. +   long_map* map = (long_map*)malloc(sizeof(long_map));
  2195. +   if(map != NULL) /* test for malloc failure */
  2196. +   {
  2197. +       map->root = NULL;
  2198. +       map->num_elements = 0;
  2199. +   }
  2200. +   return map;
  2201. +}
  2202. +
  2203. +void* get_long_map_element(long_map* map, unsigned long key)
  2204. +{
  2205. +   void* value = NULL;
  2206. +
  2207. +   if(map->root != NULL)
  2208. +   {
  2209. +       long_map_node* parent_node = map->root;
  2210. +       long_map_node* next_node;  
  2211. +       while( key != parent_node->key && (next_node = (long_map_node *)(key < parent_node->key ? parent_node->left : parent_node->right))  != NULL)
  2212. +       {
  2213. +           parent_node = next_node;
  2214. +       }
  2215. +       if(parent_node->key == key)
  2216. +       {
  2217. +           value = parent_node->value;
  2218. +       }
  2219. +   }
  2220. +   return value;
  2221. +}
  2222. +
  2223. +void* get_smallest_long_map_element(long_map* map, unsigned long* smallest_key)
  2224. +{
  2225. +   void* value = NULL;
  2226. +   if(map->root != NULL)
  2227. +   {
  2228. +       long_map_node* next_node = map->root;  
  2229. +       while( next_node->left != NULL)
  2230. +       {
  2231. +           next_node = next_node->left;
  2232. +       }
  2233. +       value = next_node->value;
  2234. +       *smallest_key = next_node->key;
  2235. +   }
  2236. +   return value;
  2237. +}
  2238. +
  2239. +void* get_largest_long_map_element(long_map* map, unsigned long* largest_key)
  2240. +{
  2241. +   void* value = NULL;
  2242. +   if(map->root != NULL)
  2243. +   {
  2244. +       long_map_node* next_node = map->root;  
  2245. +       while( next_node->right != NULL)
  2246. +       {
  2247. +           next_node = next_node->right;
  2248. +       }
  2249. +       value = next_node->value;
  2250. +       *largest_key = next_node->key;
  2251. +   }
  2252. +   return value;
  2253. +}
  2254. +
  2255. +void* remove_smallest_long_map_element(long_map* map, unsigned long* smallest_key)
  2256. +{
  2257. +   get_smallest_long_map_element(map, smallest_key);
  2258. +   return remove_long_map_element(map, *smallest_key);
  2259. +}
  2260. +
  2261. +void* remove_largest_long_map_element(long_map* map, unsigned long* largest_key)
  2262. +{
  2263. +   get_largest_long_map_element(map, largest_key);
  2264. +   return remove_long_map_element(map, *largest_key);
  2265. +}
  2266. +
  2267. +
  2268. +/* if replacement performed, returns replaced value, otherwise null */
  2269. +void* set_long_map_element(long_map* map, unsigned long key, void* value)
  2270. +{
  2271. +   stack_node* parent_list = NULL;
  2272. +   void* old_value = NULL;
  2273. +   int old_value_found = 0;
  2274. +
  2275. +   long_map_node* parent_node;
  2276. +   long_map_node* next_node;
  2277. +   stack_node* next_parent;
  2278. +   stack_node* previous_parent;
  2279. +   signed char new_balance;
  2280. +
  2281. +
  2282. +   long_map_node* new_node = (long_map_node*)malloc(sizeof(long_map_node));
  2283. +   if(new_node == NULL)
  2284. +   {
  2285. +       return NULL;
  2286. +   }
  2287. +   new_node->value = value;
  2288. +   new_node->key = key;
  2289. +   new_node->left = NULL;
  2290. +   new_node->right = NULL;
  2291. +   new_node->balance = 0;
  2292. +
  2293. +  
  2294. +
  2295. +   if(map->root == NULL)
  2296. +   {
  2297. +       map->root = new_node;  
  2298. +   }
  2299. +   else
  2300. +   {
  2301. +       parent_node = map->root;
  2302. +          
  2303. +       next_parent = (stack_node*)malloc(sizeof(stack_node));
  2304. +       if(next_parent == NULL) /* deal with malloc failure */
  2305. +       {
  2306. +           free(new_node);
  2307. +           return NULL; /* won't insert but won't seg fault */
  2308. +       }
  2309. +       next_parent->node_ptr =  &(map->root);
  2310. +       next_parent->previous = parent_list;
  2311. +       parent_list = next_parent; 
  2312. +          
  2313. +       while( key != parent_node->key && (next_node = (key < parent_node->key ? parent_node->left : parent_node->right) )  != NULL)
  2314. +       {
  2315. +           next_parent = (stack_node*)malloc(sizeof(stack_node));
  2316. +           if(next_parent == NULL) /* deal with malloc failure */
  2317. +           {
  2318. +               /* free previous stack nodes to prevent memory leak */
  2319. +               free_stack(parent_list);
  2320. +               free(new_node);
  2321. +               return NULL;
  2322. +           }
  2323. +           next_parent->node_ptr = key < parent_node->key ? &(parent_node->left) : &(parent_node->right);
  2324. +           next_parent->previous = parent_list;
  2325. +           next_parent->previous->direction = key < parent_node->key ? -1 : 1;
  2326. +           parent_list = next_parent;
  2327. +
  2328. +           parent_node = next_node;
  2329. +       }
  2330. +      
  2331. +      
  2332. +       if(key == parent_node->key)
  2333. +       {
  2334. +           old_value = parent_node->value;
  2335. +           old_value_found = 1;
  2336. +           parent_node->value = value;
  2337. +           free(new_node);
  2338. +           /* we merely replaced a node, no need to rebalance */
  2339. +       }
  2340. +       else
  2341. +       {  
  2342. +           if(key < parent_node->key)
  2343. +           {
  2344. +               parent_node->left = (void*)new_node;
  2345. +               parent_list->direction = -1;
  2346. +           }
  2347. +           else
  2348. +           {
  2349. +               parent_node->right = (void*)new_node;
  2350. +               parent_list->direction = 1;
  2351. +           }
  2352. +          
  2353. +          
  2354. +           /* we inserted a node, rebalance */
  2355. +           previous_parent = parent_list;
  2356. +           new_balance  = 1; /* initial value is not used, but must not be 0 for initial loop condition */
  2357. +          
  2358. +          
  2359. +           while(previous_parent != NULL && new_balance != 0)
  2360. +           {
  2361. +               new_balance = rebalance(previous_parent->node_ptr, previous_parent->direction, 1);
  2362. +               previous_parent = previous_parent->previous;
  2363. +           }
  2364. +       }
  2365. +   }
  2366. +
  2367. +   free_stack(parent_list);
  2368. +
  2369. +   if(old_value_found == 0)
  2370. +   {
  2371. +       map->num_elements = map->num_elements + 1;
  2372. +   }
  2373. +
  2374. +   return old_value;
  2375. +}
  2376. +
  2377. +
  2378. +void* remove_long_map_element(long_map* map, unsigned long key)
  2379. +{
  2380. +
  2381. +   void* value = NULL;
  2382. +  
  2383. +   long_map_node* root_node = map->root;  
  2384. +   stack_node* parent_list = NULL;
  2385. +
  2386. +
  2387. +   long_map_node* remove_parent;
  2388. +   long_map_node* remove_node;
  2389. +   long_map_node* next_node;
  2390. +
  2391. +   long_map_node* replacement;
  2392. +   long_map_node* replacement_parent;
  2393. +   long_map_node* replacement_next;
  2394. +
  2395. +   stack_node* next_parent;
  2396. +   stack_node* previous_parent;
  2397. +   stack_node* replacement_stack_node;
  2398. +
  2399. +
  2400. +   signed char new_balance;
  2401. +
  2402. +
  2403. +
  2404. +   if(root_node != NULL)
  2405. +   {
  2406. +       remove_parent = root_node;
  2407. +       remove_node = key < remove_parent->key ? remove_parent->left : remove_parent->right;
  2408. +      
  2409. +       if(remove_node != NULL && key != remove_parent->key)
  2410. +       {
  2411. +           next_parent = (stack_node*)malloc(sizeof(stack_node));
  2412. +           if(next_parent == NULL) /* deal with malloc failure */
  2413. +           {
  2414. +               return NULL;
  2415. +           }
  2416. +           next_parent->node_ptr =  &(map->root);
  2417. +           next_parent->previous = parent_list;
  2418. +           parent_list = next_parent; 
  2419. +           while( key != remove_node->key && (next_node = (key < remove_node->key ? remove_node->left : remove_node->right))  != NULL)
  2420. +           {
  2421. +               next_parent = (stack_node*)malloc(sizeof(stack_node));
  2422. +               if(next_parent == NULL) /* deal with malloc failure */
  2423. +               {
  2424. +                   /* free previous stack nodes to prevent memory leak */
  2425. +                   free_stack(parent_list);
  2426. +                   return NULL;
  2427. +               }
  2428. +               next_parent->node_ptr = key < remove_parent->key ? &(remove_parent->left) : &(remove_parent->right);
  2429. +               next_parent->previous = parent_list;
  2430. +               next_parent->previous->direction = key < remove_parent->key ? -1 : 1;
  2431. +               parent_list = next_parent;
  2432. +              
  2433. +              
  2434. +               remove_parent = remove_node;
  2435. +               remove_node = next_node;
  2436. +           }
  2437. +           parent_list->direction = key < remove_parent-> key ? -1 : 1;
  2438. +       }
  2439. +       else
  2440. +       {
  2441. +           remove_node = remove_parent;
  2442. +       }
  2443. +
  2444. +
  2445. +       if(key == remove_node->key)
  2446. +       {
  2447. +          
  2448. +           /* find replacement for node we are deleting */
  2449. +           if( remove_node->right == NULL )
  2450. +           {
  2451. +               replacement = remove_node->left;
  2452. +           }
  2453. +           else if( remove_node->right->left == NULL)
  2454. +           {
  2455. +
  2456. +               replacement = remove_node->right;
  2457. +               replacement->left = remove_node->left;
  2458. +               replacement->balance = remove_node->balance;
  2459. +
  2460. +               /* put pointer to replacement node into list for balance update */
  2461. +               replacement_stack_node = (stack_node*)malloc(sizeof(stack_node));
  2462. +               if(replacement_stack_node == NULL) /* deal with malloc failure */
  2463. +               {
  2464. +                   /* free previous stack nodes to prevent memory leak */
  2465. +                   free_stack(parent_list);
  2466. +                   return NULL;
  2467. +               }
  2468. +               replacement_stack_node->previous = parent_list;
  2469. +               replacement_stack_node->direction = 1; /* replacement is from right */
  2470. +               if(remove_node == remove_parent) /* special case for root node */
  2471. +               {
  2472. +                   replacement_stack_node->node_ptr = &(map->root);
  2473. +               }
  2474. +               else
  2475. +               {
  2476. +                   replacement_stack_node->node_ptr = key < remove_parent-> key ? &(remove_parent->left) : &(remove_parent->right);
  2477. +               }
  2478. +               parent_list = replacement_stack_node;
  2479. +
  2480. +           }
  2481. +           else
  2482. +           {
  2483. +               /* put pointer to replacement node into list for balance update */
  2484. +               replacement_stack_node = (stack_node*)malloc(sizeof(stack_node));
  2485. +               if(replacement_stack_node == NULL) /* deal with malloc failure */
  2486. +               {
  2487. +                   /* free previous stack nodes to prevent memory leak */
  2488. +                   free_stack(parent_list);
  2489. +                   return NULL;
  2490. +               }
  2491. +
  2492. +               replacement_stack_node->previous = parent_list;
  2493. +               replacement_stack_node->direction = 1; /* we always look for replacement on right */
  2494. +               if(remove_node == remove_parent) /* special case for root node */
  2495. +               {
  2496. +                   replacement_stack_node->node_ptr = &(map->root);
  2497. +               }
  2498. +               else
  2499. +               {
  2500. +                   replacement_stack_node->node_ptr = key < remove_parent-> key ? &(remove_parent->left) : &(remove_parent->right);
  2501. +               }
  2502. +
  2503. +               parent_list = replacement_stack_node;
  2504. +              
  2505. +
  2506. +               /*
  2507. +                * put pointer to replacement node->right into list for balance update
  2508. +                * this node will have to be updated with the proper pointer
  2509. +                * after we have identified the replacement
  2510. +                */
  2511. +               replacement_stack_node = (stack_node*)malloc(sizeof(stack_node));
  2512. +               if(replacement_stack_node == NULL) /* deal with malloc failure */
  2513. +               {
  2514. +                   /* free previous stack nodes to prevent memory leak */
  2515. +                   free_stack(parent_list);
  2516. +                   return NULL;
  2517. +               }
  2518. +
  2519. +               replacement_stack_node->previous = parent_list;
  2520. +               replacement_stack_node->direction = -1; /* we always look for replacement to left of this node */
  2521. +               parent_list = replacement_stack_node;
  2522. +              
  2523. +               /* find smallest node on right (large) side of tree */
  2524. +               replacement_parent = remove_node->right;
  2525. +               replacement = replacement_parent->left;
  2526. +              
  2527. +               while((replacement_next = replacement->left)  != NULL)
  2528. +               {
  2529. +                   next_parent = (stack_node*)malloc(sizeof(stack_node));
  2530. +                   if(next_parent == NULL) /* deal with malloc failure */
  2531. +                   {
  2532. +                       /* free previous stack nodes to prevent memory leak */
  2533. +                       free_stack(parent_list);
  2534. +                       return NULL;
  2535. +                   }
  2536. +
  2537. +                   next_parent->node_ptr = &(replacement_parent->left);
  2538. +                   next_parent->previous = parent_list;
  2539. +                   next_parent->direction = -1; /* we always go left */
  2540. +                   parent_list = next_parent;
  2541. +
  2542. +                   replacement_parent = replacement;
  2543. +                   replacement = replacement_next;
  2544. +
  2545. +               }
  2546. +
  2547. +               replacement_parent->left = replacement->right;
  2548. +              
  2549. +               replacement->left = remove_node->left;
  2550. +               replacement->right = remove_node->right;
  2551. +               replacement->balance = remove_node->balance;
  2552. +               replacement_stack_node->node_ptr = &(replacement->right);
  2553. +           }
  2554. +          
  2555. +           /* insert replacement at proper location in tree */
  2556. +           if(remove_node == remove_parent)
  2557. +           {
  2558. +               map->root = replacement;
  2559. +           }
  2560. +           else
  2561. +           {
  2562. +               remove_parent->left = remove_node == remove_parent->left ? replacement : remove_parent->left;
  2563. +               remove_parent->right = remove_node == remove_parent->right ? replacement : remove_parent->right;
  2564. +           }
  2565. +      
  2566. +
  2567. +           /* rebalance tree */
  2568. +           previous_parent = parent_list;
  2569. +           new_balance = 0;
  2570. +           while(previous_parent != NULL && new_balance == 0)
  2571. +           {
  2572. +               new_balance = rebalance(previous_parent->node_ptr, previous_parent->direction, -1);
  2573. +               previous_parent = previous_parent->previous;
  2574. +           }
  2575. +          
  2576. +          
  2577. +
  2578. +
  2579. +           /*
  2580. +            * since we found a value to remove, decrease number of elements in map
  2581. +            *  set return value to the deleted node's value and free the node
  2582. +            */
  2583. +           map->num_elements = map->num_elements - 1;
  2584. +           value = remove_node->value;
  2585. +           free(remove_node);
  2586. +       }
  2587. +   }
  2588. +
  2589. +   free_stack(parent_list);
  2590. +  
  2591. +   return value;
  2592. +}
  2593. +
  2594. +
  2595. +/* note: returned keys are dynamically allocated, you need to free them! */
  2596. +unsigned long* get_sorted_long_map_keys(long_map* map, unsigned long* num_keys_returned)
  2597. +{
  2598. +   unsigned long* key_list = (unsigned long*)malloc((map->num_elements)*sizeof(unsigned long));
  2599. +   unsigned long next_key_index;
  2600. +   if(key_list == NULL)
  2601. +   {
  2602. +       *num_keys_returned = 0;
  2603. +       return NULL;
  2604. +   }
  2605. +   next_key_index = 0;
  2606. +   get_sorted_node_keys(map->root, key_list, &next_key_index, 0);
  2607. +  
  2608. +   *num_keys_returned = map->num_elements;
  2609. +
  2610. +   return key_list;
  2611. +}
  2612. +
  2613. +
  2614. +void** get_sorted_long_map_values(long_map* map, unsigned long* num_values_returned)
  2615. +{
  2616. +   void** value_list = (void**)malloc((map->num_elements+1)*sizeof(void*));
  2617. +   unsigned long next_value_index;
  2618. +
  2619. +   if(value_list == NULL)
  2620. +   {
  2621. +       *num_values_returned = 0;
  2622. +       return NULL;
  2623. +   }
  2624. +   next_value_index = 0;
  2625. +   get_sorted_node_values(map->root, value_list, &next_value_index, 0);
  2626. +   value_list[map->num_elements] = NULL; /* since we're dealing with pointers make list null terminated */
  2627. +
  2628. +   *num_values_returned = map->num_elements;
  2629. +   return value_list;
  2630. +
  2631. +}
  2632. +
  2633. +
  2634. +
  2635. +void** destroy_long_map(long_map* map, int destruction_type, unsigned long* num_destroyed)
  2636. +{
  2637. +   void** return_values = destroy_long_map_values(map, destruction_type, num_destroyed);
  2638. +   free(map);
  2639. +   return return_values;
  2640. +}
  2641. +
  2642. +
  2643. +
  2644. +void apply_to_every_long_map_value(long_map* map, void (*apply_func)(unsigned long key, void* value))
  2645. +{
  2646. +   apply_to_every_long_map_node(map->root, apply_func);
  2647. +}
  2648. +void apply_to_every_string_map_value(string_map* map, void (*apply_func)(char* key, void* value))
  2649. +{
  2650. +   apply_to_every_string_map_node( (map->lm).root, map->store_keys, apply_func);
  2651. +}
  2652. +
  2653. +
  2654. +/***************************************************
  2655. + * internal utility function definitions
  2656. + ***************************************************/
  2657. +static void free_stack(stack_node* stack)
  2658. +{
  2659. +   while(stack != NULL)
  2660. +   {
  2661. +       stack_node* prev_node = stack;
  2662. +       stack = prev_node->previous;
  2663. +       free(prev_node);
  2664. +   }
  2665. +
  2666. +}
  2667. +
  2668. +static void** destroy_long_map_values(long_map* map, int destruction_type, unsigned long* num_destroyed)
  2669. +{
  2670. +   void** return_values = NULL;
  2671. +   unsigned long return_index = 0;
  2672. +
  2673. +   *num_destroyed = 0;
  2674. +
  2675. +   if(destruction_type == DESTROY_MODE_RETURN_VALUES)
  2676. +   {
  2677. +       return_values = (void**)malloc((map->num_elements+1)*sizeof(void*));
  2678. +       if(return_values == NULL) /* deal with malloc failure */
  2679. +       {
  2680. +           destruction_type = DESTROY_MODE_IGNORE_VALUES; /* could cause memory leak, but there's no other way to be sure we won't seg fault */
  2681. +       }
  2682. +       else
  2683. +       {
  2684. +           return_values[map->num_elements] = NULL;
  2685. +       }
  2686. +   }
  2687. +   while(map->num_elements > 0)
  2688. +   {
  2689. +       unsigned long smallest_key;
  2690. +       void* removed_value = remove_smallest_long_map_element(map, &smallest_key);
  2691. +       if(destruction_type == DESTROY_MODE_RETURN_VALUES)
  2692. +       {
  2693. +           return_values[return_index] = removed_value;
  2694. +       }
  2695. +       if(destruction_type == DESTROY_MODE_FREE_VALUES)
  2696. +       {
  2697. +           free(removed_value);
  2698. +       }
  2699. +       return_index++;
  2700. +       *num_destroyed = *num_destroyed + 1;
  2701. +   }
  2702. +   return return_values;
  2703. +}
  2704. +
  2705. +static void apply_to_every_long_map_node(long_map_node* node, void (*apply_func)(unsigned long key, void* value))
  2706. +{
  2707. +   if(node != NULL)
  2708. +   {
  2709. +       apply_to_every_long_map_node(node->left,  apply_func);
  2710. +      
  2711. +       apply_func(node->key, node->value);
  2712. +
  2713. +       apply_to_every_long_map_node(node->right, apply_func);
  2714. +   }
  2715. +}
  2716. +static void apply_to_every_string_map_node(long_map_node* node, unsigned char has_key, void (*apply_func)(char* key, void* value))
  2717. +{
  2718. +   if(node != NULL)
  2719. +   {
  2720. +       apply_to_every_string_map_node(node->left, has_key,  apply_func);
  2721. +      
  2722. +       if(has_key)
  2723. +       {
  2724. +           string_map_key_value* kv = (string_map_key_value*)(node->value);
  2725. +           apply_func(kv->key, kv->value);
  2726. +       }
  2727. +       else
  2728. +       {
  2729. +           apply_func(NULL, node->value);
  2730. +       }
  2731. +       apply_to_every_string_map_node(node->right, has_key, apply_func);
  2732. +   }
  2733. +}
  2734. +
  2735. +
  2736. +
  2737. +static void get_sorted_node_keys(long_map_node* node, unsigned long* key_list, unsigned long* next_key_index, int depth)
  2738. +{
  2739. +   if(node != NULL)
  2740. +   {
  2741. +       get_sorted_node_keys(node->left, key_list, next_key_index, depth+1);
  2742. +      
  2743. +       key_list[ *next_key_index ] = node->key;
  2744. +       (*next_key_index)++;
  2745. +
  2746. +       get_sorted_node_keys(node->right, key_list, next_key_index, depth+1);
  2747. +   }
  2748. +}
  2749. +
  2750. +static void get_sorted_node_values(long_map_node* node, void** value_list, unsigned long* next_value_index, int depth)
  2751. +{
  2752. +   if(node != NULL)
  2753. +   {
  2754. +       get_sorted_node_values(node->left, value_list, next_value_index, depth+1);
  2755. +      
  2756. +       value_list[ *next_value_index ] = node->value;
  2757. +       (*next_value_index)++;
  2758. +
  2759. +       get_sorted_node_values(node->right, value_list, next_value_index, depth+1);
  2760. +   }
  2761. +}
  2762. +
  2763. +
  2764. +
  2765. +/*
  2766. + * direction = -1 indicates left subtree updated, direction = 1 for right subtree
  2767. + * update_op = -1 indicates delete node, update_op = 1 for insert node
  2768. + */
  2769. +static signed char rebalance (long_map_node** n, signed char direction, signed char update_op)
  2770. +{
  2771. +   /*
  2772. +   printf( "original: key = %ld, balance = %d, update_op=%d, direction=%d\n", (*n)->key, (*n)->balance, update_op, direction);
  2773. +   */
  2774. +
  2775. +   (*n)->balance = (*n)->balance + (update_op*direction);
  2776. +  
  2777. +   if( (*n)->balance <  -1)
  2778. +   {
  2779. +       if((*n)->left->balance < 0)
  2780. +       {
  2781. +           rotate_right(n);
  2782. +           (*n)->right->balance = 0;
  2783. +           (*n)->balance = 0;
  2784. +       }
  2785. +       else if((*n)->left->balance == 0)
  2786. +       {
  2787. +           rotate_right(n);
  2788. +           (*n)->right->balance = -1;
  2789. +           (*n)->balance = 1;
  2790. +       }
  2791. +       else if((*n)->left->balance > 0)
  2792. +       {
  2793. +           rotate_left( &((*n)->left) );
  2794. +           rotate_right(n);
  2795. +           /*
  2796. +           if( (*n)->balance < 0 )
  2797. +           {
  2798. +               (*n)->left->balance = 0;
  2799. +               (*n)->right->balance = 1;
  2800. +           }
  2801. +           else if( (*n)->balance == 0 )
  2802. +           {
  2803. +               (*n)->left->balance = 0;
  2804. +               (*n)->right->balance = 0;
  2805. +           }
  2806. +           else if( (*n)->balance > 0 )
  2807. +           {
  2808. +               (*n)->left->balance = -1;
  2809. +               (*n)->right->balance = 0;
  2810. +           }
  2811. +           */
  2812. +           (*n)->left->balance  = (*n)->balance > 0 ? -1 : 0;
  2813. +           (*n)->right->balance = (*n)->balance < 0 ?  1 : 0;
  2814. +           (*n)->balance = 0;
  2815. +       }
  2816. +   }
  2817. +   if( (*n)->balance >  1)
  2818. +   {
  2819. +       if((*n)->right->balance > 0)
  2820. +       {
  2821. +           rotate_left(n);
  2822. +           (*n)->left->balance = 0;
  2823. +           (*n)->balance = 0;
  2824. +       }
  2825. +       else if ((*n)->right->balance == 0)
  2826. +       {
  2827. +           rotate_left(n);
  2828. +           (*n)->left->balance = 1;
  2829. +           (*n)->balance = -1;
  2830. +       }
  2831. +       else if((*n)->right->balance < 0)
  2832. +       {
  2833. +           rotate_right( &((*n)->right) );
  2834. +           rotate_left(n);
  2835. +           /*
  2836. +           if( (*n)->balance < 0 )
  2837. +           {
  2838. +               (*n)->left->balance = 0;
  2839. +               (*n)->right->balance = 1;
  2840. +           }
  2841. +           else if( (*n)->balance == 0 )
  2842. +           {
  2843. +               (*n)->left->balance = 0;
  2844. +               (*n)->right->balance = 0;
  2845. +           }
  2846. +           else if( (*n)->balance > 0 )
  2847. +           {
  2848. +               (*n)->left->balance = -1;
  2849. +               (*n)->right->balance = 0;
  2850. +           }
  2851. +           */
  2852. +           (*n)->left->balance   = (*n)->balance > 0 ? -1 : 0;
  2853. +           (*n)->right->balance  = (*n)->balance < 0 ?  1 : 0;
  2854. +           (*n)->balance = 0;
  2855. +       }
  2856. +   }
  2857. +
  2858. +   /*
  2859. +   printf( "key = %ld, balance = %d\n", (*n)->key, (*n)->balance);
  2860. +   */
  2861. +
  2862. +   return (*n)->balance;
  2863. +}
  2864. +
  2865. +
  2866. +static void rotate_right (long_map_node** parent)
  2867. +{
  2868. +   long_map_node* old_parent = *parent;
  2869. +   long_map_node* pivot = old_parent->left;
  2870. +   old_parent->left = pivot->right;
  2871. +   pivot->right  = old_parent;
  2872. +  
  2873. +   *parent = pivot;
  2874. +}
  2875. +
  2876. +static void rotate_left (long_map_node** parent)
  2877. +{
  2878. +   long_map_node* old_parent = *parent;
  2879. +   long_map_node* pivot = old_parent->right;
  2880. +   old_parent->right = pivot->left;
  2881. +   pivot->left  = old_parent;
  2882. +  
  2883. +   *parent = pivot;
  2884. +}
  2885. +
  2886. +
  2887. +
  2888. +/***************************************************************************
  2889. + * This algorithm was created for the sdbm database library (a public-domain
  2890. + * reimplementation of ndbm) and seems to work relatively well in
  2891. + * scrambling bits
  2892. + *
  2893. + *
  2894. + * This code was derived from code found at:
  2895. + * http://www.cse.yorku.ca/~oz/hash.html
  2896. + ***************************************************************************/
  2897. +static unsigned long sdbm_string_hash(const char *key)
  2898. +{
  2899. +   unsigned long hashed_key = 0;
  2900. +
  2901. +   int index = 0;
  2902. +   unsigned int nextch;
  2903. +   while(key[index] != '\0')
  2904. +   {
  2905. +       nextch = key[index];
  2906. +       hashed_key = nextch + (hashed_key << 6) + (hashed_key << 16) - hashed_key;
  2907. +       index++;
  2908. +   }
  2909. +   return hashed_key;
  2910. +}
  2911. +
  2912. +
  2913. --- a/net/ipv4/netfilter/Kconfig.orig   2014-12-08 01:21:05.000000000 +0300
  2914. +++ b/net/ipv4/netfilter/Kconfig    2015-01-27 09:40:50.961960594 +0300
  2915. @@ -190,6 +190,12 @@
  2916.       To compile it as a module, choose M here.  If unsure, say N.
  2917.       The module will be called ipt_rpfilter.
  2918.  
  2919. +config IP_NF_MATCH_WEBURL
  2920. +   tristate '"weburl" weburl'
  2921. +   depends on NETFILTER_ADVANCED
  2922. +   ---help---
  2923. +     weburl
  2924. +
  2925.  config IP_NF_MATCH_TTL
  2926.     tristate '"ttl" match support'
  2927.     depends on NETFILTER_ADVANCED
  2928. --- a/net/ipv4/netfilter/Makefile.orig  2014-12-08 01:21:05.000000000 +0300
  2929. +++ b/net/ipv4/netfilter/Makefile   2015-01-27 09:41:33.930010380 +0300
  2930. @@ -55,6 +55,7 @@
  2931.  # matches
  2932.  obj-$(CONFIG_IP_NF_MATCH_AH) += ipt_ah.o
  2933.  obj-$(CONFIG_IP_NF_MATCH_RPFILTER) += ipt_rpfilter.o
  2934. +obj-$(CONFIG_IP_NF_MATCH_WEBURL) += ipt_weburl.o
  2935.  
  2936.  # targets
  2937.  obj-$(CONFIG_IP_NF_TARGET_CLUSTERIP) += ipt_CLUSTERIP.o
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!