server/common/shstr.C

/*
 * shstr.C
 */

#include <cstring>
#include <cstdlib>

#include <tr1/unordered_set>

#include "shstr.h"

struct hash
{
  std::size_t operator ()(const char *s) const
  {
    unsigned long hash = 0;
    unsigned int i = 0;

    /* use the one-at-a-time hash function, which supposedly is
     * better than the djb2-like one used by perl5.005, but
     * certainly is better then the bug used here before.
     * 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;
  }
};

struct equal
{
  bool operator ()(const char *a, const char *b) const
  {
    return !strcmp (a, b);
  }
};

typedef std::tr1::unordered_set<const char *, hash, equal> HT;

static HT ht;

static const char *makevec (const char *s)
{
  int len = strlen (s);

  const char *v = (const char *)(2 + (int *)malloc (sizeof (int) * 2 + len + 1));

  shstr::length (v) = len;
  shstr::refcnt (v) = 1;

  memcpy ((char *)v, s, len + 1);

  return v;
}

const char *shstr::null = makevec ("<nil>");

// what weird misoptimisation is this again?
const shstr undead_name ("undead");

const char *
shstr::find (const char *s)
{
  if (!s)
    return s;

  HT::iterator i = ht.find (s);

  return i != ht.end ()
    ? *i
    : 0;
}

const char *
shstr::intern (const char *s)
{
  if (!s)
    return null;

  if (const char *found = find (s))
    {
      ++refcnt (found);
      return found;
    }

  s = makevec (s);
  ht.insert (s);
  return s;
}

// periodically test refcounts == 0 for a few strings
// this is the ONLY thing that erases stuff from ht. keep it that way.
void
shstr::gc ()
{
  static const char *curpos;

  HT::iterator i = curpos ? ht.find (curpos) : ht.begin ();

  if (i == ht.end ())
    i = ht.begin ();

  // go through all strings roughly once every 4 minutes
  int n = ht.size () / 256 + 16;

  for (;;)
    {
      if (i == ht.end ())
        {
          curpos = 0;
          return;
        }
      else if (!--n)
        break;
      else if (!refcnt (*i))
        {
          HT::iterator o = i++;
          const char *s = *o;
          ht.erase (o);

          //printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s));
          free (-2 + (int *)s);
        }
      else
        ++i;
    }

  curpos = *i;
}

//TODO: this should of course not be here
/* buf_overflow() - we don't want to exceed the buffer size of 
 * buf1 by adding on buf2! Returns true if overflow will occur.
 */

int 
buf_overflow (const char *buf1, const char *buf2, int bufsize)
{
    int len1 = 0, len2 = 0;

    if (buf1)
        len1 = strlen (buf1);
    if (buf2)
        len2 = strlen (buf2);
    if ((len1 + len2) >= bufsize)
        return 1;
    return 0;
}

Revision:	1.8
Committed:	Mon Sep 4 11:07:59 2006 UTC (17 years, 8 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.7:	+4 -1 lines
Log Message:	Changes... - alternative shstr representation, saves code - use glibs splice memory allocator (seems slower) - use simpler memory/lifetime management for objects, no recycling
#	Content
1	/*
2	* shstr.C
3	*/
4
5	#include <cstring>
6	#include <cstdlib>
7
8	#include <tr1/unordered_set>
9
10	#include "shstr.h"
11
12	struct hash
13	{
14	std::size_t operator ()(const char *s) const
15	{
16	unsigned long hash = 0;
17	unsigned int i = 0;
18
19	/* use the one-at-a-time hash function, which supposedly is
20	* better than the djb2-like one used by perl5.005, but
21	* certainly is better then the bug used here before.
22	* see http://burtleburtle.net/bob/hash/doobs.html
23	*/
24	while (*s)
25	{
26	hash += *s++;
27	hash += hash << 10;
28	hash ^= hash >> 6;
29	}
30
31	hash += hash << 3;
32	hash ^= hash >> 11;
33	hash += hash << 15;
34
35	return hash;
36	}
37	};
38
39	struct equal
40	{
41	bool operator ()(const char a, const char b) const
42	{
43	return !strcmp (a, b);
44	}
45	};
46
47	typedef std::tr1::unordered_set<const char *, hash, equal> HT;
48
49	static HT ht;
50
51	static const char makevec (const char s)
52	{
53	int len = strlen (s);
54
55	const char v = (const char )(2 + (int )malloc (sizeof (int) 2 + len + 1));
56
57	shstr::length (v) = len;
58	shstr::refcnt (v) = 1;
59
60	memcpy ((char *)v, s, len + 1);
61
62	return v;
63	}
64
65	const char *shstr::null = makevec ("<nil>");
66
67	// what weird misoptimisation is this again?
68	const shstr undead_name ("undead");
69
70	const char *
71	shstr::find (const char *s)
72	{
73	if (!s)
74	return s;
75
76	HT::iterator i = ht.find (s);
77
78	return i != ht.end ()
79	? *i
80	: 0;
81	}
82
83	const char *
84	shstr::intern (const char *s)
85	{
86	if (!s)
87	return null;
88
89	if (const char *found = find (s))
90	{
91	++refcnt (found);
92	return found;
93	}
94
95	s = makevec (s);
96	ht.insert (s);
97	return s;
98	}
99
100	// periodically test refcounts == 0 for a few strings
101	// this is the ONLY thing that erases stuff from ht. keep it that way.
102	void
103	shstr::gc ()
104	{
105	static const char *curpos;
106
107	HT::iterator i = curpos ? ht.find (curpos) : ht.begin ();
108
109	if (i == ht.end ())
110	i = ht.begin ();
111
112	// go through all strings roughly once every 4 minutes
113	int n = ht.size () / 256 + 16;
114
115	for (;;)
116	{
117	if (i == ht.end ())
118	{
119	curpos = 0;
120	return;
121	}
122	else if (!--n)
123	break;
124	else if (!refcnt (*i))
125	{
126	HT::iterator o = i++;
127	const char s = o;
128	ht.erase (o);
129
130	//printf ("GC %4d %3d %d >%s<%d\n", (int)ht.size (), n, shstr::refcnt (s), s, shstr::length (s));
131	free (-2 + (int *)s);
132	}
133	else
134	++i;
135	}
136
137	curpos = *i;
138	}
139
140	//TODO: this should of course not be here
141	/* buf_overflow() - we don't want to exceed the buffer size of
142	* buf1 by adding on buf2! Returns true if overflow will occur.
143	*/
144
145	int
146	buf_overflow (const char buf1, const char buf2, int bufsize)
147	{
148	int len1 = 0, len2 = 0;
149
150	if (buf1)
151	len1 = strlen (buf1);
152	if (buf2)
153	len2 = strlen (buf2);
154	if ((len1 + len2) >= bufsize)
155	return 1;
156	return 0;
157	}
158