ustring.cpp

khtml在gtk上的移植版本

// -*- c-basic-offset: 2 -*-
/*
 *  This file is part of the KDE libraries
 *  Copyright (C) 1999-2000 Harri Porten ([e-mail])
 *  Copyright (C) 2003 Apple Computer, Inc.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Library General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Library General Public License for more details.
 *
 *  You should have received a copy of the GNU Library General Public License
 *  along with this library; see the file COPYING.LIB.  If not, write to
 *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 *  Boston, MA 02111-1307, USA.
 *
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#ifdef HAVE_STRINGS_H
#include <strings.h>
#endif

#include "ustring.h"
#include "operations.h"
#include "identifier.h"
#include <math.h>
#include "dtoa.h"

#if APPLE_CHANGES
// malloc_good_size is not prototyped anywhere!
extern "C" {
  size_t malloc_good_size(size_t size);
}
#endif

namespace KJS {

extern const double NaN;
extern const double Inf;

CString::CString(const char *c)
{
  length = strlen(c);
  data = new char[length+1];
  memcpy(data, c, length + 1);
}

CString::CString(const char *c, int len)
{
  length = len;
  data = new char[len+1];
  memcpy(data, c, len);
  data[len] = 0;
}

CString::CString(const CString &b)
{
  length = b.length;
  if (length > 0 && b.data) {
    data = new char[length+1];
    memcpy(data, b.data, length + 1);
  }
  else {
    data = 0;
  }
}

CString::~CString()
{
  delete [] data;
}

CString &CString::append(const CString &t)
{
  char *n;
  n = new char[length+t.length+1];
  if (length)
    memcpy(n, data, length);
  if (t.length)
    memcpy(n+length, t.data, t.length);
  length += t.length;
  n[length] = 0;

  delete [] data;
  data = n;

  return *this;
}

CString &CString::operator=(const char *c)
{
  if (data)
    delete [] data;
  length = strlen(c);
  data = new char[length+1];
  memcpy(data, c, length + 1);

  return *this;
}

CString &CString::operator=(const CString &str)
{
  if (this == &str)
    return *this;

  if (data)
    delete [] data;
  length = str.length;
  if (length > 0 && str.data) {
    data = new char[length + 1];
    memcpy(data, str.data, length + 1);
  }
  else {
    data = 0;
  }

  return *this;
}

bool KJS::operator==(const KJS::CString& c1, const KJS::CString& c2)
{
  int len = c1.size();
  return len == c2.size() && (len == 0 || memcmp(c1.c_str(), c2.c_str(), len) == 0);
}

UString::Rep UString::Rep::null = { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 };
UString::Rep UString::Rep::empty = { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 };
const int normalStatBufferSize = 4096;
static char *statBuffer = 0;
static int statBufferSize = 0;

UChar UChar::toLower() const
{
  // ### properly support unicode tolower
  if (uc >= 256 || islower(uc))
    return *this;

  return (unsigned char)tolower(uc);
}

UChar UChar::toUpper() const
{
  if (uc >= 256 || isupper(uc))
    return *this;

  return (unsigned char)toupper(uc);
}

UCharReference& UCharReference::operator=(UChar c)
{
  str->detach();
  if (offset < str->rep->len)
    *(str->rep->data() + offset) = c;
  /* TODO: lengthen string ? */
  return *this;
}

UChar& UCharReference::ref() const
{
  if (offset < str->rep->len)
    return *(str->rep->data() + offset);
  else {
    static UChar callerBetterNotModifyThis('\0');
    return callerBetterNotModifyThis;
  }
}

UString::Rep *UString::Rep::create(UChar *d, int l)
{
  Rep *r = new Rep;
  r->offset = 0;
  r->len = l;
  r->rc = 1;
  r->_hash = 0;
  r->isIdentifier = 0;
  r->baseString = 0;
  r->buf = d;
  r->usedCapacity = l;
  r->capacity = l;
  r->usedPreCapacity = 0;
  r->preCapacity = 0;
  return r;
}

