<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
On 04/05/2012 11:09 AM, Gedare Bloom wrote:
<blockquote
cite="mid:CAC82fA3-jasf+0CnYdXJ66xhAdt2-S0GzfEsAgsEj4KB_A0tBA@mail.gmail.com"
type="cite">
<pre wrap="">On Thu, Apr 5, 2012 at 10:44 AM, 阿四 <a class="moz-txt-link-rfc2396E" href="mailto:ashi08104@gmail.com"><ashi08104@gmail.com></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">And another idea of hash + map, if the map part is a sub rbtree, then
the
size of hash table can be not too big, the search operation could
benifit
from the rbtree's O(lg(n)) speed, could it be a candidate of the
solution?
</pre>
</blockquote>
<pre wrap="">You mean to use a hash-array with an rbtree to handle collisions?
</pre>
</blockquote>
<pre wrap="">
Yeah, I mean it.
</pre>
<blockquote type="cite">
<pre wrap="">
It
could work, and be faster on average than just using an rbtree without
losing any worst-case time. The space overhead might be quite a bit
more to have multiple rbtree control headers and also the extra
overhead of rbtree nodes. I think that any rbtree- or chain-based
approach shifts the problem of determining the number of Keys to be
the problem of determining the number of nodes, since we cannot assume
that the Key data has a node embedded inside of it.
</pre>
</blockquote>
<pre wrap="">Gedare, I didn't quite understand this. Does rbtree approach has the problem
of determining the number of nodes? I think when the key_create() function
called, only a empty rbtree create. And when key_setspecific() function
called, a node is added to rbtree. Or you mean create a 'proper' big rbtree
when key_create(), which frontloads the insert node cost to key_create() as
you mention above? I understand when using the hash approach, determing the
number of slots(I'm confused with the Keys you use here, I guess Keys here
is the slots in hash table) of hash table is the problem of determining the
number of nodes.
</pre>
</blockquote>
<pre wrap="">It depends on the restrictions on key_create and key_setspecific; if
creation is allowed to block/fail then dynamic allocation might be ok.
I haven't looked closely enough to tell. In that case you can create
an rbtree on-the-fly by allocating it when there is a collision and
inserting the colliding nodes to it. You could also just as easily use
a linked-list (chain). The colliding nodes will need to be embedded
inside some other structure like
struct {
RBTree_Node r; // or Chain_Node
void * user_data;
}
this structure would have to be allocated as well whenever inserting a
new key (setspecific). We need to better define the restrictions on
the keys in order to understand what kind of solutions we can use.
Restrictions means timing and memory constraints, whether operations
can block..maybe others.
</pre>
</blockquote>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<a
href="http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_setspecific.html">http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_setspecific.html</a><br>
allows pthread_setspecific to return ENOMEM. Is that a hint?<br>
<blockquote
cite="mid:CAC82fA3-jasf+0CnYdXJ66xhAdt2-S0GzfEsAgsEj4KB_A0tBA@mail.gmail.com"
type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">I don't see why we don't just put a pointer to the Key in the tcb.
</pre>
</blockquote>
<pre wrap="">
Does it mean delete the POSIX Key data structure, and let the Thread
Specific Data be managed in TCB?
</pre>
</blockquote>
<pre wrap="">Yeah. We could define generic thread-specific data at the score level.
I'm not sure if this is a good idea.
</pre>
</blockquote>
It isn't if generic. It could be part of the POSIX API thread
extension<br>
structure.<br>
<br>
But it helps with unlimited threads but not with unlimited keys<br>
if you use a simple array.<br>
<br>
But a hash/rbtree for "keys used by this thread" might be an
implementation<br>
option. That is different than "threads using this key" which puts<br>
the management structure in keys.<br>
<br>
You also have to consider the case of deleting threads and deleting<br>
keys and what is required to clean up outstanding memory.<br>
It is simple now. But it is possible that you have a "management<br>
structure" in one object (key or thread) and a "clean up" structure<br>
on the other. <br>
<br>
I am sure you don't want to do a scan of all thread/keys and<br>
then see if it is impacted by a key/thread delete.<br>
<br>
I hope that makes sense.<br>
structure/list <br>
<br>
<br>
<blockquote
cite="mid:CAC82fA3-jasf+0CnYdXJ66xhAdt2-S0GzfEsAgsEj4KB_A0tBA@mail.gmail.com"
type="cite">
<pre wrap="">
-Gedare
</pre>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
Joel Sherrill, Ph.D. Director of Research& Development
<a class="moz-txt-link-abbreviated" href="mailto:joel.sherrill@OARcorp.com">joel.sherrill@OARcorp.com</a> On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985
</pre>
</body>
</html>