kwqstring.cpp

khtml在gtk上的移植版本

/*
 * Copyright (C) 2004 Apple Computer, Inc.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */


#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <limits.h>
#include <string.h>

#ifdef JS_ENABLED
#include <JavaScriptCore/dtoa.h>
#else
#define kjs_strtod strtod   
#endif

#include "KWQLogging.h"
#include "KWQString.h"
#include "KWQRegExp.h"
#include "KWQTextCodec.h"

#if KWIQ
#include <glib.h>
#include "KWIQMacros.h"
const char QChar::null = 0; 
#endif

#define CHECK_FOR_HANDLE_LEAKS 0

// Why can't I find this in a header anywhere?  It's too bad we have
// to wire knowledge of allocation sizes, but it makes a huge diffence.
#if KWIQ
#define malloc_good_size(size) size
#else
extern "C" {
int malloc_good_size(int size);
}
#endif

#define ALLOC_QCHAR_GOOD_SIZE(X) (malloc_good_size(X*sizeof(QChar))/sizeof(QChar))
#define ALLOC_CHAR_GOOD_SIZE(X) (malloc_good_size(X))

#ifdef QSTRING_DEBUG_ALLOCATIONS

#import <pthread.h>
#import <mach/mach_types.h>

static CFMutableDictionaryRef allocatedBuffers = 0;
#define ALLOCATION_HISTOGRAM_SIZE 128
static uint allocationHistogram[ALLOCATION_HISTOGRAM_SIZE];

static uint stackInstances = 0;
static uint heapInstances = 0;
static uint stringDataInstances = 0;
static uint stringDataHeapInstances = 0;
static uint stringDataDetachments = 0;
static uint handleInstances = 0;

static bool isOnStack(void *ptr)
{
    void *address;
    size_t size;
    pthread_t thisThread = pthread_self();
    
    size = pthread_get_stacksize_np(thisThread);
    address = pthread_get_stackaddr_np(thisThread);
    if (ptr >= (void *)(((char *)address) - size) &&
        ptr <= address)
        return true;
    return false;
}

static void countInstance(void *ptr)
{
    if (isOnStack(ptr))
        stackInstances++;
    else
        heapInstances++;
}

static CFMutableDictionaryRef allocatedBuffers()
{
    if (allocatedBuffers == 0){
        for (int i = 0; i < ALLOCATION_HISTOGRAM_SIZE; i++)
            allocationHistogram[i] = 0;
        allocatedBuffers = CFDictionaryCreateMutable (kCFAllocatorDefault, 1024*8, NULL, NULL);
    }
    return allocatedBuffers;
}

static char *ALLOC_CHAR(int n)
{
    char *ptr = (char *)malloc(n);

    CFDictionarySetValue (allocatedBuffers(), ptr, (void *)n);
    
    if (n >= ALLOCATION_HISTOGRAM_SIZE)
        allocationHistogram[ALLOCATION_HISTOGRAM_SIZE-1]++;
    else
        allocationHistogram[n]++;
    return ptr;
}

static char *REALLOC_CHAR(void *p, int n)
{
    char *ptr = (char *)realloc(p, n);

    CFDictionaryRemoveValue (allocatedBuffers(), p);
    CFDictionarySetValue (allocatedBuffers(), ptr, (const void *)(n));
    if (n >= ALLOCATION_HISTOGRAM_SIZE)
        allocationHistogram[ALLOCATION_HISTOGRAM_SIZE-1]++;
    else
        allocationHistogram[n]++;
    return ptr;
}

static void DELETE_CHAR(void *p)
{
    CFDictionaryRemoveValue (allocatedBuffers(), p);
    free (p);
}

