ermyth/src/shstr.C

/*
 * shstr.C: Shared string class
 *
 * Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
 * Rights to this code are as documented in COPYING.
 */

static char const rcsid[] = "$Id: shstr.C,v 1.2 2007-09-16 18:54:45 pippijn Exp $";

#include <ermyth/shstr.h>

shstr::shstr (char const * const str)
{
  insert (str);
}

shstr::shstr (const shstr &rhs)
{
  insert (rhs.m_str);
}

shstr::~shstr ()
{
  erase ();
}

char const * const 
shstr::c_str () const
{
  return m_str;
}

shstr::size_type
shstr::length () const
{
  return m_len;
}

shstr &
shstr::operator = (char const * const rhs)
{
  erase ();
  insert (rhs);

  return *this;
}

shstr &
shstr::operator = (const shstr &rhs)
{
  if (m_str == rhs.m_str)
    return *this;

  erase ();
  insert (rhs.m_str);

  return *this;
}

bool
shstr::operator == (const shstr &rhs) const
{
  return m_str == rhs.m_str;
}

bool
shstr::operator != (const shstr &rhs) const
{
  return m_str != rhs.m_str;
}

// string manager functions
shentry *
shstr::prepare (char const * const str)
{
  size_t n = hash (str);
  pairs::iterator it = find (str, n);

  shentry *entry;

  if (it == m_buckets[n].end ())
    {
      entry = new shentry (str, n);
      m_buckets[n].push_back (entry);
    }
  else
    entry = *it;

  return entry;
}

bool
shstr::unref (char const * const str)
{
  size_t n = hash (str);
  pairs::iterator it = find (str, n);

  if (it == m_buckets[n].end ())
    return false;
  else
    {
      shentry *entry =  *it;

      --entry->m_refcnt;

      if (entry->m_refcnt == 0)
        {
          m_buckets[n].erase (it);
          delete entry;
          return true;
        }
      else
        return false;
    }
}

const shentry *
shstr::get (char const * const str)
{
  size_t n = hash (str);
  pairs::iterator it = find (str, n);
  if (it == m_buckets[n].end ())
    return NULL;
  else
    return *it;
}

shstr::pairs::iterator
shstr::find (char const * const str, size_t n)
{
  pairs &bucket = m_buckets[n];
  pairs::iterator it = bucket.begin ();
  pairs::iterator et = bucket.end ();

  while (it != et)
    {
      /* we first check hash equality, because if the hash is not
       * equal, then the string most definately is not
       */
      if (n == (*it)->m_hash && __builtin_expect (!strcmp ((*it)->m_str, str), 0))
        return it;
      ++it;
    }

  return et;
}

size_t
shstr::hash (char const * const str)
{
  char const *s = str;
  unsigned long hash = 0;

  // use the one-at-a-time hash function
  // see http://burtleburtle.net/bob/hash/doobs.html
  while (*s)
    {
      hash += *s++;
      hash += hash << 10;
      hash ^= hash >>  6;
    }

  hash += hash <<  3;
  hash ^= hash >> 11;
  hash += hash << 15;

  return hash % m_bucketcnt;
}

char const * const 
shstr::insert (char const * const str, size_t *size)
{
  shentry *entry = prepare (str);
  ++entry->m_refcnt;

  if (entry->m_refcnt == 1)
    ++m_cnt;
  *size = entry->m_len;

  return entry->m_str;
}

void
shstr::erase (char const * const str)
{
  bool removed = unref (str);
  if (removed)
    --m_cnt;
}

size_t
shstr::refs (char const * const str)
{
  const shentry *entry = get (str);
  if (entry == NULL)
    return 0;
  else
    return entry->m_refcnt;
}

size_t
shstr::strcnt ()
{
  return m_cnt;
}

