Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /* libwapcaplet.c
  2.  *
  3.  * String internment and management tools.
  4.  *
  5.  * Copyright 2009 The NetSurf Browser Project.
  6.  *                Daniel Silverstone <dsilvers@netsurf-browser.org>
  7.  */
  8.  
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <assert.h>
  12.  
  13. #include "libwapcaplet/libwapcaplet.h"
  14.  
  15. #ifndef UNUSED
  16. #define UNUSED(x) ((x) = (x))
  17. #endif
  18.  
  19. static inline lwc_hash
  20. lwc__calculate_hash(const char *str, size_t len)
  21. {
  22.         lwc_hash z = 0x811c9dc5;
  23.        
  24.  
  25.         while (len > 0) {
  26.                 z *= 0x01000193;
  27.                 z ^= *str++;
  28.                 len--;
  29.         }
  30.  
  31.         return z;
  32. }
  33.  
  34. #define STR_OF(str) ((char *)(str + 1))
  35. #define CSTR_OF(str) ((const char *)(str + 1))
  36.  
  37. #define NR_BUCKETS_DEFAULT      (4091)
  38.  
  39. typedef struct lwc_context_s {
  40.         lwc_string **           buckets;
  41.         lwc_hash                bucketcount;
  42. } lwc_context;
  43.  
  44. static lwc_context *ctx = NULL;
  45.  
  46. #define LWC_ALLOC(s) malloc(s)
  47. #define LWC_FREE(p) free(p)
  48.  
  49. typedef lwc_hash (*lwc_hasher)(const char *, size_t);
  50. typedef int (*lwc_strncmp)(const char *, const char *, size_t);
  51. typedef void (*lwc_memcpy)(char *, const char *, size_t);
  52.  
  53. static lwc_error
  54. lwc__initialise(void)
  55. {
  56.         if (ctx != NULL)
  57.                 return lwc_error_ok;
  58.        
  59.         ctx = LWC_ALLOC(sizeof(lwc_context));
  60.        
  61.         if (ctx == NULL)
  62.                 return lwc_error_oom;
  63.        
  64.         memset(ctx, 0, sizeof(lwc_context));
  65.        
  66.         ctx->bucketcount = NR_BUCKETS_DEFAULT;
  67.         ctx->buckets = LWC_ALLOC(sizeof(lwc_string *) * ctx->bucketcount);
  68.        
  69.         if (ctx->buckets == NULL) {
  70.                 LWC_FREE(ctx);
  71.                 ctx = NULL;
  72.                 return lwc_error_oom;
  73.         }
  74.        
  75.         memset(ctx->buckets, 0, sizeof(lwc_string *) * ctx->bucketcount);
  76.        
  77.         return lwc_error_ok;
  78. }
  79.  
  80. static lwc_error
  81. lwc__intern(const char *s, size_t slen,
  82.            lwc_string **ret,
  83.            lwc_hasher hasher,
  84.            lwc_strncmp compare,
  85.            lwc_memcpy copy)
  86. {
  87.         lwc_hash h;
  88.         lwc_hash bucket;
  89.         lwc_string *str;
  90.         lwc_error eret;
  91.        
  92.         assert((s != NULL) || (slen == 0));
  93.         assert(ret);
  94.        
  95.         if (ctx == NULL) {
  96.                 eret = lwc__initialise();
  97.                 if (eret != lwc_error_ok)
  98.                         return eret;
  99.         }
  100.        
  101.         h = hasher(s, slen);
  102.         bucket = h % ctx->bucketcount;
  103.         str = ctx->buckets[bucket];
  104.        
  105.         while (str != NULL) {
  106.                 if ((str->hash == h) && (str->len == slen)) {
  107.                         if (compare(CSTR_OF(str), s, slen) == 0) {
  108.                                 str->refcnt++;
  109.                                 *ret = str;
  110.                                 return lwc_error_ok;
  111.                         }
  112.                 }
  113.                 str = str->next;
  114.         }
  115.        
  116.         /* Add one for the additional NUL. */
  117.         *ret = str = LWC_ALLOC(sizeof(lwc_string) + slen + 1);
  118.        
  119.         if (str == NULL)
  120.                 return lwc_error_oom;
  121.        
  122.         str->prevptr = &(ctx->buckets[bucket]);
  123.         str->next = ctx->buckets[bucket];
  124.         if (str->next != NULL)
  125.                 str->next->prevptr = &(str->next);
  126.         ctx->buckets[bucket] = str;
  127.  
  128.         str->len = slen;
  129.         str->hash = h;
  130.         str->refcnt = 1;
  131.         str->insensitive = NULL;
  132.        
  133.         copy(STR_OF(str), s, slen);
  134.  
  135.         /* Guarantee NUL termination */
  136.         STR_OF(str)[slen] = '\0';
  137.        
  138.         return lwc_error_ok;
  139. }
  140.  
  141. lwc_error
  142. lwc_intern_string(const char *s, size_t slen,
  143.                   lwc_string **ret)
  144. {
  145.         return lwc__intern(s, slen, ret,
  146.                            lwc__calculate_hash,
  147.                            strncmp, (lwc_memcpy)memcpy);
  148. }
  149.  
  150. lwc_error
  151. lwc_intern_substring(lwc_string *str,
  152.                      size_t ssoffset, size_t sslen,
  153.                      lwc_string **ret)
  154. {
  155.         assert(str);
  156.         assert(ret);
  157.        
  158.         if (ssoffset >= str->len)
  159.                 return lwc_error_range;
  160.         if ((ssoffset + sslen) > str->len)
  161.                 return lwc_error_range;
  162.        
  163.         return lwc_intern_string(CSTR_OF(str) + ssoffset, sslen, ret);
  164. }
  165.  
  166. void
  167. lwc_string_destroy(lwc_string *str)
  168. {
  169.         assert(str);
  170.        
  171.         *(str->prevptr) = str->next;
  172.        
  173.         if (str->next != NULL)
  174.                 str->next->prevptr = str->prevptr;
  175.  
  176.         if (str->insensitive != NULL && str->refcnt == 0)
  177.                 lwc_string_unref(str->insensitive);
  178.  
  179. #ifndef NDEBUG
  180.         memset(str, 0xA5, sizeof(*str) + str->len);
  181. #endif
  182.        
  183.         LWC_FREE(str);
  184. }
  185.  
  186. /**** Shonky caseless bits ****/
  187.  
  188. static inline char
  189. lwc__dolower(const char c)
  190. {
  191.         if (c >= 'A' && c <= 'Z')
  192.                 return c + 'a' - 'A';
  193.         return c;
  194. }
  195.  
  196. static inline lwc_hash
  197. lwc__calculate_lcase_hash(const char *str, size_t len)
  198. {
  199.         lwc_hash z = 0x811c9dc5;
  200.        
  201.  
  202.         while (len > 0) {
  203.                 z *= 0x01000193;
  204.                 z ^= lwc__dolower(*str++);
  205.                 len--;
  206.         }
  207.  
  208.         return z;
  209. }
  210.  
  211. static int
  212. lwc__lcase_strncmp(const char *s1, const char *s2, size_t n)
  213. {
  214.         while (n--) {
  215.                 if (*s1++ != lwc__dolower(*s2++))
  216.                         /** @todo Test this somehow? */
  217.                         return 1;
  218.         }
  219.         return 0;
  220. }
  221.  
  222. static void
  223. lwc__lcase_memcpy(char *target, const char *source, size_t n)
  224. {
  225.         while (n--) {
  226.                 *target++ = lwc__dolower(*source++);
  227.         }
  228. }
  229.  
  230. lwc_error
  231. lwc__intern_caseless_string(lwc_string *str)
  232. {
  233.         assert(str);
  234.         assert(str->insensitive == NULL);
  235.        
  236.         return lwc__intern(CSTR_OF(str),
  237.                            str->len, &(str->insensitive),
  238.                            lwc__calculate_lcase_hash,
  239.                            lwc__lcase_strncmp,
  240.                            lwc__lcase_memcpy);
  241. }
  242.  
  243. /**** Iteration ****/
  244.  
  245. void
  246. lwc_iterate_strings(lwc_iteration_callback_fn cb, void *pw)
  247. {
  248.         lwc_hash n;
  249.         lwc_string *str;
  250.        
  251.         if (ctx == NULL)
  252.                 return;
  253.  
  254.         for (n = 0; n < ctx->bucketcount; ++n) {
  255.                 for (str = ctx->buckets[n]; str != NULL; str = str->next)
  256.                         cb(str, pw);
  257.         }
  258. }
  259.