static QChar *ALLOC_QCHAR(int n)
{
    size_t size = (sizeof(QChar)*( n ));
    QChar *ptr = (QChar *)malloc(size);

    CFDictionarySetValue (allocatedBuffers(), ptr, (const void *)size);
    if (size >= ALLOCATION_HISTOGRAM_SIZE)
        allocationHistogram[ALLOCATION_HISTOGRAM_SIZE-1]++;
    else
        allocationHistogram[size]++;
    return ptr;
}

static QChar *REALLOC_QCHAR(void *p, int n)
{
    size_t size = (sizeof(QChar)*( n ));
    QChar *ptr = (QChar *)realloc(p, size);

    CFDictionaryRemoveValue (allocatedBuffers(), p);
    CFDictionarySetValue (allocatedBuffers(), ptr, (const void *)size);
    if (size >= ALLOCATION_HISTOGRAM_SIZE)
        allocationHistogram[ALLOCATION_HISTOGRAM_SIZE-1]++;
    else
        allocationHistogram[size]++;
        
    return ptr;
}

static void DELETE_QCHAR(void *p)
{
    CFDictionaryRemoveValue (allocatedBuffers(), p);
    free (p);
}

void _printQStringAllocationStatistics()
{
    const void **values;
    const void **keys;
    int j, i, count;
    int totalSize = 0;
    int totalAllocations = 0;
    
    count = (int)CFDictionaryGetCount (allocatedBuffers());
    values = (const void **)malloc (count*sizeof(void *));
    keys = (const void **)malloc (count*sizeof(void *));

    CFDictionaryGetKeysAndValues (allocatedBuffers(), keys, values);
    printf ("Leaked strings:\n");
    for (i = 0; i < count; i++){
        char *cp = (char *)keys[i];
        printf ("%04d:  0x%08x size %d \"", i, (unsigned int)keys[i], (unsigned int)values[i]);
        for (j = 0; j < MIN ((int)values[i], 64); j++){
            if (isprint(*cp))
                putchar (*cp);
            cp++;
        }
        printf ("\"\n");
        totalSize += (int)values[i];
    }
    printf ("Total leak %d\n", totalSize);
    
    printf ("\nString size histogram:\n");
    for (i = 0; i < ALLOCATION_HISTOGRAM_SIZE; i++){
        if (allocationHistogram[i])
            printf ("[%d] = %d\n", i, allocationHistogram[i]);
        totalAllocations += allocationHistogram[i];
    }
    printf ("Total allocations %d\n", totalAllocations);
    
    printf ("\nQString instance counts:\n");
    printf ("QString stack allocated instances %d\n", stackInstances);
    printf ("QString heap allocated instances %d\n", heapInstances);
    printf ("KWQStringData instances %d\n", stringDataInstances);
    printf ("KWQStringData heap allocated instances %d\n", stringDataHeapInstances);
    printf ("KWQStringData detachments (copies) %d\n", stringDataDetachments);
    printf ("KWQStringData handles %d\n", handleInstances);
    
    free(keys);
    free(values);
}

#else

#define ALLOC_CHAR( N ) (char*) malloc(N)
#define REALLOC_CHAR( P, N ) (char *) realloc(P,N)
#define DELETE_CHAR( P ) free(P)

#define ALLOC_QCHAR( N ) (QChar*) malloc(sizeof(QChar)*( N ))
#define REALLOC_QCHAR( P, N ) (QChar *) realloc(P,sizeof(QChar)*( N ))
#define DELETE_QCHAR( P ) free( P )

#endif // QSTRING_DEBUG_ALLOCATIONS

#if !KWIQ
#import <mach/vm_map.h>
#import <mach/mach_init.h>
#endif

struct HandleNode;
struct HandlePageNode;


#if !KWIQ // KWIQ: commented out OS X spesific string helper functions
static HandleNode *allocateNode(HandlePageNode *pageNode);
static HandlePageNode *allocatePageNode()

static HandlePageNode *usedNodeAllocationPages = 0;
static HandlePageNode *freeNodeAllocationPages = 0;