size_t shstr::m_cnt = 0;
size_t shstr::m_bucketcnt = 1024;
shstr::pairs *shstr::m_buckets;
Revision:	1.3
Committed:	Sat Sep 22 14:27:30 2007 UTC (16 years, 8 months ago) by pippijn
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.2:	+1 -1 lines
State:	*FILE REMOVED*
Log Message:	split up ermyth into ermyth-modules, libermyth (currently just ermyth-util) and ermyth-core
#	User	Rev	Content
1	pippijn	1.2	/*
2			* shstr.C: Shared string class
3			*
4			* Copyright © 2007 Pippijn van Steenhoven / The Ermyth Team
5			* Rights to this code are as documented in COPYING.
6			*/
7
8	pippijn	1.3	static char const rcsid[] = "$Id: shstr.C,v 1.2 2007-09-16 18:54:45 pippijn Exp $";
9	pippijn	1.2
10	pippijn	1.1	#include <ermyth/shstr.h>
11
12			shstr::shstr (char const * const str)
13			{
14			insert (str);
15			}
16
17			shstr::shstr (const shstr &rhs)
18			{
19			insert (rhs.m_str);
20			}
21
22			shstr::~shstr ()
23			{
24			erase ();
25			}
26
27			char const * const
28			shstr::c_str () const
29			{
30			return m_str;
31			}
32
33			shstr::size_type
34			shstr::length () const
35			{
36			return m_len;
37			}
38
39			shstr &
40			shstr::operator = (char const * const rhs)
41			{
42			erase ();
43			insert (rhs);
44
45			return *this;
46			}
47
48			shstr &
49			shstr::operator = (const shstr &rhs)
50			{
51			if (m_str == rhs.m_str)
52			return *this;
53
54			erase ();
55			insert (rhs.m_str);
56
57			return *this;
58			}
59
60			bool
61			shstr::operator == (const shstr &rhs) const
62			{
63			return m_str == rhs.m_str;
64			}
65
66			bool
67			shstr::operator != (const shstr &rhs) const
68			{
69			return m_str != rhs.m_str;
70			}
71
72			// string manager functions
73			shentry *
74			shstr::prepare (char const * const str)
75			{
76			size_t n = hash (str);
77			pairs::iterator it = find (str, n);
78
79			shentry *entry;
80
81			if (it == m_buckets[n].end ())
82			{
83			entry = new shentry (str, n);
84			m_buckets[n].push_back (entry);
85			}
86			else
87			entry = *it;
88
89			return entry;
90			}
91
92			bool
93			shstr::unref (char const * const str)
94			{
95			size_t n = hash (str);
96			pairs::iterator it = find (str, n);
97
98			if (it == m_buckets[n].end ())
99			return false;
100			else
101			{
102			shentry entry = it;
103
104			--entry->m_refcnt;
105
106			if (entry->m_refcnt == 0)
107			{
108			m_buckets[n].erase (it);
109			delete entry;
110			return true;
111			}
112			else
113			return false;
114			}
115			}
116
117			const shentry *
118			shstr::get (char const * const str)
119			{
120			size_t n = hash (str);
121			pairs::iterator it = find (str, n);
122			if (it == m_buckets[n].end ())
123			return NULL;
124			else
125			return *it;
126			}
127
128			shstr::pairs::iterator
129			shstr::find (char const * const str, size_t n)
130			{
131			pairs &bucket = m_buckets[n];
132			pairs::iterator it = bucket.begin ();
133			pairs::iterator et = bucket.end ();
134
135			while (it != et)
136			{
137			/* we first check hash equality, because if the hash is not
138			* equal, then the string most definately is not
139			*/
140			if (n == (it)->m_hash && __builtin_expect (!strcmp ((it)->m_str, str), 0))
141			return it;
142			++it;
143			}
144
145			return et;
146			}
147
148			size_t
149			shstr::hash (char const * const str)
150			{
151			char const *s = str;
152			unsigned long hash = 0;
153
154			// use the one-at-a-time hash function
155			// see http://burtleburtle.net/bob/hash/doobs.html
156			while (*s)
157			{
158			hash += *s++;
159			hash += hash << 10;
160			hash ^= hash >> 6;
161			}
162
163			hash += hash << 3;
164			hash ^= hash >> 11;
165			hash += hash << 15;
166
167			return hash % m_bucketcnt;
168			}
169
170			char const * const
171			shstr::insert (char const * const str, size_t *size)
172			{
173			shentry *entry = prepare (str);
174			++entry->m_refcnt;
175
176			if (entry->m_refcnt == 1)
177			++m_cnt;
178			*size = entry->m_len;
179
180			return entry->m_str;
181			}
182
183			void
184			shstr::erase (char const * const str)
185			{
186			bool removed = unref (str);
187			if (removed)
188			--m_cnt;
189			}
190
191			size_t
192			shstr::refs (char const * const str)
193			{
194			const shentry *entry = get (str);
195			if (entry == NULL)
196			return 0;
197			else
198			return entry->m_refcnt;
199			}
200
201			size_t
202			shstr::strcnt ()
203			{
204			return m_cnt;
205			}
206
207			size_t shstr::m_cnt = 0;
208			size_t shstr::m_bucketcnt = 1024;
209			shstr::pairs *shstr::m_buckets;