3 ms·
A patent for searching a linked list? This is disgusting. As a middle finger, here's me infringing on it. typedef struct node { struct node *next; v
by strlen 16y ago
A patent for searching a linked list? This is disgusting.
As a middle finger, here's me infringing on it.
typedef struct node {
struct node *next;
void *data;
} node_t;
void *find(node_t *head, void *what, int (*cmp)(void *, void *)) {
while(*head != NULL && cmp(head->data, what) != 0) {
head = head->next;
}
return head;
}
Of course, there is an age old infringer on this patent:
(define (find ll what)
(if (or (null? ll) (eq? (car ll) what))
ll
(find (cdr ll) what)))
- piotrSikora 16y agoYou didn't read the patent, did you?
- strlen 16y agoI did, the only part my code sample doesn't involve is expiring the oldest record, which is: void expire(node_t **head) { node_t *next = (*head)->next; free(*head); *head = next; } In terms of using a linked list as an LRU cache, this is done in the Java SDK by LinkedHashMap: http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html http://download.oracle.com/javase/6/docs/api/java/util/Linke... http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedHashMap.java http://grepcode.com/file/repository.grepcode.com/java/root/j...
- piotrSikora 16y agoExcept that the patent doesn't do any "expiring of the oldest record" and it's not LRU.
- fragmede 16y agoThe patent includes expiring the records in the linked list, and removing (some) expired records when doing the search: #define EXPIRE_LOOKUPS 500 typedef struct node { struct node *next; void *data; int age; } node_t; void *find(node_t *head, void *what, int (*cmp)(void *, void *)) { while(*head != NULL && cmp(head->data, what) != 0) { if (head->next == NULL) return NULL; if (head->next->age > EXPIRE_LOOKUPS) head->next = head->next->next; ++head->age; head = head->next; } return head; } (I didn't see the patent specify an actual expiry mechanism in any specific detail, so here's a useless, but patent-infringing one.)
- jws 16y agoIn the case where you expire the last entry of the linked list you will SEGFAULT. A test for head being NULL at the end of the loop would take care of that, but I'd put it in the condition of the while loop since it is probably free on a modern processor given the memory access pattern and it makes something sane happen when a client calls find(NULL,...). I also don't think the last element ages, but since aging is unrelated to reality that is ok. On second thought, it protects you from the SEGFAULT because the last element can never expire. Very cunning of you.
- fragmede 16y agoI'm not seeing the segfault, but it does leak memory like a sieve with no filter. Good point re: age. ++head->age should be the first operation of the while loop.
- jws 16y agoJust in case someone is scratching their head over this... Let's come into the while loop body with data like this where H is the head pointer, C and E are elements of the list... H -> C /* head points to current node */ C->next -> E /* expired node is next*/ E->next -> NULL /* expired node is last */ if ( head->next == NULL)... /* no, head points to C, C->next is E */ if ( head->next->age > EXP...) /* yes, head->next is E and is expired */ head->next = head->next->next /* C->next is now NULL (E->next) */ head = head->next; /* head is now NULL */ /* back to the top of the loop */ while( *head != NULL... /* BANG! a NULL value just got dereferenced */
- strlen 16y agoOn the other hand, I can see it makes interviewing a lot more difficult: "I would answer your question, but it would infringe on a patent".
- apgwoz 16y agoYou mean, garbage collection?
- strlen 16y agos/*head != NULL/head != NULL/ (d'oh)