static inline void initializeHandleNodes()
{
    if (freeNodeAllocationPages == 0)
        freeNodeAllocationPages = allocatePageNode();
}
#endif

static inline KWQStringData **allocateHandle()
{
#if KWIQ
    return static_cast<KWQStringData **>(malloc(sizeof(KWQStringData *)));

#else    

#if CHECK_FOR_HANDLE_LEAKS
    return static_cast<KWQStringData **>(malloc(sizeof(KWQStringData *)));
#endif

    initializeHandleNodes();
    
#ifdef QSTRING_DEBUG_ALLOCATIONS
    handleInstances++;
#endif
    
    return reinterpret_cast<KWQStringData **>(allocateNode(freeNodeAllocationPages));
#endif
}

static void freeHandle(KWQStringData **);

#define IS_ASCII_QCHAR(c) ((c).unicode() > 0 && (c).unicode() <= 0xff)

static const int caseDelta = ('a' - 'A');

const char * const QString::null = 0;

KWQStringData *QString::shared_null = 0;
KWQStringData **QString::shared_null_handle = 0;

// -------------------------------------------------------------------------
// Utility functions
// -------------------------------------------------------------------------

static inline int ucstrcmp( const QString &as, const QString &bs )
{
    const QChar *a = as.unicode();
    const QChar *b = bs.unicode();
    if ( a == b )
	return 0;
    if ( a == 0 )
	return 1;
    if ( b == 0 )
	return -1;
    int l = kMin(as.length(), bs.length());
    while ( l-- && *a == *b )
	a++,b++;
    if ( l == -1 )
	return ( as.length() - bs.length() );
    return a->unicode() - b->unicode();
}


static bool equal(const QChar *a, const char *b, int l)
{
    ASSERT(l >= 0);
    while (l--) {
        if (*a != *b)
            return false;
	a++; b++;
    }
    return true;
}

// Not a "true" case insensitive compare; only insensitive for plain ASCII.

static bool equalCaseInsensitive(const char *a, const char *b, int l)
{
    ASSERT(l >= 0);
    while (l--) {
        if (g_unichar_tolower(*a) != g_unichar_tolower(*b))
            return false;
	a++; b++;
    }
    return true;
}

static bool equalCaseInsensitive(const QChar *a, const char *b, int l)
{
    ASSERT(l >= 0);
    while (l--) {
        if (g_unichar_tolower(a->unicode()) != g_unichar_tolower(*b))
            return false;
	a++; b++;
    }
    return true;
}

static bool equalCaseInsensitive(const QChar *a, const QChar *b, int l)
{
    ASSERT(l >= 0);
    while (l--) {
        if (g_unichar_tolower(a->unicode()) != g_unichar_tolower(b->unicode()))
            return false;
	a++; b++;
    }
    return true;
}

static inline bool equalCaseInsensitive(char c1, char c2)
{
    return g_unichar_tolower(c1) == g_unichar_tolower(c2);
}

static inline bool equalCaseInsensitive(QChar c1, char c2)
{
    return g_unichar_tolower(c1.unicode()) == g_unichar_tolower(static_cast<unsigned char>(c2));
}

static bool ok_in_base(QChar c, int base)
{
    int uc = c.unicode();
    if (g_unichar_isdigit(uc))
	return uc - '0' < base;
    if (g_unichar_isalpha(uc)) {
        if (base > 36)
            base = 36;
	return (uc >= 'a' && uc < 'a' + base - 10)
            || (uc >= 'A' && uc < 'A' + base - 10);
    }
    return false;
}

// -------------------------------------------------------------------------
// KWQStringData
// -------------------------------------------------------------------------

// FIXME, make constructor explicity take a 'copy' flag.
// This can be used to hand off ownership of allocated data when detaching and
// deleting QStrings.