UString::Rep *UString::Rep::create(Rep *base, int offset, int length)
{
  assert(base);

  int baseOffset = base->offset;

  if (base->baseString) {
    base = base->baseString;
  }

  assert(-(offset + baseOffset) <= base->usedPreCapacity);
  assert(offset + baseOffset + length <= base->usedCapacity);

  Rep *r = new Rep;
  r->offset = baseOffset + offset;
  r->len = length;
  r->rc = 1;
  r->_hash = 0;
  r->isIdentifier = 0;
  r->baseString = base;
  base->ref();
  r->buf = 0;
  r->usedCapacity = 0;
  r->capacity = 0;
  r->usedPreCapacity = 0;
  r->preCapacity = 0;
  return r;
}

void UString::Rep::destroy()
{
  if (isIdentifier)
    Identifier::remove(this);
  if (baseString) {
    baseString->deref();
  } else {
    free(buf);
  }
  delete this;
}

// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
// or anything like that.
const unsigned PHI = 0x9e3779b9U;

// This hash algorithm comes from:
// http://burtleburtle.net/bob/hash/hashfaq.html
// http://burtleburtle.net/bob/hash/doobs.html
unsigned UString::Rep::computeHash(const UChar *s, int length)
{
    int prefixLength = length < 8 ? length : 8;
    int suffixPosition = length < 16 ? 8 : length - 8;

    unsigned h = PHI;
    h += length;
    h += (h << 10); 
    h ^= (h << 6); 

    for (int i = 0; i < prefixLength; i++) {
        h += s[i].uc; 
	h += (h << 10); 
	h ^= (h << 6); 
    }
    for (int i = suffixPosition; i < length; i++){
        h += s[i].uc; 
	h += (h << 10); 
	h ^= (h << 6); 
    }

    h += (h << 3);
    h ^= (h >> 11);
    h += (h << 15);
 
    if (h == 0)
        h = 0x80000000;

    return h;
}

// This hash algorithm comes from:
// http://burtleburtle.net/bob/hash/hashfaq.html
// http://burtleburtle.net/bob/hash/doobs.html
unsigned UString::Rep::computeHash(const char *s)
{
    int length = strlen(s);
    int prefixLength = length < 8 ? length : 8;
    int suffixPosition = length < 16 ? 8 : length - 8;

    unsigned h = PHI;
    h += length;
    h += (h << 10); 
    h ^= (h << 6); 

    for (int i = 0; i < prefixLength; i++) {
        h += (unsigned char)s[i];
	h += (h << 10); 
	h ^= (h << 6); 
    }
    for (int i = suffixPosition; i < length; i++) {
        h += (unsigned char)s[i];
	h += (h << 10); 
	h ^= (h << 6); 
    }

    h += (h << 3);
    h ^= (h >> 11);
    h += (h << 15);

    if (h == 0)
        h = 0x80000000;

    return h;
}

// put these early so they can be inlined
inline int UString::expandedSize(int size, int otherSize) const
{
  int s = (size * 11 / 10) + 1 + otherSize;
#if APPLE_CHANGES
//  s = malloc_good_size(s * sizeof(UChar)) / sizeof(UChar);
#endif
  return s;
}

inline int UString::usedCapacity() const
{
  return rep->baseString ? rep->baseString->usedCapacity : rep->usedCapacity;
}

inline int UString::usedPreCapacity() const
{
  return rep->baseString ? rep->baseString->usedPreCapacity : rep->usedPreCapacity;
}

void UString::expandCapacity(int requiredLength)
{
  Rep *r = rep->baseString ? rep->baseString : rep;

  if (requiredLength > r->capacity) {
    int newCapacity = expandedSize(requiredLength, r->preCapacity);
    r->buf = static_cast<UChar *>(realloc(r->buf, newCapacity * sizeof(UChar)));
    r->capacity = newCapacity - r->preCapacity;
  }
  if (requiredLength > r->usedCapacity) {
    r->usedCapacity = requiredLength;
  }
}

