Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright © 2010 Intel Corporation
  3.  *
  4.  * Permission is hereby granted, free of charge, to any person obtaining a
  5.  * copy of this software and associated documentation files (the "Software"),
  6.  * to deal in the Software without restriction, including without limitation
  7.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  8.  * and/or sell copies of the Software, and to permit persons to whom the
  9.  * Software is furnished to do so, subject to the following conditions:
  10.  *
  11.  * The above copyright notice and this permission notice (including the next
  12.  * paragraph) shall be included in all copies or substantial portions of the
  13.  * Software.
  14.  *
  15.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18.  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21.  * DEALINGS IN THE SOFTWARE.
  22.  */
  23.  
  24. #include <assert.h>
  25. #include <stdlib.h>
  26. #include <stdarg.h>
  27. #include <stdio.h>
  28. #include <string.h>
  29. #include <stdint.h>
  30.  
  31. /* Android defines SIZE_MAX in limits.h, instead of the standard stdint.h */
  32. #ifdef ANDROID
  33. #include <limits.h>
  34. #endif
  35.  
  36. /* Some versions of MinGW are missing _vscprintf's declaration, although they
  37.  * still provide the symbol in the import library. */
  38. #ifdef __MINGW32__
  39. _CRTIMP int _vscprintf(const char *format, va_list argptr);
  40. #endif
  41.  
  42. #include "ralloc.h"
  43.  
  44. #ifndef va_copy
  45. #ifdef __va_copy
  46. #define va_copy(dest, src) __va_copy((dest), (src))
  47. #else
  48. #define va_copy(dest, src) (dest) = (src)
  49. #endif
  50. #endif
  51.  
  52. #define CANARY 0x5A1106
  53.  
  54. struct ralloc_header
  55. {
  56. #ifdef DEBUG
  57.    /* A canary value used to determine whether a pointer is ralloc'd. */
  58.    unsigned canary;
  59. #endif
  60.  
  61.    struct ralloc_header *parent;
  62.  
  63.    /* The first child (head of a linked list) */
  64.    struct ralloc_header *child;
  65.  
  66.    /* Linked list of siblings */
  67.    struct ralloc_header *prev;
  68.    struct ralloc_header *next;
  69.  
  70.    void (*destructor)(void *);
  71. };
  72.  
  73. typedef struct ralloc_header ralloc_header;
  74.  
  75. static void unlink_block(ralloc_header *info);
  76. static void unsafe_free(ralloc_header *info);
  77.  
  78. static ralloc_header *
  79. get_header(const void *ptr)
  80. {
  81.    ralloc_header *info = (ralloc_header *) (((char *) ptr) -
  82.                                             sizeof(ralloc_header));
  83. #ifdef DEBUG
  84.    assert(info->canary == CANARY);
  85. #endif
  86.    return info;
  87. }
  88.  
  89. #define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header))
  90.  
  91. static void
  92. add_child(ralloc_header *parent, ralloc_header *info)
  93. {
  94.    if (parent != NULL) {
  95.       info->parent = parent;
  96.       info->next = parent->child;
  97.       parent->child = info;
  98.  
  99.       if (info->next != NULL)
  100.          info->next->prev = info;
  101.    }
  102. }
  103.  
  104. void *
  105. ralloc_context(const void *ctx)
  106. {
  107.    return ralloc_size(ctx, 0);
  108. }
  109.  
  110. void *
  111. ralloc_size(const void *ctx, size_t size)
  112. {
  113.    void *block = calloc(1, size + sizeof(ralloc_header));
  114.    ralloc_header *info;
  115.    ralloc_header *parent;
  116.  
  117.    if (unlikely(block == NULL))
  118.       return NULL;
  119.    info = (ralloc_header *) block;
  120.    parent = ctx != NULL ? get_header(ctx) : NULL;
  121.  
  122.    add_child(parent, info);
  123.  
  124. #ifdef DEBUG
  125.    info->canary = CANARY;
  126. #endif
  127.  
  128.    return PTR_FROM_HEADER(info);
  129. }
  130.  
  131. void *
  132. rzalloc_size(const void *ctx, size_t size)
  133. {
  134.    void *ptr = ralloc_size(ctx, size);
  135.    if (likely(ptr != NULL))
  136.       memset(ptr, 0, size);
  137.    return ptr;
  138. }
  139.  
  140. /* helper function - assumes ptr != NULL */
  141. static void *
  142. resize(void *ptr, size_t size)
  143. {
  144.    ralloc_header *child, *old, *info;
  145.  
  146.    old = get_header(ptr);
  147.    info = realloc(old, size + sizeof(ralloc_header));
  148.  
  149.    if (info == NULL)
  150.       return NULL;
  151.  
  152.    /* Update parent and sibling's links to the reallocated node. */
  153.    if (info != old && info->parent != NULL) {
  154.       if (info->parent->child == old)
  155.          info->parent->child = info;
  156.  
  157.       if (info->prev != NULL)
  158.          info->prev->next = info;
  159.  
  160.       if (info->next != NULL)
  161.          info->next->prev = info;
  162.    }
  163.  
  164.    /* Update child->parent links for all children */
  165.    for (child = info->child; child != NULL; child = child->next)
  166.       child->parent = info;
  167.  
  168.    return PTR_FROM_HEADER(info);
  169. }
  170.  
  171. void *
  172. reralloc_size(const void *ctx, void *ptr, size_t size)
  173. {
  174.    if (unlikely(ptr == NULL))
  175.       return ralloc_size(ctx, size);
  176.  
  177.    assert(ralloc_parent(ptr) == ctx);
  178.    return resize(ptr, size);
  179. }
  180.  
  181. void *
  182. ralloc_array_size(const void *ctx, size_t size, unsigned count)
  183. {
  184.    if (count > SIZE_MAX/size)
  185.       return NULL;
  186.  
  187.    return ralloc_size(ctx, size * count);
  188. }
  189.  
  190. void *
  191. rzalloc_array_size(const void *ctx, size_t size, unsigned count)
  192. {
  193.    if (count > SIZE_MAX/size)
  194.       return NULL;
  195.  
  196.    return rzalloc_size(ctx, size * count);
  197. }
  198.  
  199. void *
  200. reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count)
  201. {
  202.    if (count > SIZE_MAX/size)
  203.       return NULL;
  204.  
  205.    return reralloc_size(ctx, ptr, size * count);
  206. }
  207.  
  208. void
  209. ralloc_free(void *ptr)
  210. {
  211.    ralloc_header *info;
  212.  
  213.    if (ptr == NULL)
  214.       return;
  215.  
  216.    info = get_header(ptr);
  217.    unlink_block(info);
  218.    unsafe_free(info);
  219. }
  220.  
  221. static void
  222. unlink_block(ralloc_header *info)
  223. {
  224.    /* Unlink from parent & siblings */
  225.    if (info->parent != NULL) {
  226.       if (info->parent->child == info)
  227.          info->parent->child = info->next;
  228.  
  229.       if (info->prev != NULL)
  230.          info->prev->next = info->next;
  231.  
  232.       if (info->next != NULL)
  233.          info->next->prev = info->prev;
  234.    }
  235.    info->parent = NULL;
  236.    info->prev = NULL;
  237.    info->next = NULL;
  238. }
  239.  
  240. static void
  241. unsafe_free(ralloc_header *info)
  242. {
  243.    /* Recursively free any children...don't waste time unlinking them. */
  244.    ralloc_header *temp;
  245.    while (info->child != NULL) {
  246.       temp = info->child;
  247.       info->child = temp->next;
  248.       unsafe_free(temp);
  249.    }
  250.  
  251.    /* Free the block itself.  Call the destructor first, if any. */
  252.    if (info->destructor != NULL)
  253.       info->destructor(PTR_FROM_HEADER(info));
  254.  
  255.    free(info);
  256. }
  257.  
  258. void
  259. ralloc_steal(const void *new_ctx, void *ptr)
  260. {
  261.    ralloc_header *info, *parent;
  262.  
  263.    if (unlikely(ptr == NULL))
  264.       return;
  265.  
  266.    info = get_header(ptr);
  267.    parent = get_header(new_ctx);
  268.  
  269.    unlink_block(info);
  270.  
  271.    add_child(parent, info);
  272. }
  273.  
  274. void
  275. ralloc_adopt(const void *new_ctx, void *old_ctx)
  276. {
  277.    ralloc_header *new_info, *old_info, *child;
  278.  
  279.    if (unlikely(old_ctx == NULL))
  280.       return;
  281.  
  282.    old_info = get_header(old_ctx);
  283.    new_info = get_header(new_ctx);
  284.  
  285.    /* If there are no children, bail. */
  286.    if (unlikely(old_info->child == NULL))
  287.       return;
  288.  
  289.    /* Set all the children's parent to new_ctx; get a pointer to the last child. */
  290.    for (child = old_info->child; child->next != NULL; child = child->next) {
  291.       child->parent = new_info;
  292.    }
  293.  
  294.    /* Connect the two lists together; parent them to new_ctx; make old_ctx empty. */
  295.    child->next = new_info->child;
  296.    new_info->child = old_info->child;
  297.    old_info->child = NULL;
  298. }
  299.  
  300. void *
  301. ralloc_parent(const void *ptr)
  302. {
  303.    ralloc_header *info;
  304.  
  305.    if (unlikely(ptr == NULL))
  306.       return NULL;
  307.  
  308.    info = get_header(ptr);
  309.    return info->parent ? PTR_FROM_HEADER(info->parent) : NULL;
  310. }
  311.  
  312. static void *autofree_context = NULL;
  313.  
  314. static void
  315. autofree(void)
  316. {
  317.    ralloc_free(autofree_context);
  318. }
  319.  
  320. void *
  321. ralloc_autofree_context(void)
  322. {
  323.    if (unlikely(autofree_context == NULL)) {
  324.       autofree_context = ralloc_context(NULL);
  325.       atexit(autofree);
  326.    }
  327.    return autofree_context;
  328. }
  329.  
  330. void
  331. ralloc_set_destructor(const void *ptr, void(*destructor)(void *))
  332. {
  333.    ralloc_header *info = get_header(ptr);
  334.    info->destructor = destructor;
  335. }
  336.  
  337. char *
  338. ralloc_strdup(const void *ctx, const char *str)
  339. {
  340.    size_t n;
  341.    char *ptr;
  342.  
  343.    if (unlikely(str == NULL))
  344.       return NULL;
  345.  
  346.    n = strlen(str);
  347.    ptr = ralloc_array(ctx, char, n + 1);
  348.    memcpy(ptr, str, n);
  349.    ptr[n] = '\0';
  350.    return ptr;
  351. }
  352.  
  353. char *
  354. ralloc_strndup(const void *ctx, const char *str, size_t max)
  355. {
  356.    size_t n;
  357.    char *ptr;
  358.  
  359.    if (unlikely(str == NULL))
  360.       return NULL;
  361.  
  362.    n = strlen(str);
  363.    if (n > max)
  364.       n = max;
  365.  
  366.    ptr = ralloc_array(ctx, char, n + 1);
  367.    memcpy(ptr, str, n);
  368.    ptr[n] = '\0';
  369.    return ptr;
  370. }
  371.  
  372. /* helper routine for strcat/strncat - n is the exact amount to copy */
  373. static bool
  374. cat(char **dest, const char *str, size_t n)
  375. {
  376.    char *both;
  377.    size_t existing_length;
  378.    assert(dest != NULL && *dest != NULL);
  379.  
  380.    existing_length = strlen(*dest);
  381.    both = resize(*dest, existing_length + n + 1);
  382.    if (unlikely(both == NULL))
  383.       return false;
  384.  
  385.    memcpy(both + existing_length, str, n);
  386.    both[existing_length + n] = '\0';
  387.  
  388.    *dest = both;
  389.    return true;
  390. }
  391.  
  392.  
  393. bool
  394. ralloc_strcat(char **dest, const char *str)
  395. {
  396.    return cat(dest, str, strlen(str));
  397. }
  398.  
  399. bool
  400. ralloc_strncat(char **dest, const char *str, size_t n)
  401. {
  402.    /* Clamp n to the string length */
  403.    size_t str_length = strlen(str);
  404.    if (str_length < n)
  405.       n = str_length;
  406.  
  407.    return cat(dest, str, n);
  408. }
  409.  
  410. char *
  411. ralloc_asprintf(const void *ctx, const char *fmt, ...)
  412. {
  413.    char *ptr;
  414.    va_list args;
  415.    va_start(args, fmt);
  416.    ptr = ralloc_vasprintf(ctx, fmt, args);
  417.    va_end(args);
  418.    return ptr;
  419. }
  420.  
  421. /* Return the length of the string that would be generated by a printf-style
  422.  * format and argument list, not including the \0 byte.
  423.  */
  424. static size_t
  425. printf_length(const char *fmt, va_list untouched_args)
  426. {
  427.    int size;
  428.    char junk;
  429.  
  430.    /* Make a copy of the va_list so the original caller can still use it */
  431.    va_list args;
  432.    va_copy(args, untouched_args);
  433.  
  434. #ifdef _WIN32
  435.    /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1
  436.     * if the number of characters to write is greater than count.
  437.     */
  438.    size = _vscprintf(fmt, args);
  439.    (void)junk;
  440. #else
  441.    size = vsnprintf(&junk, 1, fmt, args);
  442. #endif
  443.    assert(size >= 0);
  444.  
  445.    va_end(args);
  446.  
  447.    return size;
  448. }
  449.  
  450. char *
  451. ralloc_vasprintf(const void *ctx, const char *fmt, va_list args)
  452. {
  453.    size_t size = printf_length(fmt, args) + 1;
  454.  
  455.    char *ptr = ralloc_size(ctx, size);
  456.    if (ptr != NULL)
  457.       vsnprintf(ptr, size, fmt, args);
  458.  
  459.    return ptr;
  460. }
  461.  
  462. bool
  463. ralloc_asprintf_append(char **str, const char *fmt, ...)
  464. {
  465.    bool success;
  466.    va_list args;
  467.    va_start(args, fmt);
  468.    success = ralloc_vasprintf_append(str, fmt, args);
  469.    va_end(args);
  470.    return success;
  471. }
  472.  
  473. bool
  474. ralloc_vasprintf_append(char **str, const char *fmt, va_list args)
  475. {
  476.    size_t existing_length;
  477.    assert(str != NULL);
  478.    existing_length = *str ? strlen(*str) : 0;
  479.    return ralloc_vasprintf_rewrite_tail(str, &existing_length, fmt, args);
  480. }
  481.  
  482. bool
  483. ralloc_asprintf_rewrite_tail(char **str, size_t *start, const char *fmt, ...)
  484. {
  485.    bool success;
  486.    va_list args;
  487.    va_start(args, fmt);
  488.    success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args);
  489.    va_end(args);
  490.    return success;
  491. }
  492.  
  493. bool
  494. ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
  495.                               va_list args)
  496. {
  497.    size_t new_length;
  498.    char *ptr;
  499.  
  500.    assert(str != NULL);
  501.  
  502.    if (unlikely(*str == NULL)) {
  503.       // Assuming a NULL context is probably bad, but it's expected behavior.
  504.       *str = ralloc_vasprintf(NULL, fmt, args);
  505.       return true;
  506.    }
  507.  
  508.    new_length = printf_length(fmt, args);
  509.  
  510.    ptr = resize(*str, *start + new_length + 1);
  511.    if (unlikely(ptr == NULL))
  512.       return false;
  513.  
  514.    vsnprintf(ptr + *start, new_length + 1, fmt, args);
  515.    *str = ptr;
  516.    *start += new_length;
  517.    return true;
  518. }
  519.