KWQStringData::KWQStringData() :
	refCount(1), _length(0), _unicode(0), _ascii(0), _maxUnicode(QS_INTERNAL_BUFFER_UCHARS), _isUnicodeValid(0), _isHeapAllocated(0), _maxAscii(QS_INTERNAL_BUFFER_CHARS), _isAsciiValid(1) 
{ 
#ifdef QSTRING_DEBUG_ALLOCATIONS
    stringDataInstances++;
#endif
    _ascii = _internalBuffer;
    _internalBuffer[0] = 0;
}

void KWQStringData::initialize()
{
    refCount = 1;
    _length = 0;
    _unicode = 0;
    _ascii = _internalBuffer;
    _maxUnicode = QS_INTERNAL_BUFFER_UCHARS;
    _isUnicodeValid = 0;
    _maxAscii = QS_INTERNAL_BUFFER_CHARS;
    _isAsciiValid = 1;
    _internalBuffer[0] = 0;
    _isHeapAllocated = 0;
}

// Don't copy data.
KWQStringData::KWQStringData(QChar *u, uint l, uint m) :
	refCount(1), _length(l), _unicode(u), _ascii(0), _maxUnicode(m), _isUnicodeValid(1), _isHeapAllocated(0), _maxAscii(QS_INTERNAL_BUFFER_CHARS), _isAsciiValid(0)
{
    ASSERT(m >= l);
#ifdef QSTRING_DEBUG_ALLOCATIONS
    stringDataInstances++;
#endif
}

// Don't copy data.
void KWQStringData::initialize(QChar *u, uint l, uint m)
{
    ASSERT(m >= l);
    refCount = 1;
    _length = l;
    _unicode = u;
    _ascii = 0;
    _maxUnicode = m;
    _isUnicodeValid = 1;
    _maxAscii = 0;
    _isAsciiValid = 0;
    _isHeapAllocated = 0;
}

// Copy data
KWQStringData::KWQStringData(const QChar *u, uint l)
{
#ifdef QSTRING_DEBUG_ALLOCATIONS
    stringDataInstances++;
#endif
    initialize (u, l);
}

#ifdef QSTRING_DEBUG_ALLOCATIONS
void* KWQStringData::operator new(size_t s)
{
    stringDataHeapInstances++;
    return malloc(s);
}
void KWQStringData::operator delete(void*p)
{
    return free(p);
}
#endif

// Copy data
void KWQStringData::initialize(const QChar *u, uint l)
{
    refCount = 1;
    _length = l;
    _ascii = 0;
    _isUnicodeValid = 1;
    _maxAscii = 0;
    _isAsciiValid = 0;
    _isHeapAllocated = 0;

    if (l > QS_INTERNAL_BUFFER_UCHARS) {
        _maxUnicode = ALLOC_QCHAR_GOOD_SIZE(l);
        _unicode = ALLOC_QCHAR(_maxUnicode);
        memcpy(_unicode, u, l*sizeof(QChar));
    } else {
        _maxUnicode = QS_INTERNAL_BUFFER_UCHARS;
        _unicode = (QChar *)_internalBuffer;
        if (l)
            memcpy(_internalBuffer, u, l*sizeof(QChar));
    }
}


// Copy data
KWQStringData::KWQStringData(const char *a, uint l)
{
#ifdef QSTRING_DEBUG_ALLOCATIONS
    stringDataInstances++;
#endif
    initialize(a, l);
}


// Copy data
void KWQStringData::initialize(const char *a, uint l)
{
    refCount = 1;
    _length = l;
    _unicode = 0;
    _isUnicodeValid = 0;
    _maxUnicode = 0;
    _isAsciiValid = 1;
    _isHeapAllocated = 0;

    if (l > QS_INTERNAL_BUFFER_CHARS) {
        _maxAscii = ALLOC_CHAR_GOOD_SIZE(l+1);
        _ascii = ALLOC_CHAR(_maxAscii);
        if (a)
            memcpy(_ascii, a, l);
        _ascii[l] = 0;
    } else {