void UString::expandPreCapacity(int requiredPreCap)
{
  Rep *r = rep->baseString ? rep->baseString : rep;

  if (requiredPreCap > r->preCapacity) {
    int newCapacity = expandedSize(requiredPreCap, r->capacity);
    int delta = newCapacity - r->capacity - r->preCapacity;

    UChar *newBuf = static_cast<UChar *>(malloc(newCapacity * sizeof(UChar)));
    memcpy(newBuf + delta, r->buf, (r->capacity + r->preCapacity) * sizeof(UChar));
    free(r->buf);
    r->buf = newBuf;

    r->preCapacity = newCapacity - r->capacity;
  }
  if (requiredPreCap > r->usedPreCapacity) {
    r->usedPreCapacity = requiredPreCap;
  }
}


UString::UString()
{
  attach(&Rep::null);
}

UString::UString(char c)
{
    UChar *d = static_cast<UChar *>(malloc(sizeof(UChar)));
    d[0] = c;
    rep = Rep::create(d, 1);
}

UString::UString(const char *c)
{
  if (!c) {
    attach(&Rep::null);
    return;
  }
  int length = strlen(c);
  if (length == 0) {
    attach(&Rep::empty);
    return;
  }
  UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) * length));
  for (int i = 0; i < length; i++)
    d[i].uc = c[i];
  rep = Rep::create(d, length);
}

UString::UString(const UChar *c, int length)
{
  if (length == 0) {
    attach(&Rep::empty);
    return;
  }
  UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) *length));
  memcpy(d, c, length * sizeof(UChar));
  rep = Rep::create(d, length);
}

UString::UString(UChar *c, int length, bool copy)
{
  if (length == 0) {
    attach(&Rep::empty);
    return;
  }
  UChar *d;
  if (copy) {
    d = static_cast<UChar *>(malloc(sizeof(UChar) * length));
    memcpy(d, c, length * sizeof(UChar));
  } else
    d = c;
  rep = Rep::create(d, length);
}

UString::UString(const UString &a, const UString &b)
{
  int aSize = a.size();
  int aOffset = a.rep->offset;
  int bSize = b.size();
  int bOffset = b.rep->offset;
  int length = aSize + bSize;

  // possible cases:
 
  if (aSize == 0) {
    // a is empty
    attach(b.rep);
  } else if (bSize == 0) {
    // b is empty
    attach(a.rep);
  } else if (aOffset + aSize == a.usedCapacity() && 4 * aSize >= bSize &&
	     (-bOffset != b.usedPreCapacity() || aSize >= bSize)) {
    // - a reaches the end of its buffer so it qualifies for shared append
    // - also, it's at least a quarter the length of b - appending to a much shorter
    //   string does more harm than good
    // - however, if b qualifies for prepend and is longer than a, we'd rather prepend
    UString x(a);
    x.expandCapacity(aOffset + length);
    memcpy(const_cast<UChar *>(a.data() + aSize), b.data(), bSize * sizeof(UChar));
    rep = Rep::create(a.rep, 0, length);
  } else if (-bOffset == b.usedPreCapacity() && 4 * bSize >= aSize) {
    // - b reaches the beginning of its buffer so it qualifies for shared prepend
    // - also, it's at least a quarter the length of a - prepending to a much shorter
    //   string does more harm than good
    UString y(b);
    y.expandPreCapacity(-bOffset + aSize);
    memcpy(const_cast<UChar *>(b.data() - aSize), a.data(), aSize * sizeof(UChar));
    rep = Rep::create(b.rep, -aSize, length);
  } else {
    // a does not qualify for append, and b does not qualify for prepend, gotta make a whole new string
    int newCapacity = expandedSize(length, 0);
    UChar *d = static_cast<UChar *>(malloc(sizeof(UChar) * newCapacity));
    memcpy(d, a.data(), aSize * sizeof(UChar));
    memcpy(d + aSize, b.data(), bSize * sizeof(UChar));
    rep = Rep::create(d, length);
    rep->capacity = newCapacity;
  }
}

const UString &UString::null()
{
  static UString n;
  return n;
}

UString UString::from(int i)
{
  return from((long)i);
}

UString UString::from(unsigned int u)
{
  UChar buf[20];
  UChar *end = buf + 20;
  UChar *p = end;
  
  if (u == 0) {
    *--p = '0';
  } else {
    while (u) {
      *--p = (unsigned short)((u % 10) + '0');
      u /= 10;