Search Results

Search found 105 results on 5 pages for 'reed knackstedt'.

Page 5/5 | < Previous Page | 1 2 3 4 5 

  • PTLQueue : a scalable bounded-capacity MPMC queue

    - by Dave
    Title: Fast concurrent MPMC queue -- I've used the following concurrent queue algorithm enough that it warrants a blog entry. I'll sketch out the design of a fast and scalable multiple-producer multiple-consumer (MPSC) concurrent queue called PTLQueue. The queue has bounded capacity and is implemented via a circular array. Bounded capacity can be a useful property if there's a mismatch between producer rates and consumer rates where an unbounded queue might otherwise result in excessive memory consumption by virtue of the container nodes that -- in some queue implementations -- are used to hold values. A bounded-capacity queue can provide flow control between components. Beware, however, that bounded collections can also result in resource deadlock if abused. The put() and take() operators are partial and wait for the collection to become non-full or non-empty, respectively. Put() and take() do not allocate memory, and are not vulnerable to the ABA pathologies. The PTLQueue algorithm can be implemented equally well in C/C++ and Java. Partial operators are often more convenient than total methods. In many use cases if the preconditions aren't met, there's nothing else useful the thread can do, so it may as well wait via a partial method. An exception is in the case of work-stealing queues where a thief might scan a set of queues from which it could potentially steal. Total methods return ASAP with a success-failure indication. (It's tempting to describe a queue or API as blocking or non-blocking instead of partial or total, but non-blocking is already an overloaded concurrency term. Perhaps waiting/non-waiting or patient/impatient might be better terms). It's also trivial to construct partial operators by busy-waiting via total operators, but such constructs may be less efficient than an operator explicitly and intentionally designed to wait. A PTLQueue instance contains an array of slots, where each slot has volatile Turn and MailBox fields. The array has power-of-two length allowing mod/div operations to be replaced by masking. We assume sensible padding and alignment to reduce the impact of false sharing. (On x86 I recommend 128-byte alignment and padding because of the adjacent-sector prefetch facility). Each queue also has PutCursor and TakeCursor cursor variables, each of which should be sequestered as the sole occupant of a cache line or sector. You can opt to use 64-bit integers if concerned about wrap-around aliasing in the cursor variables. Put(null) is considered illegal, but the caller or implementation can easily check for and convert null to a distinguished non-null proxy value if null happens to be a value you'd like to pass. Take() will accordingly convert the proxy value back to null. An advantage of PTLQueue is that you can use atomic fetch-and-increment for the partial methods. We initialize each slot at index I with (Turn=I, MailBox=null). Both cursors are initially 0. All shared variables are considered "volatile" and atomics such as CAS and AtomicFetchAndIncrement are presumed to have bidirectional fence semantics. Finally T is the templated type. I've sketched out a total tryTake() method below that allows the caller to poll the queue. tryPut() has an analogous construction. Zebra stripping : alternating row colors for nice-looking code listings. See also google code "prettify" : https://code.google.com/p/google-code-prettify/ Prettify is a javascript module that yields the HTML/CSS/JS equivalent of pretty-print. -- pre:nth-child(odd) { background-color:#ff0000; } pre:nth-child(even) { background-color:#0000ff; } border-left: 11px solid #ccc; margin: 1.7em 0 1.7em 0.3em; background-color:#BFB; font-size:12px; line-height:65%; " // PTLQueue : Put(v) : // producer : partial method - waits as necessary assert v != null assert Mask = 1 && (Mask & (Mask+1)) == 0 // Document invariants // doorway step // Obtain a sequence number -- ticket // As a practical concern the ticket value is temporally unique // The ticket also identifies and selects a slot auto tkt = AtomicFetchIncrement (&PutCursor, 1) slot * s = &Slots[tkt & Mask] // waiting phase : // wait for slot's generation to match the tkt value assigned to this put() invocation. // The "generation" is implicitly encoded as the upper bits in the cursor // above those used to specify the index : tkt div (Mask+1) // The generation serves as an epoch number to identify a cohort of threads // accessing disjoint slots while s-Turn != tkt : Pause assert s-MailBox == null s-MailBox = v // deposit and pass message Take() : // consumer : partial method - waits as necessary auto tkt = AtomicFetchIncrement (&TakeCursor,1) slot * s = &Slots[tkt & Mask] // 2-stage waiting : // First wait for turn for our generation // Acquire exclusive "take" access to slot's MailBox field // Then wait for the slot to become occupied while s-Turn != tkt : Pause // Concurrency in this section of code is now reduced to just 1 producer thread // vs 1 consumer thread. // For a given queue and slot, there will be most one Take() operation running // in this section. // Consumer waits for producer to arrive and make slot non-empty // Extract message; clear mailbox; advance Turn indicator // We have an obvious happens-before relation : // Put(m) happens-before corresponding Take() that returns that same "m" for T v = s-MailBox if v != null : s-MailBox = null ST-ST barrier s-Turn = tkt + Mask + 1 // unlock slot to admit next producer and consumer return v Pause tryTake() : // total method - returns ASAP with failure indication for auto tkt = TakeCursor slot * s = &Slots[tkt & Mask] if s-Turn != tkt : return null T v = s-MailBox // presumptive return value if v == null : return null // ratify tkt and v values and commit by advancing cursor if CAS (&TakeCursor, tkt, tkt+1) != tkt : continue s-MailBox = null ST-ST barrier s-Turn = tkt + Mask + 1 return v The basic idea derives from the Partitioned Ticket Lock "PTL" (US20120240126-A1) and the MultiLane Concurrent Bag (US8689237). The latter is essentially a circular ring-buffer where the elements themselves are queues or concurrent collections. You can think of the PTLQueue as a partitioned ticket lock "PTL" augmented to pass values from lock to unlock via the slots. Alternatively, you could conceptualize of PTLQueue as a degenerate MultiLane bag where each slot or "lane" consists of a simple single-word MailBox instead of a general queue. Each lane in PTLQueue also has a private Turn field which acts like the Turn (Grant) variables found in PTL. Turn enforces strict FIFO ordering and restricts concurrency on the slot mailbox field to at most one simultaneous put() and take() operation. PTL uses a single "ticket" variable and per-slot Turn (grant) fields while MultiLane has distinct PutCursor and TakeCursor cursors and abstract per-slot sub-queues. Both PTL and MultiLane advance their cursor and ticket variables with atomic fetch-and-increment. PTLQueue borrows from both PTL and MultiLane and has distinct put and take cursors and per-slot Turn fields. Instead of a per-slot queues, PTLQueue uses a simple single-word MailBox field. PutCursor and TakeCursor act like a pair of ticket locks, conferring "put" and "take" access to a given slot. PutCursor, for instance, assigns an incoming put() request to a slot and serves as a PTL "Ticket" to acquire "put" permission to that slot's MailBox field. To better explain the operation of PTLQueue we deconstruct the operation of put() and take() as follows. Put() first increments PutCursor obtaining a new unique ticket. That ticket value also identifies a slot. Put() next waits for that slot's Turn field to match that ticket value. This is tantamount to using a PTL to acquire "put" permission on the slot's MailBox field. Finally, having obtained exclusive "put" permission on the slot, put() stores the message value into the slot's MailBox. Take() similarly advances TakeCursor, identifying a slot, and then acquires and secures "take" permission on a slot by waiting for Turn. Take() then waits for the slot's MailBox to become non-empty, extracts the message, and clears MailBox. Finally, take() advances the slot's Turn field, which releases both "put" and "take" access to the slot's MailBox. Note the asymmetry : put() acquires "put" access to the slot, but take() releases that lock. At any given time, for a given slot in a PTLQueue, at most one thread has "put" access and at most one thread has "take" access. This restricts concurrency from general MPMC to 1-vs-1. We have 2 ticket locks -- one for put() and one for take() -- each with its own "ticket" variable in the form of the corresponding cursor, but they share a single "Grant" egress variable in the form of the slot's Turn variable. Advancing the PutCursor, for instance, serves two purposes. First, we obtain a unique ticket which identifies a slot. Second, incrementing the cursor is the doorway protocol step to acquire the per-slot mutual exclusion "put" lock. The cursors and operations to increment those cursors serve double-duty : slot-selection and ticket assignment for locking the slot's MailBox field. At any given time a slot MailBox field can be in one of the following states: empty with no pending operations -- neutral state; empty with one or more waiting take() operations pending -- deficit; occupied with no pending operations; occupied with one or more waiting put() operations -- surplus; empty with a pending put() or pending put() and take() operations -- transitional; or occupied with a pending take() or pending put() and take() operations -- transitional. The partial put() and take() operators can be implemented with an atomic fetch-and-increment operation, which may confer a performance advantage over a CAS-based loop. In addition we have independent PutCursor and TakeCursor cursors. Critically, a put() operation modifies PutCursor but does not access the TakeCursor and a take() operation modifies the TakeCursor cursor but does not access the PutCursor. This acts to reduce coherence traffic relative to some other queue designs. It's worth noting that slow threads or obstruction in one slot (or "lane") does not impede or obstruct operations in other slots -- this gives us some degree of obstruction isolation. PTLQueue is not lock-free, however. The implementation above is expressed with polite busy-waiting (Pause) but it's trivial to implement per-slot parking and unparking to deschedule waiting threads. It's also easy to convert the queue to a more general deque by replacing the PutCursor and TakeCursor cursors with Left/Front and Right/Back cursors that can move either direction. Specifically, to push and pop from the "left" side of the deque we would decrement and increment the Left cursor, respectively, and to push and pop from the "right" side of the deque we would increment and decrement the Right cursor, respectively. We used a variation of PTLQueue for message passing in our recent OPODIS 2013 paper. ul { list-style:none; padding-left:0; padding:0; margin:0; margin-left:0; } ul#myTagID { padding: 0px; margin: 0px; list-style:none; margin-left:0;} -- -- There's quite a bit of related literature in this area. I'll call out a few relevant references: Wilson's NYU Courant Institute UltraComputer dissertation from 1988 is classic and the canonical starting point : Operating System Data Structures for Shared-Memory MIMD Machines with Fetch-and-Add. Regarding provenance and priority, I think PTLQueue or queues effectively equivalent to PTLQueue have been independently rediscovered a number of times. See CB-Queue and BNPBV, below, for instance. But Wilson's dissertation anticipates the basic idea and seems to predate all the others. Gottlieb et al : Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors Orozco et al : CB-Queue in Toward high-throughput algorithms on many-core architectures which appeared in TACO 2012. Meneghin et al : BNPVB family in Performance evaluation of inter-thread communication mechanisms on multicore/multithreaded architecture Dmitry Vyukov : bounded MPMC queue (highly recommended) Alex Otenko : US8607249 (highly related). John Mellor-Crummey : Concurrent queues: Practical fetch-and-phi algorithms. Technical Report 229, Department of Computer Science, University of Rochester Thomasson : FIFO Distributed Bakery Algorithm (very similar to PTLQueue). Scott and Scherer : Dual Data Structures I'll propose an optimization left as an exercise for the reader. Say we wanted to reduce memory usage by eliminating inter-slot padding. Such padding is usually "dark" memory and otherwise unused and wasted. But eliminating the padding leaves us at risk of increased false sharing. Furthermore lets say it was usually the case that the PutCursor and TakeCursor were numerically close to each other. (That's true in some use cases). We might still reduce false sharing by incrementing the cursors by some value other than 1 that is not trivially small and is coprime with the number of slots. Alternatively, we might increment the cursor by one and mask as usual, resulting in a logical index. We then use that logical index value to index into a permutation table, yielding an effective index for use in the slot array. The permutation table would be constructed so that nearby logical indices would map to more distant effective indices. (Open question: what should that permutation look like? Possibly some perversion of a Gray code or De Bruijn sequence might be suitable). As an aside, say we need to busy-wait for some condition as follows : "while C == 0 : Pause". Lets say that C is usually non-zero, so we typically don't wait. But when C happens to be 0 we'll have to spin for some period, possibly brief. We can arrange for the code to be more machine-friendly with respect to the branch predictors by transforming the loop into : "if C == 0 : for { Pause; if C != 0 : break; }". Critically, we want to restructure the loop so there's one branch that controls entry and another that controls loop exit. A concern is that your compiler or JIT might be clever enough to transform this back to "while C == 0 : Pause". You can sometimes avoid this by inserting a call to a some type of very cheap "opaque" method that the compiler can't elide or reorder. On Solaris, for instance, you could use :"if C == 0 : { gethrtime(); for { Pause; if C != 0 : break; }}". It's worth noting the obvious duality between locks and queues. If you have strict FIFO lock implementation with local spinning and succession by direct handoff such as MCS or CLH,then you can usually transform that lock into a queue. Hidden commentary and annotations - invisible : * And of course there's a well-known duality between queues and locks, but I'll leave that topic for another blog post. * Compare and contrast : PTLQ vs PTL and MultiLane * Equivalent : Turn; seq; sequence; pos; position; ticket * Put = Lock; Deposit Take = identify and reserve slot; wait; extract & clear; unlock * conceptualize : Distinct PutLock and TakeLock implemented as ticket lock or PTL Distinct arrival cursors but share per-slot "Turn" variable provides exclusive role-based access to slot's mailbox field put() acquires exclusive access to a slot for purposes of "deposit" assigns slot round-robin and then acquires deposit access rights/perms to that slot take() acquires exclusive access to slot for purposes of "withdrawal" assigns slot round-robin and then acquires withdrawal access rights/perms to that slot At any given time, only one thread can have withdrawal access to a slot at any given time, only one thread can have deposit access to a slot Permissible for T1 to have deposit access and T2 to simultaneously have withdrawal access * round-robin for the purposes of; role-based; access mode; access role mailslot; mailbox; allocate/assign/identify slot rights; permission; license; access permission; * PTL/Ticket hybrid Asymmetric usage ; owner oblivious lock-unlock pairing K-exclusion add Grant cursor pass message m from lock to unlock via Slots[] array Cursor performs 2 functions : + PTL ticket + Assigns request to slot in round-robin fashion Deconstruct protocol : explication put() : allocate slot in round-robin fashion acquire PTL for "put" access store message into slot associated with PTL index take() : Acquire PTL for "take" access // doorway step seq = fetchAdd (&Grant, 1) s = &Slots[seq & Mask] // waiting phase while s-Turn != seq : pause Extract : wait for s-mailbox to be full v = s-mailbox s-mailbox = null Release PTL for both "put" and "take" access s-Turn = seq + Mask + 1 * Slot round-robin assignment and lock "doorway" protocol leverage the same cursor and FetchAdd operation on that cursor FetchAdd (&Cursor,1) + round-robin slot assignment and dispersal + PTL/ticket lock "doorway" step waiting phase is via "Turn" field in slot * PTLQueue uses 2 cursors -- put and take. Acquire "put" access to slot via PTL-like lock Acquire "take" access to slot via PTL-like lock 2 locks : put and take -- at most one thread can access slot's mailbox Both locks use same "turn" field Like multilane : 2 cursors : put and take slot is simple 1-capacity mailbox instead of queue Borrow per-slot turn/grant from PTL Provides strict FIFO Lock slot : put-vs-put take-vs-take at most one put accesses slot at any one time at most one put accesses take at any one time reduction to 1-vs-1 instead of N-vs-M concurrency Per slot locks for put/take Release put/take by advancing turn * is instrumental in ... * P-V Semaphore vs lock vs K-exclusion * See also : FastQueues-excerpt.java dice-etc/queue-mpmc-bounded-blocking-circular-xadd/ * PTLQueue is the same as PTLQB - identical * Expedient return; ASAP; prompt; immediately * Lamport's Bakery algorithm : doorway step then waiting phase Threads arriving at doorway obtain a unique ticket number Threads enter in ticket order * In the terminology of Reed and Kanodia a ticket lock corresponds to the busy-wait implementation of a semaphore using an eventcount and a sequencer It can also be thought of as an optimization of Lamport's bakery lock was designed for fault-tolerance rather than performance Instead of spinning on the release counter, processors using a bakery lock repeatedly examine the tickets of their peers --

    Read the article

  • Simple Grouping With TableSorter Plugin

    - by HurnsMobile
    Im playing around with the Tablesorter plug-in for jQuery and was trying to get a very simple grouping functionality added into it. Using the follow html/js works great until you click sort again and reverse the order. The headers get moved to the bottom of the group when this happens. The following is my (admitedly hacky) attempt at it. Does anyone have any ideas? <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /> <title>Table Manipulation Test</title> <link type="text/css" href="css/ui-lightness/jquery-ui-1.8.1.custom.css" rel="stylesheet" /> <link rel="stylesheet" href="tablesorter/themes/green/style.css" type="text/css"/> <script type="text/javascript" src="js/jquery-1.4.2.min.js"></script> <script type="text/javascript" src="js/jquery-ui-1.8.1.custom.min.js"></script> <script type="text/javascript" src="tablesorter/jquery.tablesorter.min.js"></script> <script type="text/javascript"> $(document).ready(function() { $("#test_table").tablesorter({ sortForce: [[3,0]] }); $(".group_details").hide(); $(".group_header").click(function(){ var group = $(this).attr("group"); var $expander = $(this).children("td.expanderguy") if ($("." + group + ":visible").length){ $("." + group + "").fadeOut('fast'); $expander.html("<img src='icons/plus.gif'>"); } else{ $("." + group + "").fadeIn('fast'); $expander.html("<img src='icons/minus.gif'>"); } }); } ); </script> <style type="text/css"> .group_header td{ background-color: #888888; !important } </style> </head> <body> <table id="test_table" class="tablesorter"> <thead> <tr><th>First Name</th><th>Last Name</th><th>Email</th><th>Due Date</th><th>Amount Due</th></tr> </thead> <tbody> <tr class="group_header" group="group1"><td class="expanderguy"><img src="icons/plus.gif"></td><td></td><td></td><td>Monday, June 7</td><td></td></tr> <tr class="group_details group1"><td>Flavian</td><td>Wenceslas</td><td>[email protected]</td><td>Monday, June 7</td><td>$100</td></tr> <tr class="group_details group1"><td>Gordian</td><td>Ives</td><td>[email protected]</td><td>Monday, June 7</td><td>$1700</td></tr> <tr class="group_details group1"><td>Saladin</td><td>Tarquin</td><td>[email protected]</td><td>Monday, June 7</td><td>$1700</td></tr> <tr class="group_details group1"><td>Urban</td><td>Cyprian</td><td>[email protected]</td><td>Monday, June 7</td><td>$1500</td></tr> <tr class="group_details group1"><td>Sargon</td><td>Swithun</td><td>[email protected]</td><td>Monday, June 7</td><td>$1100</td></tr> <tr class="group_details group1"><td>Pompey</td><td>Ladislas</td><td>[email protected]</td><td>Monday, June 7</td><td>$300</td></tr> <tr class="group_details group1"><td>Attila</td><td>Hiawatha</td><td>[email protected]</td><td>Monday, June 7</td><td>$200</td></tr> <tr class="group_header" group="group2"><td class="expanderguy"><img src="icons/plus.gif"></td><td></td><td></td><td>Tuesday, June 8</td><td></td></tr> <tr class="group_details group2"><td>Bruce</td><td>Fenton</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$1700</td></tr> <tr class="group_details group2"><td>Wade</td><td>Sequoia</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$1400</td></tr> <tr class="group_details group2"><td>Eddie</td><td>Jerold</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$1100</td></tr> <tr class="group_details group2"><td>Lynn</td><td>Lucan</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$1200</td></tr> <tr class="group_details group2"><td>Taegan</td><td>Tadg</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$100</td></tr> <tr class="group_details group2"><td>Clyde</td><td>Reed</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$6100</td></tr> <tr class="group_details group2"><td>Alaois</td><td>Art</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$2100</td></tr> <tr class="group_details group2"><td>Gilbert</td><td>Patsy</td><td>[email protected]</td><td>Tuesday, June 8</td><td>$1500</td></tr> <tr class="group_header" group="group3"><td class="expanderguy"><img src="icons/plus.gif"></td><td></td><td></td><td>Wednesday, June 9</td><td></td></tr> <tr class="group_details group3" ><td>Clem</td><td>Eben</td><td>[email protected]</td><td>Wednesday, June 9</td><td>$2100</td></tr> <tr class="group_details group3" ><td>Elijah</td><td>Julyan</td><td>[email protected]</td><td>Wednesday, June 9</td><td>$2100</td></tr> <tr class="group_details group3" ><td>Marvyn</td><td>Damian</td><td>[email protected]</td><td>Wednesday, June 9</td><td>$1100</td></tr> <tr class="group_details group3" ><td>Sawyer</td><td>Ryker</td><td>[email protected]</td><td>Wednesday, June 9</td><td>$500</td></tr> </tbody> </table> </body>

    Read the article

  • An Introduction to jQuery Templates

    - by Stephen Walther
    The goal of this blog entry is to provide you with enough information to start working with jQuery Templates. jQuery Templates enable you to display and manipulate data in the browser. For example, you can use jQuery Templates to format and display a set of database records that you have retrieved with an Ajax call. jQuery Templates supports a number of powerful features such as template tags, template composition, and wrapped templates. I’ll concentrate on the features that I think that you will find most useful. In order to focus on the jQuery Templates feature itself, this blog entry is server technology agnostic. All the samples use HTML pages instead of ASP.NET pages. In a future blog entry, I’ll focus on using jQuery Templates with ASP.NET Web Forms and ASP.NET MVC (You can do some pretty powerful things when jQuery Templates are used on the client and ASP.NET is used on the server). Introduction to jQuery Templates The jQuery Templates plugin was developed by the Microsoft ASP.NET team in collaboration with the open-source jQuery team. While working at Microsoft, I wrote the original proposal for jQuery Templates, Dave Reed wrote the original code, and Boris Moore wrote the final code. The jQuery team – especially John Resig – was very involved in each step of the process. Both the jQuery community and ASP.NET communities were very active in providing feedback. jQuery Templates will be included in the jQuery core library (the jQuery.js library) when jQuery 1.5 is released. Until jQuery 1.5 is released, you can download the jQuery Templates plugin from the jQuery Source Code Repository or you can use jQuery Templates directly from the ASP.NET CDN. The documentation for jQuery Templates is already included with the official jQuery documentation at http://api.jQuery.com. The main entry for jQuery templates is located under the topic plugins/templates. A Basic Sample of jQuery Templates Let’s start with a really simple sample of using jQuery Templates. We’ll use the plugin to display a list of books stored in a JavaScript array. Here’s the complete code: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html > <head> <title>Intro</title> <link href="0_Site.css" rel="stylesheet" type="text/css" /> </head> <body> <div id="pageContent"> <h1>ASP.NET Bookstore</h1> <div id="bookContainer"></div> </div> <script id="bookTemplate" type="text/x-jQuery-tmpl"> <div> <img src="BookPictures/${picture}" alt="" /> <h2>${title}</h2> price: ${formatPrice(price)} </div> </script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> // Create an array of books var books = [ { title: "ASP.NET 4 Unleashed", price: 37.79, picture: "AspNet4Unleashed.jpg" }, { title: "ASP.NET MVC Unleashed", price: 44.99, picture: "AspNetMvcUnleashed.jpg" }, { title: "ASP.NET Kick Start", price: 4.00, picture: "AspNetKickStart.jpg" }, { title: "ASP.NET MVC Unleashed iPhone", price: 44.99, picture: "AspNetMvcUnleashedIPhone.jpg" }, ]; // Render the books using the template $("#bookTemplate").tmpl(books).appendTo("#bookContainer"); function formatPrice(price) { return "$" + price.toFixed(2); } </script> </body> </html> When you open this page in a browser, a list of books is displayed: There are several things going on in this page which require explanation. First, notice that the page uses both the jQuery 1.4.4 and jQuery Templates libraries. Both libraries are retrieved from the ASP.NET CDN: <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> You can use the ASP.NET CDN for free (even for production websites). You can learn more about the files included on the ASP.NET CDN by visiting the ASP.NET CDN documentation page. Second, you should notice that the actual template is included in a script tag with a special MIME type: <script id="bookTemplate" type="text/x-jQuery-tmpl"> <div> <img src="BookPictures/${picture}" alt="" /> <h2>${title}</h2> price: ${formatPrice(price)} </div> </script> This template is displayed for each of the books rendered by the template. The template displays a book picture, title, and price. Notice that the SCRIPT tag which wraps the template has a MIME type of text/x-jQuery-tmpl. Why is the template wrapped in a SCRIPT tag and why the strange MIME type? When a browser encounters a SCRIPT tag with an unknown MIME type, it ignores the content of the tag. This is the behavior that you want with a template. You don’t want a browser to attempt to parse the contents of a template because this might cause side effects. For example, the template above includes an <img> tag with a src attribute that points at “BookPictures/${picture}”. You don’t want the browser to attempt to load an image at the URL “BookPictures/${picture}”. Instead, you want to prevent the browser from processing the IMG tag until the ${picture} expression is replaced by with the actual name of an image by the jQuery Templates plugin. If you are not worried about browser side-effects then you can wrap a template inside any HTML tag that you please. For example, the following DIV tag would also work with the jQuery Templates plugin: <div id="bookTemplate" style="display:none"> <div> <h2>${title}</h2> price: ${formatPrice(price)} </div> </div> Notice that the DIV tag includes a style=”display:none” attribute to prevent the template from being displayed until the template is parsed by the jQuery Templates plugin. Third, notice that the expression ${…} is used to display the value of a JavaScript expression within a template. For example, the expression ${title} is used to display the value of the book title property. You can use any JavaScript function that you please within the ${…} expression. For example, in the template above, the book price is formatted with the help of the custom JavaScript formatPrice() function which is defined lower in the page. Fourth, and finally, the template is rendered with the help of the tmpl() method. The following statement selects the bookTemplate and renders an array of books using the bookTemplate. The results are appended to a DIV element named bookContainer by using the standard jQuery appendTo() method. $("#bookTemplate").tmpl(books).appendTo("#bookContainer"); Using Template Tags Within a template, you can use any of the following template tags. {{tmpl}} – Used for template composition. See the section below. {{wrap}} – Used for wrapped templates. See the section below. {{each}} – Used to iterate through a collection. {{if}} – Used to conditionally display template content. {{else}} – Used with {{if}} to conditionally display template content. {{html}} – Used to display the value of an HTML expression without encoding the value. Using ${…} or {{= }} performs HTML encoding automatically. {{= }}-- Used in exactly the same way as ${…}. {{! }} – Used for displaying comments. The contents of a {{!...}} tag are ignored. For example, imagine that you want to display a list of blog entries. Each blog entry could, possibly, have an associated list of categories. The following page illustrates how you can use the { if}} and {{each}} template tags to conditionally display categories for each blog entry:   <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>each</title> <link href="1_Site.css" rel="stylesheet" type="text/css" /> </head> <body> <div id="blogPostContainer"></div> <script id="blogPostTemplate" type="text/x-jQuery-tmpl"> <h1>${postTitle}</h1> <p> ${postEntry} </p> {{if categories}} Categories: {{each categories}} <i>${$value}</i> {{/each}} {{else}} Uncategorized {{/if}} </script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> var blogPosts = [ { postTitle: "How to fix a sink plunger in 5 minutes", postEntry: "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna.", categories: ["HowTo", "Sinks", "Plumbing"] }, { postTitle: "How to remove a broken lightbulb", postEntry: "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna.", categories: ["HowTo", "Lightbulbs", "Electricity"] }, { postTitle: "New associate website", postEntry: "Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna." } ]; // Render the blog posts $("#blogPostTemplate").tmpl(blogPosts).appendTo("#blogPostContainer"); </script> </body> </html> When this page is opened in a web browser, the following list of blog posts and categories is displayed: Notice that the first and second blog entries have associated categories but the third blog entry does not. The third blog entry is “Uncategorized”. The template used to render the blog entries and categories looks like this: <script id="blogPostTemplate" type="text/x-jQuery-tmpl"> <h1>${postTitle}</h1> <p> ${postEntry} </p> {{if categories}} Categories: {{each categories}} <i>${$value}</i> {{/each}} {{else}} Uncategorized {{/if}} </script> Notice the special expression $value used within the {{each}} template tag. You can use $value to display the value of the current template item. In this case, $value is used to display the value of each category in the collection of categories. Template Composition When building a fancy page, you might want to build a template out of multiple templates. In other words, you might want to take advantage of template composition. For example, imagine that you want to display a list of products. Some of the products are being sold at their normal price and some of the products are on sale. In that case, you might want to use two different templates for displaying a product: a productTemplate and a productOnSaleTemplate. The following page illustrates how you can use the {{tmpl}} tag to build a template from multiple templates:   <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>Composition</title> <link href="2_Site.css" rel="stylesheet" type="text/css" /> </head> <body> <div id="pageContainer"> <h1>Products</h1> <div id="productListContainer"></div> <!-- Show list of products using composition --> <script id="productListTemplate" type="text/x-jQuery-tmpl"> <div> {{if onSale}} {{tmpl "#productOnSaleTemplate"}} {{else}} {{tmpl "#productTemplate"}} {{/if}} </div> </script> <!-- Show product --> <script id="productTemplate" type="text/x-jQuery-tmpl"> ${name} </script> <!-- Show product on sale --> <script id="productOnSaleTemplate" type="text/x-jQuery-tmpl"> <b>${name}</b> <img src="images/on_sale.png" alt="On Sale" /> </script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> var products = [ { name: "Laptop", onSale: false }, { name: "Apples", onSale: true }, { name: "Comb", onSale: false } ]; $("#productListTemplate").tmpl(products).appendTo("#productListContainer"); </script> </div> </body> </html>   In the page above, the main template used to display the list of products looks like this: <script id="productListTemplate" type="text/x-jQuery-tmpl"> <div> {{if onSale}} {{tmpl "#productOnSaleTemplate"}} {{else}} {{tmpl "#productTemplate"}} {{/if}} </div> </script>   If a product is on sale then the product is displayed with the productOnSaleTemplate (which includes an on sale image): <script id="productOnSaleTemplate" type="text/x-jQuery-tmpl"> <b>${name}</b> <img src="images/on_sale.png" alt="On Sale" /> </script>   Otherwise, the product is displayed with the normal productTemplate (which does not include the on sale image): <script id="productTemplate" type="text/x-jQuery-tmpl"> ${name} </script>   You can pass a parameter to the {{tmpl}} tag. The parameter becomes the data passed to the template rendered by the {{tmpl}} tag. For example, in the previous section, we used the {{each}} template tag to display a list of categories for each blog entry like this: <script id="blogPostTemplate" type="text/x-jQuery-tmpl"> <h1>${postTitle}</h1> <p> ${postEntry} </p> {{if categories}} Categories: {{each categories}} <i>${$value}</i> {{/each}} {{else}} Uncategorized {{/if}} </script>   Another way to create this template is to use template composition like this: <script id="blogPostTemplate" type="text/x-jQuery-tmpl"> <h1>${postTitle}</h1> <p> ${postEntry} </p> {{if categories}} Categories: {{tmpl(categories) "#categoryTemplate"}} {{else}} Uncategorized {{/if}} </script> <script id="categoryTemplate" type="text/x-jQuery-tmpl"> <i>${$data}</i> &nbsp; </script>   Using the {{each}} tag or {{tmpl}} tag is largely a matter of personal preference. Wrapped Templates The {{wrap}} template tag enables you to take a chunk of HTML and transform the HTML into another chunk of HTML (think easy XSLT). When you use the {{wrap}} tag, you work with two templates. The first template contains the HTML being transformed and the second template includes the filter expressions for transforming the HTML. For example, you can use the {{wrap}} template tag to transform a chunk of HTML into an interactive tab strip: When you click any of the tabs, you see the corresponding content. This tab strip was created with the following page: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>Wrapped Templates</title> <style type="text/css"> body { font-family: Arial; background-color:black; } .tabs div { display:inline-block; border-bottom: 1px solid black; padding:4px; background-color:gray; cursor:pointer; } .tabs div.tabState_true { background-color:white; border-bottom:1px solid white; } .tabBody { border-top:1px solid white; padding:10px; background-color:white; min-height:400px; width:400px; } </style> </head> <body> <div id="tabsView"></div> <script id="tabsContent" type="text/x-jquery-tmpl"> {{wrap "#tabsWrap"}} <h3>Tab 1</h3> <div> Content of tab 1. Lorem ipsum dolor <b>sit</b> amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna. </div> <h3>Tab 2</h3> <div> Content of tab 2. Lorem ipsum dolor <b>sit</b> amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna. </div> <h3>Tab 3</h3> <div> Content of tab 3. Lorem ipsum dolor <b>sit</b> amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna. </div> {{/wrap}} </script> <script id="tabsWrap" type="text/x-jquery-tmpl"> <div class="tabs"> {{each $item.html("h3", true)}} <div class="tabState_${$index === selectedTabIndex}"> ${$value} </div> {{/each}} </div> <div class="tabBody"> {{html $item.html("div")[selectedTabIndex]}} </div> </script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> // Global for tracking selected tab var selectedTabIndex = 0; // Render the tab strip $("#tabsContent").tmpl().appendTo("#tabsView"); // When a tab is clicked, update the tab strip $("#tabsView") .delegate(".tabState_false", "click", function () { var templateItem = $.tmplItem(this); selectedTabIndex = $(this).index(); templateItem.update(); }); </script> </body> </html>   The “source” for the tab strip is contained in the following template: <script id="tabsContent" type="text/x-jquery-tmpl"> {{wrap "#tabsWrap"}} <h3>Tab 1</h3> <div> Content of tab 1. Lorem ipsum dolor <b>sit</b> amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna. </div> <h3>Tab 2</h3> <div> Content of tab 2. Lorem ipsum dolor <b>sit</b> amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna. </div> <h3>Tab 3</h3> <div> Content of tab 3. Lorem ipsum dolor <b>sit</b> amet, consectetuer adipiscing elit. Maecenas porttitor congue massa. Fusce posuere, magna sed pulvinar ultricies, purus lectus malesuada libero, sit amet commodo magna eros quis urna. </div> {{/wrap}} </script>   The tab strip is created with a list of H3 elements (which represent each tab) and DIV elements (which represent the body of each tab). Notice that the HTML content is wrapped in the {{wrap}} template tag. This template tag points at the following tabsWrap template: <script id="tabsWrap" type="text/x-jquery-tmpl"> <div class="tabs"> {{each $item.html("h3", true)}} <div class="tabState_${$index === selectedTabIndex}"> ${$value} </div> {{/each}} </div> <div class="tabBody"> {{html $item.html("div")[selectedTabIndex]}} </div> </script> The tabs DIV contains all of the tabs. The {{each}} template tag is used to loop through each of the H3 elements from the source template and render a DIV tag that represents a particular tab. The template item html() method is used to filter content from the “source” HTML template. The html() method accepts a jQuery selector for its first parameter. The tabs are retrieved from the source template by using an h3 filter. The second parameter passed to the html() method – the textOnly parameter -- causes the filter to return the inner text of each h3 element. You can learn more about the html() method at the jQuery website (see the section on $item.html()). The tabBody DIV renders the body of the selected tab. Notice that the {{html}} template tag is used to display the tab body so that HTML content in the body won’t be HTML encoded. The html() method is used, once again, to grab all of the DIV elements from the source HTML template. The selectedTabIndex global variable is used to display the contents of the selected tab. Remote Templates A common feature request for jQuery templates is support for remote templates. Developers want to be able to separate templates into different files. Adding support for remote templates requires only a few lines of extra code (Dave Ward has a nice blog entry on this). For example, the following page uses a remote template from a file named BookTemplate.htm: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>Remote Templates</title> <link href="0_Site.css" rel="stylesheet" type="text/css" /> </head> <body> <div id="pageContent"> <h1>ASP.NET Bookstore</h1> <div id="bookContainer"></div> </div> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> // Create an array of books var books = [ { title: "ASP.NET 4 Unleashed", price: 37.79, picture: "AspNet4Unleashed.jpg" }, { title: "ASP.NET MVC Unleashed", price: 44.99, picture: "AspNetMvcUnleashed.jpg" }, { title: "ASP.NET Kick Start", price: 4.00, picture: "AspNetKickStart.jpg" }, { title: "ASP.NET MVC Unleashed iPhone", price: 44.99, picture: "AspNetMvcUnleashedIPhone.jpg" }, ]; // Get the remote template $.get("BookTemplate.htm", null, function (bookTemplate) { // Render the books using the remote template $.tmpl(bookTemplate, books).appendTo("#bookContainer"); }); function formatPrice(price) { return "$" + price.toFixed(2); } </script> </body> </html>   The remote template is retrieved (and rendered) with the following code: // Get the remote template $.get("BookTemplate.htm", null, function (bookTemplate) { // Render the books using the remote template $.tmpl(bookTemplate, books).appendTo("#bookContainer"); });   This code uses the standard jQuery $.get() method to get the BookTemplate.htm file from the server with an Ajax request. After the BookTemplate.htm file is successfully retrieved, the $.tmpl() method is used to render an array of books with the template. Here’s what the BookTemplate.htm file looks like: <div> <img src="BookPictures/${picture}" alt="" /> <h2>${title}</h2> price: ${formatPrice(price)} </div> Notice that the template in the BooksTemplate.htm file is not wrapped by a SCRIPT element. There is no need to wrap the template in this case because there is no possibility that the template will get interpreted before you want it to be interpreted. If you plan to use the bookTemplate multiple times – for example, you are paging or sorting the books -- then you should compile the template into a function and cache the compiled template function. For example, the following page can be used to page through a list of 100 products (using iPhone style More paging). <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>Template Caching</title> <link href="6_Site.css" rel="stylesheet" type="text/css" /> </head> <body> <h1>Products</h1> <div id="productContainer"></div> <button id="more">More</button> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> // Globals var pageIndex = 0; // Create an array of products var products = []; for (var i = 0; i < 100; i++) { products.push({ name: "Product " + (i + 1) }); } // Get the remote template $.get("ProductTemplate.htm", null, function (productTemplate) { // Compile and cache the template $.template("productTemplate", productTemplate); // Render the products renderProducts(0); }); $("#more").click(function () { pageIndex++; renderProducts(); }); function renderProducts() { // Get page of products var pageOfProducts = products.slice(pageIndex * 5, pageIndex * 5 + 5); // Used cached productTemplate to render products $.tmpl("productTemplate", pageOfProducts).appendTo("#productContainer"); } function formatPrice(price) { return "$" + price.toFixed(2); } </script> </body> </html>   The ProductTemplate is retrieved from an external file named ProductTemplate.htm. This template is retrieved only once. Furthermore, it is compiled and cached with the help of the $.template() method: // Get the remote template $.get("ProductTemplate.htm", null, function (productTemplate) { // Compile and cache the template $.template("productTemplate", productTemplate); // Render the products renderProducts(0); });   The $.template() method compiles the HTML representation of the template into a JavaScript function and caches the template function with the name productTemplate. The cached template can be used by calling the $.tmp() method. The productTemplate is used in the renderProducts() method: function renderProducts() { // Get page of products var pageOfProducts = products.slice(pageIndex * 5, pageIndex * 5 + 5); // Used cached productTemplate to render products $.tmpl("productTemplate", pageOfProducts).appendTo("#productContainer"); } In the code above, the first parameter passed to the $.tmpl() method is the name of a cached template. Working with Template Items In this final section, I want to devote some space to discussing Template Items. A new Template Item is created for each rendered instance of a template. For example, if you are displaying a list of 100 products with a template, then 100 Template Items are created. A Template Item has the following properties and methods: data – The data associated with the Template Instance. For example, a product. tmpl – The template associated with the Template Instance. parent – The parent template item if the template is nested. nodes – The HTML content of the template. calls – Used by {{wrap}} template tag. nest – Used by {{tmpl}} template tag. wrap – Used to imperatively enable wrapped templates. html – Used to filter content from a wrapped template. See the above section on wrapped templates. update – Used to re-render a template item. The last method – the update() method -- is especially interesting because it enables you to re-render a template item with new data or even a new template. For example, the following page displays a list of books. When you hover your mouse over any of the books, additional book details are displayed. In the following screenshot, details for ASP.NET Kick Start are displayed. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title>Template Item</title> <link href="0_Site.css" rel="stylesheet" type="text/css" /> </head> <body> <div id="pageContent"> <h1>ASP.NET Bookstore</h1> <div id="bookContainer"></div> </div> <script id="bookTemplate" type="text/x-jQuery-tmpl"> <div class="bookItem"> <img src="BookPictures/${picture}" alt="" /> <h2>${title}</h2> price: ${formatPrice(price)} </div> </script> <script id="bookDetailsTemplate" type="text/x-jQuery-tmpl"> <div class="bookItem"> <img src="BookPictures/${picture}" alt="" /> <h2>${title}</h2> price: ${formatPrice(price)} <p> ${description} </p> </div> </script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jQuery/jquery-1.4.4.js"></script> <script type="text/javascript" src="http://ajax.aspnetcdn.com/ajax/jquery.templates/beta1/jquery.tmpl.js"></script> <script type="text/javascript"> // Create an array of books var books = [ { title: "ASP.NET 4 Unleashed", price: 37.79, picture: "AspNet4Unleashed.jpg", description: "The most comprehensive book on Microsoft’s new ASP.NET 4.. " }, { title: "ASP.NET MVC Unleashed", price: 44.99, picture: "AspNetMvcUnleashed.jpg", description: "Writing for professional programmers, Walther explains the crucial concepts that make the Model-View-Controller (MVC) development paradigm work…" }, { title: "ASP.NET Kick Start", price: 4.00, picture: "AspNetKickStart.jpg", description: "Visual Studio .NET is the premier development environment for creating .NET applications…." }, { title: "ASP.NET MVC Unleashed iPhone", price: 44.99, picture: "AspNetMvcUnleashedIPhone.jpg", description: "ASP.NET MVC Unleashed for the iPhone…" }, ]; // Render the books using the template $("#bookTemplate").tmpl(books).appendTo("#bookContainer"); // Get compiled details template var bookDetailsTemplate = $("#bookDetailsTemplate").template(); // Add hover handler $(".bookItem").mouseenter(function () { // Get template item associated with DIV var templateItem = $(this).tmplItem(); // Change template to compiled template templateItem.tmpl = bookDetailsTemplate; // Re-render template templateItem.update(); }); function formatPrice(price) { return "$" + price.toFixed(2); } </script> </body> </html>   There are two templates used to display a book: bookTemplate and bookDetailsTemplate. When you hover your mouse over a template item, the standard bookTemplate is swapped out for the bookDetailsTemplate. The bookDetailsTemplate displays a book description. The books are rendered with the bookTemplate with the following line of code: // Render the books using the template $("#bookTemplate").tmpl(books).appendTo("#bookContainer");   The following code is used to swap the bookTemplate and the bookDetailsTemplate to show details for a book: // Get compiled details template var bookDetailsTemplate = $("#bookDetailsTemplate").template(); // Add hover handler $(".bookItem").mouseenter(function () { // Get template item associated with DIV var templateItem = $(this).tmplItem(); // Change template to compiled template templateItem.tmpl = bookDetailsTemplate; // Re-render template templateItem.update(); });   When you hover your mouse over a DIV element rendered by the bookTemplate, the mouseenter handler executes. First, this handler retrieves the Template Item associated with the DIV element by calling the tmplItem() method. The tmplItem() method returns a Template Item. Next, a new template is assigned to the Template Item. Notice that a compiled version of the bookDetailsTemplate is assigned to the Template Item’s tmpl property. The template is compiled earlier in the code by calling the template() method. Finally, the Template Item update() method is called to re-render the Template Item with the bookDetailsTemplate instead of the original bookTemplate. Summary This is a long blog entry and I still have not managed to cover all of the features of jQuery Templates J However, I’ve tried to cover the most important features of jQuery Templates such as template composition, template wrapping, and template items. To learn more about jQuery Templates, I recommend that you look at the documentation for jQuery Templates at the official jQuery website. Another great way to learn more about jQuery Templates is to look at the (unminified) source code.

    Read the article

  • php remove duplicates from array..

    - by SoulieBaby
    Hi all, I was wondering if anyone could help me out, I'm trying to find a script that will check my entire array and remove any duplicates if required, then spit out the array in the same format. Here's an example of my array (as you will see there are some duplicates): Array ( [0] => Array ( [0] => stdClass Object ( [bid] => 34 [name] => Adrianos Pizza & Pasta [imageurl] => sp_adrian.gif [clickurl] => # ) [1] => stdClass Object ( [bid] => 42 [name] => Ray White Mordialloc [imageurl] => sp_raywhite.gif [clickurl] => http://www.raywhite.com/ ) [2] => stdClass Object ( [bid] => 48 [name] => Beachside Osteo [imageurl] => sp_beachside.gif [clickurl] => http://www.beachsideosteo.com.au/ ) [3] => stdClass Object ( [bid] => 57 [name] => Southern Suburbs Physiotherapy Centre [imageurl] => sp_sspc.jpg [clickurl] => http://www.sspc.com.au ) [4] => stdClass Object ( [bid] => 52 [name] => Mordialloc Travel and Cruise [imageurl] => sp_morditravel.jpg [clickurl] => http://www.yellowpages.com.au/vic/mordialloc/mordialloc-travel-cruise-13492525-listing.html ) [5] => stdClass Object ( [bid] => 37 [name] => Mordialloc Cellar Door [imageurl] => sp_cellardoor.gif [clickurl] => ) [6] => stdClass Object ( [bid] => 53 [name] => Carmotive [imageurl] => sp_carmotive.jpg [clickurl] => http://www.carmotive.com.au/ ) ) [1] => Array ( [0] => stdClass Object ( [bid] => 55 [name] => 360South [imageurl] => sp_360.jpg [clickurl] => ) [1] => stdClass Object ( [bid] => 40 [name] => Ripponlea Mitsubishi [imageurl] => sp_mitsubishi.gif [clickurl] => ) [2] => stdClass Object ( [bid] => 57 [name] => Southern Suburbs Physiotherapy Centre [imageurl] => sp_sspc.jpg [clickurl] => http://www.sspc.com.au ) [3] => stdClass Object ( [bid] => 52 [name] => Mordialloc Travel and Cruise [imageurl] => sp_morditravel.jpg [clickurl] => http://www.yellowpages.com.au/vic/mordialloc/mordialloc-travel-cruise-13492525-listing.html ) [4] => stdClass Object ( [bid] => 37 [name] => Mordialloc Cellar Door [imageurl] => sp_cellardoor.gif [clickurl] => ) [5] => stdClass Object ( [bid] => 53 [name] => Carmotive [imageurl] => sp_carmotive.jpg [clickurl] => http://www.carmotive.com.au/ ) ) [2] => Array ( [0] => stdClass Object ( [bid] => 44 [name] => Mordialloc Personal Trainers [imageurl] => sp_mordipt.gif [clickurl] => # ) [1] => stdClass Object ( [bid] => 36 [name] => Big River [imageurl] => sp_bigriver.gif [clickurl] => ) [2] => stdClass Object ( [bid] => 52 [name] => Mordialloc Travel and Cruise [imageurl] => sp_morditravel.jpg [clickurl] => http://www.yellowpages.com.au/vic/mordialloc/mordialloc-travel-cruise-13492525-listing.html ) [3] => stdClass Object ( [bid] => 37 [name] => Mordialloc Cellar Door [imageurl] => sp_cellardoor.gif [clickurl] => ) [4] => stdClass Object ( [bid] => 53 [name] => Carmotive [imageurl] => sp_carmotive.jpg [clickurl] => http://www.carmotive.com.au/ ) ) [3] => Array ( [0] => stdClass Object ( [bid] => 41 [name] => Print House Graphics [imageurl] => sp_printhouse.gif [clickurl] => ) [1] => stdClass Object ( [bid] => 49 [name] => Kim Reed Conveyancing [imageurl] => sp_kimreed.jpg [clickurl] => ) [2] => stdClass Object ( [bid] => 37 [name] => Mordialloc Cellar Door [imageurl] => sp_cellardoor.gif [clickurl] => ) [3] => stdClass Object ( [bid] => 53 [name] => Carmotive [imageurl] => sp_carmotive.jpg [clickurl] => http://www.carmotive.com.au/ ) ) [4] => Array ( [0] => stdClass Object ( [bid] => 38 [name] => Lowe Financial Group [imageurl] => sp_lowe.gif [clickurl] => http://lowefinancial.com/ ) [1] => stdClass Object ( [bid] => 58 [name] => Dicount Lollie Shop [imageurl] => new dls logo.jpg [clickurl] => ) [2] => stdClass Object ( [bid] => 53 [name] => Carmotive [imageurl] => sp_carmotive.jpg [clickurl] => http://www.carmotive.com.au/ ) ) [5] => Array ( [0] => stdClass Object ( [bid] => 45 [name] => Mordialloc Sporting Club [imageurl] => msc logo.jpg [clickurl] => ) [1] => stdClass Object ( [bid] => 33 [name] => Two Brothers [imageurl] => sp_2brothers.gif [clickurl] => http://www.2brothers.com.au/ ) ) [6] => Array ( [0] => stdClass Object ( [bid] => 46 [name] => Patterson Securities [imageurl] => cmyk patersons_withtag.jpg [clickurl] => ) [1] => stdClass Object ( [bid] => 56 [name] => Logical Services [imageurl] => sp_logical.jpg [clickurl] => ) ) [7] => Array ( [0] => stdClass Object ( [bid] => 59 [name] => Pure Sport [imageurl] => sp_psport.jpg [clickurl] => http://www.puresport.com.au/ ) [1] => stdClass Object ( [bid] => 51 [name] => Richmond and Bennison [imageurl] => sp_richmond.jpg [clickurl] => http://www.richbenn.com.au/ ) ) [8] => Array ( [0] => stdClass Object ( [bid] => 39 [name] => Main Street Mordialloc [imageurl] => main street cafe.jpg [clickurl] => ) [1] => stdClass Object ( [bid] => 50 [name] => Letec [imageurl] => sp_letec.jpg [clickurl] => www.letec.biz ) ) [9] => Array ( [0] => stdClass Object ( [bid] => 54 [name] => PPM Builders [imageurl] => sp_ppm.jpg [clickurl] => http://www.hotfrog.com.au/Companies/P-P-M-Builders ) [1] => stdClass Object ( [bid] => 43 [name] => Systema [imageurl] => sp_systema.gif [clickurl] => ) ) )

    Read the article

  • Steganography Experiment - Trouble hiding message bits in DCT coefficients

    - by JohnHankinson
    I have an application requiring me to be able to embed loss-less data into an image. As such I've been experimenting with steganography, specifically via modification of DCT coefficients as the method I select, apart from being loss-less must also be relatively resilient against format conversion, scaling/DSP etc. From the research I've done thus far this method seems to be the best candidate. I've seen a number of papers on the subject which all seem to neglect specific details (some neglect to mention modification of 0 coefficients, or modification of AC coefficient etc). After combining the findings and making a few modifications of my own which include: 1) Using a more quantized version of the DCT matrix to ensure we only modify coefficients that would still be present should the image be JPEG'ed further or processed (I'm using this in place of simply following a zig-zag pattern). 2) I'm modifying bit 4 instead of the LSB and then based on what the original bit value was adjusting the lower bits to minimize the difference. 3) I'm only modifying the blue channel as it should be the least visible. This process must modify the actual image and not the DCT values stored in file (like jsteg) as there is no guarantee the file will be a JPEG, it may also be opened and re-saved at a later stage in a different format. For added robustness I've included the message multiple times and use the bits that occur most often, I had considered using a QR code as the message data or simply applying the reed-solomon error correction, but for this simple application and given that the "message" in question is usually going to be between 10-32 bytes I have plenty of room to repeat it which should provide sufficient redundancy to recover the true bits. No matter what I do I don't seem to be able to recover the bits at the decode stage. I've tried including / excluding various checks (even if it degrades image quality for the time being). I've tried using fixed point vs. double arithmetic, moving the bit to encode, I suspect that the message bits are being lost during the IDCT back to image. Any thoughts or suggestions on how to get this working would be hugely appreciated. (PS I am aware that the actual DCT/IDCT could be optimized from it's naive On4 operation using row column algorithm, or an FDCT like AAN, but for now it just needs to work :) ) Reference Papers: http://www.lokminglui.com/dct.pdf http://arxiv.org/ftp/arxiv/papers/1006/1006.1186.pdf Code for the Encode/Decode process in C# below: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Drawing.Imaging; using System.Drawing; namespace ImageKey { public class Encoder { public const int HIDE_BIT_POS = 3; // use bit position 4 (1 << 3). public const int HIDE_COUNT = 16; // Number of times to repeat the message to avoid error. // JPEG Standard Quantization Matrix. // (to get higher quality multiply by (100-quality)/50 .. // for lower than 50 multiply by 50/quality. Then round to integers and clip to ensure only positive integers. public static double[] Q = {16,11,10,16,24,40,51,61, 12,12,14,19,26,58,60,55, 14,13,16,24,40,57,69,56, 14,17,22,29,51,87,80,62, 18,22,37,56,68,109,103,77, 24,35,55,64,81,104,113,92, 49,64,78,87,103,121,120,101, 72,92,95,98,112,100,103,99}; // Maximum qauality quantization matrix (if all 1's doesn't modify coefficients at all). public static double[] Q2 = {1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1}; public static Bitmap Encode(Bitmap b, string key) { Bitmap response = new Bitmap(b.Width, b.Height, PixelFormat.Format32bppArgb); uint imgWidth = ((uint)b.Width) & ~((uint)7); // Maximum usable X resolution (divisible by 8). uint imgHeight = ((uint)b.Height) & ~((uint)7); // Maximum usable Y resolution (divisible by 8). // Start be transferring the unmodified image portions. // As we'll be using slightly less width/height for the encoding process we'll need the edges to be populated. for (int y = 0; y < b.Height; y++) for (int x = 0; x < b.Width; x++) { if( (x >= imgWidth && x < b.Width) || (y>=imgHeight && y < b.Height)) response.SetPixel(x, y, b.GetPixel(x, y)); } // Setup the counters and byte data for the message to encode. StringBuilder sb = new StringBuilder(); for(int i=0;i<HIDE_COUNT;i++) sb.Append(key); byte[] codeBytes = System.Text.Encoding.ASCII.GetBytes(sb.ToString()); int bitofs = 0; // Current bit position we've encoded too. int totalBits = (codeBytes.Length * 8); // Total number of bits to encode. for (int y = 0; y < imgHeight; y += 8) { for (int x = 0; x < imgWidth; x += 8) { int[] redData = GetRedChannelData(b, x, y); int[] greenData = GetGreenChannelData(b, x, y); int[] blueData = GetBlueChannelData(b, x, y); int[] newRedData; int[] newGreenData; int[] newBlueData; if (bitofs < totalBits) { double[] redDCT = DCT(ref redData); double[] greenDCT = DCT(ref greenData); double[] blueDCT = DCT(ref blueData); int[] redDCTI = Quantize(ref redDCT, ref Q2); int[] greenDCTI = Quantize(ref greenDCT, ref Q2); int[] blueDCTI = Quantize(ref blueDCT, ref Q2); int[] blueDCTC = Quantize(ref blueDCT, ref Q); HideBits(ref blueDCTI, ref blueDCTC, ref bitofs, ref totalBits, ref codeBytes); double[] redDCT2 = DeQuantize(ref redDCTI, ref Q2); double[] greenDCT2 = DeQuantize(ref greenDCTI, ref Q2); double[] blueDCT2 = DeQuantize(ref blueDCTI, ref Q2); newRedData = IDCT(ref redDCT2); newGreenData = IDCT(ref greenDCT2); newBlueData = IDCT(ref blueDCT2); } else { newRedData = redData; newGreenData = greenData; newBlueData = blueData; } MapToRGBRange(ref newRedData); MapToRGBRange(ref newGreenData); MapToRGBRange(ref newBlueData); for(int dy=0;dy<8;dy++) { for(int dx=0;dx<8;dx++) { int col = (0xff<<24) + (newRedData[dx+(dy*8)]<<16) + (newGreenData[dx+(dy*8)]<<8) + (newBlueData[dx+(dy*8)]); response.SetPixel(x+dx,y+dy,Color.FromArgb(col)); } } } } if (bitofs < totalBits) throw new Exception("Failed to encode data - insufficient cover image coefficients"); return (response); } public static void HideBits(ref int[] DCTMatrix, ref int[] CMatrix, ref int bitofs, ref int totalBits, ref byte[] codeBytes) { int tempValue = 0; for (int u = 0; u < 8; u++) { for (int v = 0; v < 8; v++) { if ( (u != 0 || v != 0) && CMatrix[v+(u*8)] != 0 && DCTMatrix[v+(u*8)] != 0) { if (bitofs < totalBits) { tempValue = DCTMatrix[v + (u * 8)]; int bytePos = (bitofs) >> 3; int bitPos = (bitofs) % 8; byte mask = (byte)(1 << bitPos); byte value = (byte)((codeBytes[bytePos] & mask) >> bitPos); // 0 or 1. if (value == 0) { int a = DCTMatrix[v + (u * 8)] & (1 << HIDE_BIT_POS); if (a != 0) DCTMatrix[v + (u * 8)] |= (1 << HIDE_BIT_POS) - 1; DCTMatrix[v + (u * 8)] &= ~(1 << HIDE_BIT_POS); } else if (value == 1) { int a = DCTMatrix[v + (u * 8)] & (1 << HIDE_BIT_POS); if (a == 0) DCTMatrix[v + (u * 8)] &= ~((1 << HIDE_BIT_POS) - 1); DCTMatrix[v + (u * 8)] |= (1 << HIDE_BIT_POS); } if (DCTMatrix[v + (u * 8)] != 0) bitofs++; else DCTMatrix[v + (u * 8)] = tempValue; } } } } } public static void MapToRGBRange(ref int[] data) { for(int i=0;i<data.Length;i++) { data[i] += 128; if(data[i] < 0) data[i] = 0; else if(data[i] > 255) data[i] = 255; } } public static int[] GetRedChannelData(Bitmap b, int sx, int sy) { int[] data = new int[8 * 8]; for (int y = sy; y < (sy + 8); y++) { for (int x = sx; x < (sx + 8); x++) { uint col = (uint)b.GetPixel(x,y).ToArgb(); data[(x - sx) + ((y - sy) * 8)] = (int)((col >> 16) & 0xff) - 128; } } return (data); } public static int[] GetGreenChannelData(Bitmap b, int sx, int sy) { int[] data = new int[8 * 8]; for (int y = sy; y < (sy + 8); y++) { for (int x = sx; x < (sx + 8); x++) { uint col = (uint)b.GetPixel(x, y).ToArgb(); data[(x - sx) + ((y - sy) * 8)] = (int)((col >> 8) & 0xff) - 128; } } return (data); } public static int[] GetBlueChannelData(Bitmap b, int sx, int sy) { int[] data = new int[8 * 8]; for (int y = sy; y < (sy + 8); y++) { for (int x = sx; x < (sx + 8); x++) { uint col = (uint)b.GetPixel(x, y).ToArgb(); data[(x - sx) + ((y - sy) * 8)] = (int)((col >> 0) & 0xff) - 128; } } return (data); } public static int[] Quantize(ref double[] DCTMatrix, ref double[] Q) { int[] DCTMatrixOut = new int[8*8]; for (int u = 0; u < 8; u++) { for (int v = 0; v < 8; v++) { DCTMatrixOut[v + (u * 8)] = (int)Math.Round(DCTMatrix[v + (u * 8)] / Q[v + (u * 8)]); } } return(DCTMatrixOut); } public static double[] DeQuantize(ref int[] DCTMatrix, ref double[] Q) { double[] DCTMatrixOut = new double[8*8]; for (int u = 0; u < 8; u++) { for (int v = 0; v < 8; v++) { DCTMatrixOut[v + (u * 8)] = (double)DCTMatrix[v + (u * 8)] * Q[v + (u * 8)]; } } return(DCTMatrixOut); } public static double[] DCT(ref int[] data) { double[] DCTMatrix = new double[8 * 8]; for (int v = 0; v < 8; v++) { for (int u = 0; u < 8; u++) { double cu = 1; if (u == 0) cu = (1.0 / Math.Sqrt(2.0)); double cv = 1; if (v == 0) cv = (1.0 / Math.Sqrt(2.0)); double sum = 0.0; for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) { double s = data[x + (y * 8)]; double dctVal = Math.Cos((2 * y + 1) * v * Math.PI / 16) * Math.Cos((2 * x + 1) * u * Math.PI / 16); sum += s * dctVal; } } DCTMatrix[u + (v * 8)] = (0.25 * cu * cv * sum); } } return (DCTMatrix); } public static int[] IDCT(ref double[] DCTMatrix) { int[] Matrix = new int[8 * 8]; for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) { double sum = 0; for (int v = 0; v < 8; v++) { for (int u = 0; u < 8; u++) { double cu = 1; if (u == 0) cu = (1.0 / Math.Sqrt(2.0)); double cv = 1; if (v == 0) cv = (1.0 / Math.Sqrt(2.0)); double idctVal = (cu * cv) / 4.0 * Math.Cos((2 * y + 1) * v * Math.PI / 16) * Math.Cos((2 * x + 1) * u * Math.PI / 16); sum += (DCTMatrix[u + (v * 8)] * idctVal); } } Matrix[x + (y * 8)] = (int)Math.Round(sum); } } return (Matrix); } } public class Decoder { public static string Decode(Bitmap b, int expectedLength) { expectedLength *= Encoder.HIDE_COUNT; uint imgWidth = ((uint)b.Width) & ~((uint)7); // Maximum usable X resolution (divisible by 8). uint imgHeight = ((uint)b.Height) & ~((uint)7); // Maximum usable Y resolution (divisible by 8). // Setup the counters and byte data for the message to decode. byte[] codeBytes = new byte[expectedLength]; byte[] outBytes = new byte[expectedLength / Encoder.HIDE_COUNT]; int bitofs = 0; // Current bit position we've decoded too. int totalBits = (codeBytes.Length * 8); // Total number of bits to decode. for (int y = 0; y < imgHeight; y += 8) { for (int x = 0; x < imgWidth; x += 8) { int[] blueData = ImageKey.Encoder.GetBlueChannelData(b, x, y); double[] blueDCT = ImageKey.Encoder.DCT(ref blueData); int[] blueDCTI = ImageKey.Encoder.Quantize(ref blueDCT, ref Encoder.Q2); int[] blueDCTC = ImageKey.Encoder.Quantize(ref blueDCT, ref Encoder.Q); if (bitofs < totalBits) GetBits(ref blueDCTI, ref blueDCTC, ref bitofs, ref totalBits, ref codeBytes); } } bitofs = 0; for (int i = 0; i < (expectedLength / Encoder.HIDE_COUNT) * 8; i++) { int bytePos = (bitofs) >> 3; int bitPos = (bitofs) % 8; byte mask = (byte)(1 << bitPos); List<int> values = new List<int>(); int zeroCount = 0; int oneCount = 0; for (int j = 0; j < Encoder.HIDE_COUNT; j++) { int val = (codeBytes[bytePos + ((expectedLength / Encoder.HIDE_COUNT) * j)] & mask) >> bitPos; values.Add(val); if (val == 0) zeroCount++; else oneCount++; } if (oneCount >= zeroCount) outBytes[bytePos] |= mask; bitofs++; values.Clear(); } return (System.Text.Encoding.ASCII.GetString(outBytes)); } public static void GetBits(ref int[] DCTMatrix, ref int[] CMatrix, ref int bitofs, ref int totalBits, ref byte[] codeBytes) { for (int u = 0; u < 8; u++) { for (int v = 0; v < 8; v++) { if ((u != 0 || v != 0) && CMatrix[v + (u * 8)] != 0 && DCTMatrix[v + (u * 8)] != 0) { if (bitofs < totalBits) { int bytePos = (bitofs) >> 3; int bitPos = (bitofs) % 8; byte mask = (byte)(1 << bitPos); int value = DCTMatrix[v + (u * 8)] & (1 << Encoder.HIDE_BIT_POS); if (value != 0) codeBytes[bytePos] |= mask; bitofs++; } } } } } } } UPDATE: By switching to using a QR Code as the source message and swapping a pair of coefficients in each block instead of bit manipulation I've been able to get the message to survive the transform. However to get the message to come through without corruption I have to adjust both coefficients as well as swap them. For example swapping (3,4) and (4,3) in the DCT matrix and then respectively adding 8 and subtracting 8 as an arbitrary constant seems to work. This survives a re-JPEG'ing of 96 but any form of scaling/cropping destroys the message again. I was hoping that by operating on mid to low frequency values that the message would be preserved even under some light image manipulation.

    Read the article

< Previous Page | 1 2 3 4 5